Can RSA Be Cracked? Well, Yes!

Can RSA Be Cracked? Well, Yes!

Well, if Bob sends out the same message to Alice, Carol, Dave and Trent

There’s a feeling that RSA is a 100% secure method, but it is in no way a perfect method, and it sometimes needs to be treating with care when implementing with it. Dan Shumow, for example, recently found a major problem in the way that the keys are created [here]:

and the Bleichenbacker vulnerability was published over two decades ago, and is still causing problems [here]:

Most people know, too, that RSA is in great danger of being deprecated around its robustness against quantum computers. There, too, several theoretic attacks on RSA, and one of its long term enemies is the Chinese Remainder Theorem (CRT). So, as academic exercise, let’s take a very simple example to illustrate how we crack RSA with CRT.

RSA and CRT

With CRT we might want to find the value of x and when divided by 11, 13, 19 and 81 gives the division remainder of 3, 5, 14 and 78, respectively:

x mod 11 = 3 
x mod 13 = 5 
x mod 19 = 13 
x mod 81 = 78 

In this case, the answer is x=564, as 564 divided by 11 gives 51 remainder 3.

Now let’s try cracking RSA using CRT. For RSA, we start by generating two prime numbers (p,q) and then calculate the public modulus (N):

N=pq

Next we take our 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 as C will equal M^e). So let’s say that Bob sends the same message to Alice, Carol and Dave, and who have public key modulus’ of N1, N2 and N3, respectively. The ciphers become:

C1=M^e (mod N1)

C2=M^e (mod N2)

C3=M^e (mod N3)

Eve can then solve for M^e with CRT. Once we get this value we can use logarithms to crack it, such as 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. We can crack RSA with CRT. Go try it yourself:

First principles CRT

In the previous example, we used a function in libnum to solve the CRT. Now let’s use the Garner method to solve them [1]:

For CRT, we have a value of x, and which is 0≤x≤M, and where we have the residues of v(x)=(v1,v2,…vt) and for x modulo of the moduli m1,m2,…mt. The method Garner defined is:

and here is an implementation:

Let’s say Bob ciphers the same message (M) for Alice, Carol, Dave and Trent. Alice’s public modulus (N) is 77, Carol’s is 221, Dave’s is 437 and Trent’s is 1147, and we use a public exponent of e=5. Eve then captures the ciphers of 76 (Alice), 41 (Carol), 347 (Dave) and 894 (Trent). Eve now needs to find x for:

x mod 77 = 76
x mod 221 = 41
x mod 437 = 347
x mod 1147 = 894

This gives x=7,776 [Try]. Not we just take the inverse log of this:

>>> val = 10**((math.log10(7776))/e)
>>> print (val)
6.0

And we get a value of x=6, and which is the message.

Conclusions

There are a number of attacks on RSA, and the same message with different public modulus’ is just one of them. Here are a few more:

• RSA with Weak Prime Numbers (RSALib). copper. Weak generation of prime numbers within RSA (using RSALib).
• RSA Crack in 12 lines of Python. RSA Crack in 12 lines. This is a simple RSA crack, in 12 lines of Python code.
• RSA Crack with weak keys. RSA Crack: e shares with PHI. This is a simple RSA crack when e shares a factor with PHI.

References

[1] Garner, H. L. (1959, March). The residue number system. In Papers presented at the March 3–5, 1959, western joint computer conference (pp. 146–153). [here].