So How Many Bits Does The Prime Number Have?
So How Many Bits Does The Prime Number Have?
“Education isn’t something you can finish.” — Isaac Asimov (1920–1992)
Recently, we had an interview with someone who was applying for a PhD studentship. The candidate had an MSc in Cybersecurity (from another university, I should say), and so as a little icebreaker, we said, “Do you know public key encryption?”, “Oh, yes”, “And do you know RSA?”, “Yes”, “Well, how many bits does the key have?”, “Mmm. Is it 8?”, “No. I don’t think so. That doesn’t sound like a strong key”, “Is it 128 bits? Yes. I remember something about 128 bits”, “No. Not really”, “Is it one bit?”, “Nope. Well. That wouldn’t be secure. Okay, but what’s in the key?”, “Is it bits?”, “Yes. But what do they make-up”, “Is it encryption?”.
We went onto talk about something else.
And so, I worry greatly about the consistency of standards defined in cybersecurity education, if there is at least one person who says they know RSA, and struggles to even explain the basics. For me, it’s like an electrical engineer saying that they know Ohm’s Law, but having to use Wikipedia every time they need to calculate current flows.
It’s all about primes
RSA has been around for over 40 years, and it’s at the core of much of the trust on the Internet. So let’s get down to a very basic level, and try to understand the core of the prime numbers used in RSA, and the number of bits they have.
Many operations in public-key encryption involve the (mod p) operation and where we take the modulus involving prime numbers. This is defined as a finite field. In this case, we will use Python to generate a random n-bit prime number. In RSA, for example, we take two prime numbers (p and q) and then multiply them together to create a modulus (N). The value of N is then part of the public and the private key. For RSA-2048 we use two 1,024-bit prime numbers, and RSA-4096 uses two 2,048-bit prime numbers.
In the following Python program, we will generate two random prime numbers (p and q) and which are a given length long. We will then use the RSA method of finding the modulus (N) and determine the number of decimal digits in these values [here]:
The following is a sample run and have p and q have 256 bits and N has 512 bits. We can see the number of decimal digits in N is 154 [here]:
No of bits in prime is 256
Random n-bit Prime (p): 66879465661348111229871989287968040993513351195484998191057052014006844134449
Random n-bit Prime (q): 109939025753834733498749075564102728424911782303658486825359178646821371085889
N=p*q= 7352663297745655707564770898973026111123571131674342064274310466656682149875713713190619593857622635229550350695840423707750477946865389780644345442690161
PHI (p-1)(q-1)= 7352663297745655707564770898973026111123571131674342064274310466656682149875536894699204411012894014164698279926421998574251334461848973549983517227469824
e= 65537
d= 6819755922304426102747146323998250426734036016007571769550673822980297203785407650915979348036083257381776925124546653452752122738795086061047165138871297
Count of decimal digits (p): 77
Count of decimal digits (N): 154
=== Let's try these keys ==
RSA Message: 5
RSA Cipher(c=M^e mod N): 3737300414341896687982704274640976335177867414610765937253111393444448821102093437087877905637522586212271118316233300533208156455762994160490000195316247
RSA Decipher (c^d mod N): 5
Unfortunately for RSA-2048 — which uses two 1,024 bit prime numbers — would take too long to generate with the on-line tool, so here’s a sample run:
No of bits in prime is 1024
Random N-bit Prime (p): 9284802202483365504137230473725605292106547771597500141
9347548380734496823522565044177931242947122534563813415992433917108481569319894167972639736788613656007853719476736625612543893748136536594494005487213485785676333621181690463942417781763743640447405597892807333854156631166426238815716390011586838580891
Random N-bit Prime (q): 149600854933825512159828331527177109689118555212385170831387365804008437367913613643959968668965614270559113472851544758183282789643129
469226548555150464780229538086590498853718102052468519876788192865092229749643546710793464305243815836267024770081889047200172952438000587807986096107675012284269101785114471
N=p*q= 13890143473829775722498011200310380316844447828814935927285432613507199159167722676657644390503254885067309729088246803976717186536237545696074407617252692272753523150095814175724095942210614670191629849771545994055456348662863125083954489746967620365631763638411626220580357256335085320237362476038814489657249198467580086057948518152187740483229396523233173271491163929243240236631349894842306615274693839354685812879841062224639585215273698139499197835540898969320991997758395568824475469359939378968115406019141601420464686230580766827389980948436032480690934398309104220456393444582655511612490684991989628173661
Count of decimal digits (p): 308
Count of decimal digits (N): 617
We can see, in this case, that we have 617 decimal digits for the RSA modulus, and which are generated from two 1,024 bit prime numbers. Overall RSA-2048 is used fairly extensively within digital certificates and in creating TLS tunnels. Here is an example of a connection to Twitter, and where we see that the Modulus is 2,048 bits long (RSA-2048):
Here is an outline:
Conclusions
I worry. Fundamentally we should have a profession that is trustworthy in its assessment of fundamental security. “Is this safe?”, “Yes, but …” or “No, because …”. Your learning does not stop once you graduate, and you must plug gaps that have been left behind. There is no reason not to learn technical things, as a car designer would also know how the engine works.
If you don’t know something, admit it, and go learn it, and don’t pretend that you do, as we are dealing with people’s privacy and your company’s reputation. Knowing what is acronym means does not relate to having an understanding of how it works. We must all be car mechanics, and get under the hood, sometimes.
If you are interested, here’s a quick outline of RSA: