Cracking: The Chinese Python Way

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)

e×log(M)=log(res)

log(M)=log(res)/e

M=10 ^{log(res)/e}

The coding is here [link]:

from Crypto.Util.number import *
from Crypto import Random
import Crypto
import sys
import libnum
import math

bits=60
msg="Hello"

if (len(sys.argv)>1):
        msg=str(sys.argv[1])
if (len(sys.argv)>2):
        bits=int(sys.argv[2])

p = Crypto.Util.number.getPrime(bits, randfunc=Crypto.Random.get_random_bytes)
q = Crypto.Util.number.getPrime(bits, randfunc=Crypto.Random.get_random_bytes)

n1 = p*q

e=3

m=  bytes_to_long(msg.encode('utf-8'))

c1=pow(m,e, n1)

p = Crypto.Util.number.getPrime(bits, randfunc=Crypto.Random.get_random_bytes)
q = Crypto.Util.number.getPrime(bits, randfunc=Crypto.Random.get_random_bytes)

n2 = p*q

c2=pow(m,e, n2)

p = Crypto.Util.number.getPrime(bits, randfunc=Crypto.Random.get_random_bytes)
q = Crypto.Util.number.getPrime(bits, randfunc=Crypto.Random.get_random_bytes)

n3 = p*q

c3=pow(m,e, n3)

mod=[n1,n2,n3]
rem=[c1,c2,c3]

res=libnum.solve_crt(rem,mod)

print ("String: %s, Prime size=%d " % (msg,bits))

print ("\nCipher 1: %d, N1=%d " % (c1,n1))
print ("Cipher 2: %d, N2=%d " % (c2,n2))
print ("Cipher 3: %d, N3=%d " % (c3,n3))

print ("\nM^e (calculated from CRT): %d" % res)

val = math.log10(res)/e

print ("\nLog(res)/e: %d" %val)

val=10**(math.log10(res)/e)

print ("\nResult: %d" % val)

print ("\nDecipher: %s " % long_to_bytes(int(round(val))))

and if you prefer natural logs, we can use math.log() and math.exp(), we can change to:

print ("\nResult: %d" % val)

print ("\nDecipher: %s " % long_to_bytes(int(round(val))))
val = math.log(res)/e

print (“\nLog(res)/e: %d” %val)

val=math.exp((math.log(res)/e))

print (“\nResult: %d” % val)

print (“\nDecipher: %s “ % long_to_bytes(int(round(val))))

A sample run [here]:

String: Hello, Prime size=128 

Cipher 1: 30062606975559439271719211082359375, N1=99405367339371611956149308359620242996634933534996553739627915220275076385547 
Cipher 2: 30062606975559439271719211082359375, N2=58243603637784630653851892753434651957874001108437359868873207168534480178541 
Cipher 3: 30062606975559439271719211082359375, N3=50486393054278071488561259488087786628970965760164529585983836080750871743157 

M^e (calculated from CRT): 30062606975559439271719211082359375

Log(res)/e: 11

Result: 310939249774

Decipher: Hello

And there you go. I can crack RSA with CRT. Go try it yourself: