Page 1 of 3
Public key encryption is vital to the commercial Internet. We look at how it works and explain the RSA system in detail.
Public key encryption is what makes the commercial Internet work and it provides privacy for anyone who wants it. When you don't know how it works it seems more like magic than anything else. When you do know how it works then there are still time and applications of it that seem magical.
Without it we would find it much more difficult to safeguard financial data such as credit card numbers in transit. What is more it all works behind the scenes and almost without the user knowing anything about it. At most you might see a message telling you that you are about to use a secure connection or server.
You can ignore the details if you want to, but don’t!
How it works is not only amazing but only by knowing how it works can you have any hope of evaluating how safe it all is.
Cryptography and codes
Traditionally cryptography has used a key to code a message and a key, usually the same key, to decode the cipher text.
The key is used in a process that transforms the message into the cipher text in such a way that it should be impossible to extract the message from it without the key.
You can think of this process as a sort of mixing of the message data and the key. The mixing has to be thorough enough to hide both the message and the key but it has to be structured enough to be relatively easy to undo if you have the key. How successful all of this is depends very much on how easy it is to detect the key or the original message in the cipher text.
For example, one of the simplest codes adds a constant to the character codes of each of the characters in the message. The constant is the key and the adding mixes the key with the original message data. To see how to do this you simply have to assign each character a number and then add the constant.
The only additional complication is that you have to use modular or “clock” arithmetic so that adding one to 26 takes you back to 1 i.e. z is coded as a in this case.
In this case the code is very easy to break. As soon as you have identified a single letter you can work out the constant, i.e. the key and subtract it from the rest of the cipher text.
Symmetric Key Encryption
It takes quite a bit of work to come up with a process that hides the text and the key well enough to make it difficult to break but it is possible.
Many workable encryption systems are based on this secret key encryption system. As long as the key is kept safe so is the message and here we have the problem.
How do you get the key from the source to the destination without it being at risk.
For example, there would be little point in transmitting the key to a web server just before sending an encrypted credit card number!
One solution is to pay trustworthy couriers to transport keys from one place to another in locked containers. Believe it or not this actually happens for data that has to be protected at the highest level of security. Once the key is safely with the source and the destination then data can be sent with hardly any fear that it can be cracked.
In principle the message is as secure as the key. If the key falls into the wrong hands then the game is up and the message can be read by the wrong person.
This is the way a one "time pad" works - a key as long as the message is used to encode it. Without the one time pad to decode it then it is very difficult to crack the code.
Symmetric key cryptography
This sort of encryption is called symmetric key because the same key is used for coding and decoding.
Symmetric key codes are very popular because they are fast to compute and very safe. In fact modern symmetric key codes are so secure that they don’t rely on keeping the encoding process a secret.
That is, even though you know exactly how the coding/decoding is performed, without the key the only way to decode a message is to try every key.
Two well-known symmetric key codes are DES and IDEA and the precise details of both are freely available. Unless someone is keeping it a big secret then the only way known to crack these codes is to try every possible value of the key.
What this means in practice is that security is proportional to key length. The DES code uses a 56-bit key and, given enough money it is conceivable that you could try all 2^55 combinations (i.e. 36,028,797,018,964,000) in a reasonable time.
Of course when it was invented back in 1975 even a supercomputer of the time would have taken far too long trying every key. Today it is reasonable to assume that government agencies can crack a DES code any time they feel like it.
IDEA, the code in the PGP (Pretty Good Privacy) program, is a suitable replacement for DES and it has a 128-bit key. Even with the computer power available today it is difficult to believe that a 128-bit key can be broken simply by trying every combination. When you try to estimate how long it would take, even with huge numbers of computers on the job, 2^128 is such an enormous number that times greater than the age of the universe are what you usually get!