Acest răspuns se limitează la grupuri sub operația de înmulțire modulo un prim mare $p$, deoarece întrebarea o face (alte grupuri sunt din ce în ce mai frecvente în criptografie, inclusiv grupurile de curbe eliptice).
Deci vom lucra în cadrul grupului $\mathbb Z_p^*$, o notație pentru submulțimea inelului $\mathbb Z/p\mathbb Z$ format din elemente care au un invers multiplicativ, despre care se poate demonstra că formează un grup. De cand $p$ este prim, $\mathbb Z/p\mathbb Z$ este un câmp și $\mathbb Z_p^*$ este acel câmp mai puțin neutru pentru adunare. $\mathbb Z_p^*$ poate fi asimilat numerelor întregi $\{1,2,\ldots,p-2,p-1\}$. Are $p-1$ elemente. Legea internă a acestui grup este multiplicarea modulo $p$.
Vrem un grup $\mathbb Z_p^*$ (sau un subgrup al acestuia) în care calcularea logaritmului discret este dificilă. Condiții pentru aceasta (ambele se dovedesc necesare și se presupune că sunt suficiente atunci când ambele sunt îndeplinite):
- Ordinea grupului (adică numărul de elemente) trebuie să aibă un factor prim suficient de mare $q$ a bloca Pohlig-Hellman combinat cu rho lui Pollard, care poate calcula logaritmul cu efort $\mathcal O\,\left(\sqrt q(\ln n)^3\right)$ și memorie moderată, o dată $p$ și $q$ sunt cunoscute. Așa vrem $q$ cel puțin 256 de biți de securitate pe 128 de biți.
- $p$ trebuie să fie suficient de mare pentru a bloca algoritmii familia de calcul index. Asta ar necesita $p$ de la 2048 la 4096 biți (în funcție de conservatorism, ipoteză și sursă) pentru securitate pe 128 de biți, presupunând în continuare $p$ nu este prea aproape de puterea unui întreg mic.
Cum se instalează sistemele practice cu logaritm discret?
Primul lucru este să decidem ce fel de cadru logaritmic discret dorim să setăm și asta depinde de ceea ce intenționăm să-l folosim. Există trei tipuri utilizate în mod obișnuit:
- Grupul complet $\mathbb Z_p^*$, cu ordine $2q=p-1$ și $q$ prim. Acesta este folosit atunci când ceva impune un generator al întregului grup (ca „generatorul de grup multiplicativ al întrebării” $\mathbb Z/p\mathbb Z$" luat la litera nu).
- Subgrupul de reziduuri pătratice, cu ordin prim $q=(p-1)/2$. Elementele sale sunt $y$ în $\mathbb Z_p^*$ care poate fi scris ca $y=u^2$ pentru un element $u$ de $\mathbb Z_p^*$ (și apoi și pentru $u'=p-u$, desigur). Există astfel de grupuri standard cu generator $g=2$, vedea RFC 3526. Ele pot fi folosite pentru majoritatea utilizărilor care nu necesită un generator al întregului grup.
- Un subset mai mic al submulțimii de reziduuri pătratice, cu ordinul prim $q=(p-1)/r$ pentru unii (chiar) $r$. Acestea se numesc grupul Schnorr. Sunt folosite în semnătura originală Schnorr și DSA.
Există adesea un motiv pentru a nu folosi (1.): dacă $g$ este un generator (adică orice element al grupului poate fi exprimat ca $g^x$ ), apoi din valoarea lui $g^x$ este ușor de spus dacă $x$ este par sau impar (prin calculul Simbol Legendre). Acest lucru contravine ipotezei de dorit pentru dovezile de securitate simple, împotriva obiectivelor din dovezile cu cunoștințe zero și ar putea permite atacuri (de exemplu, criptarea ElGamal eșuează CPA).
Există uneori un motiv pentru a nu folosi (2.) și preferați (3.): în aplicațiile de semnătură cel puțin, una dintre componentele semnăturii are aceeași dimensiune de biți ca și $q$, care trebuie să fie mare, dar poate fi mult mai mică decât $p$. Folosind astfel un mic $q$ permite semnături mai scurte. Acesta este motivul pentru care au fost introduse grupurile Schnorr.
Pentru (1.) și (2.), generând $p$ și $q$ se rezumă la generarea primului $q$ cu $p=2q+1$ de asemenea prim. Este eficient să faci un test relativ rapid $q$ nu este compus (de exemplu, un test Fermat la baza 2: verificați că $2^{q-1}\bmod q=1$), apoi un test amănunțit că $p=2q+1$ este prim; apoi un test amănunţit că $q$ este prim. Mai mult, pentru un prim mic $s$, tine $q\bmod s\nu\în\{0,(s-1)/2\}$. Prin urmare $q\bmod3=2$, $q\bmod5\in\{1,3,4\}$, prin urmare $q\bmod30\in\{11,23,29\}$, ceea ce restrânge căutarea. Avand in vedere ceva mai mare $s$ poate fi folosit pentru o sită sau alte accelerații.
De asemenea, se poate arăta că pt $p$ și $q$ în ceea ce privește (1.) sau (2.), $g=2$ este un generator pentru (1.) dacă și numai dacă $q\bmod4=1$ (echivalent $p\bmod8=3$ ); iar un generator pentru (2.) altfel. Astfel de folosit $g=2$ (cel mai mic generator posibil și unul care simplifică puțin unele calcule), vrem $q\bmod60\in\{29,41,53\}$ pentru (1.) și $q\bmod60\in\{11,23,59\}$ pentru (2.).
Pentru (3.), putem alege primul aleatoriu $q$ de dimensiunea dorită, apoi chiar aleatoriu $r$ de dimensiuni adecvate pentru a avea $p=q\,r+1$ prim. Un generator este $g=2^r$ (cu excepția cazului în care este $1$, ceea ce este cel puțin covârșitor de puțin probabil; Ma intreb daca este chiar posibil):
Dacă vrem un generator aleatoriu, putem alege un secret aleatoriu $x$ în $[1,q-1]$ si foloseste $g$ după cum urmează:
- pentru (1.) și $p\bmod8=3$: $g\gets2^{2x+1}$
- pentru (1.) și $p\bmod8=7$: prin încercare și eroare găsim $y$ cu $y^{(p-1)/2}\bmod p\ne 1$ (echivalent, cu $y^{(p-1)/2}\bmod p=p-1$ ); numărul așteptat de încercări este de aproximativ două dacă explorăm impare consecutive $u$ pornire $u=3$; atunci $g\obține u^{2x+1}$.
- pentru (2.), $g\gets2^{2x}$
- pentru (3.), $g\gets2^{((p-1)/q)\,x}$
Nu există un algoritm cunoscut de găsit $g$ în timp polinomial.
Acest lucru este adevărat dacă factorizarea ordinii de grup este necunoscută sau dacă ne limităm la determinat algoritmi. Dar, în practică, ordinea este cunoscută, uneori putem prezice un generator, iar algoritmii probabilistici simpli vor da rapid unul altfel.
Există pachete cu număr mare?
Python are suport nativ pentru numere mari și este un exercițiu simplu pentru a construi parametrii $(p,g)$ în Python pur. Singurele dificultăți ușoare sunt testul prim și generația prime aleatoare. Dar ele pot fi făcute în Python pur și există suport pentru acestea în mai multe pachete, inclusiv SymPy. De cand $(p,g)$ sunt de obicei publice, canalele secundare nu reprezintă o problemă.
