Cryptography: Theory and Practice Cryptography: Theory and Practice
by Douglas Stinson
CRC Press, CRC Press LLC
ISBN: 0849385210   Pub Date: 03/17/95
  

Previous Table of Contents Next


1.2.1 Cryptanalysis of the Affine Cipher

As a simple illustration of how cryptanalysis can be performed using statistical data, let’s 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:

Table 1.2 Frequency of Occurrence of the 26 Ciphertext Letters
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.

1.2.2 Cryptanalysis of the Substitution Cipher

Here, we look at the more complicated situation, the Substitution Cipher. Consider the following ciphertext:

Table 1.3 Frequency of Occurrence of the 26 Ciphertext Letters
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