This is an example to show how R.S.A algorithm worls:
1) given p=11, q=13, m=2 2) n=p*q=11*13=143 3) phi(n)=(p-1)*(q-1)=10*12=120 4) choose e=11 ,a prime number 5)d=e^-1 mod phi(n)
=11^-1 mod 120
Euclid's Algorithm to find GCD
Q | A1 A2 A3 | B1 B2 B3 | B1=A1-QA1, B2=A2-QA2, B3=A3-QA3
A3/B3=Q= - | 1 0 120 | 0 1 11 |
120/11= 10 | 0 1 11 | 1 -1 10 |
11/10= 1 | 1 -1 10 | 0 11 1 |
d=23
6) c=(m^e)mod n
= (2^11)mod 143 = (2^1 mod 143)(2^2 mod 143)(2^4 mod 143)(2^4 mod 143) = (2*4*16*16)mod 143 c = 46
7) m=(c^d) mod n
= (46^11) mod 143 = (46^1 mod 143)(46^2 mod 143)(46^4 mod 143)(46^4 mod 143) =(46*114*126*126) mod 143 m=2
8) hence m=2 in original message.
By Kailash Gajara