Why does the mathematically mysterious nature of prime numbers make them so useful in the current digital age?
Since the ancient Greeks, prime numbers[i] have been of enormous interest to mathematicians due to their seemingly mysterious nature, and their unpredictability. If you look at a table of whole numbers and highlight the primes, they appear to be random. If you know that one number is prime, it is very difficult to know when the next prime will appear. In the 20th and 21st centuries, however, these properties have made prime numbers an integral part of our digital world; in this age, cryptography is vital. Every time you purchase something online you send your credit card information across the internet. This data needs to be secure and kept locked away, so that, even with the most sophisticated and powerful computer in the world, an interceptor would be still unable to decrypt the sender’s message. However, no matter what level of encryption is used, it is vital that the intended recipient (for example, the bank) is still able to decrypt it easily; or else the entire point of cryptography is defeated. This creates an interesting problem, one which was researched in 1974 by three cryptographers: Rivest, Shamir and Adleman, at MIT. Their aim was to create a system which satisfied the requirements of being secure, yet still efficient at transmitting information. This had to match an age where computers were getting quicker, which meant their ability to ‘crack’ codes, by result, was increasing in speed.
The breakthrough of these three researchers was their decision to harness the strange nature of prime numbers. As we have seen, prime numbers behave mysteriously, and this is essential to Rivest’s idea. Successful encryption has the aim of preventing others from managing to reverse your encryption algorithm. So, surely, if one were to use prime numbers somewhere in the algorithm, a topic which humans do not fully understand, it will be harder to reverse the algorithm. This algorithm was named ‘RSA’ encryption, anachronized to give recognition to the three mathematicians who invented it. The actual mathematics behind this algorithm is beyond the scope of this article (although it is surprisingly simple and could probably be understood by most high school maths students!) But it is of deep interest how these prime numbers are used in theory. After all, even today, your personal information is reliant on RSA and prime numbers!
One fundamental concept of ‘Public-Key Cryptography’ (this is a general term for systems such as RSA) is that factorising large numbers is difficult. For instance, it is very easy for my computer to multiply two large prime numbers together, if we understand ‘large’ as numbers with 600 or so digits. Yet, it is extraordinarily difficult for computers to reverse this process. This is due to the strange, random nature of primes. But, given the large number, it would take an inconceivable amount of computing power to work out which two primes I have multiplied.
For the rest of this article, I shall refer to the two large primes as ‘p’ and ‘q’, and their product as ‘N’. Suppose you need to send a credit card number to Google. Google will have a ‘Public-Key’ number, which is the large number N, created by multiplying p and q together. This number is totally public (in fact, it has 617 digits!) The RSA algorithm then uses this large number, N, and your credit card number to produce a code,[ii] which is then sent. At Google’s end, the RSA algorithm is reversed to find your credit card number. But, crucially, Google can only do this because they alone know the values of p and q.
Just think about that for a second: this large number, N, can be found with a very quick search on the internet. In theory, if anyone were to find the two primes p and q, which multiply to make N, Google’s encryption would be compromised. One may consider this to sound insecure, however the enormous size of the number makes it virtually impossible for even the most powerful computers in the world to factorise it.
In 2003, RSA used optimistic expectations of how technology will progress, predicting that it would be possible to factorise a 617-digit number in as little as five months by 2030. Although this system of encryption is widely used and is currently very secure, this suggested outcome heralds a potential downfall. Due to us not fully understanding primes, the only real way to try to hack an RSA code is brute force: simply trying every possible combination of prime numbers to see if they multiply together to make N. Although this takes a long time, it creates a constant arms-race between cryptographers and hackers. The progress of technology puts hackers at an advantage, enabling them to get through their attempts quicker. All that can be done from the cryptographers’ perspective is to make the size of N even more ‘massive’. This is simply in order to create further possibilities that hackers must try in order to break the encryption, taking them more time.
Every day, mathematicians in universities around the world continue to study these fascinating properties of prime numbers. Perhaps one day, purely in the pursuit of mathematical knowledge, someone will make a ground-breaking discovery which clears up this mystery behind primes. However, in doing so, they could unintentionally render our current encryption methods useless.
Overall, I believe that the advantages of using prime numbers in RSA Encryption outweigh their disadvantages, due to their mysterious nature. Although the progression of technology causes a problem when shorter encryption codes are used, this is easily combated by making encryption codes longer. These would take centuries to factorise, even with the most powerful of computers. The unusual properties of prime numbers are fundamental to their application here; no other sequence of integers provide as much mystery and intrigue. Thereby, our limited understanding of the mysterious nature of prime numbers is what makes them crucial in modern-day cryptography.
[i] A number is prime if its only factors are one, and itself.
[ii] As I mentioned, it is beyond the purpose of this article to explain this exact mathematical procedure, but I encourage you to look into it!