Why Is The Number of Bits used in RSA So Much More Than Other Public Key Methods?

Why Is The Number of Bits Used in RSA So Much More Than Other Public Key Methods?

Remember as a child you perhaps asked why the sky was blue, or why birds can fly? For some reason, as we get older we lose the ability to questions things, and everything is just taken for granted. Overall I find that those who innovate best, and those who have great ideas, are the people who have not lost their continual questioning of our world, and asking what seems like simple questions.

So, if you can answer why we talk about 512-bit, 1K and 2K keys, but in other public key methods, we only talk about 256-bit keys, then you have reach the end of this article. If not, read on …

Why RSA has more bits than others?

I was asked by one of our students, why is the number of bits used in the RSA modulus so much larger as compared with other public key methods? In elliptic curve methods, for example, the prime number only has to have 256 bits for good security, but, in RSA, we need at least 512 bits. It is a great question, and I’ll try and explain it here.

Every integer number is made up of the multiplication of prime numbers. For example:

• 743,243 = 193 x 3,851 here.
• 2,542 = 2 x 31 x 41. here.
• 653,764,321,953,243 = 3 x 3 x 17 x 51,151 x 83,536,381 here.

If the puzzle is for me to find the factors of an integer, it is a whole lot easier for me to find them if we have small integers involved.

And so, with RSA, we take two prime numbers (p and q), and multiply them to give a modulus N:

N = p q

The number of bits in the modulus defines the strength of RSA (typically defined with 512 bits or 1,024 bits). We also calculate PHI, which is (p-1)(q-1), and it is this value that allows us to determine (or crack) the decryption key.

Now let’s try and example. Let’s say we select two prime numbers and calculate the modulus. If we select p=61,211 and q=45,887 [here], we get:

N=p*q= 2,808,789,157

PHI (p-1)(q-1)= 2,808,682,060

p and q, in this case are 16-bit values, so I will have to search for prime numbers within the 2¹⁶ number space. But let’s say that I select p=3 and q=2,526,639,991. Now we get:

N=p*q=7,579,919,973
PHI (p-1)*(q-1)= 5,053,279,980

The size of the modulus is around the same size as the previous one, but it is so much easier to crack, as I select p=2, and try, and then p=3, and then I’ve cracked it.

Thus, the size of the modulus of the multiplication of two n-bit numbers is 2n, but strength of the multiplication of two n-bit prime numbers, is equal to n bits. Thus, a 512-bit RSA modulus, has a strength of just 256 bits. This is why we see the strength of RSA often requiring double the bits to have the same strength as other methods.

For the size of the prime numbers, the optimal security is then when we have two prime numbers of the same number of bits:

The security is then related to the number of bits in the smallest prime number (as this will be the easiest to find).

If you are interested in factorizing integers, or even in determining if a number if prime or not, have a look at smooth numbers, as these are the numbers that we try first in factorizing:

Conclusions

Go on, let your mind think like a child again, and question this world. To be an innovative, you need to look at the world differently, and question everything. Unfortunately, we may be creating a future generation who do not question this technology-driven world … how does a network packet get from here to there? how does a computer read my face? If we all just assume that it “all just works”, we have become the consumers of technology, and not its creators. Go do research, go setup a start-up, go force yourself to learn a difficult topic, start to learn deeply about topics, … just don’t stop questioning.

Many people, too, are switched off by the sight of numbers and some basic operations. I think perhaps that school does this, so see if you can switch that little number light on again in your brain.