The way to write a digital signature is to perform some action on data provided by the other party that only you could have performed, thereby proving you are who you say. We will look at what this action might be, as follows.

So the "action" mentioned earlier, to prove you are who you say you are, would be to encrypt some piece of text using your private decryption key. Anyone can then decrypt it using your public key. If it decrypts to meaningful text, it came from you, otherwise not.

For instance, let's apply the technology to a simple matter of the heart. You subscribe to a lonely hearts newsgroup where people describe their attractions and their willingness to engage with persons of complementary romantic desires. The person you fancy publishes his or her public key at the bottom of the message describing his or her attractions. You reply:

I am (insert unrecognizably favorable description of self). Meet me behind the 
bicycle sheds at 00.30. My heart burns .. (etc.)

You encrypt this with your paramour's public key and send it. Whoever sees it on the way, or finds it lying around on the computer at the other end, will not be able to decrypt it and so learn the hour of your happiness. But your one and only can decrypt it and can, in turn, encrypt a reply:

YES, Yes, a thousand times yes!

using the private key and send it back. If you can decrypt it using the public key, then you can be sure that it is from the right person and not a bunch of jokers who are planning to gather round you at the witching hour to make low remarks.

However, anyone who guesses the public key to use could also decrypt the reply, so your true love could encrypt the reply using his or her private key (to prove he or she sent it) and then encrypt it again using your public key to prevent anyone else from reading it. You then decrypt it twice to find that everything is well.

The encryption and decryption modules have a single, crucial property: although you have the encrypting key number in your hand, you can't deduce the decrypting one. (Well, you can, but only after years of computing.) This is because encryption is done with a large number (the key), and decryption depends on knowing its prime factors, which are very difficult to determine.

The strength of PK encryption is measured by the length of the key, because this influences the length of time needed to calculate the prime factors. The Bad Guys (see the second footnote in Chapter 1) and, oddly, the American government would like people to use a short key, so that they can break any messages they want. People who do not think this is a good idea want to use a long key so that their messages can't be broken. The only practical limits are that the longer the key, the longer it takes to construct it in the first place, and the longer the sums take each time you use it.

An experiment in breaking a PK key was done in 1994 using 600 volunteers over the Internet. It took 8 months' work by 1,600 computers to factor a 429-bit number (see PGP: Pretty Good Privacy by Simson Garfinkel [O'Reilly, 1994]). The time to factor a number roughly doubles for every additional 10 bits, so it would take the same crew a bit less than a million million million years to factor a 1024-bit key.

Something, somewhere had improved by 2000, for a Swedish team won a $10,000 prize from Simm Singh, the author of the The Code Book (Anchor Books, 2000), for reading a message encrypted with a 512-bit key. They used 70 years of PC time.

However, a breakthrough in the mathematics of factoring could change that overnight. Also, proponents of quantum computers say that these (so far conceptual) machines will run so much faster that 1024-bit keys will be breakable in less-than-lifetime runs.

We have to remember that complete security (whether in encryption, safes, ABM missiles, castles, fortresses...) is an impossible human goal. The best we can do is to slow the attacker down so that we can get out of the way or she loses interest, gets caught, or dies of old age in the process.

The PK encryption method achieves several holy grails of the encryption community:

The discoverers of public-key encryption must have thought it was Christmas when they realized all this. On the other hand, PK is one of the few encryption methods that can be broken without any traffic. The classical way to decrypt codes is to gather enough messages (which in itself is difficult and may be impossible if the user cunningly sends too few messages) and, from the regularities of the underlying plain text that shows through, work back to the encryption key. With a lot of help on the side, this is how the German Enigma codes were broken during World War II. It is worth noticing that the PK encryption method is breakable without any traffic: you "just" have to calculate the prime factors of the public key. In this it is unique, but as we have seen earlier, that isn't so easy either.

Given these two numbers, the public and private keys, the two modules are interchangeable: as well as working the way you would expect, you can also take a plaintext message, decrypt it with the decryption module, and encrypt it with the encryption module to get back to plain text again.

The point of this is that you can now encrypt a message with your private key and send it to anyone who has your public key. The fact that it decodes to readable text proves that it came from you: it is an unforgeable electronic signature.

This interesting fact is obviously useful when it comes to exchanging money over the Web. You open an account with someone like American Express. You want to buy a copy of this excellent book from the publishers, so you send Amex an encrypted message telling them to debit your account and credit O'Reilly's. Amex can safely do this because (provided you have been reasonably sensible and not published your private key) you are the only person who could have sent that message. Electronic commerce is a lot more complicated (naturally!) than this, but in essence this is what happens.

The technology exists to make this kind of encryption as uncrackable as PK: the only way to attack a good system is to try every possible key in turn, and the key does not have to be very long to make this process take up so much time that it is effectively impossible. For instance, if you tried each possibility for a 128-bit key at the rate of a million a second, it would take 10²⁵ years to find the right one. This is only 10¹⁵ times the age of the universe, but still quite a long time.

11. Security		11.3. Certificates