Cracking: The Chinese Python Way

Did you know we can crack the RSA public key encryption method with Chinese Remainder Theory (CRT)? With CRT, we might have a problem where we divide a number (val) with a given value and note the remainder:

val /51 Remainder is 45
val /41 Remainder is 14
val /13 Remainder is 5

In this case we can use CRT to determine that val is 96. We normally use the (mod N) notation to define a remainder given a division by N.

For RSA, we start by generating two prime numbers (p,q) and then calculate the modulus (N):

N=pq

Now we have a message (M), and create a cipher with:

C=M^e (mod N)

The value of M^e will always be much greater in value than N (otherwise we could solve with logarithms and C will equal M^e). So let’s say we manage to capture the same message encrypted with three different modulus:

C1=M^e (mod N1)

C2=M^e (mod N2)

C3=M^e (mod N3)

We can then solve for M^e with CRT. Once we get this value we can use logarithms to crack it. Once we have this we can determine M with:

log(M^e)=log(res)