Cryptography: Theory and Practice by Douglas Stinson CRC Press, CRC Press LLC ISBN: 0849385210 Pub Date: 03/17/95 |
Previous | Table of Contents | Next |
As a simple illustration of how cryptanalysis can be performed using statistical data, lets look first at the Affine Cipher. Suppose Oscar has intercepted the following ciphertext:
Example 1.9
Ciphertext obtained from an Affine Cipher
FMXVEDKAPHFERBNDKRXRSREFMORUDSDKDVSHVUFEDK APRKDLYEVLRHHRH
The frequency analysis of this ciphertext is given in Table 1.2.
There are only 57 characters of ciphertext, but this is sufficient to cryptanalyze an Affine Cipher. The most frequent ciphertext characters are: R (8 occurrences), D (7 occurrences), E, H, K (5 occurrences each), and F, S, V (4 occurrences each). As a first guess, we might hypothesize that R is the encryption of e and D is the encryption of t, since e and t are (respectively) the two most common letters. Expressed numerically, we have eK(4) = 17 and eK(19) = 3. Recall that eK(x) = ax + b, where a and b are unknowns. So we get two linear equations in two unknowns:
letter | frequency | letter | frequency |
---|---|---|---|
A | 2 | N | 1 |
B | 1 | O | 1 |
C | 0 | P | 2 |
D | 7 | Q | 0 |
E | 5 | R | 8 |
F | 4 | S | 3 |
G | 0 | T | 0 |
H | 5 | U | 2 |
I | 0 | V | 4 |
J | 0 | W | 0 |
K | 5 | X | 2 |
L | 2 | Y | 1 |
M | 2 | Z | 0 |
This system has the unique solution a = 6, b = 19 (in ). But this is an illegal key, since gcd(a, 26) = 2 > 1. So our hypothesis must be incorrect.
Our next guess might be that R is the encryption of e and E is the encryption of t. Proceeding as above, we obtain a = 13, which is again illegal. So we try the next possibility, that R is the encryption of e and H is the encryption of t. This yields a = 8, again impossible. Continuing, we suppose that R is the encryption of e and K is the encryption of t. This produces a = 3, b = 5, which is at least a legal key. It remains to compute the decryption function corresponding to K = (3, 5), and then to decrypt the ciphertext to see if we get a meaningful string of English, or nonsense. This will confirm the validity of (3, 5).
If we perform these operations, we have dK(y) = 9y - 19 and the given ciphertext decrypts to yield:
algorithmsarequitegeneraldefinitionsofarit hmeticprocesses
We conclude that we have determined the correct key.
Here, we look at the more complicated situation, the Substitution Cipher. Consider the following ciphertext:
letter | frequency | letter | frequency |
---|---|---|---|
A | 0 | N | 9 |
B | 1 | O | 0 |
C | 15 | P | 1 |
D | 13 | Q | 4 |
E | 7 | R | 10 |
F | 11 | S | 3 |
G | 1 | T | 2 |
H | 4 | U | 5 |
I | 5 | V | 5 |
J | 11 | W | 8 |
K | 1 | X | 6 |
L | 0 | Y | 10 |
M | 16 | Z | 20 |
Example 1.10
Ciphertext obtained from a Substitution Cipher
YIFQFMZRWQFYVECFMDZPCVMRZWNMDZVEJBTXCDDUMJ NDIFEFMDZCDMQZKCEYFCJMYRNCWJCSZREXCHZUNMXZ NZUCDRJXYYSMRTMEYIFZWDYVZVYFZUMRZCRWNZDZJJ XZWGCHSMRNMDHNCMFQCHZJMXJZWIEJYUCFWDJNZDIR
The frequency analysis of this ciphertext is given in Table 1.3.
Previous | Table of Contents | Next |
Copyright © CRC Press LLC