Cum mă ajută să decriptez cunoașterea factorilor cheii?

Am dat peste algoritmul lui Shor (care rezolvă următoarea problemă: „Dând un număr întreg N, găsiți factorii primi”).

De fapt, algoritmul lui Shor rezolvă problema „dată o funcție periodică $f$, adică dacă $\underbrace{f(f(... f(a))...)}_{k\text{ ori}} = a$, ceea ce este $k$?"

Prin precizarea $f$ în mod inteligent, putem folosi acest lucru pentru a rezolva problema factorizării. Remarc acest lucru deoarece poate fi folosit pentru a rezolva și alte probleme interesante.

În orice caz, ceea ce întrebați cu adevărat este „dacă putem lua în calcul cheia, cum ne ajută asta să spargem RSA”? Rețineți că bazându-vă pe dificultatea factorizării, de ce depinde RSA; alte metode (cum ar fi Diffie-Hellman) sunt la fel de vulnerabile la algoritmul lui Shor, dar folosesc un alt $f$ funcţie.

Ei bine, cu RSA, exponentul public $e$ și exponentul privat $d$ sunt legate de $e \cdot d \equiv 1 \pmod{\text{lcm}(p-1, q-1)}$. Se dovedește că dacă cunoaștem factorii primi $p, q$ și cunoaștem exponentul public $e$ (care este dat în cheia publică), este ușor de calculat exponentul privat $d$; care ne oferă imediat o modalitate de a decripta via $P = C^d \bmod n$.