înregistrare Logare
Puncte:1
Johny Dow avatar Crypto

De ce funcționează trucul lui Shamir pentru RSA

drapel fr
Johny Dow

Am citit că trucul lui Shamir poate proteja RSA cu CRT împotriva atacurilor de eroare. Cu toate acestea, nu îmi este clar de ce următoarele ecuații $$ s_{p}^{*}=m^{d \bmod \varphi(p \cdot t)} \bmod p \cdot t \ s_{q}^{*}=m^{d \bmod \varphi(q \cdot t)} \bmod q \cdot t $$ implică faptul că: $$ s_{p}^{*} = s_{q}^{*} \bmod t $$

172
0 + 0
fgrieu avatar
drapel ng
fgrieu
Acesta nu este trucul lui Shamir așa cum îl știu, care calculează $x^a\,y^b\bmod n$ la aproximativ 60% din costul calculării lui ca $(x^a\bmod n)\,y^b\bmod n$. OTOH Shamir are cu siguranță multe trucuri. De asemenea, în timp ce ecuația menționată este valabilă, aceasta nu este contramăsura standard împotriva atacurilor de eroare, care este să verificăm $s^e\bmod n=m$.
2
Răspunde
Johny Dow avatar
drapel fr
Johny Dow
@fgrieu Este numit trucul lui Shamir în [Topics in Cryptology â CT-RSA 2009](https://link.springer.com/book/10.1007/978-3-642-00862-7) și de aici am ajuns numele de la.
1
Răspunde
fgrieu avatar
drapel ng
fgrieu
Da, acum văd că este în Matthieu Rivain, [Securing RSA against Fault Analysis by Exponențierea lanțului de adăugare dublă](https://eprint.iacr.org/2009/165.pdf) (versiune actualizată), inițial [în lucrările CT-RSA 2009](https://doi.org/10.1007/978- 3-642-00862-7_31). Totuși, [această referință](https://doi.org/10.1007/978-1-4419-5906-5_1157) face din _Shamir's Trick_ sinonim cu [_Simultaneous Exponentiation_](https://doi.org/10.1007/978-1 -4419-5906-5_45).
1
Răspunde
Puncte:2
Daniel S avatar Crypto
drapel ru
Daniel S

Avem $\varphi(t)|\varphi(pt)$ și $\varphi(t)|\varphi(qt)$ astfel încât dacă $d_1$ și $d_2$ sunt exponenții pentru $s_p^*$ și $s_q^*$ atunci $d=d_1+k_1\varphi(t)$ și $d=d_2+k_2\varphi(t)$ pentru unele numere întregi $k_1$ și $k_2$. Rezultă că $d_1=d_2+(k_2-k_1)\varphi(t)$ și, prin urmare $$d_1\equiv d_2\pmod{\varphi(t)}.$$

Rezultă că $m^{d_1}\equiv m^{d_2}\pmod t$ prin teorema lui Euler.

0 + 0
Johny Dow avatar
drapel fr
Johny Dow
Tocmai mi-am dat seama că nu înțeleg cu adevărat de ce $d_1\equiv d_2\pmod{\phi(t)}$ ai putea explica asta mai departe? Mulțumesc!
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.