Criptosisteme asimetrice bazate pe curbe în afară de curbe eliptice

Criptografia cu curbă eliptică (ECC) a câștigat multă popularitate recent datorită securității sale. Tind să găsesc procesul de codificare a textului simplu folosind ECC deosebit de interesant, așa că mă întrebam dacă s-a dovedit/dezaprobat faptul că puteți găsi alte curbe pe baza cărora puteți crea criptosisteme? Dacă s-a dovedit că așa este, ce fel de curbe?

Pentru că nu toate curbele au aceleași proprietăți pe care le au curbele eliptice. De exemplu, dacă selectați oricare două puncte dintr-o curbă eliptică și trasați o linie prin ele, această linie va intersecta curba eliptică exact în alt punct. Această proprietate este utilizată intens în ECC.

De exemplu, dacă selectați oricare două puncte dintr-o curbă eliptică și trasați o linie prin ele, această linie va intersecta curba eliptică exact în alt punct. Această proprietate este utilizată intens în ECC.

Ceea ce descrieți aici este operația de grup pe curba eliptică.După cum sa subliniat deja, curbele hipereliptice, care sunt o generalizare a curbelor eliptice, sunt de asemenea utile pentru aplicații criptografice.

O curbă hipereliptică a genului $g$ peste câmp finit $\mathbb{F}_q$ poate fi descris printr-o ecuație de formă $$ C: y^2 + h(x)y = f(x) $$ Unde $f(x)$ este un polinom monic de grad $2g+1$, $h(x)$ este un polinom de cel mult grad $g$ cu unele conditii suplimentare.

Curbele eliptice pot fi privite ca curbe hipereliptice ale genului $g=1$, vă puteți aminti că o curbă eliptică în formă Weierstrass este dată de $ y^2 = x^3 + ax + b$, unde vedeți acel grad de polinom în $x$ este intr-adevar $2g +1 = 3$.

Aici, aș dori să mă concentrez pe curbele hipereliptice ale genului $2$. Voi explica în cele din urmă de ce acest caz particular este o alternativă interesantă la ECC. Dacă caracteristica câmpului finit $\mathbb{F}_q$ nu este $2$, apoi HEC de gen $2$ este dat de ecuație $$ y^2 = x^5 + b_4x^4 + b_3x^3 +b_2x^2 + b_1x + b_0, \quad b_i \in \mathbb{F}_q .$$ Avem o structură de grup în raport cu punctele de pe curbă? Raspunsul este nu. Dar aproximativ vorbind, putem descrie o structură de grup folosind „perechi de puncte” pe curbă.

În imaginea de mai sus, curba albastră este unicul cubic care trece prin $P_1, P_2, Q_1, Q_2$ (determinat prin interpolare).

Aici vă puteți pune următoarele întrebări:

1. Ce garantează că o dreaptă intersectează o curbă eliptică în trei puncte?
2. Câte puncte de intersecție are o linie cu o curbă hipereliptică a genului $2$?

Răspunsul se află în teorema lui Bezout pentru curbele algebrice plane. Pentru a înțelege structura de grup asociată cu curbele hipereliptice (cunoscută sub numele de Jacobian a curbei hipereliptice), veți avea nevoie și de o anumită înțelegere a geometriei algebrice. Aici este un bun punct de plecare pentru curbele hipereliptice.

HEC al genului $2$ sunt cele mai interesante pentru aplicațiile criptografice bazate pe Discrete Log Problem, deoarece pentru curbele de gen superioare, aveți atacuri de calcul index care pot fi folosite pentru a rezolva DLP.

Vedea această hârtie pentru aritmetică eficientă asupra HEC a genului $2$.

Există o premisă falsă în întrebare - și anume:

Curbele arbitrare pot fi utile în criptografie. Pe care îl deduc din citatul din întrebare:

s-a dovedit/infirmat că puteți găsi alte curbe pe baza cărora puteți crea criptosisteme

Să spun adevărul, nu a fost infirmat. Dar motivul ECC poate fi folosit în criptografie, este că poate servi ca a compact înlocuirea directă a criptografiei bazate pe logaritmi discreti bazată pe câmpuri finite de ordin prim (deoarece aritmetica punctual formează un grup).

Deci acum, dacă vrem să arătăm că curbele non-eliptice pot fi utilizate în criptografia cu cheie publică, atunci trebuie fie să arătăm că

1. ei formează, de asemenea, un grup fără mai multă slăbiciune decât ECC, sau
2. ele pot fi utilizate diferit și nu admit o bază de securitate mai proastă decât ECC.

Și, în mod ideal, sunt mai eficiente decât ECC.

Pe lângă curbele eliptice, secțiuni conice (peste un câmp finit adecvat $\mathbb F_p$) oferă, de asemenea, o structură de grup.

Prin urmare, acestea ar putea fi utilizate în schimburile de chei Diffie-Hellman. Rețineți, totuși, că aceste curbe nu par sigure de utilizat pentru criptografie, deoarece problema logaritmului discret pare ușor de rezolvat în grupul de puncte de peste aceste curbe. În general, DLP-ul poate fi redus la câmpul de bază.

Pentru un exemplu concret: asta hârtie studiază curba cu ecuație $x^2 ​​- Dy^2 = 1$, pentru o alegere adecvată a $D$. cu alte cuvinte, acesta este setul de soluții la această ecuație peste $\mathbb F_p$. Se arată că jurnalul discret este ușor.