RSA: Over 40 Years Old and Still Amazing! — Let’s Crack It

I really dislike those CAPTCHA exercises, and especially when there’s a little bit of a traffic light that you have to select. So I had to…

RSA: Over 40 Years Old and Still Amazing! — Let’s Crack It

I really dislike those CAPTCHA puzzles, and especially when there’s a little bit of a traffic light that you have to select, or where I’m asked to find the crosswalk — in the UK we would call them Zebra crossings, and they don’t look too much like the ones you get in the USA. So I had to smile yesterday when I logged in to a crypto conference and it gave me:

So, after more than 40 years, RSA is still alive and kicking. In this article I will give you an RSA challenge, and — hopefully — you will be able to crack it and find the rock band:

Can you find the rock band? 
N=879509040449463763008386484793372267, cipher=850431005415590313843011081245086829

For me. The RSA method is a thing of beauty. For over 40 years it has protected users against cybercrime more than virtually everything else. It is still at the core of PKI, and protects users against fake sites, it proves their identities, and it stops others from other spying on their activities. While elliptic curve methods are beating it in most things, it is still there, and it is still a winner.

Meet The Champ …

In August 1977, The Stranglers were in the charts with “Something Better Change” and something really was changing, and it something that would change the world forever. This was the month that Martin Gardner, in his Scientific American column, posted a challenge of a method that has stood the test of time: RSA.

It related to the work of R(ivest), A(dleman) and S(hamir) and was a puzzle on their discovery of a method which allowed two keys to be created, where one could encrypt, and the other to decrypt. Their work had been based on a proposal from Whitfield Diffie and Martin Hellman on trapdoor functions that could be used to create the key pair.

In order to explain the RSA concept, Martin’s provided a background with the Diffie-Hellman method for which he outlined:

Then in 1975 a new kind of cipher was proposed that radically altered the situation by supplying a new definition of “unbreakable.” a definition that comes from the branch of computer science known as complexity theory. These new ciphers are not absolutely unbreakable in the sense of the one-time pad. but in practice they are unbreakable in a much stronger sense than any cipher previously designed for widespread use. In principle these new ciphers can be broken. but only by computer programs that run for millions of years!

Overall the Diffie-Hellman method has had a good run, but it has struggled in recent years to keep up with the processing power for computers, and the millions of years of running are not quite the case in the modern area, and where the original ciphers could now easily be broken with the simplest of computers within minutes.

With the RSA method, Martin Gardner outlined:

Their work supported by grants from the NSF and the Office of Naval Research. appears in On Digital Signatures and Public-Key Cryptosystems (Technical Memo 82. April. 1977) issued by the Laboratory for Computer Science Massachusetts Institute of Technology 545 Technology Square. Cambridge Mass. 02139.

The memorandum is free to anyone who writes Rivest at the above address enclosing a self-addressed. 9-by-12-inch clasp.

On receipt the requesters eventually (it took over four months in many cases) received a precious piece of history:

It seems unbelievable these days, but the original methods were based on two 63-digit prime numbers that would be multiplied to create a 126-digit value:

Contrast this with the difficulty of finding the two prime factors of a 125- or 126-digit number obtained by multiplying two 63-digit primes. If the best algorithm known and the fastest of today’s computers were used, Rivest estimates that the running time required would be about 40 quadrillion years’

A 256-bit number, at its maximum, generates 78-digits [here]:

115,792,089,237,316,195,423,570,985,008,687,907,853,269,984,665, 640,564,039,457,584,007,913,129,639,936

The 40 quadrillion years has not quite happened, and where 512-bit keys are easily broken in Cloud. If you are interested, here is a 512-bit integer value and which has 148 digits, such as [example]:

13,407,807,929,942,597,099,574,024,998,205,846,127,479,365,820,5 92,393,377,723,561,443,721,764,030,073,546,976,801,874,298,166,9 03,427,690,031,858,186,486,050,853,753,882,811,946,569,946,433,6 49,006,084,096

The search for prime numbers, too, has been progressive since 1977, and by 2014, the world discovered a 17,425,170-digit prime number. The finding of prime numbers make the finding of them in the RSA method must easier.

So the RSA method has been under attack for years, from both discovering prime numbers and also in factorizing. Along with this computing power has increased massively. If think that 40 years that have passed, and take a quick assumption that computing power doubles every year then we get:

1977 4 Quadrillion Years (4,000,000,000,000,000)
1978 2 Quadrillion Year
1979 1 Quadrillion Year...2015 3,637 years

and if we get an NVIDIA card with 4,000 processors, we take it to less than a year, and we get of few of them today into a cluster, and we crack it within one day! The FREAK vulnerability was actually caused by the limiting of RSA keys, due to US Export controls, to 512-bits [view].

The RSA paper has become one of the most cited papers in the whole of computer science — with 22,019 citations [here]:

So let’s see if we can crack our RSA cipher puzzle …

The basics of RSA

The basics of RSA is that we have two random prime numbers (p and q) and then create a modulus (N):

N=pq

Now we calculate PHI:

PHI=(p-1)(q-1)

Now we select an encryption key value (e) that does not share a factor with PHI. If we select a low prime number, we should be able to select any value, but the most common value is 65,537. Our encryption key is (e,N), and we encrypt with:

M^e (mod N)

To calculate our decryption key value (d) we find:

d . e (mod PHI) = 1

The value of d can be found with the inverse of e mod N. The code to perform the decryption once we know the cipher value (c), p and q [here]:

https://asecuritysite.com/encryption/rsa12_2
from Crypto.Util.number import long_to_bytes
import libnum
import sys

p=954354002755510667
q=801297755486859913
c=607778777406675887172756406181993732
#N=764721720347891218098402268606191971


n = p*q
PHI=(p-1)*(q-1)

e=65537
d=(libnum.invmod(e, PHI))


res=pow(c,d, n)

print ("Cipher: ",c)
print ("p: ",p)
print ("q: ",q)

print ("\n=== Calc ===")
print ("d=",d)
print ("n=",n)
print ("Decrypt: %s" % ((long_to_bytes(res))))

So the challenge is to factor the value of N, and if we have used relatively small prime numbers — such as below 128 bits — we can easily factorize N, in p and q, and then decrypt the cipher.

If we get a challenge of:

Can you find the city in England? N=826382916071823972711332001902568877 cipher=511617430183577168370958189976920833

We can use a factorization program [factor] to factorize N:

Next we can just copy-and-paste our values:

And, our cipher becomes “york”.

Conclusions

The RSA method is just as beautiful.

So what is the rock band?

N=879509040449463763008386484793372267, cipher=850431005415590313843011081245086829