It’s estimated that 74 billion dollars a day are transmitted electronically around the world – and some of that’s probably yours. If this e-commerce is not absolutely secure, millions of people are risking billions of pounds. Why do you trust it?
The history of encryption is filled with examples of people breaking codes that were previously thought to be absolutely secure. So what’s different about modern encryption? Modern mathematical thought and computing technology tell us that due to the properties of the current state of the art encryption algorithm, it would take millions of years to break it and that’s good enough for the world banking system.
Electronic padlocks
Online retailers and banks have particular requirements for their code technology. Everyone needs to be able to send them encrypted messages, but no one except the retailer should be able to decrypt what’s been sent. So, how do you do this?
The retailer publicly reveals a unique way of locking up the message: a ‘padlock’ to which only they have the key. They distribute the padlocks everywhere, so that anyone who wants to send them their credit card information can just secure it with the padlock. When it gets to – eg Amazon.co.uk, it can use its key to unlock the padlock; but no one else can.
That’s great for padlocks, but we’re sending information. These locks are securing strings of digits flying through the ether; and they need to be made using maths. So we ask ourselves, what does this algorithm need to do to be like the padlock? It needs to be in two parts (the lock and the key). The padlock should be easy to put on, but impossible to take off without the key. And the key needs to be unique. There should be no way of breaking down the padlock to make a replica key.
Don’t open that trapdoor
We now know a lot about the algorithm we’re looking for. It should take as parameters two pieces, or sets, of information: one public and one private. It needs to use a mathematical function that, in the language of cryptographers, is a trapdoor – it’s easy to go through one way, but not the other. And there should be no way of getting from the public information to the private information.
Secure transmission of data is a crucial problem for governments as well as financiers, and is a juicy problem for mathematicians to chow down on. Because of this several groups of people have worked on this problem, some of whom were forbidden from talking about it for years, making it difficult to pinpoint the inventor of the system.
The first person to solve this problem was Clifford Cocks, a mathematician working at the UK’s Government Communications Headquarters (GCHQ) in 1973. However, his bosses did not want to publish the decision at that time (he doesn’t seem too bitter about this, and he’s now Chief Mathematician at GCHQ, so he’s doing OK). It was left to Rivest, Shamir and Adleman, a team of academics at the Massachusetts Institute of Technology (MIT) to reveal the method now known as RSA encryption. Amazingly, they had both developed the same technique independently, and it is now the standard communication protocol worldwide.
How to encrypt with RSA
The method relies on the difficulty of finding prime factors of very large numbers – between 1024 and 2048 bits long. Each recipient chooses two very large prime numbers, p and q, and multiplies them together to get a third number, which we can call N. They also have to choose another number which is co-prime with N, called e. N and e are then made widely available as the public key for this person – let’s call her Alice, for tradition’s sake.
To encrypt a message, the sender – say, Robert – converts his message into a number, M. This could, for example, be done using ASCII (American Standard Code for Information Interchange), a protocol where each symbol is represented by 7 bits.
Secure communication works as follows:
1. Bob transforms his message into a code text, C.
C = Me mod N
2. Bob sends C to Alice.
3. Alice, who remember chose the values of p and q in the first place, now crunches a few numbers. She calculates a new number, d, so:
e · d = 1 mod ((p-1) · (q-1))
This is a bit of a tricky equation, but an ancient algorithm (the Chinese Remainder Theorem) can solve it.
4. Now in possession of d, Alice can find the message by performing
M=Cd
Voila!
Crack that!
The only way someone who is not Alice can read Bob’s message is by finding p and q, assuming Bob has her correct public key. However, as described earlier, multiplying primes is a one-way function: it might take perhaps 10 seconds to multiply two large primes (large here means that N ends up with about 300 digits). To factor it, you’re looking at a thousand years, even if a hundred million personal computers were networked together for the task. That’s pretty secure.
With sufficiently large primes, RSA is considered strong enough for the most important financial transactions. The US government is so concerned about terrorist groups using it to hide their communications that they have prosecuted people who export RSA encryption software under the same legislation as that for arms dealers.
RSA will stay safe as long as factoring large primes remains difficult. Prizes are on offer for finding and understanding primes, which continue to fuel research into this part of number theory.
It’s possible that in the future, a new way of factoring primes might be discovered – perhaps it already has been, in some secret government agency. Whether RSA is the final word on security or not, cryptography remains one of the few areas where pure maths translates directly into essential technology, and a big employer for mathematicians
