Nu știu nimic, dar ați putea să construiți unul. (Totuși, de ce ai vrea unul este o altă întrebare...)
Generalități
Puteți găsi o întrebare oarecum înrudită și un răspuns excelent Aici, deși nu este vorba în mod specific de curbele eliptice.
TL;DR înseamnă că este mai ușor să construiești o hartă biliniară pe grupuri de ordine compusă $N=pq$ cu $p$ și $q$ numere prime, deoarece acestea vor avea două subgrupuri de ordin prima mare în mod natural din teorema lui Lagrange.
Acum, pentru Curbele Eliptice lucrurile sunt ușor diferite. Construim un „grup de curbe eliptice” care este definit pe un anumit câmp.
„Coordonatele” punctelor curbei eliptice sunt „vii” în acel câmp, dar punctele în sine sunt „vii” în grupul EC.
Amândoi au comenzi diferite. Câmpul are propria sa ordine, iar grupul de curbe eliptice are propria sa ordine $n$ (care poate fi compus sau prim). Când vorbim despre curbele de ordin prim, luăm în considerare de obicei ordinea grupului de curbe eliptice, nu cea a câmpului de bază peste care este definită.
Atacul MOV și gradul de încorporare
Un lucru care este important de știut în acest domeniu este că există așa-numitul Atacul MOV care utilizează o împerechere biliniară care mapează două puncte dintr-o curbă eliptică $E(\mathbb{F}_q)$ la un element din domeniu $\mathbb{F}_{q^k}$, pentru $k$ gradul de încorporare al acelei curbe.
Noi definim $k$ ca fiind cea mai mică valoare astfel încât $n | q^k-1$.
Atacul MOV este periculos pentru că dacă $k$ este mic, atunci rezolvarea DLP în acel câmp de extensie este mai ușoară decât în grupul inițial de curbe eliptice și mapează înapoi la soluția de pe curba eliptică, rupând efectiv securitatea acesteia.
Deci, curbele eliptice tipice pe care le folosim pentru ECDSA, ECDH și alte scheme bazate pe curbe eliptice (care nu sunt bazate pe împerechere) au o cerință ca gradul lor de încorporare să fie mare. SEC 1 v2 spune de exemplu:
În cele din urmă, deși nu sunt cunoscuți algoritmi subexponențiali generali pentru a rezolva ECDLP, trei clase de curbe sunt susceptibile la algoritmi cu scop special. În primul rând, curbele eliptice $E$ peste $F_q$ cu $n$ împărțind $q^B â1$ pentru mici $B$ sunt susceptibili la atacurile descrise de Menezes, Okamoto și Vanstone [MOV93] și Frey și Rück [FR94]. Atacurile reduc eficient ECDLP
pe aceste curbe la problema tradițională a logaritmului discret într-o extensie de grad mic de $F_q$. Un legat $B â¥20$ a fost actualizat la $B â¥100$ în [X9.62a] pentru a oferi o marjă mare de siguranță.
Aici lor $B$ este valoarea noastră $k$.
De ce contează gradul de încorporare
Alegerea acelui grad de încorporare $k$ pentru criptografia bazată pe perechi este un compromis între securitate și eficiență: un grad de încorporare mai mare înseamnă că problema logaritmului discret este mai greu de rezolvat în grupul multiplicativ rezultat, dar înseamnă și că operațiunile sunt efectuate într-un câmp de extensie de grad mai mare. , care este mai puțin eficient...
Acum, când vorbim despre curbele „prietenoase pentru asociere”, ceea ce se înțelege de obicei este că știm o modalitate de a construi o pereche care va fi "ușor" calculat pentru acea curbă eliptică. De asemenea, înseamnă că de obicei ne așteptăm să avem o valoare relativ „scăzută” pentru $k$, de cele mai multe ori $k \leq 24$.
(Dacă doriți să aveți o imagine de ansamblu asupra curbei eliptice de gradul de încorporare 1, vă recomand să citiți această lucrare din 2016.)
Ce înseamnă despre securitatea DLP?
Lăsa $G$ fi un subgrup de ordine $q$ în $E(F_p)$.
The Algoritmul Pollard-Rho pe subgrup $G$ a curbei noastre eliptice va lua $\sqrt{\frac{Ïq}{2}}$ pași, iar fiecare pas are ~$O(\log^2(p))$.
Aceasta înseamnă că vrem să ne asigurăm că subgrupul nostru este ordonat $q$ este cât mai mare posibil pentru ca algoritmul Pollard-Rho să dureze cât mai mult posibil.
Cu atacul MOV menționat mai sus, hai $e : G\time G' âF_{p^k}$ , Unde $k$ este gradul de încorporare, DLP activat $G$ poate fi apoi tradus în DLP on $F_{p^k}$ și Pollard-Rho pe câmpul nostru de extindere $F_{p^k}$ nevoi de asemenea $\sqrt{\frac{Ïq}{2}}$ pași, dar fiecare pas durează numai $O(k \log(p))$, aceasta este o diferență uriașă de complexitate.
Acesta este motivul pentru care dorim să avem un grad mare de încorporare $k$ pentru curbele eliptice utilizate pentru ECC obișnuit, așa cum am menționat deja mai sus, dar nu neapărat în criptografia bazată pe perechi.
Cazul de ordin primar
În cele din urmă, este important să ne amintim de ce „comenzile prime” sunt interesante cu DLP: asta din cauza Algoritmul Pohlig-Hellman, al cărui caz de complexitate cel mai rău este cel al algoritmului baby-step-giant-step când ordinea este primă.
Pohlig-Hellman este practic la fel ca CRT pentru RSA, ne permite să lucrăm în grupuri mai mici și mai ușoare dacă ordinea grupului nostru inițial nu este primară.
În acest tip de configurație, este logic să avem o ordine primă mare, deoarece toate subgrupurile din grupul nostru inițial trebuie să-și împartă ordinea, prin urmare suntem siguri că Pollard-Rho este cât de greu poate fi.
Cazul ECDLP
Interesant este că cel mai bun atac (general) cunoscut (vezi acest) pe criptografia cu curbe eliptice este o combinație a ambilor algoritmi Pohlig-Hellman și Pollard-Rho.
Dacă denotați $l$ cel mai mare divizor prim al $n$, acest atac este capabil să abordeze ECDLP numai în $O(\sqrt{l})$ timp, de aceea am dori să avem un divizor prim mare în ordinea noastră $n$...
Observați că pentru curba anormală, adică curbele eliptice peste un câmp $F_p$ al cărui ordin CE este de asemenea $p$, avem atacuri care rulează în timp polinomial! Vezi Satoh și Araki Aici, sau Semaev, sau Inteligent:
În practică, metoda descrisă înseamnă că atunci când alegeți curbele eliptice de utilizat în criptografie trebuie eliminate toate curbele ale căror ordine de grup sunt egale cu ordinea câmpului finit
(sublinierea mea)
Observați că, în general, dacă $nâ1$ este un produs al numerelor prime mici, atunci algoritmul PohligâHellman poate rezolva eficient problema logaritmului discret din acest grup, ceea ce este de obicei un motiv pentru care am alege un prim sigur atunci când avem de-a face cu DLP: asigură că avem un " mare" prim în descompunerea lui $n-1$.
Pe ordinea comenzilor EC vs punctul de bază
Observați că ordinea unei curbe este practic numărul de puncte raționale de pe acea curbă eliptică. Dacă lucrăm $F_p$, atunci știm că acel număr de puncte în CE nostru este $p+1-t$ Unde $t$ este Frobenius urma curbei. Prin teorema lui Hasse știm și că $t$ este între $-2 \sqrt{p}$ și $2 \sqrt{p}$.
Dar în ECC lucrăm de obicei la un subgrup a unei curbe eliptice definite de un punct de bază. Ordinea punctului de bază este un divizor prim al $p+1-t$ prin teorema Lagrange.
Deci, care dintre ele ai vrea să fie un prim sigur? Aș presupune subgrupul generat de un punct de bază dat.
Acest lucru este valabil și pentru criptografia bazată pe împerechere: împerecherile sunt definite pe un subgrup al grupului EC. De obicei Împerecherea Tate presupune $k>1$, $\#E(F_p) = hn$, pentru $n$ un prim și funcționează în subgrupul de ordine $n$ a acelei curbe eliptice.
Cum să construiești unul?
Din păcate, așa cum v-am spus la început, nu cunosc o curbă prietenoasă cu asociere a cărei ordine a subgrupului este un prim sigur. Ar trebui să fie posibil să construiesc unul, dar nu am avut timp (încă) să scriu un script de căutare care să producă unul.
Cum facem? Ei bine, mă tem că cea mai ușoară cale este „încercare și eroare” acolo!
Barreto și Naehrig au dat o metodă pentru curbele de ordin prim cu $k = 12$, care a fost „extins” la curbe cu $k= 3, 4, 6$ de Freeman.
Din păcate, nu sunt conștient de o implementare open source care să vă permită să o faceți cu ușurință
încercați să generați aceste curbe.
