Numere prime mari în ECC și logaritm discret

În criptografia cu curbe eliptice folosind protocolul Diffie-Hellman, trebuie să folosim numere prime mari.

Deci întrebarea mea este ce face logaritmul discret greu de rezolvat atunci când folosim numere prime mari.

Bănuiesc că, deoarece folosim numere prime mari, vom avea o mulțime de puncte care ne satisface ecuația curbei

Răspunsul nu este atât de simplu;

• În primul rând numărul de puncte care satisfac ecuația curbei $N$ pe curbă este mărginită de limita lui Hasse $$|N - (q+1)| \le 2 \sqrt{q}$$ pentru un prim $q$. Acest lucru spune pur și simplu că, dacă doriți o curbă care are un număr mare de puncte, atunci aveți nevoie de un prim mare (nuvelă).

• Ordinea curbei trebuie să fie primă (curbe prime) sau trebuie să aibă cel puțin un factor prim mare.Curba25519 nu este o curbă primă, care are un cofactor $h=N/8$, aceasta permite reprezentarea Montgomery a curbei care ajută la securizarea implementărilor. Dacă curba are ordine lină, ceea ce înseamnă că nu va avea un prim mare atunci Poglig-Helamn îl va distruge indiferent de ordine. Este important să ai o comandă mare sau o comandă principală mare.

• Răsucirea curbei trebuie să aibă o ordine primă mare împotriva atacuri de răsucire.

• Ordinea curbei și ordinea câmpului de bază $(K)$ sunt aceleași, atunci logaritmul discret de pe această curbă rulează în timp liniar Smart 97.

• Curba nu ar trebui să fie suprasingular, în caz contrar, logaritmul discret este ușor (acum sunt utilizați pentru izogenie care nu folosește logaritmul discret și se așteaptă să fie în siguranță împotriva atacului lui Shor)

Acum, combinând acestea, putem spune dacă grupul de curbe de puncte al ECC are un prim mare și nu are o proprietate specială (putem spune că este un curba generica) atunci cel mai bun atac este Rho-ul lui Pollard cu $\mathcal{O}(\sqrt{N})$.

Cu aceasta, putem spune că Curve25519 are o securitate a jurnalelor discrete de aproximativ 128 de biți, iar Curve448 are securitate a jurnalelor discrete de 224 de biți.

Și, în sfârșit, pentru mai multe informații vizitați curbe sigure.

În criptografia cu curbe eliptice folosind protocolul Diffie-Hellman, trebuie să folosim numere prime mari.

Mai precis

• De obicei folosim o curbă cu un generator a cărui ordine este divizibilă cu un prim mare, deoarece aceasta oferă asigurare împotriva Pohlig-Hellman metoda de calcul a logaritmilor discreti.
• Adesea facem generatorul exact din ordinea principală, deoarece putem face acest lucru cu ușurință, iar asta face ca curba+generatorul să fie mai potrivit pentru alte utilizări, cum ar fi semnătura. Totuși, acest lucru nu este util pentru securitatea lui Diffie-Hellman, AFAIK.
• Adesea folosim o curbă pe un câmp de ordin prim mare, chiar dacă nu avem prea, din motive discutate Acolo.