Public Key Cryptography in Today's Communication
Created | Updated Oct 22, 2007
The fact that we are able to browse h2g2 shows that we live in an information society. We do not trade goods for money (well, not all the time), but we trade information for information. Even a bank account nowadays does not consist of coins and bills, but of bits and bytes. So the more we depend on information the more crucial it is to be able to rely on information. That's when cryptography enters the theatre.
From ancient Greek: cryptos (hidden, secret, clandestine), graphein (to write).
Cryptography - the Art of Writing Secrets
Modern, user-friendly cryptography has two very important benefits; firstly, we can transmit information without anyone else but the designated recipient being able to read it. Secondly, we can receive information without anyone else but the original sender having been able to send it.
With symmetric encryption as DES for example, only one key is used to encrypt and to decrypt the message - hence the name single-key encryption. The downside of this method is that you first need to negotiate a common secret key with your communication partner. If this negotiation or the transmission of the common secret key is intercepted, your communication is compromised. So you have to set up a secure channel for transmitting the secret key. If you have that secure channel for the key, why not use it for communication?
Asymmetric encryption or public key encryption works with pairs of keys. Every participant has a private and a public key. Any message which is encrypted with a private key can only be decrypted with the corresponding public key (and vice versa). By using two different keys a secure channel for exchanging the key is no longer needed, as only the public key would be exchanged.
How Does this Work? Some Maths...
The background of modern, computer-based cryptography is highly mathematical. Two seemingly simple mathematical concepts build the basement: Factorisation and Modulo Arithmetics. A little example can show the strength of factorisation-based cryptography - factorise, ie try to find the prime factors of 1633 without using a calculator. That will keep you busy for quite a while. And now try to calculate 23 x 71 (without a calculator, of course). You'll see that the breaking of the big number is much harder than building it. If some additional information is provided ('factorise 1633, one of the factors is 71'), the breaking speeds up dramatically. If a computer is used for all the calculating, the same speed differences apply. The numbers are just larger.
Modulo arithmetics seem to be very tricky to understand at first glance. The big difference to 'regular' arithmetics is that you have only a limited number space available. The most common example is the 12 hours on a clock. If it's 11am and you wait for five hours, it's going to be 4pm rather than 16am1. If you combine factorisation with modulo arithmetics, you can design some one way functions.
How Does this Work?
One of the most common cryptographic tools is PGP (Pretty Good Privacy). It is an asymmetric or public key cryptosystem. Every participant has a private and a public key; the private key is meant to be kept secret, the public key should be spread all over the world. These two keys are like key and lock to each other. The private key unlocks what the public one has locked, and vice versa.
Keys and padlocks are an excellent description for asymmetric cryptography; if you want somebody to send you a box that can be opened only by you, you give him an open padlock and keep the key. He can close the padlock without any effort, but only you can open it again. If you want the recipient of a box to be sure that it was sent by you, you give him a key and keep the padlock. Once you have locked it, it cannot be opened without the proper key. As you are the only one who can issue that key to the public, the box must have been sent from you.
If Alice sends a message to Bob, she uses her private key to sign it (in fact, she encrypts a kind of 'checksum' of the message) and then she encrypts the results with Bob's public key. Bob receives the message, uses his private key to decrypt it and re-checks the signature ('checksum') with Alice's public key2.
The same thing with 'locks' and 'keys'. Alice writes a message to Bob. She puts it into a box, locked with her private lock (her private key). Then she puts that box into another box, locked with Bobs public lock (his public key). She can use his public lock, as it has been spread all over the world. No one can open the outer box, as only Bob has a key to his public lock. As Bob receives the box, he opens it with his private key. Then he finds the second box, which is locked. As the box is supposed to be sent by Alice, he takes Alice's public key (which has been spread all over the world) from his key ring and opens the box. 'Oh, it fits. Now I know for sure that the message is in fact from Alice.'
The ever present eavesdropper 'Mallory' may have intercepted the message, but what he has got is a meaningless and unbreakable3 letter salad with delicious number dressing, for example:
As the message was sent to Bobs Crypto-Identity (his private key) only the keeper of his private key can read it in plaintext. If he has taken care of his private key, this will be him. The even more important benefit of the whole signature/encryption/decryption/verification - process is the fact that Bob can be sure the message was sent by Alice and has not been tampered with (otherwise the 'checksum' would not be valid). And, if Alice is tempted to deny the message later ('This message is false, it's not mine'), Bob can at least prove that it was signed with Alice's private key, and if Alice does not take proper care of her privates, it's her own fault.
Problem - Key Exchange
How can Alice know that it's Bob's public key that she uses? Frankly, she can't. That seems to be a real drag in cryptography. There are, however, some ways to solve that problem. One is to verify a cryptographical 'fingerprint' (again, that's a kind of 'One Way Checksum' of Bob's key) of Bob's public key by calling him on the phone and letting him read the hexadecimal numbers which make up the fingerprint. That works only if Alice knows Bob's voice without the shadow of a doubt5, and verifying more than a couple of keys on the phone means a lot of work.
Another more common way is the Web of Trust, where key users are kind of introduced to each other by other users they both trust:
Hi, Bob, I'm Alice, you know and trust me. Let me introduce you to Peter, whom I know and trust. I give my word that the person I'm introducing to you definitely is Peter and nobody else.
If Bob trusts Alice, and she gives her word that Peter is OK (ie, she signs Peter's public key with her own private key, so anyone who trusts Alice can verify Peter's key by checking Alice's signature under Peter's key), Bob might as well trust Peter. If he is in doubt, he wait for more people to sign Peter's public key. Researches have been made that no two 'Web-of-Trust' users are more than 7 people apart. (That's what has been reported. As cryptography is a rapidly growing thing, this number may have changed.)
You can compare the web of trust to the human society. Normally you know and trust your parents, your siblings, your friends. They know other people, and you can ask them 'Who's that?' As time goes by you know a lot of people, and you have been asked to introduce someone you know to some other person many times. But to be precise: If someone asks you 'Who's that?' you can answer 'That's Mr Jones.' or you can say 'My brother said that he was told by a reliable person that that's Mr Jones.'
That's very close to paranoia, but you can have paranoia and enemies at the very same time.
Despite of all the problems with key exchange, verification, authentification, and so on, a powerful encryption system, such as PGP, enables us to be pretty sure of 'pretty good privacy' and of pretty authentic messages. It's as simple as putting your snail mail in envelopes instead of writing postcards, and it should become as common. And... PGP is free of charge for private users.