Puncte:0

Eșantionarea aleatorie versus aleatoritatea incrementală în protocoalele criptografice

drapel do

Ca exemplu la întrebarea mea, postez algoritmul de semnare ECDSA pentru referință (de la wikipedia) pentru a semna un mesaj $m$:

  1. calculati $e = H ( m )$.
  2. Selectați un număr întreg aleatoriu $k \in [ 1 , n â 1 ] $
  3. Calculați punctul curbei $( x_1 , y_1 ) = k à G $
  4. calculati $r = x_1$ mod $n$. Dacă $r = 0$ , reveniți la pasul 2.
  5. calculati $s = k ^{â 1} ( z + r d_A )$ mod $n$. Dacă $s = 0$, reveniți la pasul 2.
  6. Semnătura este perechea $( r , s )$

Întrebarea mea este următoarea. Când pașii 4 sau 5 eșuează, de ex. $r=0$ sau $s=0$ algoritmul trebuie să facă bucla înapoi și să eșantioneze o nouă aleatorie $k$ (deși probabilitatea pentru asta este mică ca ordinul $n$ a grupului $G$ este foarte mare). Dar, în acest caz, de ce algoritmul trebuie să facă o nouă eșantionare aleatorie? Nu ar fi mai eficient să crești $k$ in schimb? Am adus această întrebare pentru ECDSA ca exemplu, dar acest lucru se aplică și altor protocoale criptografice, văd reeșantionarea aleatorie peste tot în loc să se incrementeze.Și din punct de vedere al securității, creșterea aleatoriei nu ar trebui să facă diferența.

Puncte:3
drapel my

Și din punct de vedere al securității, creșterea aleatoriei nu ar trebui să facă diferența.

Există două motive pentru a „întoarce” mai degrabă decât să facem o logică specială.

Primul motiv este reducerea cantității de coduri speciale „greu de testat”. Orice modalitate de „incrementare”. $k$' ar implica cod care este extrem de rar rulat (și pentru care ar fi greu de conceput teste unitare). Orice astfel de cod greu de atins este o locație fertilă pentru erori de codare nedetectate și, prin urmare, ar trebui evitat dacă este posibil. În schimb, întoarcerea și reluarea în esență a aceleiași proceduri este considerabil mai puțin predispusă la erori.

Celălalt motiv este că reutilizarea datelor care au fost considerate „inacceptabile” se poate scurge.

De exemplu, să presupunem că adversarul este capabil să detecteze când are loc o astfel de creștere (de exemplu, prin monitorizarea atentă a timpului necesar pentru a genera o astfel de semnătură), și de fapt se întâmplă deoarece $s=0$. Dacă da, tocmai am scăpat cheia privată.

Iată cum se întâmplă asta: în prima iterație, calculăm $s = k^{-1}( z + rd_A )$ și găsiți că este 0. Deci, noi așa $r' = ((k+1)G)_x$ în schimb și scoateți asta (și continuați să calculați $s'$, pe care acest atac nu îl folosește).

Ceea ce poate face atacatorul este să reconstruiască punctul $(k+1)G$ din coordonata x pe care tocmai i-am dat-o (de fapt, este unul din cele două puncte; asta înseamnă doar că le încearcă pe ambele); care îi permite apoi să recalculeze $kG$, și astfel originalul $r$

Acum, el știe asta $k^{-1}(z + rd_A) = 0$, acum $k^{-1} \ne 0$ (inversurile nu sunt niciodată zero), și așa $d_A = -r^{-1}z$; el stie $z$ (din mesajul care a fost semnat) și $r$, care îi oferă cheia privată $d_A$.

Acum, dacă selectăm un complet aleatoriu $k$ de fiecare dată, nu trebuie să ne îngrijorăm cu privire la atacuri neevidente ca acesta.

Acum, în practică, asta $s=0$ în esență, condiția nu se întâmplă niciodată (se întâmplă cu aceeași probabilitate ca o presupunere aleatorie a cheii private să fie corectă), așa că s-ar putea părea că nu trebuie să ne facem griji. Aș avea în continuare încredere în metoda mai puțin predispusă la erori și mai sigură, chiar dacă durează mai mult timp (și dacă nu se întâmplă aproape niciodată, timpul necesar este de obicei irelevant).

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.