Apr 02, 2013— read in full
From state secrets to online shopping, cryptography is one of the most important applications of maths in the world today.
Cryptography answers a simple question that has a multitude of uses: how do you tell someone a secret when you know someone else might be listening in? While in the past this has mainly been a question for spies and military leaders, in the modern world it affects everyone who doesn't want other people snooping on their web browsing habits or credit card number.
Algorithms and keys
There are two parts to a cryptographic system: the algorithm and the key. The algorithm is the series of mathematical steps that turn the secret into something unreadable. The key is a number that affects the result of the algorithm. For example, your could say that for the simple code:
Replace each letter with the letter two places
along the alphabet, so that A becomes C, B
becomes D and so on.
the algorithm is:
Replace each letter with the letter a certain
number of places along the alphabet.
and the key is 2. You could use the algorithm with 7 or 12 or any other number as the key. The important thing is that it doesn't matter if everybody knows what they algorithm is: they need to know the key as well if they want to read the message.
Of course, with this algorithm you could just try every number until you got the right one. Even if you didn't know the algorithm, you might be able to decode the message by looking at which letters come up most often - for example, the letter that appears most probably represents E, as E is the most common letter in English. Real-world encryption algorithms are much more complex, making it impractical to work out the original message without the key, and can use very long keys to make guessing the key almost impossible.
Who knows the key?
The simplest way to encrypt a message securely is to have the same key for encrypting and decrypting a message. This means that you and the person you're sending your secret to both need to have access to the key - and that can cause problems. If you have to share the key with someone else, it increases the chance that somebody you don't want to know your secret will get hold of it.
The alternative uses one key to encrypt the message and another one to decrypt it. The keys are mathematically related, but the relationship between them is too complex to work out one from the other, even with a fast computer. In fact, the relationship is so hard to work out that making the keys a little bit longer makes them much harder to crack - so making a key twice as long makes it much more than twice as secure.
Having two keys means that you can let anybody send you a secret safely, because you can share the one that encrypts messages with everyone - you could even put it online. This key is known as your public key. The decryption key is your private key, because that's the one you need to keep to yourself if you don't want other people to be able to decrypt what you're being sent.
It can sometimes be useful to swap the two around, letting everyone know the decryption key and keeping the encryption key for yourself. This means that you can prove that a message comes from you by including a 'signature' encrypted with the key only you know: if the key you shared can decrypt it, then only you could have sent the message.
These common ways of encrypting information aren't perfect: they rely on the fact that it would take thousands of years of computer power or a huge breakthrough in mathematics to break them. However, it is possible to make an unbreakable code using a 'one-time pad'.
This can be only slightly more complicated than the example code above. Instead of changing moving every letter 2 places, you have a different key for each letter, chosen at random. So for the message HELLO, you could use the key
14 17 26 21 17
and you would get the result VVLJF.
Even though the method is simple, it's completely impossible to work out from VVLJF that the original message was HELLO unless you've got the key. However, you can only use the key once, which is why it's called a one-time pad - and you have to make sure that only you and the person you're communicating with get hold of the key.