Euristica Fiat-Shamir este o metodă generală de a construi o schemă de dovadă (sau semnătură) non-interactivă dintr-o schemă de dovadă interactivă a cunoștințelor. Un exemplu a schemei interactive adaptabile euristicii Fiat-Shamir este schnorr-identificare protocol într-un grup Schnorr. Așa voi interpreta întrebarea (celălalt răspuns discutați perspectiva mai generală a euristicii Fiat-Shamir).
Un grup Schnorr este un subgrup de ordin prim $q$, și generator $g$, din grupa multiplicativă modulo unele prime $p$. Acel grup principal $\mathbb Z_p^*$ are ordine $\varphi(p)=p-1$. Deoarece ordinea unui subgrup împarte ordinea grupului, $q$ trebuie să fie o divizare primară $p-1$. De cand $g$ este un generator, trebuie să fie astfel încât $g^q\equiv1\pmod p$ și $g\nu\equiv1\pmod p$. Grupul Schnorr este de obicei menționat ca trei numere întregi $(p,q,g)$.
Cât de mare ar trebui să fie numărul prim $p$ fi? Cum să selectezi $p$ astfel încât, de exemplu, algoritmul PohligâHellman sau alți algoritmi cunoscuți nu l-ar putea rupe?
Pentru ca grupul Schnorr să fie de interes criptografic, problema logaritmului discret trebuie să fie dificilă în grupul Schnorr. Aceasta implică rezistența unor algoritmi DLP cunoscuți. Algoritmul care determină practic dimensiunea necesară a $p$ într-un grup Schnorr este varianta DLP a GNFS, care este calculul indicelui specializată să $\mathbb Z_p^*$. The recordul curent este un bit de 795 de biți $p$, iar o dimensiune minimă recomandată pentru aplicațiile actuale este de 2048 de biți sau de 3072 de biți pentru „2030 și mai departe”.
De asemenea, este necesar ca $q$ este suficient de mare încât Rho lui Pollard pentru DLP este imposibil de realizat. Costul este de aproximativ $\Theta(\sqrt q)$ înmulțiri de grup. Prin urmare, este recomandat un minim de 224 de biți sau 256 de biți $q$.
Aceste cerințe sunt suficiente pentru a asigura Pohlig-Hellman algoritmul este să nu te temi. Asta pentru că Pohlig-Hellman necesită rezolvarea unui DLP în fiecare subgrup de ordine $q^k$ cu $k\ge 1$, $q$ prim, și $q^k$ împărțirea ordinii grupului de bază; și $k=1$ este cel mai simplu caz.
Cum se selectează rădăcina primitivă $g$?
Acest algoritm de timp polinomial probabilist va face:
- alege primul aleator $q$ de dimensiunea dorită
- alege chiar aleatoriu $r$ pentru prim $p=qr+1$ de dimensiunea dorită
- ales aleatoriu $s$ în $[2,p-2]$, și calculați $g=s^{(p-1)/q}\bmod p$, pana cand $g\ne1$ (ceea ce este aproape sigur)
- ca verificare a coerenței, verificați $g^q\bmod p=1$ (acesta este valabil, dacă nu a existat o eroare).
Este sigur să folosiți aceleași valori ale $p$ și $g$ pentru câteva provocări?
Da. Cunoașterea soluției pentru un anumit DLP dintr-un grup Schnorr, în mod demonstrabil, nu ajută la rezolvarea altor DLP-uri aleatoare neînrudite pe același grup Schnorr (rămâne posibilitatea ca o anumită precalculare să poată fi amortizată între mai multe DLP-uri, dar asta este marginal).
De ce este mai bine să folosiți un grup Schnorr în loc de un prim sigur $p$?
Un prim sigur $p$ corespunde $p-1=2q$, sau $r=2$ în cele de mai sus. Deși din punct de vedere tehnic, aceasta încă se potrivește cu definiția unui grup Schnorr, nu îndeplinește o motivație cheie a grupurilor Schnorr: a avea o comandă. $q$ de dimensiuni mult mai mici decât $p$. Acest lucru este interesant pentru că sunt exponenți $\mathbb Z_q$, deci mai scurt $q$ duce la o exponențiere mai rapidă, secrete mai scurte și (într-o variantă comună a euristicii Fiat-Shamir) semnături mai scurte. De asemenea, căutarea $p$ este ceva mai implicat. Din câte știm, folosind un grup Schnorr suficient de mare $q$ și $p$ este la fel de sigur ca și folosirea unui prim sigur $p$ de dimensiuni comparabile.
