Chinese Remainder Theory (CRT)CRT allows us to solve for the value of \(x\), if we know \(x = a_1 \pmod{N_1}\), \(x = a_2 \pmod{N_2}\) and \(x = a_3 \pmod{N_3}\): Codingfrom functools import reduce def xeuclid(a, b): """ return gcd(a,b), x and y in 'gcd(a,b) = ax + by'. """ x = [1, 0] y = [0, 1] sign = 1 while b: q, r = divmod(a, b) a, b = b, r x[1], x[0] = q*x[1] + x[0], x[1] y[1], y[0] = q*y[1] + y[0], y[1] sign = -sign x = sign * x[0] y = -sign * y[0] return a, x, y def gauss_crt(a, m): """ return x in ' x = a mod m'. """ modulus = reduce(lambda a,b: a*b, m) multipliers = [] for m_i in m: M = modulus / m_i gcd, inverse, y = xeuclid(M, m_i) multipliers.append(inverse * M % modulus) result = 0 for multi, a_i in zip(multipliers, a): result = (result + multi * a_i) % modulus return result a = [3,5,7] N = [5,7,9] for x in range(len(a)): print("x = ",a[x]," mod ",N[x]) print("The value of x is",gauss_crt(a,N)) A sample run gives: 3 = x mod 5 5 = x mod 7 7 = x mod 9 The value of x is 313 This is true as 313 divided by 5 gives a remainder of 3 (63 r 3), 313 divided by 7 gives a remainder of 5 (44 r 5), and 313 divided by 9 gives a remainder of 7 (34 r 7). One application area of this is in decrypting RSA messages. For example, if Bob ciphers the same message (\(M\) with three different keys (\((N_1,e),((N_2,e) and ((N_3,e)\): \(c_1 = M^e \pmod{N_1}\) \(c_2 = M^e \pmod{N_2}\) \(c_3 = M^e \pmod{N_3}\) Then, with CRT, we can determine the value of \(M^e\), and simply have to take the value of \(e\) - which is part of the public key - and then take the inverse log of \(M^e\) such as \(log_{10}{M^e}\) divided by \(log_{10}{e}\). BackgroundThe Chinese remainder theorem was first published by Chinese mathematician Sun Tzu. It determines a number x so that, when divided by some given divisors, leaves given remainders. As public key encryption typically involves this type of operation, CRT is well setup to help to crack encrypted messages. So what value will x equal in the following [Soln]: x mod 3 = 2 x mod 5 =3 x mod 7 = 2 The answer is 23, as 23 divided by 3 gives 21 remainder 2, 23 divided by 5 gives 4 remainder 3, and 23 divided by 7 gives 3 remainder 2. CRT and RSA If we capture enough RSA encrypted messages with the same e value and different modulus values (N), we can crack the message using Chinese Remainder Theorm (CRT). For example, if we have an e value of 3 we just need to capture three cipher messages to be able to recover the message. So I've created an example here: In this case we will use the following (where p1 and q1 generate N1, p2 and q2 generate N2 and p3 and q3 generate N3): e=3, message=123456789123456, p1=1131701, q1=1131721, p2=1131727, q2=1131737, p3=1131749, q3=1131751 The run the gives: GCD of N values: 1 N1= 1280769787421 N2= 1280817319799 N3= 1280858062499 Message= 1234567891234 e= 3 Cipher1= 184224238921 Cipher2= 173356604414 Cipher3= 369941826218 The equations we have to solve are then: M^e mod 1280769787421=184224238921 M^e mod 1280817319799=173356604414 M^e mod 1280858062499=369941826218 If we now use Chinese Remainder Theorem we get a result of: Result (M^e) is: 188,1676,377,431,587,319,857,436,861,793,600,904 And then we just use: 10^(log10(M^e)/e) and recover the message of 1234567891234 Try [here] |