Prendiamo due numeri primi p e q molto grandi e moltiplichiamoli fra loro
\[ n = p q\]
Visto che i due fattori sono numeri primi avremo che il valore della funzione \(\phi\) di Eulero è:
\[\phi(n)=(p-1)(q-1)\]
La sicurezza di questo sistema risiede nel fatto che non sono noti algoritmi efficienti per fattorizzare un numero molto grande di questo tipo.
Ne scorciatoie per calcolare il valore della funzione phi se non si può fattorizzare l'argomento.
Scegliamo un valore e tale che: \(e<\phi(n)\) e che sia coprimo con \(\phi(n)\)
Significa allora che \(mcd(e,\phi(n))=1\)
Risulta possibile mediante l'algoritmo di Euclide esteso, calcolare l'inverso moltiplicativo di e modulo \(\phi(n)\)
ossia un numero d tale che:
\[de \equiv 1 mod_{\phi(n)}\]
La chiave pubblica nell'algoritmo RSA è costituita dalla coppia di valori (e,n)
La chiave privata dalla coppia di valori (d,n)
Per crittografare un valore x si calcola semplicemente il valore:
\[c=x^{e}mod_{n}\]
Pe riottenere il valore in chiaro x avendo ricevuto il valore c si applica la chiave privata:
\[c^{d} mod_{n} = x^{e{}^{d}} mod_{n} =x^{ed} mod_{n} = x^{1}mod_{n}=x\]
Sappiamo infatti dal teorema di Eulero che quando x e n sono coprimi:
\[x^{\phi(n)} \equiv 1 mod_{n}\]
da come abbiamo calcolato d ossia in modo tale che
\(de \equiv 1 mod_{\phi(n)}\)
possiamo scrivere
\[x^{ed}=x^{1+k\phi(n)}mod_{n}\]
Si applica quindi il teorema di Eulero si giunge alla conclusione mostrata perché
\[ x x^{\phi(n)^{k}} mod_{n} =x \]
(Se invece x non è coprimo con n, la dimostrazione può essere fatta applicando il teorema cinese del resto)
Prova un modello come esempio