Cryptography: Theory and Practice:Classical Cryptography | Modern Cryptography: Theory and Practice

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

Table of Contents

Example 1.8

Suppose the key is K = 8, and the plaintext is

                              rendezvous.

We first convert the plaintext to a sequence of integers:

The keystream is as follows:

Now we add corresponding elements, reducing modulo 26:

In alphabetic form, the ciphertext is:

                             ZVRQHDUJIM.

Now let’s look at how Alice decrypts the ciphertext. She will first convert the alphabetic string to the numeric string

Then she can compute

Next,

and so on. Each time she obtains another plaintext character, she also uses it as the next keystream element.

Of course, the Autokey Cipher is insecure since there are only 26 possible keys.

In the next section, we discuss methods that can be used to cryptanalyze the various cryptosystems we have presented.

1.2 Cryptanalysis

In this section, we discuss some techniques of cryptanalysis. The general assumption that is usually made is that the opponent, Oscar, knows the cryptosystem being used. This is usually referred to as Kerckhoff’s principle. Of course, if Oscar does not know the cryptosystem being used, that will make his task more difficult. But we do not want to base the security of a cryptosystem on the (possibly shaky) premise that Oscar does not know what system is being employed. Hence, our goal in designing a cryptosystem will be to obtain security under Kerckhoff’s principle.

First, we want to differentiate between different levels of attacks on cryptosystems. The most common types are enumerated as follows.

Ciphertext-only

The opponent possesses a string of ciphertext, y.

Known plaintext

The opponent possesses a string of plaintext, x, and the corresponding ciphertext, y.

Chosen plaintext

The opponent has obtained temporary access to the encryption machinery.

Hence he can choose a plaintext string, x, and construct the corresponding ciphertext string, y.

Chosen ciphertext

The opponent has obtained temporary access to the decryption machinery. Hence he can choose a ciphertext string, y, and construct the corresponding plaintext string, x.

In each case, the object is to determine the key that was used. We note that a chosen ciphertext attack is relevant to public-key cryptosystems, which we discuss in the later chapters.

We first consider the weakest type of attack, namely a ciphertext-only attack. We also assume that the plaintext string is ordinary English text, without punctuation or “spaces.” (This makes cryptanalysis more difficult than if punctuation and spaces were encrypted.)

Many techniques of cryptanalysis use statistical properties of the English language. Various people have estimated the relative frequencies of the 26 letters by compiling statistics from numerous novels, magazines, and newspapers. The estimates in Table 1.1 were obtained by Beker and Piper.

On the basis of the above probabilities, Beker and Piper partition the 26 letters into five groups as follows:

1. E, having probability about 0.120

2. T, A, O, I, N, S, H, R, each having probabilities between 0.06 and 0.09

3. D, L, each having probabilities around 0.04

4. C, U, M, W, F, G, Y, P, B, each having probabilities between 0.015 and 0.028

5. V, K, J, X, Q, Z, each having probabilities less than 0.01.

It may also be useful to consider sequences of two or three consecutive letters called digrams and trigrams, respectively. The 30 most common digrams are (in decreasing order) TH, HE, IN, ER, AN, RE, ED, ON, ES, ST, EN, AT, TO, NT, HA, ND, OU, EA, NG, AS, OR, TI, IS, ET, IT, AR, TE, SE, HI, and OF. The twelve most common trigrams are (in decreasing order) THE ING, AND, HER, ERE, ENT, THA, NTH, WAS, ETH, FOR, and DTH.

**Table 1.1** Probabilities of Occurrence of the 26 Letters
letter	probability	letter	probability
A	.082	N	.067
B	.015	O	.075
C	.028	P	.019
D	.043	Q	.001
E	.127	R	.060
F	.022	S	.063
G	.020	T	.091
H	.061	U	.028
I	.070	V	.010
J	.002	W	.023
K	.008	X	.001
L	.040	Y	.020
M	.024	Z	.001

Table of Contents