Sebery J.Cryptography.An introduction to computer security.1989

3.1 Classical Ciphers

71

If we use this conversion, then encryption in the above cipher can be de ned

as

c = Ek(m) = m + 3 (mod 26): The decryption is

m = Dk(c) = c

3 (mod 26)

Notice that the cipher does not have any key! The integer 3 which determines the rotation is xed (and perhaps known to the cryptanalyst). If we replace the integer by the key, we get the Caesar cipher.

The cryptanalysis of the cipher is easy { there are 26 possible keys only. In Figure 3.2 we have a histogram of the percentage frequency of English characters in text. In Figure 3.3 this has been shifted using the Caesar cipher with k = 3. So if a ciphertext is given, it is easy to get frequency of characters in the ciphertext and compare it with the frequency of the language. So having the ciphertext

L FDPH L VDZ L FRQTXHUHG it is easy to nd out that k = 3 and the plaintext is:

I CAME I SAW I CONQUERED

Caesar cipher

Message Space: M = f0; 1; : : : ; 25g { letters converted to their positions in the alphabet.

Cryptogram Space: C = f0; 1; : : : ; 25g.

15

10

5

0 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

Fig. 3.2. English character frequencies

72 3 PRIVATE-KEY CRYPTOSYSTEMS

Key Space: K = f0; 1; : : : ; 25g, j K j= 26 and H(K) 4:7.
Encryption: c = Ek(m) = m + k				(mod 26).
Decryption: m = Dk(c) = c			k	(mod 26).
	H(K)
Unicity Distance: N		1:5 letters (assuming D = 3:2).
	D

Cryptanalysis: Uses letter frequency distributions. If encipherment is achieved by a simple letter shift then a frequency count of the letter distributions in the ciphertext will yield the same pattern as the original host language of the plaintext but shifted.

3.1.2 AÆne Ciphers

This is a generalization of the Caesar cipher obtained by numbering the letters of the alphabet and then multiplying the number of the letter to be enciphered by k1 where gcd(k1; 26) = 1 and adding a constant k2. The answer is then reduced modulo 26. Figure 3.4 shows what happens to the histogram of Figure 3.2 when the aÆne cipher c = Ek (m) = k1m + k2 (mod 26) is applied with k1 = 5 and k2 = 7.

Decryption m = D	(c) = (c		k	)k 1	(mod 26) recovers the message m
k			2	1

from the cryptogram c. It works only if k1 has its inverse k1 1 or equivalently, gcd(k1; 26) = 1.

Suppose we have to decipher:

WZDUY ZZYQB OTHTX ZDNZD KWQHI BYQBP WZDUY ZXZDSS we note that:

15

10

5

0 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

Fig. 3.3. Encryption character frequencies with c = m + 3 (mod 26)

3.1 Classical Ciphers

73

15

10

5

0

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

Fig. 3.4. Encryption character frequencies with c = 5m + 7

Z occurs 8 times

D occurs 5 times

Yoccurs 4 times

W, Q, B occur 3 times each

Assuming the language is English, we note that the most frequently occurring letters in English text are, in order:

E, T, R, I, N, O, A

This leads us to try Z ! E and D ! T or Y ! T. That is, we try to simultaneously solve,

25	4k1 + k2	(mod 26)	or	25	4k1 + k2	(mod 26)
3	19k1 + k2	(mod 26)		24	19k1 + k2	(mod 26)

which have as solution k1 = 2, k2 = 17 in the rst case (we reject it as k1 1 does not exist) and k1 = 19, k2 = 1 in the second. If we try to decipher the letters WZDUY (the integers 22, 25, 3, 20, 24) using (c k2) k1 1, which, in this case, is (c 1) 19 1 or (c 1) 11, we will get the following plaintext

23, 4, 22, 1, 7 or XEWBH

which is not a part of any recognizable English expression or word. In fact, we could try all combinations Z ! E with other letters and nd that, in fact, Z does not map to E.

After much trial and error, we would nd that Z ! O (we would expect the most common letter to be a vowel). Now let us try Z ! O and D ! T or Y ! T. That is, we simultaneously try to solve,

74	3 PRIVATE-KEY CRYPTOSYSTEMS
		25	14k1 + k2	(mod 26)	or	25		14k1 + k2	(mod 26)
		3	19k1 + k2	(mod 26)		24		19k1 + k2	(mod 26)
which have solutions k1 = 6 and k2 = 19 or k1 = 5 and k2 = 7.
	Now if we use the second of these to decode,
			WZDUYZ (the integers 22, 25, 3, 20, 24, 25)
using (c k2) k1 1 = (c				7) 21, we get 3, 14, 20, 13, 19, 14 or DOUNTO which
is recognizable as the words DO UNTO. We leave the reader to decipher the
remainder of the message.

AÆne cipher

Message Space: M = f0; 1; : : : ; 25g { letters converted to their positions in the
alphabet.
Cryptogram Space: C = f0; 1; : : : ; 25g.
Key Space: K = fk = (k1; k2) j k1; k2				2 f0;1; : : : ; 25g; gcd(k1; 26) = 1g, j K j=
312, H(K) 8:3.
Encryption: c = Ek(m) = k1m + k2				(mod 26).
Decryption: m = Dk(c) = (c			k2)k1 1	(mod 26)
Unicity Distance: N	H(K)
	D	2:6 letters (D = 3:2).

Cryptanalysis: Uses letter frequency distributions. The letter frequencies are still preserved but permuted according to the secret key k = (k1; k2).

3.1.3 Monoalphabetic Substitution Ciphers

It is a common practice to use a secret word or words, not repeating letters, and write them in a rectangle to use as a mnemonic to translate plaintext into ciphertext. Suppose the secret words were STAR WARS. We note that STAR WARS has the letters A, R and S repeated so we use only the letters S, T, A, R, W. We write these rst and then ll out the rectangle with the unused letters of the alphabet:

S T A R W

B C D E F

G H I J K

L M N O P

Q U V X Y Z

3.1 Classical Ciphers

75

Columns are then read o to give us the following plaintext to ciphertext transformation:

0	1	2	3	4	5 6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21 22 23	24	25
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
S B G L Q Z T C H M U A D I													N V R E J					O X W F K P Y

Thus,

I KNOW ONLY THAT I KNOW NOTHING

becomes:

H UINF NIAP OCSO H UINF INOCHIT

The above cipher is a substitution cipher. The nice property of it is that the secret permutation can be readily reconstructed from a relatively short and easy to memorize word or sentence. A general instance of a substitution cipher can be obtained if the secret word consists of a random permutation of 26 letters. Unfortunately, such a secret is diÆcult to learn by heart. Mathematically, the secret key is the permutation : Z26 ! Z26, where Z26 = f0; 1; : : : ; 25g. A message m 2 Z26 is encrypted into c = (m). The decryption is m = 1(c) where 1 is the inverse permutation of .

Cryptanalysis uses frequency analysis on the letters of the alphabet. Short amounts of ciphertext can readily be attacked by computer search but even reasonable amounts of ciphertext are easy to decipher by hand. For example, to decipher

BRYH DRL R ITEEIA IRBS TEF CIAAXA NFR NDTEA RF FGKN RGL AOAYJNDAYA EDRE BRYH NAGE EDA IRBS NRF FMYA EK ZK TE CKIIKNAL DAY EK FXDKKI KGA LRH NDTXD NRF RZRTGFE EDA YMIAF,

we do a frequency analysis and note the following distribution of letters:

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

17 4 2 10 13 10 5 3 9 1 9 4 2 9 1 15 2 6 3 6 2

So the most frequent letters are:

A, R, E, D or F, I or K or N

D

H(K)

76 3 PRIVATE-KEY CRYPTOSYSTEMS

There is a one letter word so R is I or A. The two most common three letter words in English are THE and AND. So we guess EDA is one of these. Since the most common letters in English are

E, T, R, I, N, : : :,

we will guess EDA is THE and that R is A so our message becomes:

BaYH HaL a ITttle IaBS TtF CIeeXe NaF NhDte aF FGKN aGL eOeYJNheYe that BaYH NeGT the IaBS NaF FMYe tK ZK Tt CKIIKNeL heY tK FXhKKI KGe LaH NhTXh NaF aZaTGFt the YMIeF.

Which resolves to:

mary had a little lamb its eece was white as snow and everywhere that mary went the lamb was sure to go it followed her to school one day which was against the rules.

Monoalphabetic substitution cipher

Message Space: M

= f0; 1; : : : ; 25g

=

Z26

Cryptogram Space:

C = f0; 1; : : : ; 25g

= Z26.

Key Space:

K

=

f

j

:

Z

26

! Z

26

g

,

j K j

= 26!, and H(K) = log2 26!

88:3.

To evaluate log2 26!, Sterling's approximation can be used and log2

26!

26 log2

26

.

e

Encryption: c = Ek(m) = (m).

Decryption: m = Dk(c) = 1(c).

Unicity Distance: N 27:6 letters (assuming D = 3:2). Cryptanalysis: Uses letter frequency distributions. The letter frequencies are

still preserved but permuted according to the permutation .

3.1.4 Transposition Ciphers

The other principal technique for use on alphabets is transposition of characters. Thus,

plaintext ! rearrange characters ! ciphertext. Write the plaintext CRYPTANALYST as a 3 4 matrix:

3.1 Classical Ciphers

77

1 2 3 4 C R Y P T A N A L Y S T

and read o the columns in the order 2, 4, 1, 3 to get,

RAYPATCTLYNS.

This technique can also be used for n-dimensional arrays. Transposition ciphers often use a xed period d. Let Zd be the integers from 0 to d 1, and: Zd ! Zd be a permutation. Then the key is the pair k = (d; ) and blocks of d characters are enciphered at a time. Thus, the sequence of letters

m0 md 1 md m2d 1

is enciphered to,

m (0) m (d 1) md+ (0) md+ (d 1) :

Suppose d = 4 and = ( (0); (1); (2); (3)) = (1;2; 3; 0). Then the following shows a message broken into blocks and enciphered:

Plaintext: CRYP TOGR APHY

Ciphertext: PCRY RTOG YAPH

Note that the frequency distribution of the characters of the ciphertext is exactly the same as for the plaintext. A knowledge of the most frequent pairs and triples in a language is used with anagraming. The most frequent pairs of letters in English, on a relative scale from 1 to 10, are:

TH 10.00	ED 4.12 OF 3.38
HE 9.50	TE 4.04 IT 3.26
IN 7.17	TI 4.00 AL 3.15
ER 6.65	OR 3.98 AS 3.00
RE 5.92	ST 3.81 HA 3.00
ON 5.70	AR 3.54 NG 2.92
AN 5.63	ND 3.52 CO 2.80
EN 4.76	TO 3.50 SE 2.75
AT 4.72	NT 3.44 ME 2.65
ES 4.24	IS 3.43 DE 2.65

We note some other salient features of English:

783 PRIVATE-KEY CRYPTOSYSTEMS

1.The vowel-consonant pair is most common { no high frequency pair has two vowels.

2.Letters that occur in many di erent pairs are probably vowels.

3.Consonants, except for N and T, occur most frequently with vowels.

4.If XY and YX both occur, one letter is likely to be a vowel.

The most frequent three letter combinations, on a scale of 1 to 10, are:

THE 10.00 FOR 1.65 ERE 1.24

AND 2.81 THA 1.49 CON 1.20

TIO 2.24 TER 1.35 TED 1.09

ATI 1.67 RES 1.26 COM 1.08 Decipher the following ciphertext:

LDWEOHETTHSESTRUHTELOBSEDEFEIVNT

We start by looking at blocks of various lengths by dividing up the text:

LD WE OH ET TH SE ST RU HT EL OB SE DE FE IV NT

Is d = 2? The pairs LD WE, which can only be permuted to DL EW, tell us no.

LDW EOH ETT HSE STR UHT ELO BSE DEF EIV NT

Is d = 3? The triple LDW in any permutation tells us no.

LDWE OHET THSE STRU HTEL OBSE DEFE IVNT

Is d = 4? This case is a bit harder because we have to try 16 permutations on the rst two groups of four letters but we become convinced that none of these make sense.

LDWEO HETTH SESTR UHTEL OBSED EFEIV NT

Is d = 5? A bit harder because we have to try 5! permutations on the rst two groups of ve letters but become convinced that none of these make sense.

LDWEOH ETTHSE STRUHT ELOBSE DEFEIV NT

Is d = 6? The second group of six letters suggests

THESET or TTHESE.

That means we try the following permutations for deciphering:

3.1 Classical Ciphers

79

d N=0.3d log2 (d/e)				N
3	0.9	log2 (3/e)		0.12804
4	1.2	log2	(4/e)	0.66877
5	1.5	log2	(5/e)	1.31885
6	1.8	log2	(6/e)	2.05608
7	2.1	log2	(7/e)	2.86579

Table 3.1. The period and associated unicity distance

(205134), (250134), (405132), (450132) (501234), (301245), (510243), (310245)

When we try (450132) on the other blocks we recover the following message:

WE HOLD THESE TRUTHS TO BE SELF EVIDENT

Transposition cipher

Message Space: M = Z26 : : : Z26 = Z26d { collection of sequences with d
	|		{z	}
letters.			d
Cryptogram Space: C = Z26d			{ d-letter sequences.
Key Space: K = f	j :		Zd	! Zdg, j K j= d! and H(K) = log2 d!
d log2 (d=e).

Encryption: A message m = (m0; : : : ; md 1) is encrypted into cryptogram c =

Ek(m) = (c0; : : : ; cd 1) = (m (0); : : : ; m (d 1)).

Decryption: m = D	(c) = (c			1	(0)	; : : : ; c	1	(d 1)	).
k
Unicity Distance: N		H(K)	(Table 3.1).
		D

Cryptanalysis: Uses letter frequency distributions. First, the period d needs to be guessed. Next single letter frequencies combined with the most frequent pairs and triples allows to break the cipher.

3.1.5 Homophonic Substitution Ciphers

Letters which occur frequently may be mapped into more than one letter in the ciphertext to atten the frequency distribution. The number of cipher letters for a given character is determined by its frequency in the original language.

Suppose the alphabet is mapped into the numbers 0 to 99 then,

80 3 PRIVATE-KEY CRYPTOSYSTEMS

map E to 17, 19, 23, 47, and 64 map A to 8, 20, 25, and 49 map R to 1, 29, 65

map T to 16, 31, and 85

but otherwise the ith letter maps to the the integer 3i. Then the plaintext

MANY A SLIP TWIXT THE CUP AND THE LIP

will become

M A N Y A S L I P T W I X T T

08	20			16	31 85
36 08	39 72 20	54 33 24 45		16	66 24 69 31 85
H E C U P A N D T H E L I P
17		25	16		47
21 17	06 60 45	25 39 09 16		21	47 33 24 45.

If a letter is to be encrypted, a single element is chosen at random from all homophones associated with the letter.

For each message m 2 Z26, the cipher assigns the set Hm of homophones or positive integers. Each set contains at least one element. Usually the cardinality of a set Hm is proportional to the frequency of the letter m in the language. The cryptogram space C = Sm2M Hm ZH where ZH is the smallest possible set that contains all homophones. The parameters and properties of the cipher are summarized below.

Homophonic cipher

Message Space: M = Z26.

Cryptogram Space: C = Sm2M Hm ZH .

Key Space: The secret key is the assignment of homophones to all messages so k = (H0; H1; : : : ; H25). If we assume that sizes of Hi for i = 0; : : : ; 25 are known (or easy to guess from the statistical analysis of the language), then the number of possible keys is equal the number of possible arrangements of H elements into 26 compartments. Each compartment has to contain

ni =j Hi	j di erent elements. Thus the number of all keys is j K j=							H	!
								n0
H n0	!	: : :	n24 + n25	!	where H =	P	i25=0 ni.
n1			n24