înregistrare Logare
Puncte:2
James avatar Crypto

Criptografie cu curbă eliptică de cracare

drapel br
James

Sunt destul de nou în studiul criptografiei cu curbe eliptice și, ca atare, s-ar putea să întreb ceva cu o soluție banală, dar nu pot găsi cu ușurință o astfel de soluție online. Înțeleg eu despre ECC că puteți genera o cheie privată (unele numere întregi $k$), un punct de plecare pe curbă ($G$), și o ecuație de curbă și apoi generează o cheie publică prin găsire $kG$. Înțeleg atunci că computerul dvs. ar efectua oricât de multe operațiuni sunt necesare pentru a găsi $kG$ (dacă $k$ avea 16 ani, atunci ar fi patru operații).

Cu aceste date punctul de plecare $G$, ecuația curbei și cheia publică este făcută publică. Ceea ce mă întreb este de ce un atacator nu poate încerca să afle care este cheia privată $k$ pur și simplu, luați punctul de plecare și efectuați operațiuni până ajung la cheia publică și, ca atare, știu ce $k$ este? Se bazează pe faptul că expeditorul are nevoie doar de 4 operații pentru a calcula $kG$ întrucât atacatorul ar avea nevoie de 16 operațiuni (pentru exemplul dat)?

1127
1 + 7
drapel ca
MaiaVictor
Trebuie să ghiciți o cheie privată înainte de a începe operațiunile. Dacă vorbim despre chei private pe 256 de biți, există chei `2^256` de încercat. Veți ajunge la cheia publică a țintei doar dacă ați ghicit cheia privată corectă. Asta înseamnă că, dacă alegeți o cheie privată aleatorie și efectuați operațiuni în speranța de a ajunge la cheia publică a țintei, există doar `0,0000000000...(+66 zerouri)...8` șanse de succes la fiecare încercare.
1
Răspunde
James avatar
drapel br
James
Dar dacă computerul utilizatorului, de exemplu, a luat 10 calcule pentru a calcula o cheie publică (un exemplu simplist), computerul atacatorului ar trebui doar să pornească de la $G$ și să efectueze aproximativ 1024 de calcule pentru a ajunge la punctul de $kG$. Pot să văd că aceasta este potențial o diferență destul de mare, dar se pare că un supercomputer ar putea trece printr-un exemplu mai mare într-o perioadă finită de timp (săptămâni sau cam asa ceva).
0
Răspunde
dave_thompson_085 avatar
drapel cn
dave_thompson_085
Pentru dimensiunile considerate în prezent sigure (256 sau 255 biți mai sus) acest „atac” necesită mai multă energie decât există în univers. Trebuie să controlezi un număr imens -- trilioane de trilioane -- de alte universuri, ceea ce înseamnă că trebuie să fii un zeu, iar profilul tău nu te identifică ca zeu. Consultați https://crypto.stackexchange.com/questions/58373/how-to-calculate-a-private-key-from-public-key-on-elliptic-curve și multe altele legate acolo.
1
Răspunde
fgrieu avatar
drapel ng
fgrieu
Vezi parabola [grâu și tablă de șah](https://en.wikipedia.org/wiki/Wheat_and_chessboard_problem), doar cu o tablă de șah mai mare când vine vorba de curbele eliptice utilizate efectiv (unde $k$ poate dura $n\approx2^{ 256}valori $). De altfel, „luați punctul de plecare și efectuați operațiuni până ajung la cheia publică” este departe de cea mai bună strategie: dacă există $n$ valori posibile de $k$, este nevoie de $\Theta(n)$ pași, când există sunt strategii care necesită doar $\Theta(\sqrt n)$ pași.
3
Răspunde
drapel jp
user253751
@James Bine, ce se întâmplă dacă computerul utilizatorului a luat 256 de calcule pentru a calcula cheia publică? Câte calcule trebuie să facă computerul atacatorului?
0
Răspunde
PrincePolka avatar
drapel cn
PrincePolka
„Se bazează pe faptul că expeditorul are nevoie doar de 4 operațiuni pentru a calcula kG, în timp ce atacatorul ar avea nevoie de 16 operațiuni (pentru exemplul dat)?” da
1
Răspunde
James avatar
drapel br
James
Vă mulțumesc pentru toate exemplele și răspunsurile. Înțeleg cât de repede acest atac simplist devine acum neviabil din punct de vedere computațional.
0
Răspunde
Puncte:5
jjj avatar Crypto
drapel cn
jjj

A calcula $kG$ ai nevoie $O(log(k))$ operațiuni. (Pentru fiecare bit, dublați rezultatul și adăugați suplimentar $G$ dacă bit este $1$). După cum ați menționat într-un comentariu pentru aproximativ $k=1024$ ai avea nevoie ca $10$ operatii de calculat $kG$. Dar acest exemplu este mult prea mic pentru uz practic, iar efectul exponențial nu se manifestă încă. În mod normal, când curba are ordine în jur $2^n$, $k$ ar fi de o amploare similară cu $2^n$.

Deci pentru curbe cu ordine $2^{256}$ai nevoie în jur $log(2^{256})=256$ operatii de calculat $kG$ dar $2^{256}$ să-l atace. Există doar o problemă cu curbele absurd de mici, cu ordin de poate până la câteva miliarde sau trilioane (ca în exemplul dvs.).

0 + 3
AAA avatar
drapel nl
AAA
Puteți face mai bine decât $2^{256}$. Puteți folosi baby-step giant-step pentru a recupera $k$ în aproximativ $2^{128}$ timp. Cu toate acestea, ideea rămâne: este nevoie de timp polinom pentru a calcula $kG$, dar cele mai cunoscute atacuri necesită timp exponențial pentru a recupera $k$.
3
Răspunde
James avatar
drapel br
James
Dacă putem spune că, de exemplu, un computer poate calcula 80.000.000.000 de operații pe secundă (optzeci de computere care efectuează o operație la fiecare nano-secundă), ceea ce reprezintă aproximativ 2$^{36}$ operațiuni pe secundă, iar cele mai rapide atacuri pot găsi cheia în operațiunile de $2^{n/2}$ unde $n$ este dimensiunea cheii, nu ar fi suficientă o dimensiune a cheii de 138 pentru a face, în esență, orice atac neviabil (durand aproximativ 3200 de ani pentru a calcula)?
0
Răspunde
James avatar
drapel br
James
Ca o alternativă suplimentară, dacă există atât de multe îngrijorări cu privire la faptul că Quantum Computing poate ataca criptarea unor chei de dimensiuni mai mici, nu ar fi suficient de posibil să se creeze un Criptosistem cu curbă eliptică cu chei de dimensiuni mari fără a dura prea mult timp pentru a calcula (1024 operațiunile nu pare că ar dura prea mult timp pentru ca un computer modern să efectueze, chiar dacă fiecare operație a durat 1.000.000 de nanosecunde)?
0
Răspunde
drapel ag
Gabriel Garrett
@AAA Există vreo implementare cunoscută public a pasului gigant pentru criptarea curbei eliptice?
0
Răspunde
drapel romania
SEF 777
întrebarea această in alte limbi:

Postează un răspuns

Majoritatea oamenilor nu înțeleg că a pune multe întrebări deblochează învățarea și îmbunătățește legătura interpersonală. În studiile lui Alison, de exemplu, deși oamenii își puteau aminti cu exactitate câte întrebări au fost puse în conversațiile lor, ei nu au intuit legătura dintre întrebări și apreciere. În patru studii, în care participanții au fost implicați în conversații ei înșiși sau au citit transcrieri ale conversațiilor altora, oamenii au avut tendința să nu realizeze că întrebarea ar influența – sau ar fi influențat – nivelul de prietenie dintre conversatori.