|RSA| Este normal ca $\phi(n)$ să funcționeze ca modul RSA?

Așa că exersam lejer RSA pe hârtie pentru un examen, am făcut tot procesul pe care l-am scris mai jos, iar când am încercat criptarea și decriptarea m-am distras și în loc să fac $m^e \mod n$

am facut $m^e \mod {\phi(n)}$ și atât decriptarea, cât și criptarea au funcționat. Este normal?

Iată numerele: $$ p = 11\ q = 23\ n = (p\cdot q) = (7 \cdot 23) = 253\ \phi(n) = (p-1) \cdot (q-1) = 220\ e = 7\ d = 63 \ $$ Am obținut d folosind algoritmul euclidian extins: $$ gcd(220, 7)\ 220 = 7 * 31 + 3 \ 7 = 3 * 2 + 1 \ $$ $$ 1 = 7 + 3(-2)\\ 1 = 7 + (220 + 7(-31))(-2)\\ 1 = 7(63) + 220(-2)\\ $$

În general, o pereche de exponenți de decriptare RSA calculati în acest fel pentru un modul $N$ va funcționa și pentru orice modul $M$ care satisface $\lambda(M)|\phi(N)$ Unde $\lambda$ este Funcția Carmichael.

În exemplul tău $M=\phi(N)=220$ și $\lambda(M)=\mathrm{lcm}(\phi(4),\phi(5),\phi(11))=\mathrm{lcm}(2,4,10)=20$ chiar se împarte $\phi(N)=220$. Acest set de circumstanțe a fost ajutat de faptul că 11 se împart $\phi(23)$. În general, dacă modulul RSA $pq$ are $p|q-1$ atunci $\phi(p)|\phi(\phi(q))$ și asta ajută foarte mult.

Acest tip de fenomen este mai puțin probabil să se întâmple când $p-1$ și $q-1$ au divizori primi mari. Cu toate acestea, ar trebui să fie posibil să se construiască alte exemple prin alegere $p$ și $q$ Unde $p-1$ și $q-1$ nu sunt divizibile cu numere prime mari, dar sunt divizibile cu toate puterile prime mici.