De ce curbele eliptice peste câmpuri binare sunt utilizate mai puțin decât cele peste câmpuri prime?¼

În aplicațiile practice, curbe eliptice peste $F_p$ par a fi mai populari decât cei de peste $F_{2^n}$. Oare pentru că operațiunile peste câmpurile prime sunt mai rapide decât cele de peste $F_{2^n}$ pentru acelasi nivel de securitate?

Poate este imaginația mea. Doar că văd multe alte proiecte deschise folosind curbe eliptice peste $F_p$ dar nu la fel de multe peste $F_{2^n}$.

Securitate: Câmpurile binare au mai mulți vectori de atac decât câmpurile prime

Jurnalul discret al ECC-urilor cu câmpul binar nu este întrerupt. Nu acesta este motivul. Bernstein spus;

povestea de securitate pentru câmpurile non-prime (de exemplu, câmpurile de extensie binare) este mai complicat și mai puțin stabil decât povestea de securitate pentru domeniile principale, așa cum este ilustrată de 1998 Frey, 2002 GaudryâHessâSmart, 2009 Gaudry și 2012 PetitâQuisquater.

Ca rezultat, alegerea câmpurilor prime reduce vectorii de atac, astfel încât există mai puține preocupări pentru securitate.

• 2002 Fațete constructive și distructive ale coborârii Weil pe curbele eliptice

  În această lucrare ne uităm în detaliu la curbele care apar în metoda lui Galbraith și Smart pentru producerea de curbe în restricția Weil a unei curbe eliptice peste un câmp finit de caracteristica doi de grad compus. Explicăm modul în care această metodă poate fi utilizată pentru a construi criptosisteme hipereliptice care ar putea fi la fel de sigure ca și criptosistemele bazate pe curba eliptică originală. Pe de altă parte, arătăm că aceasta poate oferi o modalitate de a ataca criptosistemul original al curbei eliptice folosind progresele recente în studiul problemei logaritmului discret pe curbele hipereliptice.

• 2004 Calcul indicelui pentru varietăți abeliene și problema logaritmului discret al curbei eliptice de Pierrick Gaudry

  Am arătat că asimptotic, curbele eliptice definite pe câmpuri de extensie de grad mic sunt mai slab decât cele definite peste câmpuri prime sau câmpuri mari de extensie de gradul prim.

• 2012 Despre sistemele polinomiale care decurg dintr-o coborâre Weil de Christophe Petit și Jean-Jacques Quisquater

  Ei s-au uitat la ECDLP pe câmpul de extensie binar și au arătat că algoritmul lor depășește algoritmii generici de logaritm discret pentru $N >2000$. Dimensiunile recomandate nu sunt încă afectate!

Brevete ale Certicom (și altele)

O altă problemă importantă este brevete că în principal Certicom-ul are/a avut.

Primul citatul lui Bruce Schneier

„Certicom poate revendica cu siguranță proprietatea asupra ECC”, ne-a spus Schneier. "Algoritmul a fost dezvoltat și brevetat de fondatorii companiei, iar brevetele sunt bine scrise și puternice. Nu îmi place, dar pot revendica proprietatea."

• Unul dintre brevetele Certicom era despre eficiență $\operatorname{GF}(2^n)$ înmulțirea în reprezentarea de bază normală; Brevetul U.S. 5.787.028. Acest brevet a fost acordat în 1998 și a expirat în cele din urmă în 2016.
• NSA avea niște brevete $\operatorname{GF}(2^n)$, de asemenea; [1] [2] [3] [4], cu toate acestea, acestea au expirat mult mai devreme, deoarece NSA nu a plătit taxele (cred că a fost intenționat)

Stadiul actual al atacurilor de comparat

Dacă ne uităm la Provocările ECC ale Certicom

• O curbă Koblitz peste $2^{108}$ este stricat in 2000.
• A $109$ curba bit prime este ruptă în 2002.
• O curbă peste $2^{109}$ este spart în 2004.
• Provocările binare sau Prime pe 131 de biți nu sunt încă rupte.

În afară de aceste provocări;

• Problema logaritmului discret al curbei eliptice de 117,35 de biți pe o curbă binară este întreruptă în 2016 de Bernstein et. al

Un fapt cu picioarele pe pământ care schimbă echilibrul spre $\mathbb F_p$ este că procesoarele standard din anii 1990 și începutul anilor 2000 aveau adesea instrucțiuni de multiplicare, dar nu suporta hardware pentru produs fără transport, inversând avantajul $\mathbb F_{2^k}$ are in hardware. Și aritmetica în $\mathbb F_p$ a fost studiat pe larg pentru RSA și DSA. Deci este de înțeles că oamenii au început să folosească $\mathbb F_p$, și atunci nu a existat niciun motiv convingător să se schimbe. Poate (per in acest comentariu) Brevetele Certicom privind ECC în $\mathbb F_{2^k}$ a alungat propectele. De asemenea, mai mulți oameni înțeleg aritmetica în $\mathbb F_p$, și nimeni nu a fost concediat pentru că a ales-o.

Din punct de vedere al securității, cred că există un sentiment rezonabil cu care $\log_2p\aproximativ m$, ECC în câmpul principal $\mathbb F_p$ este mai sigur decât în ​​câmpul binar $\mathbb F_{2^m}$. Motivele pe care le inteleg sunt:

• Pentru un dat $m$, sunt aproximativ $\aproximativ 0,69\cdot2^m/m$ alegeri pentru $p$. Toate câmpurile finite de un ordin dat sunt izomorfe. Asa de $\mathbb F_{2^m}$ este un caz special, iar în cripto, cazurile speciale rareori sunt mai sigure.
• Cel puțin în hardware, adăugarea punctului ECC este semnificativ mai costisitoare pe teren $\mathbb F_p$ decât în ​​câmp $\mathbb F_{2^m}$. Poate că mai greu înseamnă mai sigur și mai greu să implici mai puțin sigur ar fi destul de surprinzător.
• Rezolvarea DLP în subgrupul multiplicativ al câmpului $\mathbb F_p$ este mult mai greu decât pentru $\mathbb F_{2^m}$, după cum se poate vedea din înregistrări ($795\text{-bit }p$ în $\mathbb F_p$, $m=30750$ în $\mathbb F_{2^m}$ ). Din nou, poate DLP mai greu în subgrupul multiplicativ implică DLP mai greu în grupul ECC și ar fi o surpriză că a implicat DLP mai ușor în grupul ECC.

Există și alte motive de securitate. Mă refer la primele trei gloanțe ale celălalt răspuns. Abia le înțeleg suficient pentru a spune că nu duc la un atac general asupra ECC în $\mathbb F_{2^m}$, de exemplu. pe curbele în secțiunea 3 din sec2v2. Dar totuși, este rezonabil ca acestea să insufle neliniște.

Până la urmă, ca majoritatea, accept Înțelepciunea Safecurve :

2006 Bernstein a declarat că câmpurile prime „au virtutea de a minimiza numărul de preocupări de securitate pentru criptografia cu curbă eliptică”. În mod similar, standardul Brainpool și standardele Suite B ale NSA necesită câmpuri principale. Există un acord general că câmpurile principale sunt alegerea sigură și conservatoare pentru ECC.