In the previous post, we learned how to decrypt RSA by getting the factors of the big number N and computing for the inverse of e (the encoding number) modulo N. There is also another way to decrypt an RSA encrypted message. This is when you are able to get the period of the ciphertext. If c is the ciphertext, the period r is the smallest integer that satisfies:
Once we get the period, we compute for , the inverse of e modulo r:
The inverse can then be used to decrypt the ciphertext:
In our previous example, we encrypted the message
THIS IS A SECRET MESSAGE
using public key p=53, q=59, N=pq=3127 and e=7 and private key d=431. The “plain text” is
1907 0818 2608 1826 0026 1804 0217 0419 2612 0418 1800 0604
and the ciphertext is:
0794 1832 1403 2474 1231 1453 0268 2223 0678 0540 0773 1095
Let’s compute the period of the first block of our ciphertext:
Using the python script below, we can compute the period
for r in range(1,100): p=pow(794,r,N) if p == 1: print "%d %d" % (r,p)
The result of running the above program gives r=58. We can then compute using the following equation:
The above equation is satisfied when m=3 and . Using this value of , we can compute for
which gives us the original message!
However, unlike using the private key, you need to compute the period r and for every block of the ciphertext (unless the ciphertext is composed of only one block). However, that should not stop a cracker from deciphering all the blocks.