Digital signatures, part 2

This is a continuation of the Digital Signatures overview series.

---

2.0  Cryptography Basics

Cryptography is quite involved, and an in-depth look at it is well beyond our scope. What we'll cover here is a basic view, meant only to explain enough to understand how digital signatures work, and how we can encrypt electronic documents such as email messages. Since encryption is the basis for this, let's start there.

Encryption is simply the process of encoding a message so that it can be read only after decryption. Put as a simple mathematical formula, it means that we have a function (E) that takes plain text (t_p) and turns it into cipher text (t_c):

E(t_p) → t_c

Decryption, then, involves a corresponding function, D, which transforms the cipher text back into plain text:

D(t_c) → t_p

Using an old grade-school substitution cipher, where we replace each letter with the one that follows it, we have this example:

E("hello") → "ifmmp"
D("ifmmp") → "hello"

Of course, such an encryption algorithm is too easy for anyone to decipher; we'd like to make it easy for the intended recipient, but difficult for others. To that end, a great deal of research and development has been done over the years on encryption algorithms, with names like RC4, RSA, DES, and AES. We won't discuss the specific algorithms here, but there are two general mechanisms used in digital encryption: symmetric-key encryption (also called single-key) and public-key encryption.

2.1  Symmetric-Key Encryption

Modern encryption algorithms use a second variable in the general encryption formula, a variable called a key. The purpose of the key is to allow each person to use the same, complex functions as everyone else for encryption and decryption, but to allow the result to vary, preventing outside parties from being able to duplicate the results. That changes the encryption and decryption formulas to these, where "k_e" is the encryption key and "k_d" is the decryption key:

E(k_e, t_p) → t_c
D(k_d, t_c) → t_p

In symmetric-key encryption, the functions are such that the same key is used for encryption and decryption — that is, k_e == k_d.

If I send you a message encrypted with a symmetric-key algorithm, I must also somehow give you the key that was used to encrypt it — and anyone who has that key can decrypt the message and can encrypt others, so we must keep that key secret, between the two of us alone. If I want to exchange secret messages with two people, I need a separate key for each, so that they can't each read the messages that were intended for the other. What's more, if all three of us need mutual secure contact, we need another key that we all share.

Consider, then, a group of four people (a, b, c, and d) who require encryption among them in all combinations. Here are the keys they'd need: k_ab, k_ac, k_ad, k_bc, k_bd,k_cd, k_abc, k_abd, k_acd, k_bcd, k_abcd. That's eleven different keys to be exchanged, managed, and kept secret. Adding a fifth person to the mix raises the number of keys to 26, and with ten people the number is 1013!

Clearly, key management is a tremendous problem, and it gets worse when a key is compromised and needs to be replaced and re-distributed.

Next time: Public-Key Encryption