Este puțin ciudat să spui că „rup RSA”, pentru că, desigur, cunoașterea cheii secrete vă permite să decriptați mesajul - asta este ceea ce ați face în cazul cinstit atunci când vă decriptați propriile mesaje.
El afirmă mai întâi că aceasta este echivalentă cu $k=ed-1$ fiind multiplu al celui mai mic multiplu comun al $p-1$ și $q-1$. De ce #1? Încercarea mea: știu că prin teorema lui Euler, $m^{\varphi(n)}\equiv 1\mod n$ și asta $\varphi(n)=(p-1)(q-1)$ de cand $(m,n)=1$. Mai mult de vreme ce $(m,n)=1$ ne putem împărți ecuația la $m$ și obțineți $m^k\equiv 1\mod n$. Cred că pierd ultimul pas...
Ești pe drumul cel bun. pentru că $m^{\varphi(n)}\equiv 1\pmod n$, atunci acest lucru implică faptul că dacă putem găsi un $d$ astfel încât $ed = r\varphi(n) + 1$ pentru unii $r$, atunci
$$m^{ed}\equiv m^{r\varphi(n) + 1} \equiv (m^{\varphi(n)})^r \cdot m^1 \equiv 1^r \cdot m \ echiv m\pmod n$$
Deci, pentru o anumită cheie de criptare $e$, cheia de decriptare corespunzătoare $d$ este pur și simplu o valoare astfel încât $ed = r\varphi(n) + 1$. In intrebarea ta, $k = r\varphi(n)$.
$k$ va fi chiar pentru că $\varphi(n)$ va fi chiar și în acest caz - $p, q$ sunt ambele numere prime distincte și toate numerele prime, cu excepția lui 2, sunt impare, deci cel puțin unul dintre $(p-1)$, $(q-1)$ trebuie să fie un număr par (și probabil ambele vor fi, deoarece primul $2$ nu ar fi folosit niciodată în RSA.
Daca totusi exista unul $m$ astfel încât $m^{k/2}\not\equiv 1\mod n$, atunci același lucru este valabil pentru cel puțin jumătate din $m$e in $\mathbb Z_n^*$. De ce #2? Încercarea mea: aceasta ar trebui să fie o consecință a faptului că dacă $m_0$ este un astfel de element, apoi dat $m_1\in \mathbb Z_n^*$ produsul $m_0m_1$ este de asemenea astfel încât $$(m_0m_1)^{k/2}=m_0^{k/2}m_1^{k/2}\not\equiv1\mod n, $$ dar nu sunt sigur de ce asta înseamnă că cel puțin jumătate dintre elemente împărtășesc această proprietate.
Luați în considerare un $m_0$ astfel încât $m_0^{k/2} \not\equiv 1 \pmod{n}$. Fiecare putere ciudată $m_0^{2j + 1}$ de $m_0$ va avea aceeași problemă, pentru că
$$(m_0^{2j+1})^{k/2} \equiv (m_0^{k/2})^{2j}\cdot m_0^{k/2} \equiv (m_0^k)^j \cdot m_0^{k/2} \equiv 1 \cdot m_0^{k/2} \not\equiv 1 \pmod{n}$$
deoarece $m_0^k \equiv 1 \pmod{n}$. Deci fiecare putere impară nu funcționează, dar fiecare putere pară funcționează, deci avem 50/50.
atunci nu putem avea $k/2\equiv 0\mod (p-1)$ precum și $k/2\equiv 0\mod (q-1)$. De ce #3? Încercarea mea: aceasta ar trebui să fie pur și simplu pentru că, dacă ambele aceste congruențe sunt valabile, atunci $k/2$ este un multiplu al ambelor $p-1$ și $q-1$ şi deci de $\phi(n)$, și astfel prin teorema lui Euler $m^{k/2}$ ar trebui să fie $1$ $\mod n$ pentru toți $m\in \mathbb Z_n^*$ împotriva ipotezei noastre.
Corect.
Deci, oricare dintre aceste congruențe este valabilă și nu cealaltă (de exemplu, $k/2\equiv 0\mod p-1$ dar $k/2\not\equiv 0\mod q-1$) sau niciunul nu ține. În primul caz, $m^{k/2}$ Este mereu $\equiv 1\mod p$ dar exact $50\%$ a timpului congruent cu $-1$ modulo $q$. De ce #4? Încercarea mea: sunt destul de confuz de acesta. Presupun că $m^{k/2}\equiv 1\mod p$ din nou prin teorema lui Euler, ca $k/2$ este un multiplu de $p-1$, adică un multiplu al $\phi(p)$. Dar nu văd de ce $m^{k/2}$ este congruent cu $-1$ modulo $q$ exact $50\%$ a timpului...
Considera $(m^{k/2})^2 \pmod n$. Aceasta este $m^{k} \equiv 1 \pmod{n}$. Dar pentru că $(m^{k/2}) \equiv 1 \pmod{p}$, atunci $(m^{k/2}) \equiv \pm 1 \pmod{q}$, altfel nu s-ar pătra cu $1$. Argumentul este similar cu cel de mai sus pentru a arăta că obținem fiecare caz în 50% din timp (deoarece acum suntem garantați că nu este congruent cu 1 de fiecare dată).
