înregistrare Logare
Puncte:1
Tom avatar Crypto

Cum se măsoară lungimea ciclului PRNG de 128 de biți?

drapel tf
Tom

Am tastat PRNG pe 128 de biți. A trecut testele PractRand și Dieharder, dar nu am idee despre durata ciclului de așteptat al acestuia (pentru diferite chei și diferite semințe).

Există o modalitate de a o estima, prin rezultatele analizei acestui generator? Încerc să analizez ciclurile în părți de 16 biți ale ieșirilor de 128 de biți. Numerele pe 16 biți se repetă în părți trunchiate de 16 biți ale ieșirii de 128 de biți în medie în fiecare $6331708$ trepte. De exemplu, numărul $14649$ apare la 16 biți neregulați după:

$1385856, 6793856, 4734720, 4043776, 17823744, 3705088, 5609216, 1174784, 3718656, 181504, 14063616, 13729024, 10346880, 15782016, 1561088, 1996672, 988544$

pași (și arată similar când verificăm fiecare alt număr de 16 biți, cu oricare dintre taste). Dar pe baza unei astfel de analize a părților consecutive ale generatorului de 16 biți, se pot trage concluzii despre ciclul întregului generator?

Apropo, nu ar trebui să ne așteptăm la un număr aleatoriu de 16 biți să apară o dată la fiecare $2^{16}$ pași? La început, numerele de 16 biți alese aleatoriu sunt rare pentru mine sau înțeleg ceva greșit?

64
0 + 0
fgrieu avatar
drapel ng
fgrieu
Se poate demonstra experimental că un PRNG este nesigur sau are o perioadă scurtă. Nicio metodă de examinare a ieșirii nu poate determina dacă este sigură sau are o perioadă lungă de timp. Pentru aceasta, este necesar să se examineze modul în care funcționează PRNG.
3
Răspunde
Tom avatar
drapel tf
Tom
Ok, trebuie să consider că nu am nicio teorie despre perioada. Deci nu există nicio modalitate de a ști nimic despre perioada PRNG? Deci, nu contează dacă trece PractRand la 2^42 de octeți, poate intra în ciclu de lungime $2^{50}$ sau $2^{100}$ și nu putem afla cum este, doar analizând iesiri?
0
Răspunde
Maarten Bodewes avatar
drapel in
Maarten Bodewes
Prin definiție (?), ieșirea RNG-ului nu ar trebui să vă spună nimic despre starea PRNG-ului. Așadar, doar privind anumite părți ale rezultatului, nu veți obține prea multe informații despre posibilitatea unui ciclu. Puteți găsi doar nereguli, dar acestea ar trebui să apară în testare. Dacă testele eșuează, atunci cred că dacă este un ciclu sau nu este lipsit de importanță :)
2
Răspunde
fgrieu avatar
drapel ng
fgrieu
Exact. Cu excepția cazului în care perioada este mai mică (cu o mică marjă) decât lungimea testată, un test statistic care funcționează la ieșirea PRNG nu poate găsi perioada. Din nou, testele statistice sunt utile doar pentru a demonstra că PRNG-urile proaste sunt proaste sau/și au o perioadă scurtă. Când un test nu descoperă un defect/perioadă scurtă, nu putem ajunge la nicio concluzie despre PRNG-ul testat. La fel ca după ce am văzut o furnică trecând în siguranță peste un pod, nu putem ajunge la nicio concluzie pozitivă despre pod. Trebuie să vedem schema sa de proiectare și să inspectăm construcția acesteia.
3
Răspunde
kodlu avatar
drapel sa
kodlu
afirmatia ta este imprecisa. dacă acestea sunt distribuții gap pentru o anumită fereastră de 16 biți, ați verificat *toate* ferestrele de 16 biți? este acea distribuție a decalajului tipică pentru întregul set de ferestre pe 16 biți?
0
Răspunde
Tom avatar
drapel tf
Tom
@kodlu Am greșit, nu pot fi lacune atât de mari și nu sunt (am greșit codul Python).
0
Răspunde
user2357 avatar
drapel us
user2357
@fgrieu ce zici de lfsr unde se calculează cea mai lungă perioadă și ar putea fi realizată prin considerațiile cu polinoame primitive? Tocmai citeam despre așa ceva în cartea intitulată înțelegerea criptografiei.
0
Răspunde
Puncte:3
poncho avatar Crypto
drapel my
poncho

Există o modalitate de a o estima, prin rezultatele analizei acestui generator?

După cum au spus comentariile, nu chiar (cu excepția cazului în care generatorul a fost foarte rău).

Încerc să analizez ciclurile în părți de 16 biți ale ieșirilor de 128 de biți. Apropo, nu ar trebui să ne așteptăm la un număr aleatoriu de 16 biți să apară o dată la fiecare $2^{16}$ pași?

Ceea ce ar trebui să facă un PRNG bun este să amestece toate părțile stării împreună, prin urmare, privirea la bucățile trunchiate de 16 biți nu ar trebui să vă spună nimic.

Pe de altă parte, se pare că enumerați goluri în aparițiile unei anumite valori de 216 biți (14649), iar acele lacune arată destul de ciudat. Dacă PRNG a fost bun, ne-am aștepta ca decalajele dintre apariții să urmeze o distribuție exponențială (cu media la 65536, așa cum ați spus); în timp ce uneori veți vedea decalaje considerabil mai mari decât media, aproape niciodată nu ar trebui să vedeți un decalaj de 100 de ori mai mare decât media (și le arătați chiar și mai mari) - acesta este un tip de „câștigă la loterie-de mai multe ori” eveniment. Faptul că arătați ar indica fie a) nu interpretez corect datele, b) nu măsurați corect decalajul, fie c) PRNG-ul este grav neuniform.

Verificarea neuniformității este simplă - pur și simplu rulați PRNG și numărați de câte ori vedeți fiecare valoare - dacă vedeți valori al căror număr este un multipli mari ai abaterii standard de la medie (în oricare direcție), aveți o problemă serioasă. problemă.

Desigur, dacă acesta ar trebui să fie un generator de numere aleatoare sigur din punct de vedere criptografic, ei bine, cerințele pentru acesta sunt semnificativ mai stricte...

0 + 0
Tom avatar
drapel tf
Tom
Ai dreptate, am greșit codul și am măsurat greșit aceste repetări. Cu astfel de abateri, acest generator va eșua cu siguranță testele. Oricum, trebuie să lucrez la teoria despre ciclurile acestui generator.
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.