Image for post
Image for post
Photo by Ariel on Unsplash

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 implement with it. Dan Shumow, for example, recently found a major problem in the way that the keys are created [here]:

Image for post
Image for post

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

Image for post
Image for post

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.

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:

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]:

Image for post
Image for post

For CRT, we have a value of x, and which is 0≤xM, 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:

Image for post
Image for post

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.

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.

[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].

ASecuritySite: When Bob Met Alice

This publication brings together interesting articles…

Prof Bill Buchanan OBE

Written by

Professor of Cryptography. Serial innovator. Believer in fairness, justice & freedom. EU Citizen. Auld Reekie native. Old World Breaker. New World Creator.

ASecuritySite: When Bob Met Alice

This publication brings together interesting articles related to cyber security.

Prof Bill Buchanan OBE

Written by

Professor of Cryptography. Serial innovator. Believer in fairness, justice & freedom. EU Citizen. Auld Reekie native. Old World Breaker. New World Creator.

ASecuritySite: When Bob Met Alice

This publication brings together interesting articles related to cyber security.

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store