înregistrare Logare
Puncte:0
cryptonoob avatar Crypto

Determinați dacă o funcție este un PRG atunci când PRG este concatenat cu Seed?

drapel bd
cryptonoob

Sunt un începător în criptografie și am probleme în a rezolva următoarea întrebare.

Lăsa $G: \{0,1 \}^n \rightarrow \{0,1 \}^{l(n)}$ fi un PRG și $x \epsilon \{0,1 \}^n$. Determinați dacă funcția $Z: \{0,1 \}^n \rightarrow \{0,1 \}^{(l(n)+n)}$ Sf. $Z(x) := G(x)||x$ este, de asemenea, un PRG.

Prima mea presupunere a fost că este un PRG, deoarece concatenarea PRG Output G(x) ca șir pseudoaleatoriu cu un șir aleator x distribuit uniform este, de asemenea, un șir aleatoriu. Prin urmare, nici nu poate fi distins de un adversar. În plus, l(n)+n > n, deci și extinderea este ok.

Cum pot dovedi asta? Ideea mea este o Reducere că, dacă există un deosebitor D care rupe Z(x) ar rupe și G(x) cu probabilitate non-negl, ceea ce contrazice presupunerea inițială că G(x) este un PRG.

Sunt pe drumul cel bun sau sunt complet pierdut?

223
0 + 6
Maarten Bodewes avatar
drapel in
Maarten Bodewes
Deci, funcția dvs. Z emite sămânța împreună cu valorile aleatoare derivate din aceasta? Algoritmul este de asemenea cunoscut.
1
Răspunde
cryptonoob avatar
drapel bd
cryptonoob
@MaartenBodewes Da, exact. Dar ce vrei să spui cu „algoritmul este cunoscut și el”? G ist nu este specificat în continuare. Prin urmare, dacă trebuie să dau un contraexemplu pentru cazul în care Z nu este un PRG, pot proiecta G oricum vreau.
0
Răspunde
Maarten Bodewes avatar
drapel in
Maarten Bodewes
Nu, acest lucru nu este de obicei corect. În general, presupunem principiul lui Kerckhoff: orice securitate nu se află în algoritm, ci în cheie sau - în acest caz - sămânță. Puteți proiecta $G$ așa cum doriți, dar ar trebui să presupuneți că orice adversar cunoaște algoritmul. Cu alte cuvinte: nu puteți presupune că $G$ generează orice secret în afară de sămânța $x$. Acum, ce s-ar întâmpla dacă mai întâi ați genera o cheie și apoi un IV folosind $Z$?
0
Răspunde
SEJPM avatar
drapel us
SEJPM
Sugestie: Există poate un fel de test/distinctor care poate verifica dacă un anumit șir cu aspect aleatoriu provine de la $Z$ sau pur și simplu aleatoriu? Să presupunem că adversarul poate calcula și $G$.
2
Răspunde
cryptonoob avatar
drapel bd
cryptonoob
@MaartenBodewes Singura idee pe care o am este că un adversar poate obține cheia/sămânța de la ieșirea lui Z prin efectuarea unei tăieturi (pentru că adversarul cunoaște algoritmul și știe că cheia are o lungime de n). Apoi poate introduce această „cheie” în funcție și poate verifica dacă este aceeași ieșire sau nu. Din câte știu eu, un PRG este determinist. Și în acest caz chiar știe cheia. Calea corectă?
0
Răspunde
Maarten Bodewes avatar
drapel in
Maarten Bodewes
Da, asta e drumul cel bun. În general, nu ar trebui să fie posibilă derivarea stării RNG, deoarece ar scurge informații despre toți ceilalți octeți din flux.
0
Răspunde
drapel romania
SEF 777
întrebarea această in alte limbi:

Postează un răspuns

Majoritatea oamenilor nu înțeleg că a pune multe întrebări deblochează învățarea și îmbunătățește legătura interpersonală. În studiile lui Alison, de exemplu, deși oamenii își puteau aminti cu exactitate câte întrebări au fost puse în conversațiile lor, ei nu au intuit legătura dintre întrebări și apreciere. În patru studii, în care participanții au fost implicați în conversații ei înșiși sau au citit transcrieri ale conversațiilor altora, oamenii au avut tendința să nu realizeze că întrebarea ar influența – sau ar fi influențat – nivelul de prietenie dintre conversatori.