Cryptographic Basics
All modern crypto systems depend on keys. A
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
changed.
This is done by applying a
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.
No comments:
Post a Comment