Public key encryption is vital to the working of the Internet and the commercial web in particular. We look at how it works and explain the RSA system in detail and wonder about its future.

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 times 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.  You can easily identify a single letter just by finding the code symbol that occurs most frequently and identifying it as the letter "e" (assuming that the original text is in English.) 

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 AES 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⁵⁵ 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.

AES Advanced Encryption Standard is the generally accepted replacment for DES and it has a 128, 192 and 256 bit keys. 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!

Public key cryptography

Modern symmetric key cryptography works very well but it suffers from the problem of transporting the keys and keeping the keys secret. Imagine that you want to buy something from a website. If you want to send your credit card number using a symmetric cipher then either you have to send the website your key or it has to send you its.

Forget for a moment the transport problem which could presumably be solved by sending a letter, i.e. using the post, or by paying it a visit in person. If

key transport were the only way to make things work even existing institutions like banks would take on the job of securely transporting keys – for a fee of course!

Even if you can transport keys there is still a problem – once the website has your key it can use it to encode information to be sent to you and decode information you send to it but it can also use it to decode any message you send using that key!

The key both locks and unlocks the message and it doesn’t matter whom the message was intended for. What this means is that you would need to set up a different key for every website you wanted to work with.

So many keys are bound to make the system less secure and error prone and it is lucky for us that there is an alternative.

Public key encryption seems so unlikely a process that you have to see it in action to believe that it works!

The basic idea is that now we have two keys – a public key and a private key.

The public key can be freely handed out to anyone who wants it and it is used to code a message and send it to the destination.

The magic is that the coding procedure mixes up the message and the public key in such a way that even knowledge of the public key doesn’t help in the task of unmixing.

To unmix the public key and the message you need a second key – the private key – which is, of course, kept secret. Using the private key you can easily undo the mixing and retrieve the message.

Not only does the encryption process hide the original text in a way that cannot be undone by the public key even knowledge of the public key doesn’t give any clue as to what the private key, its unique counterpart, might be.

This is all very mysterious! How exactly does this work?

The whole thing relies on an idea called a "trapdoor" function. This is a function of the data that is very difficult to reverse - in other words the inverse function is much more difficult to compute than the function itself. However in some cases if you provide a tiny bit of extra information then finding the inverse function becomes easy.

First recall that a prime number is one that doesn’t have any factors – so 7 is prime as no integer exactly divides it but 9 isn’t because it is divisible by 3. Now to multiply two primes together e.g. 3 times 7 giving 21 then to compute the function all I need is simple multiplication.

To perform the inverse operation I have to find the prime factors of 21 and this is more difficult and it gets much more difficult as the size of the numbers involved goes up. Essentially the only direct way of doing it is to try each of the primes in turn until you find one that divides the number exactly.

However if I tell you that one of the primes was 3 all you have to do is divide by three to recover the 7. The problem of prime factoring has a "trap door" that leads you straight to the answer if you know one of the primes involved.

There are a number of public key systems based on exactly this prime factor principle and one of the best known is the RSA cipher so lets take a look at this in detail.

<ASIN:1857028899>

<ASIN:0192803158>