It is a frequently expressed view among computer security experts that cryptography must "just work", hidden from the user's view and requiring no special understanding or knowledge.
This text is based on a different proposition: without a good understanding of the fundamentals, an end user will invariably make some seemingly trivial error that will, unknown to him, completely subvert the security of the system. Without knowledge of the fundamentals, it is difficult to differentiate between trivial and significant issues, or between minor and critical errors. Without an understanding of the functionality of the hardware devices and operating system components, and without a similar understanding of cryptography, participation in any activity that requires a high level of digital security is, at best, imprudent. The following text will provide the absolutely minimal level of understanding of public key cryptography that is required for the effective use of GnuPG.
Cryptography is the art of simplifying the management of secrets.
"Classical cryptography" achieves this by reducing the size of a secret. A large volume of text or data that needs to be kept secret (plain-text) is "scrambled", i.e., is processed by a special-purpose algorithm (encrypted) in such a manner that in its processed form (cipher-text) it becomes indistinguishable from a stream of random characters. The encryption process uses a short data string (a key) which defines what operations are carried out on the plain-text in order to transform it into the cipher-text. In addition to that, the very same key also specifies what operations must be carried out in order to transform (decrypt) the cipher-text back into plain-text. Without the key, it is either impossible or extremely difficult to transform the cipher-text back into the plain-text. Cipher-text, of which there might be a very large volume, need not be kept secret; only the key - typically a short string of characters - must be. A "big secret" - voluminous plain-text - is transformed into a "little secret", a short key string, which, by virtue of its size, becomes easier to protect from an adversary.
Over the centuries, a large number of encryption/decryption algorithms (often called cryptographic primitives) have been proposed and extensively studied. This activity accelerated significantly with the advent of digital computers. The purpose of such studies has been, more often than not, the search for methods to defeat the encryption (cryptanalysis); i.e., to turn the cipher-text back into the plain-text without knowledge of the key. The ability of a cryptographic primitive to resist cryptanalysis is referred to as its strength. When a sufficiently easy method of turning cipher-text into plain-text without knowledge of the key has been found, the cryptographic algorithm is considered broken and must be quickly replaced wherever it is used.
There are no methods in existence that would a priory determine the strength of a cryptographic algorithm; the only measure of its strength is the amount of effort that has been devoted to the cryptanalysis of an algorithm without actually breaking it.
If the purpose of encryption is only to safeguard some data at rest, i.e., secret data stored for later use by the same individual who encrypted it, the purpose has been achieved; only the short key must be kept secret between the time of the encryption and decryption. If the purpose of encryption is to exchange some secret data between two individuals, only the key must be transferred from the sender to the recipient in secret; the larger volume of secret data in cipher-text form can be sent to the recipient via an untrusted courier or through a communication channel open to eavesdroppers.
There are two sets of circumstances where the necessity to transmit the key in secret can become a significant problem. The first is obvious: the sender and the recipient can't meet in person to exchange the key and they have no secure channel by which even a small volume of data - the key - can be sent and received securely. The second problem becomes significant only when the number of senders and recipients becomes high. If, for instance, there are a hundred individuals that must communicate in secret, so that the content of communication is kept protected from anyone other than the sender and the recipient, then each individual will have ninety-nine keys that he must transmit in secret, and there will be a total of 9900 (100 participants with 99 keys each) keys that need to be secretly exchanged and kept protected thereafter. As the number of participants grows, the problem of safe transmission and continuous protection of keys becomes harder and harder to solve adequately and reliably.
While describing "classical cryptography", it was stated that the same key specified both the encrypt, as well as the decrypt operations. This, indeed, was the only method by which cryptography was performed for centuries. However, in the second half of the last century, a novel set of algorithms was invented. These use one key to encrypt the data, and a related but entirely different key to decrypt the data.
An analogy to these algorithms might be a strong mailbox, with two openings: the first being a narrow "slot" through which a sheet of paper with a message written on it can be inserted into, but not retrieved from the mailbox. Additionally, the mailbox has a large opening through which all sheets of paper in it can be retrieved in order to be read. Both openings have a cover, protected by different locks, having different keys.
Any number of copies of the key that protects the insertion slot (encryption key, public key) can be made and can be given freely to anybody who wants to send secret messages to the mailbox owner. The mailbox owner is however the only one that possesses the key to the large opening through which messages can be retrieved in order to be read (decryption key, private key, secret key). If the box is physically strong enough, it can be placed unattended at the street corner or it can be sent on message collection rounds by an untrusted courier - as long as the private key is safely in the exclusive possession of the mailbox owner. There is no need for any secure exchange of the keys. Public keys can be distributed with no restrictions; for convenience, they might even be given out by the courier who transports the mailbox. Each participant needs to safeguard only one key: his own private, secret, decryption key.
In the computer implementation of such scheme, the public and private keys are dependent on each other, and they must be created by a single process. However, the private key should be (next to) impossible to create from the known public encryption key. Public keys can be known to everybody - this is why this method of encryption and decryption is known as public key cryptography. Since it uses two different keys, one for encryption and another for decryption, this type of cryptography is also known as asymmetrical cryptography, in contrast to the classical, single-key, or symmetrical cryptography.
It might appear that the public key cryptography is the perfect solution to the previously mentioned problems of key-distribution and key management. In practice however, public key cryptography is burdened with its own imperfections and problems.
The first problem of public key cryptography is that its algorithms are relatively new inventions and that their strength is consequently still in some doubt. But even if and when they are considered "secure enough", they are slow and can encrypt only relatively short messages; much too short to be of use for the secure transmission of even a single page of secret text. Consequently, the only practical way to use public key cryptography is in a "hybrid mode". The message is first encrypted using a symmetrical algorithm with a random, on-the-spot generated, message-specific key (session key). This key is then encrypted with the recipient's public key using an asymmetric algorithm, and sent, in this encrypted form, along with the message cipher-text, to the recipient. The recipient must first decrypt the session key using his private key, and then use the decrypted session key to decrypt the full volume of the cipher-text using a symmetrical algorithm.
The second problem of public key cryptography is much more difficult to solve. It has to do with the authenticity of the public key, and we will again use the physical mailbox analogy to describe it.
If the mailbox courier is the one who provides the message senders with the public key, he could easily defeat the security of the channel by carrying not one, but two boxes: one that belongs to the recipient, and his own. He presents the sender with his own box, pretending it is the one that belongs to the recipient, and instead of the recipient's public key, he provides the one that protects the insertion slot of his own box. Once safely out of the sender's view, he opens his box (to which he has both keys!), reads the message, and then places it into the recipient's mailbox: its encryption key is known to everybody, including the courier. This method of attack is often called man-in-the-middle, as the mailbox courier (or the communication channel operator) is no longer just a passive transporter, but instead an active adversary who operates clandestinely between the sender and the receiver. In order to prevent the man-in-the-middle attack, there must be a method by which the sender can authenticate the key: i.e., ensure that the public key which he obtained, by whatever means, is indeed the one created by the intended recipient of the message.
To utilize our physical mailbox analogy for one last time, we will assume that the recipient does not only create a pair of physical keys, but that immediately thereafter he measures the depth of indentations of the public key (i.e., the one that opens the message insertion slot). These measurements, represented by a series of numbers (key fingerprint) uniquely describe the key. If they are passed on to the message sender, he can take the same measurements of the key given to him by the mailbox courier, and compare the numbers (authenticate the key). If the numbers do not match, then he knows that whoever provided the him with the message recipient's public key is attempting to subvert the security of the system.
The public key owner must find a way to ensure that every user of the key has, in his possession, the fingerprint that can be used to authenticate the key. Just like the public key itself, the fingerprint need not be distributed in secret. If it is not transferred in direct personal contact between the sender and the recipient, it must be transferred via a channel which, while possibly open to an eavesdropping adversary, does not allow him to change the information flowing through it, and which does not allow the adversary to impersonate the key owner. (The conventional telephone system comes rather close to this description). If the message recipient is a public persona, he might publish the key and its fingerprint on his or her contact web page. While it would be simple enough for an adversary to forge the fingerprint "in transit" when the page is accessed, it becomes next to impossible to know exactly when to forge and when not to: the page author himself, as well as possibly a large number of his followers are likely to keep verifying the content of the page by accessing it from multiple, different and anonymous network end-points.
Alternative methods of "remote" public key authentication have also been proposed and implemented, but without complete success. For instance, if the sender and the recipient have someone they both trust, (a trusted third party) that can sign both the public key and with it some information positively identifying the key owner, the signed public key might be considered authenticated and safe to use. Instead of one unreservedly trusted person (or institution), this signing can be done by a large number of individuals, who can sign each other's public keys based on their knowledge of the identity of the individual who requests that their public key be signed. While a sender, who is in possession of a public key with a large number of signatures might not trust any of those signatures, there will likely exist a "chain" of signatures that, over a series of other public keys signed by multiple and different signatories, "leads back" to an individual who is completely trusted by the message sender. This network of multiple public keys, with signatures by numerous, somewhat or partially trusted individuals is called a web-of-trust. It provides a source of information by which the trustworthiness of any given public key can be measured, and the use or rejection of a public key can be decided based on such a measure of trustworthiness.
Both alternative methods of public key authentication (trusted-third-party and web-of-trust) are in current use. However, neither has been proven adequate in practice. Trusted third parties have been cought breaking the trust, either by incompetence or by legal or extra-legal coercion. The web-of-trust, on the other hand, results in such an extraordinarily complex system and a large set of arcane operational rules, that it is of little or no practical value. There is another, even more serious liability of the web-of-trust: the repertoire of signatures on public keys provides the adversary with a wholesale list of self-identified individuals who believe they have a need to communicate in secret and the precise knowledge of their interconnections. In almost any human activity that requires secure communication, such knowledge is typically of greater value to an adversary than is the content of any specific secret message. This is especially true when the adversary has at his disposal methods of coercion for the production of private keys.
All security-related computer applications which are commonly referred to as "public key systems" are, as explained before, actually hybrid systems. When the strength of the underlying mathematical cryptography in a security application is considered, it must always be understood that a hybrid system depends on three critical primitives: the symmetric algorithm, the generation of the random session key and the asymmetric algorithm. In contrast, a purely symmetric system is dependent on only one cryptographic primitive: the symmetric algorithm.
In summary:
Whenever there is a choice, symmetrical encryption is preferable to hybrid.
If hybrid encryption can not be avoided, the public key fingerprint must be reliably communicated by the owner to the sender without dependence on intermediaries.
What are the benefits of a hybrid cryptosystem over a symmetric one?
Hybrid cryptosystems require no secret key exchange, only a positive authentication of the public key. This positive authentication might not be trivial, but it will invariably be simpler than the secret exchange of a symmetric key. Indeed, the solution of the problem of the secret exchange of a symmetric key is the essence of a hybrid system.
The total number of keys that must be protected from an adversary in the operation of a multi-user hybrid system is significantly smaller than the similar number in a symmetric system. Each participant in a hybrid system must protect only one key: his own.