Algoritmo rsa - teoria

[pmic]

Ciao a tutti,
sto studiando l'algoritmo rsa attraverso queste slide allegate qui:

http://speedy.sh/KRkah/Crittografia-asimmetrica.pdf

A pagina 67 mi trovo in difficoltà in quanto non riesco a capire (dimostrare) perchè vale la relazione:
\(\displaystyle e*d=\phi(n)+1 \)

Partendo da queste assunzioni:
\(\displaystyle m^(k\phi(n)+1) = m mod(n) \)
\(\displaystyle p*q=n \)
con n,p primi e m Potreste aiutarmi a capire il passaggio? Grazie.

[pmic]

Bene penso di aver capito, posto qui la soluzione sperando sia corretta come spiegazione:

Esempio:
\(\displaystyle p=11 \) e \(\displaystyle q=5 \)
\(\displaystyle \phi(55)=40 \)
scelgo \(\displaystyle e=7 \) come chiave pubblica per l'encryption
ora devo verificare \(\displaystyle e*d=1 mod \phi(n) \) quindi:
\(\displaystyle e*(e^-1)=1 mod \phi(n) \) dato che la chiave privata deve essere l'inverso in modulo
ottengo \(\displaystyle d=23 \) in quanto
\(\displaystyle 23*7=161= 1mod40 \) ovvero \(\displaystyle 1+k*\phi(n) \) con k=4