Cryptography: Theory and Practice:Classical Cryptography

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



Cryptography. Theory and Practice
Modern Cryptography: Theory and Practice
ISBN: 0130669431
EAN: 2147483647
Year: 1995
Pages: 133
Authors: Wenbo Mao

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net