Computer Security: Art and Science

9.1 What Is Cryptography?

The word cryptography comes from two Greek words meaning "secret writing" and is the art and science of concealing meaning. Cryptanalysis is the breaking of codes. The basic component of cryptography is a cryptosystem.

Definition 9�1. A cryptosystem is a 5-tuple (E, D, M, K, C), where M is the set of plaintexts, K the set of keys, C is the set of ciphertexts, E: M x K C is the set of enciphering functions, and D: C x K M is the set of deciphering functions.

EXAMPLE: The Caesar cipher is the widely known cipher in which letters are shifted. For example, if the key is 3, the letter A becomes D, B becomes E, and so forth, ending with Z becoming C. So the word "HELLO" is enciphered as "KHOOR." Informally, this cipher is a cryptosystem with:

M = { all sequences of Roman letters }
K = { i | i an integer such that 0 i 25 }
E = { E_k | k K and for all m M, E_k(m) = (m + k) mod 26 }

Representing each letter by its position in the alphabet (with A in position 0), "HELLO" is 7 4 11 11 14; if k = 3, the ciphertext is 10 7 14 14 17, or "KHOOR."

D = { D_k | k K and for all c C, D_k(c) = (26 + c � k) mod 26 }

Each D_k simply inverts the corresponding E_k.

C = M

because E is clearly a set of onto functions.

The goal of cryptography is to keep enciphered information secret. Assume that an adversary wishes to break a ciphertext. Standard cryptographic practice is to assume that she knows the algorithm used to encipher the plaintext, but not the specific cryptographic key (in other words, she knows D and E). She may use three types of attacks:

In a ciphertext only attack, the adversary has only the ciphertext. Her goal is to find the corresponding plaintext. If possible, she may try to find the key, too.
In a known plaintext attack, the adversary has the ciphertext and the plaintext that was enciphered. Her goal is to find the key that was used.
In a chosen plaintext attack, the adversary may ask that specific plaintexts be enciphered. She is given the corresponding ciphertexts. Her goal is to find the key that was used.

A good cryptosystem protects against all three types of attacks.

Attacks use both mathematics and statistics. The statistical methods make assumptions about the statistics of the plaintext language and examine the ciphertext to correlate its properties with those assumptions. Those assumptions are collectively called a model of the language. Figure 9-1 presents a character-based, or 1-gram, model of English text; others are 2-gram models (reflecting frequencies of pairs of letters), Markov models, and word models. In what follows, we use the 1-gram model and assume that the characters are chosen independently of one another.

Figure 9-1. Table of character frequencies in the English language, from Denning [269], Figure 2.3, p. 65.

graphics/09fig01.gif

Top