Why I Do Cyber Security Research … The Sheer Joy of Cracking Puzzles!

Why I Do Cyber Security Research … The Sheer Joy of Cracking Puzzles!

I have a short journey into work on a bus, so I always try to have a “bus paper”, and which is a normally research paper which I can dip into. For some reason my best learning is done on the bus into work in the morning (and not so much on the trip back in the evening). But for a change this week, I focused on this blog post [here]:

And so the author tackles the cracking of RSA in such an engaging way. He sets up the problem beautifully, and then poses a question that is unanswered. Finally, he follows through with a workable solution. Basically it is cybersecurity problem solving in a nutshell.

So, I’m not going to cover the basics of the RSA method, but, if you are interested in cracking your own simple examples, here is how it is done:

In RSA, we generate two prime numbers (p and q) and multiply them to give N (the modulus). This becomes part of our key. If we find p and q, we then calculate PHI which is (p-1) times (q-1). Next we taken an exponent (e), and our public is e,N. After that we have cracked p and q, it is this then an easy task to determine d. This is the decryption exponent, and where we simply take the cipher message and raise it to the power of d, and then take (mod N), and we will recover the message.

With small values, such as with 60 digits, the cracking is easy:

Encryption parameters
e:	65537
N:	1034776851837418228051242693253376923
Cipher:	582984697800119976959378162843817868
We are using  60 bit primes

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

Then, using Python, 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 (d). Finally we decrypt with Message=Cipherᵈ (mod N):

>>> d=568411228254986589811047501435713
>>> cipher=582984697800119976959378162843817868
>>> N=1034776851837418228051242693253376923
>>> print pow(cipher,d,N)
345

Fortunately, for our security, it gets a lot harder when we use much larger prime numbers, and this is the reason that RSA is safe for a modulus of 2,048 bit and above (unfortunately our CPUs don’t quite like them as they use a good deal of their time and energy in calculating values using these large numbers). Note, for a 2,048 bit modulus we need two 1,024 bit prime numbers to multiply together, and there are a great deal of 1,204 bit prime numbers. If I run this code using the Riemannr method [here]:

from mpmath import *

print “\nRange\tEst number of primes”

val=2**1024
val2=2**1023
print “”,int(riemannr(val))-int(riemannr(val2))

I get an estimate that the number of 1,024 bit prime numbers is:

126691644892970358380427490926939356454723247188496143392476652502699531007595837129481293240468742382467025120913518137109672918250221680859672250355250660838394556806299217183402234779768002807879623065822080202513999439628970955789026304528777698360560517487360234622406536447129531599628766639300804608

It thus will not be possible for me to randomly search for prime numbers, or to pre-computing them and generate a range of modulus’ — even the NSA doesn’t have that amount of computing power and memory.

To understand the limits of this cracking, the author of the blog quotes research from 2010 and which factorized a 768-bit modulus (a 232-digit number). Unfortunately (and ‘fortunately’ for our safety) it it took the equivalent of 1,500 years (and which was cracked by 100s of computers):

And so, it may be possible for someone with enough computing power to crack RSA if we use a 768-bit RSA modulus. It is this is the reason that we use modulus values for our RSA keys on our digital certificates of 1,204 bits. As we are worried that 1K keys will get cracked, we normally start at 2,048 bits for the modulus, and most web sites now have this value as a minimum. Some companies are even moving to 4K keys (‘just in case’). Here is a 2K (2,048 bit) RSA modulus as used by RBS:

The crack of the decryption key (d,N) means that someone who has the private key which is associated with the public key (e,N), can thus digital sign entities in the same way that the valid company can. There are many well know examples of this, such as with Adobe, and where hackers managed to crack Adobe’s private key, and then were able to sign Adobe updates with this key, and which had back-doors in them. As far as the user was concerned these looked like valid updates, as they were signed by Adobe. It also happened with Sony on their PlayStation product.

And so Bob and Alice are safe if they use randomly generated prime numbers which give a modulus of over 1,024 bits. But the author outlines that the task becomes a great deal easier if Bob picks a prime number that Eve knows about. This is simply the case that if Eve has used 7 as one of the prime numbers, and the modulus is 77, she can now simply search for the other one (11), and it thus becomes a much easier task.

With this, the author outlines the research of Lenstra et al, and where the research team collected 6.2 million real RSA public keys and were able to crack 12,934 of them within just a few hours:

They did this by finding out whether the keys shared a common prime factor with other keys, and they did this on a single core of a PC, and not on a distributed system with GPUs. The blog author then proposes that this is strange, as it should take years to compute the common factors for this number of public keys.

The delema here is that there should be almost impossible to have common prime numbers for these modulus’, so there must be systems which are taking default ones.

And so how did they do it? Well, the blog post carries through and shows a possible solution for the magic involved. If you are interested in spending some “travel time” on it, here it is:

Work like this is why I adore Cybersecurity. Not the criminals steal people’s money, or the attacks on critical national infrastructure, but the shear joy of people cracking puzzles, and in working in a community that like to share their knowledge.

If you want more puzzle cracking, try this: