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.

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 Control^{1)} 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.

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.

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é