Preambul
O parte a securității ECDSA depinde de securitatea logaritmului discret al curbei eliptice utilizate (numiți-o $E$). Curbele eliptice formează un grup algebric aditiv de ordine $n$. Dacă grupul format din curba utilizată este un grup generic, atunci cel mai bun atac clasic este $\mathcal{O}(\sqrt{2^n})$ - Rho al lui Pollard.
ECDSA
Cheia privată $k$ se calculează ca un întreg aleatoriu în interval $[1,n-1]$ și ținut secret tot timpul. Rețineți că cheia privată $k$ este un număr întreg, nu un punct pe curbă $E$.
Cheia publică $P$, pe de altă parte, se calculează ca punct $p = [k]G$ Unde $G$ este punctul de bază al curbei definite în standarde și operație $[k]G$ se numește înmulțire scalară definită ca;
$$[k]G : = \underbrace{G + G + \cdots + G}_{k ori}$$
Acest lucru nu trebuie confundat cu înmulțirea, nu asta este ceea ce scriem pentru a simplifica $k$-ori adăugiri.
The $[k]P$ poate fi calculat cel puțin cu algoritmul dublu și adăugare pentru a fixa calculul $\mathcal{O}(\log k)$-timp.
Punctele
Acum, după cum putem vedea, chiar și $k=0$ nu este o problemă în ECDSA, deoarece nu este o valoare validă pentru $k$.
Dacă jurnalul discret este ușor
Dacă jurnalul discret este ușor pe această curbă, aceasta este o constatare $k$ dat $[k]G$, atunci fiecare valoare este ușor de obținut.
Dacă curba are ușă în spate cu un alt punct de bază $H$, adică cineva poate rezolva logaritmul discret la bază $H$ pe grupul de curbe. Apoi pot folosi acest lucru pentru a rezolva Dlog-ul de pe bază $G$ foarte usor;
- Ei calculează $G = [t]H$ pentru $t \în [1,n-1]$ doar o data
- Ei rezolvă $P =[k\cdot a]G$ până la bază $H$ pentru $a \in [0,n-1]$. O singura data $ka$ se găsește $k$ poate fi calculat ca $k = a \cdot k \cdot a^{-1}$ din moment ce știm $a$ și $a^{-1} \cdot a = 1 \bmod n$.
Dacă jurnalul discret nu este ușor
În acest caz, se pot calcula unele dintre ele până la puterea lor maximă. Să presupunem că poți folosi supercomputerul Summit și că ai puterea de a calcula $2^{70}$ dublați și adăugați pentru un număr dat $t$. Ei calculează și stabilesc un tabel hash pentru a interoga rapid existența jurnalului discret în interval $[1,2^{70}]$. Se rulează într-un an, iar stocarea necesară este $2^{70}*256*3$-biți (~147574 Petabyte). Ei bine, stocarea este una dintre probleme, iar cealaltă este ca tabelul de hash să nu fie $\mathcal{O}(1)$ mai mult. Să presupunem că ați rezolvat această problemă, atunci care este probabilitatea ca să găsiți o anumită cheie privată din cheia publică. Valoarea exactă depinde de grupul de curbe, presupunem că se utilizează un grup de curbe de dimensiune $2^{256}$ pentru a fi în siguranță împotriva atacurilor standard Dlog. Probabilitatea de lovire este $$\frac{2^{70}}{2^{256}} = \frac{1}{2^{186}}.$$ Acest lucru are chiar o probabilitate mult mai mică decât $\dfrac{1}{100}$, așa că spunem că nu se va întâmpla!
În loc de alegeri aleatorii secvențiale ale $t$Schimbați rezultatul, NU!
Nota speciala 1:0x0000...0000 este codificarea obișnuită a $\mathcal{O}(n)$ de cand $(0,0)$ nu este pe curbă. Aceasta nu este acceptată ca cheie publică validă în SEC 1 Ver. 2.0 secțiunea 3.2.2.1.
Nota speciala 2: Unele curbe eliptice sunt curbe prime, ceea ce înseamnă că grupul pe care l-au format are ordine primă. În acest caz, fiecare element este un generator, cu excepția elementului de identitate. Dacă ordinea nu este primă, ca în Curba25519, atunci avem cofactorul $h = \#E(K)/n$ Unde $n$ este cel mai mare prim care împarte ordinul curbei. Dacă se folosește întregul grup, este ușor de observat elementele mici ale comenzii, pur și simplu verificați $[o]P = \mathcal{O}$ sau nu, unde $o$ este mica comanda. Pentru Curve25519, $o$ valorile sunt $2,4,$ și $8$. Aceasta nu este o problemă de securitate de atunci utilizatorii legitimi aleg întotdeauna $k \equiv 0 \pmod 8$.
