Aveți nevoie de ajutor pentru a înțelege atacul cu modulul comun RSA pentru a obține cheia privată

Învăț despre atacul cu modulul comun și am aflat că atacurile cu modulul public pot afla cheia privată. Să presupunem că există 2 utilizatori cu chei publice și private $(e_1, d_1)$ și $(e_2, d_2)$. Scenariul este atacatorul are cheile sale publice și private $(e_2, d_2)$ și cheia publică a victimei $e_1$ Iată pașii pentru a obține cheia secretă:

1. $t= e_2\cdot d_2-1$
2. Atacatorul folosește algoritmul euclidian extins pentru a găsi $f=\gcd(t,e_1)$ ale căror perechi de numere $(r,s)$ satisface ecuația $r\cdot t + s\cdot e_1 = f$
3. Dacă $f=1$ a stabilit $d_1' = s$ și returnează cheia privată $d_1'$
4. Dacă $f\neq 1$ a stabilit $t=\frac t s$ și reveniți la pasul 2

Am un exemplu cu $d_1=17, M = 25$ sunt două valori pe care ar trebui să le găsim. n = 253 (modul comun) $e_1 = 13$ (cheia publică a victimei) $e_2 = 23$ (cheia publică a atacatorului) $d_2 = 67$ (cheia privată a atacatorului) $C = 27$ (text cifrat). Atacatorul va găsi $d_1'$ dupa pasii:

1. $t= e_2\cdot d_2-1 = 23\cdot 67 = 1540$
2. $\gcd(t,e_1) = 1 \implica r = -2, s = 237$
3. Asa de $d_1' = s = 237$
4. Verifica $M = C^{d_1} \bmod n = 27^{237} \bmod 253 = 25$

Problema este că nu înțeleg de ce cu astfel de pași vom găsi cheia secretă. Imi poate explica cineva pls?

Vom folosi foarte mult următorul fapt: pentru un modul public fix $n$ produs de numere prime distincte, o pereche de numere întregi $(e,d)$ formează o pereche potrivită de exponenți RSA [adică cu $c\mapsto c^d\bmod n\,=\,m$ capabil să descifreze în mod fiabil orice text simplu $m$ în $[0,n)$ cifrat per $m\mapsto m^e\bmod n\,=\,c$ ] dacă și numai dacă$$e\cdot d\equiv1\pmod{\lambda(n)}$$Unde $\lambda$ este Funcția Carmichael. Acest lucru poate fi demonstrat că rezultă din definiția lui $\lambda(n)$ ca cel mai mic număr întreg strict pozitiv $y$ astfel încât $m^y\equiv 1\pmod n$ pentru toți $m\in\mathbb Z^*$. Acest lucru este valabil indiferent de semnul de $d$.

Rezultă că $t$ al pasului 1 al algoritmului întrebării este astfel încât există $k\in \mathbb Z$ cu $t=k\cdot\lambda(n)$.

Dacă algoritmul găsește $f=1$ la prima execuție a pasului 2, se menține astfel $r\cdot k\cdot\lambda(n)+s\cdot e_1=1$, prin urmare $s\cdot e_1=1+(-r\cdot k)\cdot \lambda(n)$, deci când algoritmul se setează $d'_1=s$ la pasul 3 se menține $e_1\cdot d'_1\equiv1\pmod{\lambda(n)}$. Aplicând primul fapt, $(e_1,d'_1)$ este o pereche potrivită de exponenți RSA pentru modulul public $n$. Dacă vrem $d'_1$ să fim non-negativi putem face $d'_1=s\bmod t$, care prin definiție este în interval $[0,t)$ și de asemenea așa încât $e_1\cdot d'_1\equiv1\pmod{\lambda(n)}$.

Lucrurile merg prost când $f\ne1$ la prima executare a pasului 2. Adesea $s$ nu se va împărți $t$ în pasul 4, împiedicând aplicarea algoritmului așa cum este. Exemplu: $p=13$, $q=19$, $n=247$, $\varphi(n)=216$, $\lambda(n)=36$, $e_1=91$, $e_2=25$, $d_1=19$, $d_2=121$, $t=3024$, $r=-4$, $s=133$, $f=7$, $t/s=432/19\nu\în\mathbb Z$.

Schimbarea $t:=\frac t s$ la $t:=\frac t f$ în pasul 4 asigură divizibilitatea și lasă algoritmul să funcționeze. Argument: $f$ desparte $e_1$, și $\gcd(e_1,\lambda(n))=1$, prin urmare $f$ este coprim cu $\lambda(n)$, astfel reîncepem pașii 2 cu $t$ încă un multiplu de $\lambda(n)$.

Alternativ: dat $(n,e_2,d_2)$ adversarul poate factor $n$ (vedea acest) și din acela obține $\hat{d_1}=e^{-1}\bmod\lambda(n)$ potrivire $(n,e_1)$, de obicei cu $\hat{d_1}$ mai mic/mai rapid decât $d'_1$; sau obțineți o cheie privată funcțională în formularul care permite Funcționare CRT astfel decriptare sau semnătură și mai rapidă.