Cu toate acestea, poate cineva să-mi explice în termeni simpli de ce am avea nevoie în acest context de o comandă mare de G și cum va contribui la a face g^ab mai sigur
Context (pe care probabil îl știți deja), cu El Gamal, textul cifrat este perechea $g^r, h^r \cdot m$ (Unde $h$ este cheia publică și $r$ este o valoare aleatorie); dacă ne-am putea da seama care este valoarea $r$ adică ne-am putea recupera $m$ (pentru că presupunem că știm valoarea $h$).
Deci, unul dintre lucrurile de care trebuie să ne asigurăm este că, având în vedere valoarea $g^r$, nu putem deduce ce $r$ este; aceasta este cunoscută sub numele de „problema logaritmului discret”.
Având în vedere acest lucru, iată câteva dintre matematica din spatele scenei:
Definim „ordinea lui G” ca fiind cea mai mică valoare $k > 0$ pentru care $G^k = 1$. Acest lucru este interesant pentru că $G^r$ poate prelua numai $k$ valori diferite, $G^1, G^2, ..., G^{k-1}, G^k = 1$. Dacă continuăm, vom ajunge să repetăm, începând din nou la $G^1$și asta nu ne ajută cu nimic.
Dacă există doar $k$ valori diferite ale $r$ care ne dau valori diferite ale $G^r$, atunci dacă $k$ este mic, ceea ce ar putea face atacatorul este să încerce totul $k$ valori diferite ale $r$ și vezi dacă lucrează unul; dacă poate face asta, poate recupera valoarea corectă a $r$ [1]. De fapt, se dovedește că, dacă atacatorul folosește doar o ofertă de inteligență, el poate efectua această căutare cu aproximativ $\sqrt{k}$ înmulțiri; deci dacă vrem să ne asigurăm că atacatorul trebuie să efectueze $2^{128}$ operațiuni pentru a ataca sistemul (care este standardul actual pentru „care depășește capacitatea oricui”), atunci avem nevoie de un $k$ macar $2^{256}$.
Și, se dovedește că mai trebuie făcută o observație: dacă $k$ este compus și are un factor prim $s$, atacatorul poate calcula $r \bmod s$ cu $\sqrt{s}$ operațiuni (prin folosirea aceluiași tip de inteligență); aceasta reduce puterea unui astfel de $G$.
folosind p = 2q+1 denotă că ordinul lui G este 2 și q și că „g este apoi ales uneori pentru a genera subgrupul de ordinul q al lui G, mai degrabă decât G, astfel încât simbolul Legendre al lui g^a nu dezvăluie niciodată valoarea scăzută. comanda bit de a.
Aceasta vorbește despre o metodă comună de a face față atacurilor de mai sus (nu singura metodă, mintea).
Se dovedește că dacă $p = 2q+1$ prim, unde $q$ este prim, de asemenea, și dacă $p \mod 8 = 7$ (ceva pe care Wikipedia a uitat să menționeze), apoi valoarea $g=2$ are întotdeauna ordine $q$; care este un prim mare. Ce e atât de special la 2? Ei bine, face calcularea exponențiației puțin mai ușoară (deoarece înmulțirea cu 2 modulo p este destul de ieftină).
Și, când vorbește despre simbolul Legendre, dezvăluie ceva despre $g^a$, ei bine, aceasta este o metodă specială de găsire $a \bmod 2$; în esență, este aceeași abordare la care am făcut referire mai sus pentru a recupera $a \bmod s$ pentru $s=2$; funcționează numai dacă ordinul de $g$ are 2 ca factor. Pentru că am ales un $g$ care are o ordine ciudată $q$, nu merge.
[1]: S-ar putea să întrebi: chiar dacă $G^r$ este la fel, nu ar fi posibil ca $H^r$ ia valori diferite? Se dovedește că nu, asta nu se poate întâmpla - dacă găsim vreo valoare $r$ care îi conferă valoarea observată a $G^r$, el poate folosi asta pentru a decripta.
