At StayPrivate, we use encryption all the time, to encrypt data, files and emails, both before storing and before transferring to or from a web browser, mobile app or external email server. More widely, encryption has become completely standard on the internet. Almost every website you visit uses encryption to ensure that your connection to the site is secure. Without encryption it would be impossible to make online payments, conduct business or communicate online in private. All these things we take for granted – they all rely on encryption.
Computers are very good at encrypting things. They can scramble and unscramble billions of digits efficiently and quickly. And with enough scrambling it soon becomes virtually impossible to crack a code. But the problem is how to communicate scrambling or unscrambling instructions to the intended recipient without anyone else finding out?
The piece of magic which enables this is called public-key cryptography. The idea is that the public key can be shared widely and is used to encrypt data. But only the private key can be used to unencrypt data, and this is kept secret. And this works because some mathematical problems are much easier to do in one direction than the other. We can illustrate this with a simple example.
Imagine you were given a calculator and asked to multiply the two numbers, 2017 and 6113. Assuming you typed correctly, this would be no problem at all, and you would quickly arrive at the answer: 12,329,921. But, if instead, you were asked to use the same calculator to work out which two numbers multiply together to make 12,329,921, that would be much, much harder. You would have to sit there trying dividing by different numbers until you got lucky. Eventually you would arrive at 2017 and 6113, but it would, unless you were extremely lucky, take a lot longer.
This is the principle behind the math underlying public-key cryptography. The idea is to find calculations that are much easier to perform in one direction than the other. In 1977, the US trio of Ron Rivest, Adi Shamir and Leonard Adleman became the first to publish such an algorithm, which became known as ‘RSA’. [It later turned out that Clifford Cocks, a UK mathematician working for GCHQ (the British intelligence agency), had discovered an equivalent system in 1973 but it had remained classified and was never put into active use.]
According to Wikipedia, RSA has a charming origin story, when after several months of struggling, the inspiration came to Rivest in a flash after he and the others had spent a long evening drinking wine. Rivest then sat up all night committing the idea to paper. No doubt there is message for us all in there somewhere!
RSA remains the most popular choice for signing website certificates, but more recently there has been a growing concern that if a private key is ever divulged then all messages ever sent using that key would easily be unencrypted. The solution is to provide ‘forward secrecy’ by creating a new private/public key pair each time. Unfortunately, with RSA a significant amount of computing effort is required to create a new key pair, and so a new algorithm has come to the fore, called ‘Elliptic-curve Diffie-Hillman’ or ‘ECDH’, under which it is much easier to generate key pairs. The maths behind ECDH is more complicated than RSA, but the principle remains the same – the calculation is much easier in one direction than the other.
The threat of quantum computing
Quantum computers represent a threat to current public-key encryption methods, including both RSA and ECDH. Quantum computers will be (in theory, at least) much better than digital computers at solving certain problems by making use of an approach called Shor’s algorithm. Shor’s algorithm can only be applied to a narrow set of problems but interestingly this set of problems happens to include all current public-key encryption methods.
As far as we know, quantum computers are still in their infancy and are a long way from the level of sophistication required to implement Shor’s algorithm in practice. It is possible that intelligence agencies are further ahead but, of course, they are not likely to let on – it would be such an incredible advantage to be able to decrypt internet communications that anyone who possessed such a power would surely try to keep it secret for as long as possible.
The good news is that if and when a Shor-resistant method is needed, it should not be too difficult to find. Various methods have been proposed, most of which are similar to what has gone before but with even more complicated maths – for example, one popular candidate uses super-singular elliptic curve isogeny. On that note we will leave it to the reader to investigate further!