User:Kailashtg

From Wikipedia, the free encyclopedia

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