Cryptographic Basics

All modern crypto systems depend on keys. A key is a value required to recover the message. Without burying you in the mathematics of cryptography (if you wish to delve further, the book Applied Cryptography , by Bruce Schneier, is an excellent resource), the idea is to employ a mathematical function that is very easy to use in combination with the key but is impossible to use without it. Such a function is called a one-way function. Use that term and people will think you know a lot about cryptography. Try it! It works!

A cryptographic system that requires that both parties in the communication know and use the same key is called a symmetric-key cryptographic system. There are quite a few of these systems. The widely used (but no longer terribly secure) U.S. Data Encryption Standard (DES) is a 56-bit key symmetric-key cipher.

GPG uses a newer and, in some ways, more useful cryptographic system. With GPG, you generate two keys. One key you keep secret. This is called a private key. The other key you give away. You don't care who has this key. Go ahead and give it to your enemies. This key is known as your public key.

To decrypt a message requires both your public and private keys. To encrypt it requires only your public key. So anyone can send you a message encrypted with your public key, but you and only you can decrypt such a message ( assuming you have kept your private key properly private). Such a system is called a public-key cryptographic system.

If this were all you could do with a public-key crypto system, it would be little better than a symmetric one. It turns out that a public-key cypto system has one more very appealing use. You can "sign" a message with your private key. Once this is done, anyone with your public key can validate that the message is yours and that it is exactly the message you sent, with not a comma changed.

This is done by applying a message hashing algorithm to the message. A hashing algorithm is any function that takes an arbitrarily large and complex set of data and produces a fixed-size result. A function that sums all the bytes in a message and takes the low-order 8 bits of that sum would qualify as a hashing algorithm, albeit a relatively usesless one. Hashing functions have many applications in computer science, from sorting to databases, but we are concerned with their applicability to digital signatures.

For digital signatures we must have a function such that it is impossible for any two differing messages of the same length to have the same hash value. It turns out there are a number of such so-called message digest functions.

So to sign a message, we calculate the message digest value on the message. We then encrypt the hash value with our private key. This encrypted hash of the message serves as a signature. When our recipient gets this message, she calculates the hash of the message as received, decrypts the signature with her copy of our public key, and then compares the two values. If they match, it is absolutely certain both that the message was signed with our private key (or else our public key will not have been able to decrypt it) and that the message was not changed in any way (or the match would have failed).

The success of digital signatures depends entirely on the "split" private key/public key pair. A symmetric cryptographic system could not be used to validate identity in this way. The system depends on one and only one party in the communication having the private key.

One very important attribute of public key/private key pairs is that it is difficult if not impossible to derive one key given the other in the pair. In other words, you need two values that are easy to generate but difficult to derive. A number of algorithms for such have been put forward, but many, such as the "knapsack" algorithm, have proven to be flawed. The system used in all common public-key cryptographic systems is based on the product of primes.

Basically, it is very easy to multiply two very large prime numbers together, but it is very difficult to factor the resulting large number. Remember, GPG keys are from 512 to 2048 bits. These are truly huge numbers.

The public and private keys are not merely the two prime factors of a very large number. There are additional transformations applied to them to arrive at the key values, but the principle is the same. It's easy to make them, hard to break them. Merely possessing one half of the keypair confers no advantage in deriving the other. That is the main point.

These descriptions are somewhat simplified ”there are some additional complexities in the actual implementation. We'll address those as we come to them.