niulogo

Overview of PGP

PGP stands for "pretty good privacy". It was originally devised by Phil Zimmermann in the early 1990s, when the use of strong cryptography was hampered by export laws, patents and other restrictions. Some history and more details can be found at the international PGP site.

Since then the restrictions have largely disappeared, and many people are using software based on the original idea. One of such packages is the commercial PGP, which is now owned and marketed by Network Associates. Another one is the GNU Privacy Guard, based on an "Open PGP" standard, and mostly (but not totally) compatible with PGP. We will use "PGP" as a generic term describing the process, rather than specific implementation. See this document for a brief introduction to GNUPG on our system.

What does PGP do?

It provides a practical and fairly easy to use implementation of the idea of "asymmetric", or "public key" cryptography (PKC) invented by Diffie and Hellman, and developed further by Rivest, Shamir and Adleman who went on to form the famous corporation "RSA Associates".

In "symmetric" ciphers (and most spy novels) both sides know the secret (algorithm, and/or password) needed to encrypt and decrypt messages. In asymmetric ciphers there is an imbalance. Each person has two separate "keys", i.e. functions that can be applied to chunks of messages: a secret key S, and a public key P.

The message is split into chunks or transformed in some way so we can assume that the data we operate on are all in some mutually agreed upon, large but manageable, domain D, e.g. all integers expressible as 1024 bit words w.

Then S and P are selected to be functions from D to D which are inverses of each other.

My Control1) in London publishes his public key P on the Internet, or in a newspaper ad, or gives it to me by phone, or sends it in a letter. When I have something to report to him, I apply P to each word w of my message, and send all the P(w) to him. He then applies S to my P(w)'s, and gets the original w's back, thus reconstructing the text.

This has the tremendous advantage in that the public key can be easily distributed, i.e. my handler doesn't have to fly to Kyrgistan with a fake passport and beard to meet with me.

But it is also tricky, since it calls for a particular type of P and S: knowing what P is (e.g. by intercepting enough of my P(w)'s) must not be sufficient to figure out what S might be. At the same time the knowledge of an additional secret ought to make S easy and fast to calculate. Functions of this type are sometimes called "trapdoor functions". Easy to calculate one way, very hard to invert by "brute force", and easy to invert given one more piece of information.

One such scheme is (very roughly) to rely on the fact that if you know the factorization of a huge integer n into two large primes p and q, and you design the functions so that computing P relies on knowing pq while computing S efficiently requires the knowledge of p, then you can safely publish P (or the product pq); but anyone trying to find S would have to factor your pq first. So computing values of S might take miliseconds when p and q are known, but decades may be needed to find p and q given only pq.

In practice the computations involved are more complex (hence slower) than in various traditional symmetric ciphers, so -- especially in high-speed real-time applications -- this scheme is only used in the first stages of the transaction, to establish the secret channel. After that the two sides typically agree on some symmetric code, exchange the keys for it, and proceed in a more traditional way.

What else can this do?

One of the very useful features of public key cryptography is the ability to sign messages. Suppose that I use Control's public key to encrypt a message to him. But then I take a mutually agreed upon piece of information, such as his public key k itself, and I encrypt it using my secret key S, i.e. compute S(k). I then append it to the message. At the other end Control detaches this last piece, and applies my public key P to it, getting P(S(k)) = k back. If the k that he got is identical to what was agreed, e.g. his public key, then he can be very highly confident that the message came from me, since only I could have applied S to k.

Even better, given my plaintext message M that I'm about to encrypt, I can first compute its "checksum", or "digest": a practically unique value which depends highly on the contents of the message. There are several algorithms for generating such "fingerprints"; one of them is md5, which -- say -- applied to a program I just compiled gives the hex value 200cb533aa1f81c6aeb468573df418ac. In the future if I have any suspicion that someone tampered with that program, or that it was damaged during copying etc., I can compute this checksum again. The checksum will be different (with extremely high probability) if even a single bit in that file has changed. In other words even though md5 cannot be a one-to-one function (since its domain, all files of finite length, is much larger than the range, all 32-digit hex numbers), it is in practice one-to-one -- in that the probability of md5(M) = md5(N) with M distinct from N is infinitesimally low for any two messages M and N which can be reasonably considered to be valid in a specific context (e.g. two computer programs that actually compile, or two files which can be opened in Excel as spreadsheets).

So if in the process above I compute the checksum of the original message, md5(M), then I use that as the k used in signing, the recipient will be able to recover the k that I computed, and he can compute his own checksum of the message that he decoded. If the two match, then he will not only be sure that I sent the letter (because only I could compute S(k)), but he will have extremely high confidence that the message is a true copy of what I sent (otherwise the checksum he computed would almost certainly differ from the one I sent). This is how one can verify the integrity of messages, which is extremely important in banking, transmitting computer code, etc.

Practical considerations

In various implementations, such as PGP, one weak link is that the secret key has to reside somewhere, usually on disk, on a computer that is typically connected to the Internet, and is often used by many people. So it is crucial to protect the key from prying eyes. The way it normally works is that the secret key (or rather the "keyring", because one might have different keys corresponding to different "personalities") is itself stored in encrypted form, and the information in it is extracted only when it's needed, after you give a correct passphrase which unlocks it. Otherwise anyone with sufficient privileges (e.g. the system administrator) would have access to your secret key.

So it's essential to come up with a good password (it can be much longer than typical passwords, so it's easy to pick something good), and to make sure that it is used on a machine which is reasonably secure. On a public unprotected PC, for example, a passerby could have installed a "keystroke sniffer" which is reporting what you type (e.g. the passphrase) to some remote location, and all the encryption and secrets are then worth nothing.

Another point is that when I download the other person's public key, I should somehow make sure that it is a real thing, i.e. that it corresponds to the secret key which only that person has. Otherwise I could be lured into using a key generated by the Kyrgistan secret police, and when they intercept my code they will be able to read it. This involves developing trust between key holders.

For example, after I have verified (over the phone or in person) that I have Control's genuine public key, PGP allows me to sign Control's public key with my secret key. Then someone who knows me and trusts me to be a reliable "certifier" (e.g. not a double agent), can similarly verify that he has my authentic public key. Then he can grab Control's key off of the Web and check that my signature on it is indeed mine. From then on this third party can trust Control's key without bothering to verify it personally. This is all made easier with "key fingerprints", i.e. relatively short checksums similar to md5 mentioned above -- one can just verify the fingerprint instead of the several hundred characters of a typical public key.

Last but not least, most implementations such as PGP or GNUPG combine encryption with good compression, so that encrypted files are not only safe from prying eyes but also smaller than the originals.


1) See for example any book by John LeCarré