Cum este dificultatea problemei cu logaritmul discret legată de criptografia cu curbe eliptice?

Prin definiție, problema logaritmului discret este de a rezolva următoarea congruență pentru $x$ și se știe că nu există un algoritm eficient pentru asta, în general.

$$\begin{align*} b^x\equiv r&\pmod p\quad(1)\end{align*}$$ Este de a găsi $x$ (dacă există) pentru dat $r,b$ ca numere întregi mai mici decât un prim $p$.

Am dreptate până acum? va rog sa ma corectati daca am inteles gresit ceva.

În criptografia cu curbă eliptică se spune că în $P=a\ori G$ nu putem calcula $a$ prin cunoaştere $P$ și $G$ deoarece problema logaritmului discret este greu de rezolvat. Nu înțeleg că cum este aceasta legată de ecuația 1. Vreau să spun că numai terminologia este similară în ambele probleme?

Pentru a clarifica întrebarea mea, să ne imaginăm că un geniu din generațiile viitoare poate introduce în sfârșit o soluție la ecuația 1, care se face într-un timp fezabil folosind o configurație hardware medie a timpului. Algoritmul pe care îl propun este capabil să găsească $x$ (dacă există) pentru orice prim dat $p$ și orice dat $r, b$. Acum, vreau să știu că această invenție este o amenințare pentru securitatea criptografiei cu curbe eliptice? Cu alte cuvinte, cunoașterea unui astfel de algoritm va ajuta la regăsire $a$ din $P$?

Dacă da, vă rugăm să explicați cum este definită această relație și care este fluxul matematic prin care putem calcula $a$ din $P$, pe care cred că va trebui să treacă prin rezolvarea unei congruențe similare cu ecuația 1.

Dacă nu, vă rog să-mi spuneți care este diferența dintre problema durității logaritmului discret în curbele eliptice și cea a ecuației 1 și de ce este folosită această terminologie aici.

The problema logaritmului discret poate fi definit pentru orice grup ciclic finit, nu doar pentru grupul multiplicativ modulo un număr prim. Cea mai cunoscută instanță este problema pe care o descrieți, dar nu este singura.

Grupurile pot fi scrise cu notație multiplicativă (ca și în cazul grupului multiplicativ modulo $p$), astfel încât operația de grup să fie scrisă ca $*$, $\ori$, $\cdot$ sau pur și simplu implicit. În toate aceste cazuri luăm notația naturală pentru utilizarea repetată a operației de grup cu un singur element, i.e. $b^2:=b*b$ și generalizări similare. Astfel, problema generică a logaritmului discret pentru un grup ciclic $C$ scris cu notatie multiplicativa generata de $b$ este dată $r\în C$ găsiți un număr întreg $x$ astfel încât $b^x=r$.

Alte grupuri sunt scrise cu notație aditivă (aceasta este de obicei rezervată pentru grupurile abeliene, inclusiv grupurile de curbe eliptice). În acest caz se notează operația de grup $+$ (dar nu ar trebui citit ca adaos în sensul obișnuit) și din nou există o notație naturală pentru utilizarea repetată a operației de grup cu un singur element, i.e. $2G=G+G$ si asa mai departe. Când este scrisă în acest fel problema logaritmului discret pentru un grup ciclic $C$ generat de $G$ devine: dat $P\în C$ găsiți un număr întreg $x$ astfel încât $xG=P$.

Nu se crede că există o traducere clară între problemele de logaritm discret în diferite grupuri. Există unele grupuri în care problema logaritmului discret este ușoară (de exemplu, grupuri aditive modulo $p$, grupuri multiplicative modulo $2^n$ și chiar (în sens cvasi-polinomial) grup multiplicativ de $GF(2^n)$).

Pentru cazul particular al grupelor multiplicative modulo $p$ cel mai cunoscut atac (clasic) este cel ciur câmp numeric care rezolvă problema în timp sub exponenţial. Acest atac poate fi aplicat doar unor clase foarte rare de curbe eliptice (curbe MOV) iar cele mai cunoscute atacuri generice împotriva curbelor eliptice sunt atacurile „rădăcină pătrată” care se aplică tuturor grupurilor.

Rețineți că toate problemele cu logaritmi discreti pot fi rezolvate în timp polinomial (cuantic) prin algoritmul lui Shor.

Lăsa $E$ fie o curbă eliptică definită pe un câmp finit $\mathbb{F}_p$:

$$E : y^2 = x^3 + Ax + B \text{ cu } A, B \in \mathbb{F}_p$$

Lăsa $P$ și $T$ fii puncte în $E(\mathbb{F}_p)$. Găsiți un număr întreg $a$ asa de acea

$$ P =aG$$

Aceasta este problema pentru curbele eliptice. Problema poate fi rescrisă folosind un logaritm:

$$ a = log_G (P)$$

Puteți compara asta cu logaritmul discret „standard”:

$$ b^x \equiv r \mod p \Rightarrow x = log_b(r)$$

Vedeți acum asemănările?

Notă: Geniul tău ar trebui să aibă o modalitate eficientă de a o sparge, nu pentru că are resurse nelimitate. Și da, dacă aveți o modalitate eficientă de a rupe logaritmul discret, puteți folosi o variație a acestuia pentru a rupe curbele eliptice. Principalul punct al cripto-curbei eliptice este că calculele sunt mai rapide decât pentru sistemele de logaritm discret „standard” (există o mulțime de alte avantaje diferite pentru ecc).