Puncte:2

Putem combina două generatoare aleatorii adevărate pentru a obține unul nou?

drapel co

Este bine cunoscut faptul că un adevărat generator aleatoriu exploatează aleatoritatea care apare în unele fenomene fizice. De asemenea, ieșirea unui generator aleatoriu adevărat poate fi fie părtinitoare, fie corelată. Prin urmare, sunt necesare tehnici de de-skewing.

Întrebarea mea este că, dacă avem doi generatori de biți aleatori adevărați ale căror ieșiri nu trec de suita de testare a NIST, putem combina aceste ieșiri pentru a obține un generator de biți aleatori care trece suitele de testare ale aleatoriei statistice?

Maarten Bodewes avatar
drapel in
Este foarte probabil ca simpla concatenare sau chiar XOR-ing biți din PRNG să arate părtinire, așa că cred că răspunsul este un simplu *nu*. Sau poate ca „combine” nu este descris. Bănuiesc că ar trebui să conțină tehnici de de-skewing similare cu a avea de a face cu un TRNG. De fapt, cred că puteți demonstra că acest lucru este cazul prin simpla împărțire a fluxului TRNG în două, luând fiecare alt bit.
Paul Uszak avatar
drapel cn
Multe mai multe despre asta [aici](https://cs.stackexchange.com/q/57648/31167)...
Puncte:3
drapel cn

Acest lucru se face de fapt destul de frecvent în circuite. Luați în considerare un TRNG generic complet digital bazat pe oscilatoare inelare: -

ros

Cel de mai sus este un exemplu și mai extrem decât al dvs., în care sunt utilizate multe (poate 32) oscilatoare inelare individuale. Toate sunt identice, toate eșuează în mod spectaculos orice test de aleatorie, dar produc singure entropie. Dacă sunt necesare 32 de oscilatoare inelare pentru a produce 1 bit/tic de entropie, vă puteți imagina că fiecare trebuie să producă mult mai puțin. Prejudecățile lor trebuie să fie, de asemenea, foarte mari (ceea ce este o caracteristică a unor astfel de oscilatoare). Combinarea acestora îmbunătățește considerabil rata de entropie și, prin urmare, reduce polaritatea de ieșire.

Un alt exemplu este generarea de $m \times n$ matrice de extracție aleatorie utilizată în TRNG-uri. De la ID Quantique, Document tehnic despre Randomness Extractor, versiunea 1.0, septembrie 2012:-

În mod ideal, sursele individuale r utilizate în procedura descrisă pentru a genera matricea m ar trebui să fie obținute din surse diferite.

Acest lucru ilustrează în mod anecdotic conceptul.Din punct de vedere matematic, paradigma potrivită este Lema Piling Up (Mitsuru Matsui, Metoda de criptoanaliza liniară pentru DES Cipher) :-

Pentru $n$ variabile binare aleatoare, independente, $X_1, X_2, \ldots X_n$,

$$ Pr(X_1 \oplus \ldots \oplus X_n = 0) = \frac{1}{2} + 2^{n-1} \prod_{i=1}^n \epsilon_i $$

Rearanjarea, astfel încât dacă $ \epsilon_{1,2, \ldots, n} $ reprezintă părtinirea $ X_1 \oplus \ldots \oplus X_n = 0 $, obținem părtinirea finală a $n$ surse independente combinate ca: -

$$ \epsilon_{1,2, \ldots, n} = 2^{n-1} \prod_{i=1}^n \epsilon_i $$

Pe scurt, pe măsură ce combinați din ce în ce mai multe RNG-uri independente, distorsiunea globală a ieșirii tinde asimptotic spre zero. Deci creând unul nou, mai bun.

kodlu avatar
drapel sa
Lema 4 este cunoscută și sub numele de Lema acumulată a lui Matsui.
Puncte:2
drapel in

Da. Putem combina două PRNG-uri și să facem unul mai bun. Cea mai simplă formă ar fi să XOR cele două valori. Dacă cel puțin unul dintre ele este aleatoriu, la fel va fi și rezultatul. Acest lucru nu rezolvă totul, dar are proprietăți frumoase demonstrabile. În esență, este cel puțin la fel de bun ca oricare dintre ele (presupunând că nu au fost corelate de la început).

Cu toate acestea, dacă avem surse foarte părtinitoare cu o oarecare entropie reală, probabil că dorim să aplicăm un hash criptografic. Acest lucru este bun chiar și cu o singură sursă RNG.

Generatoarele aleatorii securizate colectează de obicei entropia din mai multe surse slabe și le amestecă criptografic (în esență un hash). Atunci acest pool de entropie este o sămânță pentru un PRNG sigur din punct de vedere criptografic. Să presupunem că suntem îngrijorați de adversarii cu calcul nelimitat. În acest caz, încercăm să estimăm câtă entropie reală am colectat și scoatem doar o cantitate mai mică de biți aleatori până când colectăm mai multă entropie.

Puncte:1
drapel cn
Leo

Dacă unele condiții sunt adevărate, este posibil să combinați două TRNG-uri într-unul singur și să obțineți rezultate mai bune din ele.

Voi numi cele două generatoare originale TRNG-1 și TRNG-2 și combinația lor TRNG-3.

  1. Dacă se generează TRNG-1 $k$ biți de ieșire pe secundă și se generează TRNG-2 $l$ biți de ieșire pe secundă, combinația lor (TRNG-3) trebuie să producă mai puțin de $k+l$ biți de ieșire pe secundă. Rata reală de ieșire trebuie determinată cu atenție, luând în considerare entropia estimată a ambelor generatoare și cât de multă corelație există între ele.
  2. TRNG-1 și TRNG-2 nu trebuie să fie complet corelate. Atâta timp cât există o variație mică, independentă între ele, o ieșire mai bună poate fi generată prin combinare decât folosind oricare dintre ele singur.

Există mai multe moduri de a combina TRNG-1 și TRNG-2. Mai jos sunt câteva exemple.

  1. Funcții hash criptografice
  2. Funcții de burete precum Keccak sau buretele Gimli
  3. Înmulțirea cu o matrice umplută aleatoriu
  4. Chiar și metode simple, cum ar fi hashingul Pearson.

Dacă TRNG-urile sunt bune singure și nu au o corelație semnificativă, ați putea scăpa cu un simplu XOR. Dar metodele de mai sus nu sunt prea complexe sau costisitoare, așa că aș recomanda să rămâneți în siguranță și să implementați una dintre ele.

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.