[Back] In RSA, we can crack the method if the value of \(M^e\) is less than N (where N is \(p \times q)\):

## RSA Crack with short messages |

## Method

So how does it work? First, it doesn't matter the length of p and q, in fact the larger the better. What we must make sure is the message is short, and e is relatively small.

In the RSA encryption method we calculate our cipher (C) as:

\(C = (M)^e \mod N\)

where N is \(p \times q\) (known as the modulus).

But if (M^e) is less than (N), we turn to the John Napier for the answer:

\(C = M^e\)

or:

\(M^e = C\)

So can take the log of each side:

\(\log(M^e) = \log (C)\)

and with the power of logs where \(log(a^b)\) is \(b \times log(a)\):

\(e \times \log (M) = \log (C) \\ log (M) = \log (C)/e \\ M = Invlog (\log(C)/e)\)

Note that e is not the natural log in this case, but is the encryption key (e).

To make it easy we can use Base 10 for the logs (as it's on her calculator).

So lets take an example. If we select p=14222331744261730109 and q=6549179332223292769, N is 93144601115542176265237708764769281821. Next we select a message of 65, and e as 7. We can calculate the cipher as:

\(Cipher = (Message)^e \mod N \\ Cipher = 65^7 \mod 93144601115542176265237708764769281821 \\ Cipher = 4,902,227,890,625 \)

Now we will crack it:

\(Message= 10^(log(Cipher)/e) \\ Message= 10^{log(4,902,227,890,625)/7)}\)

which is:

\(Message = 10^{1.813}\)

which is 65!!!!!!

## Code

An outline of the code used is:

import math import sys p=14222331744261730109 q=6549179332223292769 message=5 e=7 N=p*q Cipher=(message**e) % N print 'Message=',message print 'N=',N print 'e=',e print 'Cipher=',Cipher print '==============' Message = 10**(math.log10(Cipher)/e) print 'Message is:',int(round(Message)), ' Calculated from log10(Cipher/e)' if ((message**e) > N): print 'Method will not work as M^e is larger than N'