În practică, pentru a alege o uniformă aleatorie $x\in \mathbb{Z}^*_q$, reducem această sarcină la problema alegerii de biți uniform aleatori și independenți. Pe un sistem informatic modern, va exista un serviciu de sistem de operare care furnizează astfel de biți, de ex. /dev/urandom pe multe derivate Unix (vom reveni la problema cum au fost obținuți astfel de biți în a doua secțiune).
Cea mai simplă metodă de a alege un uniform aleatoriu $x\in \mathbb{Z}^*_q$, adică un număr întreg în $[0,q)$, numit uneori eșantionare de respingere, spune:
- Ca preliminar efectuată o dată indiferent câte $x$ vrem să generăm: ca funcţie (deterministă) a $q$, alege unele $k$ cu $2^k\ge q$, de exemplu. $k$ puțin peste numărul de biți din expresia binară a $q$.
- A desena $k$ biți uniform aleatori și independenți $b_i$, pentru $0\le i<k$
- Asamblați $k$ biți în număr întreg $y=\sum b_i\,2^i$
- Dacă $y<(2^k\bmod q)$, continuați la 2.
- Calculați și ieșiți $x=y\bmod q$.
Probabilitatea ca $x$ este un anumit întreg în $[0,q)$ este exact 1 USD/q$ sub ipoteza bitii $b_i$ sunt uniform aleatoare și independente.
Variații comune:
- Producerea biților $b_i$ grupate într-un cuvânt computerizat și/sau $k$ forțat să fie un multiplu al unor dimensiuni de cuvinte.
- Big Endianness la 2: $y=\sum b_i\,2^{k-i-1}$; aceasta permite de asemenea $y$ pentru a fi construit pe măsură ce desenăm $b_i$ la fel de $y_0=0$, $y_{i+1}=y_i+y_i+b_i$ pentru $0\le i<k$, $y=y_k$.
- Condiție de testare diferită la 4, de ex. $y\ge2^k-(2^k\bmod q)$.
De asemenea, putem elimina pasul 4 (caz în care metoda nu mai este eșantionarea de respingere). Dacă nu $q$ este o putere a doi, aceasta lasă numere întregi $[0,2^k\bmod q)$ mai probabil decât cei din $[(2^k\bmod q), q)$, cu probabilitate $\lceil 2^k/q\rceil/2^k$ Decat $\lfloor 2^k/q\rfloor/2^k$. Dar dacă $k$ este adecvat mai mare decât numărul de biți în $q$ (Spune, $k\>\lceil\log_2 q\rceil+64$ ), sau/și dacă $\min(2^k\bmod q,-2^k\bmod q)/q$ este mai mică decât o limită adecvată (de ex. $2^{-128}$ ), atunci această părtinire este nedetectabilă experimental.
(Există caracterizări mai bune ale momentului în care putem elimina pasul 4 și metode mai complexe pentru a minimiza numărul de $b_i$ generate la realizarea multor $x$, dar utilizarea lor este neobișnuită).
Ne-am întors la problema alegerii de biți uniform aleatori și independenți, sau poate cuvinte de computer constând din astfel de biți.
Metodele recomandate folosesc toate același principiu larg: sursele de aleatorie imperfectă sunt post-procesate în biți, sperăm că nu se pot distinge (în mod ideal, inclusiv pentru adversarii puternici arbitrar; sau ca o alternativă, computabil) de biții uniform aleatori și independenți doriti.
Exemple de surse:
- Intrări, inclusiv apăsarea tastelor, poziția mouse-ului, microfonul, intrarea camerei.
- Ora când apar apăsări de taste, poziția mouse-ului se modifică, blocurile de disc sau pachetul Ethernet/Wifi/Bluetooth/USB ajunge la placa de bază, măsurat de ex. în cicluri de ceas de la pornirea computerului
- Un dispozitiv dedicat. O metodă compară tensiunea instantanee pe a diodă Zener la medie, și eșantionează rezultatul la intervale regulate. Un alt eșantionează un oscilator sperăm că haotic folosind un altul, sperăm independent.
Ar trebui să se depună mult efort în supravegherea sursei (surselor), pentru a ne asigura că aceasta/ele funcționează corect (sau dacă combinăm mai multe, pentru a estima un minim entropie putem fi încrezători că oferă în mod colectiv).
Una dintre cele mai simple mijloace eficiente de postprocesare este hashing: un număr de biți de la sursă (surse) sunt hashing, iar rezultatul (sau o parte a acestuia) formează ieșirea condiționată. Acest lucru este sigur pentru un hash care nu se poate distinge din punct de vedere computațional de un oracol aleatoriu (pentru lungimea de intrare utilizată) și un suficient de mare (min-)entropie a intrării hash.
Dacă avem nevoie de mulți biți aleatori, le putem face la costuri reduse prin însămânțare a Generator de numere pseudoaleatoare securizat criptografic cu aleatorie obţinută ca în ultimul paragraf. Cu toate acestea, dacă starea CSPRNG este compromisă (de exemplu, de canalele laterale), tot ceea ce iese este. Din acest motiv, există metode mai elaborate pentru a obține biți aleatorii foarte siguri la o rată ridicată, într-un mod care se recuperează frumos din compromisul stării lor interne.
Adăugare: pe procesoarele moderne, există adesea o sursă on-die (care a fost cândva în chipset). Adesea, ieșirea sa nu este accesibilă într-un mod bine documentat. Scuzele pentru asta sunt că oamenii l-ar folosi direct sau/și l-ar lăuda că au detectat anumite părtiniri în el, deși este de așteptat. Programatorul ar trebui să folosească o ieșire condiționată în mod misterios prin intermediul unor instrucțiuni (de ex. RDRAND). Modul în care este monitorizată sănătatea sursei este adesea lăsat prost documentat și/sau nu este acceptat în software/OS. Alte probleme posibile cu RNG-urile bazate pe CPU includ protejarea slabă a confidențialității ieșirii lor, vezi de ex. acest. Trageți propriile concluzii despre dacă acestea ar trebui să fie de încredere ca unică sursă sau aleatorie în cripto.
