[Back] RSA can be cracked if we slightly modify the e key and get the same message ciphered:

## RSA Crack with different e value |

## Presentation

## Method

Bob selects an e of 5 and N of 15 (p=3, q=5), with a message of 7, so the cipher is:

\(C_1 = 7^5 \mod 15 = 7\)

Now we pass Bob a slightly different encryption key (e2=6), and then get him to encrypt the same message:

\(C_2 = 7^6 \mod 15 = 4\)

Now I have done a few simple calculations and created an equation of x.e1 + y.e2 =1, so if I raise C1 and C2 to the power of x and y, respectively, I get:

\((M^{e1})^x + (M^{e2})^y\)

which, thanks to the great magician John Napier, gives:

\((M)^{e1.x} +(M)^{e2.y}\)

which is equal to:

\(M^{e1.x + e2+y}\)

which will equal:

\(M^1\)

which is M ... yippeee!!!!

So all I have to is to find the values of x and y which make this true:

\(x.e1 + y.e2\)

\(5x + 6y=1\)

which is simple, as x=-1, and y=1.

So \(C_2=M^{e1+1}\) and \(C_1=M^{e1}\)

If we divide the two we get:

\(\frac{C_2}{C_1} = \frac{M^{e1+1} (\mod N)}{M^{e1} (\mod N)} \)

\((C_1)^{-1} . (C_2)^1 = M (\mod N)\)

\((7)^{-1} . (4) = M (\mod 15)\)

\(4 = 7 \times M (\mod 15)\)

and thus M=7 works (as 7 x 7 mod 15 equals 4).

So the crack is that we solve for:

\(C_2 = C_1 \times M (\mod N)\)

## Code

Some sample code is:

e1 = 5 n = 7*11 m= 7 def calcM(c1,c2,n): m=0 r=[] while True: m = m + 1 res = (c1 * m) % n if (res==c2): r.append(m) if (m>60): return(r) return r e2 = e1 + 1 c1 = (m**e1) % n c2 = (m**e2) % n print 'M is\t\t',m print 'e1 is\t\t',e1 print 'e2 is\t\t',e2 print 'N is\t\t',n print 'Cipher 1 is\t',c1 print 'Cipher 2 is\t',c2 print '\n==== Eve then cracks by solving C2 = C1 x M (mod N)===' crack = calcM(c1,c2,n) print "Eve calculates message as ",crack print '\n=========' if (m in crack): print 'Message has been cracked' else: print 'Message has not been cracked'