[Back] RSA can be cracked if the intruder records enough cipher text messages which use the same e value. We will take three N values (modulus) and a message, and create three cipher messages. These will be used to crack RSA:
RSA Crack with Chinese Remainder Theorem
The following shows values for a message of 1500000 and p1=4519, q1=4523, p2=4547, q2=4549, p3=4561, q3=4567:
N1= 20439437 N2= 20684303 N3= 20830087 Message= 1500000 e= 3 Cipher1= 6509102 Cipher2= 9683741 Cipher3= 3214286 =======Equations to solve======= M^e mod 20439437=6509102 M^e mod 20684303=9683741 M^e mod 20830087=3214286 ======Chinese Remainder Theorm Calc======== Result (M^e) is: 3375000000000000000 Calculated value of m is 1500000 Using 10^(log10(M^e)/e)
Eve used the Chinese remainer theorem (CRT) to solve the value of M^e, and simply used logs after that. For this she needed three cipher values which use the same e value and a different N value (which is similar to passing three public key values for Bob to encrypt). This gives:
\(C_1 = M^e \mod N_1 \\ C_2 = M^e \mod N_2 \\ C_3 = M^e \mod N_3 \)
which we can solve for \(M^e\) with Chinese remainer theorem (CRT).
With p1=2, q1=3 (N1=6) p2=5, q2=7 (N2=35), and p3=11, q3=13 (N3=143), and with e=3, with a message value of 5, we get:
\(5 = M^e mod (6) \\ 20= M^e mod (35) \\ 125= M^e mod (143) \)
Let solve this with Chinese remainer theorem
This gives a value of 125 for M^e.
Now, she doesn't have to worry about mod operations any more, and she has:
\(M^3 = 125\)
which we can solve by logs:
\(log (M^3) = log(125) \\ 3 \times log (M) = log(125) \\ log (M) = log(125)/3 \\ M = inv Log (log(125)/3) \)
which gives M =5
... and we have cracked RSA.
An outline of the code used is:
import sys import fractions import math p1=2 q1=3 p2=5 q2=7 p3=11 q3=13 nval= aval= message=5 e=3 N1 = p1*q1 N2 = p2*q2 N3 = p3*q3 def chinese_remainder(n, a): sum = 0 prod = reduce(lambda a, b: a*b, n) for n_i, a_i in zip(n, a): p = prod / n_i sum += a_i * mul_inv(p, n_i) * p return sum % prod def mul_inv(a, b): b0 = b x0, x1 = 0, 1 if b == 1: return 1 while a > 1: try: q = a / b a, b = b, a%b x0, x1 = x1 - q * x0, x0 except: print "Bad N values (check no common factors in N vals)" return 0 if x1 < 0: x1 += b0 return x1 def GCD(a,b): """ The Euclidean Algorithm """ a = abs(a) b = abs(b) while a: a, b = b%a, a return b def GCD_List(list): """ Finds the GCD of numbers in a list. Input: List of numbers you want to find the GCD of E.g. [8, 24, 12] Returns: GCD of all numbers """ return reduce(GCD, list) nval.append(N1) nval.append(N2) nval.append(N3) C1 = (message)**e % (N1) C2 = (message)**e % (N2) C3 = (message)**e % (N3) aval.append(C1) aval.append(C2) aval.append(C3) n = nval a = aval g = GCD_List(n) print "GCD of N values: "+ str(g) print "N1=",N1, print "N2=",N2, print "N3=",N3 print "Cipher1=",C1, print "Cipher2=",C2, print "Cipher3=",C3 print "Message=",message, print "e=",e print "==============" if (g>1): print "Cannot compute - check your N values for a common factor" else: result = chinese_remainder(n, a) count=0 for str1 in nval: print "x mod "+str(str1)+"="+str(aval[count]) count=count+1 print "==============" print "Result (x) is: ",result,"\n" m = 10**(math.log10(result)/e) print 'Calculated value of m is ',int(round(m))