Ref.: https://www.abc.net.au/news/science/2018-01-20/how-prime-numbers-rsa-encryption-works/9338876
19 Jan 2018
[...] Don't know if you've heard, but there's a new largest known prime number in town.
On 26 December, mathematicians scored a late Christmas present when a computer owned by a 51-year-old engineer in the US discovered the numerical beast, which starts with a 4 and ends in 1 — with 23,249,423 digits in between.
If you need a refresher on the definition of a prime number, it's a number larger than 1 that's divisible only by itself and 1.
The first few primes are 2, 3, 5, 7 and 11. The rest, like 4 for instance, are not prime: 4 can be broken down to 2 times 2, as well as 4 times 1.
But when mathematicians and computer scientists talk about large prime numbers — hundreds or thousands of digits long — it's often in the context of encryption: big primes, they say, help send secure messages between people, or computers.
So why is that?
Introducing the RSA algorithm
Prime numbers are fundamental to the most common type of encryption used today: the RSA algorithm.
The RSA algorithm was named after the three mathematicians who first publicly unveiled it in 1977.
They commercialised the idea and did very well out of it.
(A mathematician at the UK Government Communications Headquarters devised it separately four years earlier, but it wasn't considered useful and ended up being shelved. Oops.)
The RSA algorithm, in essence, allows a message to be encrypted without the sender knowing the key, says Lynn Batten, a mathematician and security researcher at Deakin University.
Here's how it works. The maths might seem a bit gnarly, but… that's kind of the point. Stick with it!
Public key locks private messages
Let's say I want to send you an encrypted message.
To do this, you need to make a public key, which comprises two numbers, available to me.
First, you choose two prime numbers: 11 and 17. These aren't your key — just a starting point. In calculations, we call these numbers p and q.
You keep p and q private. (Yes, you need to mind your Ps and Qs.)
Multiply p and q to get 187. Let's call this value N — it's one of your public key numbers.
Your second public number is a smaller one, which you can choose, and goes by the nickname e.
There are some rules that restrict your choice*, but let's say you pick 7.
Congratulations! You've now set up your encryption scheme. Easy, hey?
Now publish N and e wherever you like — shout them from the rooftops if you want — but "you'd usually publish it on an online directory just like a telephone number", Professor Batten said.
How to encrypt a message…
Now I'm going to send you a message outlining how many bottles of beer are on the wall — 99, of course — but we don't want anyone else to know.
(Even if the message isn't a number, it can easily be represented as one; your phone or computer has made that conversion for you to read this article.)
I look you up on a directory and find your public key — your N and e — 187,7.
Then the calculations start. I raise my message to e (it's an exponential, get it?).
In other words, I multiply 99 x 99 x 99 x 99 x 99 x 99 x 99 (seven times) and end up with a very large number. It's more than 93 trillion.
I then divide this massive number by your N (187). The answer to this calculation is still pretty big (498,430,667,329.9412) — but in fact, all I'm interested in is the remainder.
Remember learning fractions and decimals? Divide a large number by a small number and you can end up with leftovers. For instance, 6 divided by 4 equals 1 with a remainder of 2.
(In maths jargon, this is called the modulus.)
In our encryption example, the remainder is 176. And it's this number that I send to you; that's our encrypted message. We don't care if it's intercepted, because only you can decipher it.
Aren't we clever?
... then decrypt it
But how the devil do you decrypt 176 to get my real message, 99?
Well, you start with another secret number called d.
It's calculated based on your two original, secret prime numbers (p and q) and your public e. In this case (trust me**) it's 23.
And now the numbers get even bigger. You take my message (176) and multiply it by itself 23 times, ending up with a mammoth figure that's 50-odd digits long.
Then divide this new, monster number by N (187, the product of your original primes p and q) and find the remainder.
Bingo! The remainder is 99 — my original message.
There you have it: an encrypted, then decrypted, message.
All up, you keep p, q and d secret; N and e are public.
There are, of course, online calculators that do all these sums for you. And in real encryption, you'd never choose simple prime numbers like 11 and 15 as p and q, Professor Batten explained.
You'd go for much larger primes, hundreds or maybe thousands of digits long.
The reason prime numbers are fundamental to RSA encryption is because when you multiply two together, the result is a number that can only be broken down into those primes (and itself an 1).
In our example, the only whole numbers you can multiply to get 187 are 11 and 17, or 187 and 1.
It's easy enough to break 187 down into its primes because they're so small.
But when you use much larger prime numbers for your p and q, it's pretty much impossible for computers to nut them out from N.
Massive Mersenne primes
Still, computers are getting faster and more powerful all the time, so mathematicians continue to search for large prime numbers.
And when it comes to the biggest known prime numbers, Mersenne primes are most prolific.
Named after a French polymath, Mersenne primes take the form of 2 multiplied by itself a certain number of times, minus 1.
The Boxing Day prime is a Mersenne prime: it's 2 multiplied by itself 77,232,917 times, minus 1.
Nine of top 10 largest known primes fall into the Mersenne category.
Mersenne primes hold a special place in encryption too.
It turns out that in binary — the language of computers — Mersenne primes can be denoted as strings of 1s only.
For instance, the number 3 is written as 11 in binary. 7 is 111, 15 is 1111, 31 is 11111 and so on.
But as neat and effective as RSA encryption is, it won't be our secret-keeper of choice forever.
When quantum computers, capable of performing billions of calculations each second, start unpicking public keys to break them down to their primes, RSA will no longer be safe.
RSA isn't the only encryption technique out there though, and research teams are already finding ways to ensure we stay secure in the quantum computing age.
As Professor Batten said: "There are plenty of other [techniques] that will do just fine."
* For the mathematically keen, these are the rules for finding your e:
Take 1 off p and q, then multiply them. In our case, this means 10 times 16, which gives us 160.
Your e can be anything you like, as long as it doesn't share any prime factors with 160: that is, 2 or 5.
So in our case, e can't be 2, 4, 5, 10, 20, 40 or 80. We went with 7.
** For the even keener — this is how you calculate d:
Remember how you took 1 off p and q and multiplied them to get 160? You then add 1 to this and divide by e. 161 divided by 7 is 23. That's our d!
19 Jan 2018
[...] Don't know if you've heard, but there's a new largest known prime number in town.
On 26 December, mathematicians scored a late Christmas present when a computer owned by a 51-year-old engineer in the US discovered the numerical beast, which starts with a 4 and ends in 1 — with 23,249,423 digits in between.
If you need a refresher on the definition of a prime number, it's a number larger than 1 that's divisible only by itself and 1.
The first few primes are 2, 3, 5, 7 and 11. The rest, like 4 for instance, are not prime: 4 can be broken down to 2 times 2, as well as 4 times 1.
But when mathematicians and computer scientists talk about large prime numbers — hundreds or thousands of digits long — it's often in the context of encryption: big primes, they say, help send secure messages between people, or computers.
So why is that?
Introducing the RSA algorithm
Prime numbers are fundamental to the most common type of encryption used today: the RSA algorithm.
The RSA algorithm was named after the three mathematicians who first publicly unveiled it in 1977.
They commercialised the idea and did very well out of it.
(A mathematician at the UK Government Communications Headquarters devised it separately four years earlier, but it wasn't considered useful and ended up being shelved. Oops.)
The RSA algorithm, in essence, allows a message to be encrypted without the sender knowing the key, says Lynn Batten, a mathematician and security researcher at Deakin University.
Here's how it works. The maths might seem a bit gnarly, but… that's kind of the point. Stick with it!
Public key locks private messages
Let's say I want to send you an encrypted message.
To do this, you need to make a public key, which comprises two numbers, available to me.
First, you choose two prime numbers: 11 and 17. These aren't your key — just a starting point. In calculations, we call these numbers p and q.
You keep p and q private. (Yes, you need to mind your Ps and Qs.)
Multiply p and q to get 187. Let's call this value N — it's one of your public key numbers.
Your second public number is a smaller one, which you can choose, and goes by the nickname e.
There are some rules that restrict your choice*, but let's say you pick 7.
Congratulations! You've now set up your encryption scheme. Easy, hey?
Now publish N and e wherever you like — shout them from the rooftops if you want — but "you'd usually publish it on an online directory just like a telephone number", Professor Batten said.
How to encrypt a message…
Now I'm going to send you a message outlining how many bottles of beer are on the wall — 99, of course — but we don't want anyone else to know.
(Even if the message isn't a number, it can easily be represented as one; your phone or computer has made that conversion for you to read this article.)
I look you up on a directory and find your public key — your N and e — 187,7.
Then the calculations start. I raise my message to e (it's an exponential, get it?).
In other words, I multiply 99 x 99 x 99 x 99 x 99 x 99 x 99 (seven times) and end up with a very large number. It's more than 93 trillion.
I then divide this massive number by your N (187). The answer to this calculation is still pretty big (498,430,667,329.9412) — but in fact, all I'm interested in is the remainder.
Remember learning fractions and decimals? Divide a large number by a small number and you can end up with leftovers. For instance, 6 divided by 4 equals 1 with a remainder of 2.
(In maths jargon, this is called the modulus.)
In our encryption example, the remainder is 176. And it's this number that I send to you; that's our encrypted message. We don't care if it's intercepted, because only you can decipher it.
Aren't we clever?
... then decrypt it
But how the devil do you decrypt 176 to get my real message, 99?
Well, you start with another secret number called d.
It's calculated based on your two original, secret prime numbers (p and q) and your public e. In this case (trust me**) it's 23.
And now the numbers get even bigger. You take my message (176) and multiply it by itself 23 times, ending up with a mammoth figure that's 50-odd digits long.
Then divide this new, monster number by N (187, the product of your original primes p and q) and find the remainder.
Bingo! The remainder is 99 — my original message.
There you have it: an encrypted, then decrypted, message.
All up, you keep p, q and d secret; N and e are public.
There are, of course, online calculators that do all these sums for you. And in real encryption, you'd never choose simple prime numbers like 11 and 15 as p and q, Professor Batten explained.
You'd go for much larger primes, hundreds or maybe thousands of digits long.
The reason prime numbers are fundamental to RSA encryption is because when you multiply two together, the result is a number that can only be broken down into those primes (and itself an 1).
In our example, the only whole numbers you can multiply to get 187 are 11 and 17, or 187 and 1.
It's easy enough to break 187 down into its primes because they're so small.
But when you use much larger prime numbers for your p and q, it's pretty much impossible for computers to nut them out from N.
Massive Mersenne primes
Still, computers are getting faster and more powerful all the time, so mathematicians continue to search for large prime numbers.
And when it comes to the biggest known prime numbers, Mersenne primes are most prolific.
Named after a French polymath, Mersenne primes take the form of 2 multiplied by itself a certain number of times, minus 1.
The Boxing Day prime is a Mersenne prime: it's 2 multiplied by itself 77,232,917 times, minus 1.
Nine of top 10 largest known primes fall into the Mersenne category.
Mersenne primes hold a special place in encryption too.
It turns out that in binary — the language of computers — Mersenne primes can be denoted as strings of 1s only.
For instance, the number 3 is written as 11 in binary. 7 is 111, 15 is 1111, 31 is 11111 and so on.
But as neat and effective as RSA encryption is, it won't be our secret-keeper of choice forever.
When quantum computers, capable of performing billions of calculations each second, start unpicking public keys to break them down to their primes, RSA will no longer be safe.
RSA isn't the only encryption technique out there though, and research teams are already finding ways to ensure we stay secure in the quantum computing age.
As Professor Batten said: "There are plenty of other [techniques] that will do just fine."
* For the mathematically keen, these are the rules for finding your e:
Take 1 off p and q, then multiply them. In our case, this means 10 times 16, which gives us 160.
Your e can be anything you like, as long as it doesn't share any prime factors with 160: that is, 2 or 5.
So in our case, e can't be 2, 4, 5, 10, 20, 40 or 80. We went with 7.
** For the even keener — this is how you calculate d:
Remember how you took 1 off p and q and multiplied them to get 160? You then add 1 to this and divide by e. 161 divided by 7 is 23. That's our d!