De ce protocoalele de criptografie cu curbe eliptice depind de curbele fixe?

Învăț despre Ed25519. Depinde de o grămadă de valori magice: Câmpul finit al ordinii $2^{255}-19$, curba eliptică specifică peste acel câmp, un punct specific pe curba respectivă. Acest lucru este în contrast cu Diffie-Hellman sau RSA.

De ce este asta? Și invers, de ce nu fixează DH numărul prim și generatorul sau RSA, să zicem, $n = pq$ valoare?

Bănuiesc că în cazul DH & RSA este foarte ușor să generați noi instanțe ale protocolului. Știm multe despre numere prime, așa că este ușor să generați altele noi și, de asemenea, dimpotrivă, dacă am fixa un prim pentru toate instanțele protocolului, am putea să-l analizăm al naibii și să-l distrugem.

Deci, în cazul curbelor eliptice, nu este atât de ușor să găsești o curbă și un generator?

Motivul pentru a nu repara o anumită curbă/grup/orice asupra căruia trebuie să lucrați este dacă dăunează securității, și anume dacă:

1. Există atacuri de precalculare – un atac care costă $T$ care poate fi amortizat peste $n$ utilizatorii acum costă efectiv $T/n$. Pentru $n\aprox$ 1 miliard acest lucru poate modifica calculele cost/beneficiu.

2. Este posibil ca un organism de standardizare rău intenționat să standardizeze o curbă/grup/orice „slab”, de exemplu una cu ușă în spate sau una care este pur și simplu mai slabă decât una „aleatorie” într-un fel.

Acestea sunt probleme pentru anumite probleme dificile – problema LWE și DH cu câmp finit admit ambele atacuri de precalculare, de exemplu. Pentru LWE, aceasta este folosită ca justificare pentru nestandardizarea unei „Matrice LWE $\mathbf{A}$".

Acestea fiind spuse, pot exista beneficii în a remedia o anumită curbă/grup/oricare ar fi. Și anume:

1. Nu mai trebuie să-l generați în timpul protocoalelor, economisind o anumită eficiență.
2. Nu mai trebuie să-l transmiteți (sau puteți transmite o descriere succintă a numărului constant de obiecte standardizate), economisind o anumită lățime de bandă
3. Puteți optimiza operațiunile pentru acea curbă/grup/orice, economisind eficiența
4. Este mai greu să alegi curbe/grupuri/orice „slab” din greșeală.

În ceea ce privește motivul pentru care curba 25519 ia forma particulară pe care o are, vezi de exemplu Curbe sigure pagina pentru câteva descrieri/comparații ale diferitelor proprietăți ale curbelor.

Pentru aceste intrebari:

De ce nu fixează DH numărul prim și generatorul

Se întâmplă în anumite aplicații. Iată o listă de grupuri DH cu câmp finit utilizate în TLS (inclusiv 1.3). Rețineți că trebuie să fiți atenți cu acest lucru, deși â erau grupuri „slabe” standardizate ($\aproximativ 512$ biți) pe care nimeni nu le-ar folosi în mod realist. Prezența lor în această listă de grupuri standardizate a dus la Atacul blocaj, unde se montează atacul de precomputație împotriva lor + îl combină cu un anumit „atac de downgrade”.

Sau RSA remediază, să zicem $n=pq$ valoare?

Nu este clar cum ați putea utiliza acest lucru practic, deoarece există într-adevăr doar o singură cheie privată asociată cu ea, așa că doi utilizatori diferiți nu ar putea folosi ambii o singură cheie privată. $n$ pentru criptare. De fapt, chiar dacă folosesc $n, n'$ care au un factor comun, duce la atacuri (și o altă lucrare Nadia Heninger, Exploatarea P și Q-urile tale). Acestea fiind spuse, există aplicații speciale în care poate fi util, vezi de exemplu această lucrare despre generarea de modul RSA distribuit pentru unele discuții despre aplicații.

Motivul tipic pentru care oamenii folosesc de obicei curbele eliptice prespecificate în loc să le genereze este eficiența. Nu este foarte dificil să generați o curbă eliptică, dar în general este dificil să generați a sigur curba eliptică și, în plus, este relativ dificil să convingi cealaltă parte că curba este sigură pe lățimea de bandă limitată a protocolului. The Site-ul web SafeCurves explică multe dintre atributele care sunt de dorit într-o curbă și explică o parte din deciziile Curbe25519.

Cele mai multe dintre curbele eliptice binecunoscute sunt, de asemenea, alese special pentru eficiență, folosind un prim sau o formă care este concepută pentru a fi cât mai eficientă. De exemplu, utilizarea curbelor cu un prim fix aproape de o putere de doi face operațiuni specifice mult, mult mai rapide, iar implementările sunt de obicei codificate pentru a profita de anumite prime.

Mai mult, utilizarea curbelor eliptice prespecificate înseamnă că este mult mai ușor să scrieți implementări în timp constant. Acest lucru este foarte important în protocoalele online, cum ar fi TLS, unde se poate demonstra că implementările în timp non-constant sunt exploatabile. Este posibil pentru a scrie implementări generice în timp constant ale curbelor eliptice, dar este complex și oamenii practic nu o fac.

Este cu siguranță posibil să se utilizeze grupuri fixe în Diffie-Hellman non-EC; TLS face acest lucru, iar SSH o face, de asemenea. Atâta timp cât se alege un grup suficient de mare de formă adecvată, aceasta este sigură. Utilizarea unui grup fix este, de asemenea, mai eficientă în ceea ce privește lățimea de bandă a protocolului, deoarece parametrii nu trebuie să fie trimiși.

De asemenea, este posibil să se genereze grupuri de câmpuri finite aleatorii și securizate și acest lucru este mult mai rapid decât generarea de curbe eliptice securizate, dar este încă suficient de lent încât, de obicei, oamenii precalculează parametrii o dată și apoi îi folosesc pentru o perioadă de timp.

În ceea ce privește RSA, reutilizarea parametrilor nu este de obicei sigură. În plus, din motive de eficiență, cheia privată include adesea $p$ și $q$, ceea ce ar compromite imediat cheia privată a oricărei persoane care partajează $N$. Chiar dacă se distribuie $N$ nu a avut probleme de securitate, pentru că $p$ și $q$ nu ar putea fi expus, acest lucru ar fi mult mai puțin eficient decât generarea de noi parametri per utilizator.