Exponentiarea generatoarelor liniare congruentiale

Generatori liniari congruențiali, acea clasă de generatoare pseudoaleatoare cu regulă recursivă

$x_{n+1}\equiv a\cdot x_n +b\ \ (\mod m)$, $a,b,x_n\în Z/mZ$, $m,n\în N$

sunt considerate inapte pentru utilizare în criptografie, ca constante $a$, $b$ poate fi dedus dintr-un set mic de rezultate $x_n$. Acum, când alegi $m=p-1$ pentru un prim ciudat $p$, secvența $(x_n)_{n\în N}$ poate trăi ca exponenți ai unui generator $g$ a grupului ciclic multiplicativ $Z/pZ^*$, la fel de $y_n:=g^{x_n}, n\în N$:

$y_{n+1}\equiv g^{x_{n+1}}\equiv g^{a\cdot x_n+b}\equiv (g^{x_n})^a\cdot g^b\equiv y_n ^a\cdot g^b\ (\mod p)$

Aceasta este o serie de puteri echivalente.

Distribuția egală vine cu o perioadă maximă. Conditii pentru perioada maxima $m$ a secvenței $(y_n)_{n\în N}$ sunt date de teorema lui Knuth

1. $gcd(m,b)=1$
2. Pentru descompunerea primului $m=:\prod p_i^{\alpha_i}$ și toți factorii primi $p_i$: $\ \ \ p_i/(a-1)$
3. $m\equiv 0\ (\mod 4) \implies a-1\equiv 0\ (\mod 4)$

La fel de $m=p-1$ este par și există foarte puține numere prime cu formă $p=2^k+1$, cea mai ușoară compoziție comună a $p-1$ din numere prime ar fi $p-1=2^k\cdot p'$, $k\geq 1$ cu $p'$ alt prim.

Conform a 2-a condiție cea mai mică alegere de $a$ este de $a-1=2\cdot p'$. Pentru a evita cazurile banale $a-1=m$, $k\geq 2$ este necesar. Cu aceasta ajungem în a treia condiție, astfel încât $a-1$ are un factor de cel puțin două ori mai mare $2$. Din nou, evitarea cazului trivial necesită $k\geq 3$.

Acum, o pereche primară $(p,p')$ potrivirea ecuaţiei liniare $p=8p'+1$ permite alegeri non-triviale $a-1=4p'$ iar cu aceasta seria de putere $(y_n)$ poate avea o perioadă maximă $m$.

Întrebare: Deoarece avem 3 parametri ascunși $g, g^a,g^b$ iar găsirea de logaritmi în grupuri multiplicative este considerată dificilă, poate succesiunea aleatorie $(y_n){n\în N}$ să fie considerat sigur pentru utilizare în criptografie; există alegeri mai bune pentru constantă $a$?

EDITAȚI | × $g$ de fapt, nu este important ca parametru, deoarece creștem puterile $a$, unde în plus $p$ nu este cunoscut din ieșire, adică parametrii necunoscuți sunt $(p, a, g^b)$ .

Mai multe observatii:

• Păstrarea $a$ secretul este crucial. Dacă adversarul știe asta și vede $y_i, y_{i+1} = (y_i^a) \cdot g^b$, el poate calcula $g^b = y_{i+1} \cdot y_i^{-a}$, apoi mergeți mai departe și calculați restul secvenței.

Puteți spune „dar presupunem că jurnalul discret este greu” - cu toate acestea, sugerați și dvs $p = 8p'+1$ și $a-1 = 4p'$, acesta este, $a = (p+1)/2$; asta ar face recuperarea $a$ uşor.

• Adevăratul test acid pentru CSRNG-uri este dacă un adversar (care știe totul, cu excepția valorilor secrete) poate distinge rezultatul CSRNG-urilor de o secvență cu adevărat aleatorie cu aceeași distribuție de probabilitate.

Acum dacă $g$ este un generator al întregului grup, se dovedește a fi ușor de determinat dacă $x$ este par sau impar din $g^x \bmod p$. Cu generatorul dvs., acest bit inferior va alterna întotdeauna între „par” și „impar” cu succesive $y_i$ valori, făcându-l astfel distins.

Ceea ce facem de obicei atunci când folosim câmpuri finite este să lucrăm în mod deliberat într-un subgrup de dimensiune primă (care, evident, nu poate fi întregul $\mathbb{Z}_p^*$ grup); care împiedică atacatorul să recupereze orice informații despre $x$ din $g^x$.

Desigur, acest lucru reduce dimensiunea perioadei - totuși, atâta timp cât perioada este mai lungă decât, să zicem, $2^{64}$ (care este mult mai mare decât numărul de ieșiri pe care le-am genera practic), este suficient de mare.

Punând toate acestea cap la cap, aș sugera această idee alternativă similară:

• cădere brusca $b$; în schimb, folosește un simplu $y_{i+1} = (y_i)^a \bmod p$ generator.

• Selectați un prim $p = kp' + 1$, Unde $p'$ este un prim Sophie-Germain, adică $(p'-1)/2$ este, de asemenea, prim. $p$ ar trebui să fie suficient de mare pentru a îngreuna problema jurnalului discret (de exemplu, cel puțin 2048 de biți) și $p'$ ar trebui să fie suficient de mare pentru a îngreuna problema jurnalului discret din subgrup (de exemplu, cel puțin 256 de biți; cu toate acestea, poate fi mult mai mare, de exemplu, $k=2$ este practic).

• Selectați $y_0$ a fi membru (altul decât 1) al subgrupului de mărime $p'$

• Selectați $a > 0$ să fie o valoare aleatorie pentru care $a^{(p'-1)/2} \bmod p' \ne 1$ (ceea ce va fi valabil pentru jumătate din valorile posibile ale $a$)

Aceasta va genera o secvență de perioade $p'-1$ (care este destul de lung); vezi Teorema 3.2.1.2.C din Knuth. Și, pentru că $a$ poate fi selectat dintr-un număr mare de posibilități, nu poate fi ghicit.

Acum, nicio versiune nu ar fi a practic CSRNG (a face o exponențiere modulară pe ieșire este destul de lent - avem CSRNG-uri mult mai bune); Cred că răspunde la întrebarea ta.