TLDR: Dacă ne specializăm un punct generator $G$ dintr-un grup de curbe eliptice de ordin prim, putem în mod constant defini GCD-ul a două puncte pentru acel generator. Dar nu putem eficient găsi este pentru puncte arbitrare și un grup de interes criptografic, unde problema logaritmului discret este grea.
Înainte de a găsi ceva, trebuie să știm despre ce este vorba. De aici subîntrebarea lui Poncho:
Ce ar însemna „GCD-ul a două puncte pe o curbă primă”?
GCD înseamnă Cel mai mare divizor comun. Astfel, trebuie să definim trei noțiuni
- Ce este o „curbă primă”. In acest, curba reprezintă Curba eliptică. Și prim este o proprietate a fiecăreia
- baza câmp finitordinea lui (acea ordine primă este adesea notă $p$, iar apoi câmpul este pur și simplu numerele întregi modulo $p$);
- ordinea curbei, adică câte elemente din grup finit a punctelor curbei, inclusiv neutrul;
- sau ordinul a subgrup a curbei (apoi adesea notat $n$, așa cum vom face).
- Noțiunea de „divizor” a unui punct al unei curbe eliptice prime, pe care o vom presupune că este un punct al curbei eliptice cu o anumită proprietate de definit.
- Noțiunea de „cel mai mare” dintre punctele unei curbe eliptice.
Putem defini astfel de lucruri în mod constant! Presupunem că o „curbă primă” este un subgrup de ordin prim $n$ a unei curbe eliptice (poate întreaga curbă, care poate folosi un câmp prim; de ex. secp256k1, secp256r1), și $G$ un punct dat al curbei / un element al grupului, altul decât neutru. Acum setul de $n$ numere întregi în $[0,n)$ este izomorf cu curba, prin izomorfismul trivial $i\mapsto i\,G$ definit ca de obicei: $0\,G$ este neutru al grupului, $i\,G$ este $((i-1)\,G)+G$ pentru orice $i\în[1,n)$ cu $+$ legea grupului.
Putem defini „divizor” și „cel mai mare” pe platou $[0,n)$. Și putem defini GCD-ul a două elemente ale acelui set (împreună cu oarecum arbitrar $\gcd(0,0)=0$ ). Apoi putem folosi acest izomorfism pentru a defini cel mai mare divizor comun al două puncte dintr-un grup de curbe eliptice de ordin prim prevăzut cu un punct generator $G$.
Cu alte cuvinte, definesc GCD-ul de puncte $P$ și $Q$ ca punct în care cheia privată corespunzătoare (pentru generator $G$) este GCD-ul cheilor private care se potrivesc $P$ și $Q$, cu cheie privată corespunzătoare un număr întreg în $[0,n)$.
Dacă putem rezolva eficient problema logaritmului discret în grupul considerat, atunci putem calcula eficient GCD (rezolvăm două DLP, calculăm GCD-ul numerelor întregi și revenim la curbă).
Actualizare: invers este adevărat într-o oarecare măsură. Dacă putem calcula eficient GCD-ul de orice două puncte $P$ și $Q$, atunci putem folosi acel algoritm pentru a calcula eficient logaritmul discret $i$ din oricare $P$. Schiță: selectăm primele prime $r_j$ pana cand $n<\prod r_j$, și pentru fiecare $j$ găsim $i\bmod r_j$ prin solicitarea GCD-ului de $(P+k\,G,r_j\,G)$ care este fie $G$ sau $r_j\,G$, în cazul ulterior dezvăluind că $i+k\equiv0\pmod{r_j}$. Apoi găsim $i$ de teorema chineză a restului. Optimizările sunt posibile pentru a grupa un număr considerabil de interogări într-una singură. De exemplu. depune $(P+k\,G,30\,G)$ și testează dacă rezultatul este $G$, $2\,G$, $3\,G$, $5\,G$, $6\,G$, $10\,G$, $15\,G$ sau $30\,G$. Reduceri suplimentare sunt posibile prin calcularea logaritmului discret al ieșirii oracolului folosind variante Baby-Step/Giant-Step.
Nu cunosc nicio aplicație, în criptografie sau altfel.
