RSA Cracking Claims!
RSA Cracking Claims!
Well, Robert Grant (CEO of Crown Sterling) has been presenting on cryptography again, and it has kept Twitter ablaze with this comments:
For me, I kinda like his presentations. They are fun, and where he — at least — tries to explain some difficult concepts in an engaging way, but sadly some of the claims are not quite up to current standards. While you can see he doesn’t have a core depth of knowledge, and often gets things mixed up, he at least tries to explain the importance of public key encryption. But, when he outlines that “A times B equals C” is a discrete log problem, you see that there’s a bit of a lack of depth in some of the knowledge.
What I like in his presentation ithat he is correct in identifying that many industry people just don’t understand even the basics of the methods used in encryption. As this is a foundation element of good cybersecurity, we must thus worry about the state of the industry. As for the scientific claims in the talk, I leave it to you to make up your own mind.
It is Bruce Schneier who really highlights the weaknesses of the claims in this presentation which:
decrypts two 256-bit asymmetric public keys in approximately 50 seconds from a standard laptop computer
Bruce outlines that a 426-bit key was factored in 1994, and the further claim of the factorization of a 512-bit key in five hours was cracked in 1999 [here]. The challenge of cracking a 1,024 bit key is vastly more difficult (double … double … double … 512 times), and for most RSA methods we have 2,048 bit keys and which would are almost uncrackable.
In order to understand the concept of work in cracking cryptography, Lenstra [here] defined the concept of Global Security in order to show the amount of energy required to crack cryptographic algorithms and compare this with the amount of water that energy could boil. This could be seen as the carbon footprint of cracking. For a 242-bit RSA key, you only need to pay for the boiling of a teaspoon of energy, and for a 453-bit RSA key, you just need to have enough money to pay for a shower:
To break a 1990-bit key would require the energy to boil every ocean in the world. Global security — 2,380 RSA key bits — is boiling all water on the planet amounts. That’s a lot of energy!
RSA in 12 lines of Python
I set myself a task to write a minimal number of lines to implement a full RSA key generation, encryption and decryption system, and I got it down to 12 lines (not including import statements). The code is [here]:
from Crypto.Util.number import *
from Crypto import Random
import Crypto
import gmpy2
import sys
bits=60
msg="Hello"
p = Crypto.Util.number.getPrime(bits, randfunc=Crypto.Random.get_random_bytes)
q = Crypto.Util.number.getPrime(bits, randfunc=Crypto.Random.get_random_bytes)
n = p*q
PHI=(p-1)*(q-1)
e=65537
d=(gmpy2.invert(e, PHI))
m= bytes_to_long(msg.encode('utf-8'))c=pow(m,e, n)
res=pow(c,d ,n)
print "Message=%s\np=%s\nq=%s\nN=%s\ncipher=%s\ndecipher=%s" % (msg,p,q,n,c,(long_to_bytes(res)))
A test run shows it working:
Message=hello
p=242648958288128614541925147518101769011
q=299356840913214192252590475232148200447
N=72638625604016464006874651287120524699932001616388639276131104258310920947917
cipher=5847803746095553957863305890801268831081138920772806292673259864173015661385
decipher=hello
RSA Method and Cracker
Do you have what it takes to be an RSA cipher cracker? Well here is a challenge for you [here]:
RSA Encryption parameters. Public key: [e,N].
e: 65537
N: 498702132445864856509611776937010471
Cipher: 96708304500902540927682601709667939
We are using 60 bit primesCan you find the value of the message?
With this we are using the RSA encryption method, and we have the encryption key (e,N). We must find the two prime numbers which create the value of N (p and q), and must use a factorization program to find them. Once we find the factors it is easy to then determine the decryption key (d,N).
Here is an example:
Encryption parameters
e: 65537
N: 1034776851837418228051242693253376923
Cipher: 582984697800119976959378162843817868
We are using 60 bit primes
Now we have to crack N by finding the primes that make up the value.
If we use this [link], we get:
Factors
-------
1,034,776,851,837,418,228,051,242,693,253,376,923 = 1,086,027,579,223,696,553 x 952,809,000,096,560,291
p=1,086,027,579,223,696,553 q=952,809,000,096,560,291
Now we work out PHI, which is equal to (p−1)×(q−1):
>>>p=1086027579223696553
>>>q=952809000096560291
>>> print (p-1)*(q-1)
1034776851837418226012406113933120080
Now we find e⁻¹ (mod PHI) (and where (d×e) (mod PHI)=1), such as using [here]:
Inverse of 65537 mod 1034776851837418226012406113933120080
Result: 568411228254986589811047501435713
This is the decryption key. Finally we decrypt with Message=Cipherᵈ (mod N):
>>> d=568411228254986589811047501435713
>>> cipher=582984697800119976959378162843817868
>>> N=1034776851837418228051242693253376923
>>> print pow(cipher,d,N)
345
The message is 345
Finally, let’s check the answer. So we can re-cipher with the encryption key and we use Cipher=Mᵉ (mod N):
>>> m=345
>>> e=65537
>>> N=1034776851837418228051242693253376923
>>> print pow(m,e,N)
582984697800119976959378162843817868
This is the same as the cipher, so the encryption and decryption keys have worked. Thus the encryption key is [65537, 1034776851837418228051242693253376923] and the decryption key is [568411228254986589811047501435713, 1034776851837418228051242693253376923]
Conclusions
This is fairly simple to compute as the prime numbers are fairly small. In real-life these will be 1,024 bit prime numbers, and N will have 2,048 bit numbers, which will be extremely difficult to factorize.
If you want here’s some challenges:
- Challenge with 60-bit primes:
RSA Encryption parameters. Public key: [e,N].
e: 65537
N: 911844725340031776516886332975892441
Cipher: 801127314512167104045686292190207406
We are using 60 bit primesCan you find the value of the message?
2. Challenge with 80-bit primes:
RSA Encryption parameters. Public key: [e,N].
e: 65537
N: 1157170973102575683016736411062049761643292045397
Cipher: 398616441584847118291875619819339172891325623639
We are using 80 bit primesCan you find the value of the message?
3. Challenge with 128-bit primes:
RSA Encryption parameters. Public key: [e,N].
e: 65537
N: 49141939931137261116843775362783398673931258031923895283286320973486872970729
Cipher: 14199123787046830048066972290052136769415356824981695836360604590953658335413
We are using 128 bit primesCan you find the value of the message?
— — — — — — — — — -
— — — — — — — — — -
Answers
— — — — — — — — — -
1. Answer is: 1497
2. Answer is: 427
2. Answer is: 145