Classical (secret-key) cryptosystems
‹#›
Classical (secret-key) cryptosystems
1
CHAPTER 4: Classical (secret-key) cryptosystems
•
•   In this chapter we deal with some of the very old or quite old classical (secret-key or
symmetric) cryptosystems that were primarily used in the pre-computer era.
IV054
•   These cryptosystems are too weak nowadays, too easy to break, especially with computers.
•   However, these simple cryptosystems give a good illustration of several of the important ideas
of the cryptography and cryptanalysis.
• Moreover, most of them can be very useful in combination with more modern cryptosystem - to add a
new level of security.

‹#›
Classical (secret-key) cryptosystems
2
Classical (secret-key) cryptosystems
Cryptology, Cryptosystems - secret-key cryptography
•Cryptology (= cryptography + cryptoanalysis)
•has more than two thousand years of history.
IV054
Basic historical observation
• People have always had fascination with keeping information away from others.
• Some people – rulers, diplomats, militaries, businessmen – have always had needs to keep some
information away from others.
Importance of cryptography nowadays
• Applications:  cryptography is the key tool to make modern information transmission secure, and
to create secure information society.
• Foundations: cryptography gave rise to several new key concepts of the foundation of informatics:
one-way functions, computationally perfect pseudorandom generators, zero-knowledge proofs,
holographic proofs, program self-testing and self-correcting, …

‹#›
Classical (secret-key) cryptosystems
3
Classical (secret-key) cryptosystems
Approaches and paradoxes of cryptography
•Sound approaches to cryptography
•
•Shannon’s approach based on information theory (enemy has not enough information to break a
cryptosystem)
•Current approach based on complexity theory (enemy has not enough computation power to break a
cryptosystem).
•Very recent approach based on the laws and limitations of quantum physics
•(enemy would need to break laws of nature to break a cryptosystem).
IV054
Paradoxes of modern cryptography
•  Positive results of modern cryptography are based on negative results of complexity theory.
•  Computers, that were designed originally for decryption, seem to be now more useful for
encryption.

‹#›
Classical (secret-key) cryptosystems
4
Classical (secret-key) cryptosystems
Cryptosystems - ciphers
•The cryptography deals the problem of sending a message (plaintext, cleartext), through a insecure
channel, that may be tapped by an adversary (eavesdropper, cryptanalyst), to a legal receiver.
IV054
01

‹#›
Classical (secret-key) cryptosystems
5
Classical (secret-key) cryptosystems
Components of cryptosystems:
IV054
•Plaintext-space:   P – a set of plaintexts over an alphabet
•
•Cryptotext-space:   C – a set of cryptotexts (ciphertexts) over alphabet
•
•Key-space:   K – a set of keys
•
•
•
   Each key k determines an encryption algorithm ek and an decryption algorithm dk such that, for
any plaintext w, ek (w) is the corresponding cryptotext and

                                                   or

Note: As encryption algorithms we can use also randomized algorithms.

‹#›
Classical (secret-key) cryptosystems
6
Classical (secret-key) cryptosystems
100 – 42 B.C., CAESAR cryptosystem, Shift cipher
•CAESAR can be used to encrypt words in any alphabet.                                   In order to
encrypt words in English alphabet we use:
•
IV054
Key-space:   {0,1,…,25}
An encryption algorithm ek substitutes any letter by the letter occurring k positions ahead
(cyclically) in the alphabet.
A decryption algorithm dk substitutes any letter by the one occurring k positions backward
(cyclically) in the alphabet.

‹#›
Classical (secret-key) cryptosystems
7
Classical (secret-key) cryptosystems
100 – 42 B.C., CAESAR cryptosystem, Shift cipher
•Example e2(EXAMPLE) = GZCOSNG,
•               e3(EXAMPLE) = HADPTOH,
• e1(HAL) = IBM,
•               e3(COLD) = FROG
•                                                       ABCDEFGHIJKLMNOPQRSTUVWXYZ
•
IV054
Example Find the plaintext to the following cryptotext obtained by the encryption with CAESAR with
k = ?.
Cryptotext: VHFUHW GH GHXA, VHFUHW GH GLHX,
                  VHFUHW GH WURLV, VHFUHW GH WRXV.
Numerical version of CAESAR is defined on the set {0, 1, 2,…, 25} by the encryption algorithm:
ek(i) = (i + k) (mod 26)

‹#›
Classical (secret-key) cryptosystems
8
Classical (secret-key) cryptosystems
POLYBIOUS cryptosystem
•for encryption of  words of the English alphabet without J.
•
•Key-space:   Polybious checkerboards 5×5 with 25 English letters and with rows + columns labeled
by symbols.
•Encryption algorithm: Each symbol is substituted by the pair of symbols denoting the row and the
column of the checkerboard in which the symbol is placed.
•Example:
•
•
•
•
•
•KONIEC --�
•Decryption algorithm: ???
IV054
F
G
H
I
J
A
A
B
C
D
E
B
F
G
H
I
K
C
L
M
N
O
P
D
Q
R
S
T
U
E
V
W
X
Y
Z

‹#›
Classical (secret-key) cryptosystems
9
Classical (secret-key) cryptosystems
Kerckhoff’s Principle
•The philosophy of modern cryptoanalysis is embodied in the following principle formulated in 1883
by Jean Guillaume Hubert Victor Francois Alexandre Auguste Kerckhoffs von Nieuwenhof (1835 - 1903).
IV054
The security of a cryptosystem must not depend on keeping secret the encryption algorithm. The
security should depend only on keeping secret the key.

‹#›
Classical (secret-key) cryptosystems
10
Classical (secret-key) cryptosystems
Requirements for good cryptosystems
•(Sir Francis R. Bacon (1561 - 1626))
•
•1.   Given ek and a plaintext w, it should be easy to compute c = ek(w).
IV054
2.   Given dk and a cryptotext c, it should be easy to compute w = dk(c).
4.   It should be unfeasible to determine w from ek(w) without knowing dk.
5.   The so called avalanche effect should hold: A small change in the plaintext, or in the key,
should lead to a big change in the cryptotext (i.e. a change of one bit of the plaintext should
result in a change of all bits of the cryptotext, each  with the probability close to 0.5).
6.   The cryptosystem should not be closed under composition, i.e. not for every two keys k1,
k2 there is a key k such that
ek (w) = ek1 (ek2 (w)).
7.   The set of keys should be very large.
3.   A cryptotext ek(w) should not be much longer than the plaintext w.

‹#›
Classical (secret-key) cryptosystems
11
Classical (secret-key) cryptosystems
Cryptoanalysis
•The aim of cryptoanalysis is to get as much information about the plaintext
•or the key as possible.
•Main types of cryptoanalytics attack
•
•1.Cryptotexts-only attack. The cryptanalysts get cryptotexts
•c1 = ek(w1),…, cn = ek(wn) and try to infer the key k or as many of the plaintexts w1,…, wn as
possible.
IV054
2.  Known-plaintexts attack  (given are some pairs plaintextàcryptotext)
The cryptanalysts know some pairs wi, ek(wi), 1 <= i <= n, and try to infer k, or at least wn+1 for
a new cryptotext many plaintexts ek(wn+1).
3.  Chosen-plaintexts attack (given are cryptotext for some chosen plaintexts)
The cryptanalysts choose plaintexts w1,…, wn to get cryptotexts ek(w1),…, ek(wn), and try to infer
k or at least wn+1 for a new cryptotext cn+1 = ek(wn+1).  (For example, if they get temporary
access to encryption machinery.)

‹#›
Classical (secret-key) cryptosystems
12
Classical (secret-key) cryptosystems
Cryptoanalysis
4.
•4.  Known-encryption-algorithm attack
•The encryption algorithm ek is given and the cryptanalysts try to get the decryption algorithm dk.
IV054
5.  Chosen-cryptotext attack (given are plaintexts for some chosen cryptotexts)
The cryptanalysts know some pairs
(ci , dk(ci)), 1 Ł i Ł n,
where the cryptotexts ci have been chosen by the cryptanalysts. The aim is to determine the key.
(For example, if cryptanalysts get a temporary access to decryption machinery.)

‹#›
Classical (secret-key) cryptosystems
13
Classical (secret-key) cryptosystems
WHAT CAN a BAD EVE DO?
•Let us assume that a clever Alice sends an encrypted message to Bob. What can a bad enemy, called
usually Eve (eavesdropper), do?
•
·  Eve can read (and try to decrypt) the message.
•
·  Eve can try to get the key that was used and then decrypt all messages encrypted with the same
key.
•
·  Eve can change  the message sent by Alice into another message, in such a way that Bob will have
the feeling, after he gets the changed message, that it was a message from Alice.
•
·  Eve can pretend to be Alice and  communicate with Bob, in such a way that Bob thinks he is
communicating with Alice.
•An eavesdropper can therefore be passive - Eve or active - Mallot.
IV054

>

‹#›
Classical (secret-key) cryptosystems
14
Classical (secret-key) cryptosystems
Basic goals of broadly understood cryptography
•Confidentiality: Eve should not be able to decrypt the message Alice sends to Bob.
•Data integrity: Bob wants to be sure that Alice's message has not been altered by  Eve.
•Authentication: Bob wants to be sure that only Alice could have sent the message he has received.
•Non-repudiation: Alice should not be able to claim that she did not send messages that she has
sent.
•Anonymity: Alice does want that Bob finds who send the message
IV054

>

‹#›
Classical (secret-key) cryptosystems
15
Classical (secret-key) cryptosystems
HILL cryptosystem
•The cryptosystem presented in this slide was probably never used. In spite of that this
cryptosystem played an important role in the history of modern cryptography.
•
•We describe Hill cryptosystem or a fixed n and the English alphabet.
•
•Key-space: matrices M of degree n with elements from the set {0, 1,…, 25} such that M-1 mod 26
exist.
•
•Plaintext + cryptotext space: English words of length n.
•
•Encoding: For a word w let cw be the column vector of length n of the integer codes of symbols of
w. (A -> 0, B -> 1, C -> 2, …)
•
•Encryption: cc = Mcw mod 26
•
•Decryption: cw = M-1cc mod 26
IV054

>

‹#›
Classical (secret-key) cryptosystems
16
Classical (secret-key) cryptosystems
HILL cryptosystem
•Example 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
•
•
•Plaintext: w = LONDON
•
•
•
•
•
•Cryptotext: MZVQRB
•
•
•Theorem
•
•
•Proof: Exercise
IV054

‹#›
Classical (secret-key) cryptosystems
17
Classical (secret-key) cryptosystems
Secret-key (symmetric) cryptosystems
•A cryptosystem is called secret-key cryptosystem if some secret piece of information – the key –
has to be agreed first between any two parties that have, or want, to communicate through the
cryptosystem. Example: CAESAR, HILL. Another name is symmetric cryptosystem (cryptography).
IV054
Two basic types of secret-key cryptosystems
•  substitution based cryptosystems
•  transposition based cryptosystems
Two basic types of substitution cryptosystems
•  monoalphabetic cryptosystems  –  they use a fixed substitution –
   CAESAR,  POLYBIOUS
•  polyalphabetic  cryptosystems– substitution keeps changing during  the                encryption
A monoalphabetic cryptosystem with letter-by-letter substitution is uniquely specified by a
permutation of letters. (Number of permutations (keys) is 26!)

‹#›
Classical (secret-key) cryptosystems
18
Classical (secret-key) cryptosystems
Secret-key cryptosystems
•Example: AFFINE cryptosystem is given by two integers
•1 Ł a, b Ł 25, gcd(a, 26) = 1.
•
•Encryption: ea,b(x) = (ax + b) mod 26
•
•Example
• a = 3, b = 5, e3,5(x) = (3x + 5) mod 26,
• e3,5(3) = 14,  e3,5(15) = 24 - e3,5(D) = 0,  e3,5(P) = Y
•
•
•Decryption: da,b(y) = a-1(y - b) mod 26
IV054

‹#›
Classical (secret-key) cryptosystems
19
Classical (secret-key) cryptosystems
Cryptanalysis’s
•The basic cryptanalytic attack against monoalphabetic substitution cryptosystems begins with a
frequency count: the number of each letter in the cryptotext is counted. The distributions of
letters in the cryptotext is then compared with some official distribution of letters in the
plaintext laguage.
•The letter with the highest frequency in the cryptotext is likely to be substitute for the letter
with highest frequency in the plaintext language …. The likehood grows with the length of
cryptotext.
•Frequency counts in English:
•
•
•
•and for other languages:
•
•
•
•
•The 20 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. The six most common trigrams: THE, ING, AND, HER, ERE, ENT.
IV054
%
%
%
E
12.31
L
4.03
B
1.62
T
9.59
D
3.65
G
1.61
A
8.05
C
3.20
V
0.93
O
7.94
U
3.10
K
0.52
N
7.19
P
2.29
Q
0.20
I
7.18
F
2.28
X
0.20
S
6.59
M
2.25
J
0.10
R
6.03
W
2.03
Z
0.09
H
5.14
Y
1.88
5.27
70.02
24.71
English
%
German
%
Finnish
%
E
12.31
E
18.46
A
12.06
T
9.59
N
11.42
I
10.59
A
8.05
I
8.02
T
9.76
O
7.94
R
7.14
N
8.64
N
7.19
S
7.04
E
8.11
I
7.18
A
5.38
S
7.83
S
6.59
T
5.22
L
5.86
R
6.03
U
5.01
O
5.54
H
5.14
D
4.94
K
5.20
French
%
Italian
%
Spanish
%
E
15.87
E
11.79
E
13.15
A
9.42
A
11.74
A
12.69
I
8.41
I
11.28
O
9.49
S
7.90
O
9.83
S
7.60
T
7.29
N
6.88
N
6.95
N
7.15
L
6.51
R
6.25
R
6.46
R
6.37
I
6.25
U
6.24
T
5.62
L
5.94
L
5.34
S
4.98
D
5.58

‹#›
Classical (secret-key) cryptosystems
20
Classical (secret-key) cryptosystems
Cryptanalysis’s
•Cryptoanalysis of a cryptotext encrypted using the AFINE cryptosystem with an encryption algorithm
•ea,b(x) = (ax + b) mod 26 = (xa+b) mod 26
•where 0 Ł a, b Ł 25, gcd(a, 26) = 1. (Number of keys: 12 × 26 = 312.)
•Example: Assume that an English plaintext is divided into blocks of 5 letter and encrypted by an
AFINE cryptosystem (ignoring space and interpunctions) as follows:
•
•
•
•
• How to find
•the plaintext?
IV054
B
H
J
U
H
N
B
U
L
S
V
U
L
R
U
S
L
Y
X
H
O
N
U
U
N
B
W
N
U
A
X
U
S
N
L
U
Y
J
S
S
W
X
R
L
K
G
N
B
O
N
U
U
N
B
W
S
W
X
K
X
H
K
X
D
H
U
Z
D
L
K
X
B
H
J
U
H
B
N
U
O
N
U
M
H
U
G
S
W
H
U
X
M
B
X
R
W
X
K
X
L
U
X
B
H
J
U
H
C
X
K
X
A
X
K
Z
S
W
K
X
X
L
K
O
L
J
K
C
X
L
C
M
X
O
N
U
U
B
V
U
L
R
R
W
H
S
H
B
H
J
U
H
N
B
X
M
B
X
R
W
X
K
X
N
O
Z
L
J
B
X
X
H
B
N
F
U
B
H
J
U
H
L
U
S
W
X
G
L
L
K
Z
L
J
P
H
U
U
L
S
Y
X
B
J
K
X
S
W
H
S
S
W
X
K
X
N
B
H
B
H
J
U
H
Y
X
W
N
U
G
S
W
X
G
L
L
K

‹#›
Classical (secret-key) cryptosystems
21
Classical (secret-key) cryptosystems
Cryptanalysis’s
•
•Frequency analysis of plainext and
•frequency table for English:
•
•
•First guess: E = X, T = U
•Encodings: 4a + b = 23 (mod 26)
•xa+b=y 19a + b = 20 (mod 26)
•Solutions: a = 5, b = 3 à a-1      =
•Translation table
•
•
•
•
•
•
•provides from the above cryptotext the plaintext that starts with KGWTG CKTMO OTMIT DMZEG, what
does not make a sense.
IV054
%
%
%
E
12.31
L
4.03
B
1.62
T
9.59
D
3.65
G
1.61
A
8.05
C
3.20
V
0.93
O
7.94
U
3.10
K
0.52
N
7.19
P
2.29
Q
0.20
I
7.18
F
2.28
X
0.20
S
6.59
M
2.25
J
0.10
R
6.03
W
2.03
Z
0.09
H
5.14
Y
1.88
5.27
70.02
24.71
X -
32
J -
11
D -
2
U -
30
O -
6
V -
2
H -
23
R -
6
F -
1
B -
19
G -
5
P -
1
L -
19
M -
4
E -
0
N -
16
Y -
4
I -
0
K -
15
Z -
4
Q -
0
S -
15
C -
3
T -
0
W -
14
A -
2
B
H
J
U
H
N
B
U
L
S
V
U
L
R
U
S
L
Y
X
H
O
N
U
U
N
B
W
N
U
A
X
U
S
N
L
U
Y
J
S
S
W
X
R
L
K
G
N
B
O
N
U
U
N
B
W
S
W
X
K
X
H
K
X
D
H
U
Z
D
L
K
X
B
H
J
U
H
B
N
U
O
N
U
M
H
U
G
S
W
H
U
X
M
B
X
R
W
X
K
X
L
U
X
B
H
J
U
H
C
X
K
X
A
X
K
Z
S
W
K
X
X
L
K
O
L
J
K
C
X
L
C
M
X
O
N
U
U
B
V
U
L
R
R
W
H
S
H
B
H
J
U
H
N
B
X
M
B
X
R
W
X
K
X
N
O
Z
L
J
B
X
X
H
B
N
F
U
B
H
J
U
H
L
U
S
W
X
G
L
L
K
Z
L
J
P
H
U
U
L
S
Y
X
B
J
K
X
S
W
H
S
S
W
X
K
X
N
B
H
B
H
J
U
H
Y
X
W
N
U
G
S
W
X
G
L
L
K
crypto
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
plain
P
K
F
A
V
Q
L
G
B
W
R
M
H
C
X
S
N
I
D
Y
T
O
J
E
Y
Z
Z
U

‹#›
Classical (secret-key) cryptosystems
22
Classical (secret-key) cryptosystems
Cryptanalysis’s
•Second guess: E = X, A = H
•Equations 4a + b = 23 (mod 26)
•        b = 7 (mod 26)
•Solutions: a = 4 or a = 17 and therefore a=17
•This gives the translation table
•
•
•and the following
•plaintext from the
•above cryptotext
IV054
S
A
U
N
A
I
S
N
O
T
K
N
O
W
N
T
O
B
E
A
F
I
N
N
I
S
H
I
N
V
E
N
 T
I
O
N
B
U
T
T
H
E
W
O
R
D
I
S
F
I
N
N
 I
S
H
T
H
E
R
E
A
R
E
M
A
N
Y
M
O
R
E
S
 A
U
N
A
S
I
N
F
I
N
L
A
N
D
T
H
A
N
E
L
 S
E
W
H
E
R
E
O
N
E
S
A
U
N
A
P
E
R
E
V
E
R
Y
T
H
R
E
E
O
R
F
O
U
R
P
E
O
P
L
E
F
I
N
N
S
K
N
O
W
W
H
A
T
A
S
A
U
N
A
I
S
E
L
S
E
W
H
E
R
E
I
F
Y
O
U
S
E
E
A
S
I
G
N
S
A
U
N
A
O
N
T
H
E
D
O
O
R
Y
O
U
C
A
N
N
O
T
B
E
S
U
R
E
T
H
A
T
T
H
E
R
E
I
S
A
S
A
U
N
A
B
E
H
I
N
D
T
H
E
D
O
O
R
crypto
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
plain
V
S
P
M
J
G
D
A
X
U
R
O
L
I
F
C
Z
W
T
Q
N
K
H
E
Y
Z
B
Y

‹#›
Classical (secret-key) cryptosystems
23
Classical (secret-key) cryptosystems
Example of monoalphabetic cryptosystem
•Symbols of the English alphabet will be replaced by squares with or without points and with or
without surrounding lines using the following rule:
•
•
•
•For example the plaintext:
• WE TALK ABOUT FINNISH SAUNA MANY TIMES LATER
•results in the cryptotext:
•
•
•
•Garbage in between method: the message (plaintext or cryptotext) is supplemented by ''garbage
letters''.
•
•Richelieu cryptosystem
•  used sheets of card
•   board with holes.
IV054
08a 08b 08c 08d

‹#›
Classical (secret-key) cryptosystems
24
Classical (secret-key) cryptosystems
Polyalphabetic Substitution Cryptosystems
•Playfair cryptosystem
•Invented around 1854 by Ch. Wheatstone.
•Key - a Playfair square is defined by a word w of length at most 25. In w repeated letters are
then removed,  remaining letters of alphabets (except j) are then added and resulting word is
divided to form an 5 x 5 array (a Playfair square).
•
IV054
Encryption: of a pair of letters x,y
•If x and y are in the same row (column), then they are replaced by the pair of symbols to the
right (bellow) them.
•If x and y are in different rows and columns they are replaced by symbols in the opposite corners
of rectangle created by x and y.
Example: PLAYFAIR is encrypted as LCMNNFCS
Playfair was used in World War I by British army.
Playfair square:

‹#›
Classical (secret-key) cryptosystems
25
Classical (secret-key) cryptosystems
Polyalphabetic Substitution Cryptosystems
•VIGENERE and AUTOCLAVE cryptosystems
•
•Several of the following polyalphabetic cryptosystems are  modification of the CAESAR
cryptosystem.
•
•A 26 ×26 table is first designed with the first row containing a permutation of all symbols of
alphabet and all columns represent CAESAR shifts starting with the symbol of the first row.
•
•Secondly, for a plaintext w  a key k is a word of the same length as w.
•
•Encryption: the i-th letter of the plaintext - wi is replaced by the letter in the wi-row and
ki-column of the table.
IV054
VIGENERE cryptosystem: a short keyword p is chosen and
k = Prefix|w|poo
VIGENERE is actually a cyclic version of the CAESAR cryptosystem.
AUTOCLAVE cryptosystem:        k = Prefix|w|pw.

‹#›
Classical (secret-key) cryptosystems
26
Classical (secret-key) cryptosystems
Polyalphabetic Substitution Cryptosystems
•VIGENERE and AUTOCLAVE cryptosystems
•
•
•   Example:
•
•
•
•
•
•
•
•
•
•Keyword: H A M B U R G
•Plaintext: I N J E D E M M E N S C H E N G E S I C H T E S T E H T S E I N E G
•Vigenere-key: H A M B U R G H A M B U R G H A M B U R G H A M B U R G H A M B U R
•Autoclave-key: H A M B U R G I N J E D E M M E N S C H E N G E S I C H T E S T E H
•Vigerere-cryp.: P N V F X V S T E Z T W Y K U G Q T C T N A E E V Y Y Z Z E U O Y X
•Autoclave-cryp.: P N V F X V S U R W W F L Q Z K R K K J L G K W L M J A L I A G I N
IV054
09

‹#›
Classical (secret-key) cryptosystems
27
Classical (secret-key) cryptosystems
CRYPTOANALYSIS of cryptotexts produced by VINEGAR cryptosystem
1.Task 1 -- to find the length of the key
•
•Kasiski method (1852) - invented also by Charles Babbage (1853).
•Basic observation If a subword of a plaintext is repeated at a distance that is a multiple of the
length of the key, then the corresponding subwords of the cryptotext are the same.
IV054
Example, cryptotext:
Substring ''CHR'' occurs in positions 1, 21, 41, 66: expected keyword length is therefore 5.
CHRGQPWOEIRULYANDOSHCHRIZKEBUSNOFKYWROPDCHRKGAXBNRHROAKERBKSCHRIWK
Method. Determine the greatest common divisor of the distances between identical subwords (of
length 3 or more) of the cryptotext.

‹#›
Classical (secret-key) cryptosystems
28
Classical (secret-key) cryptosystems
CRYPTOANALYSIS of cryptotexts produced by VINEGAR cryptosystem
•Friedman method Let ni be the number of occurrences of the  i-th letter in the cryptotext.
•Let l be the length of the keyword.
•Let n be the length of the cryptotext. Then it holds
•
•Once the length of the keyword is found it is easy to determine the key using the statistical
(frequency analysis)method of analyzing monoalphabetic cryptosystems.
•
IV054

‹#›
Classical (secret-key) cryptosystems
29
Classical (secret-key) cryptosystems
Derivation of the  Friedman method
1. Let ni be the number of occurrences of i-th alphabet symbol in a text of length n.
•The probability that if one selects a pair of symbols from the text, then they are the same is
•
•and it is called the index of coincides.
IV054
2. Let pi be the probability that a randomly chosen symbol is the i -th symbol of the alphabet. The
probability that two randomly chosen symbol are the same is
For English text one has
For randomly chosen text:
Approximately

‹#›
Classical (secret-key) cryptosystems
30
Classical (secret-key) cryptosystems
Derivation of the  Friedman method
•Assume that a cryptotext is organized into l columns headed by the letters of the keyword
•
•
•
•First observation Each column is obtained using the CAESAR cryptosystem.
•Probability that two randomly chosen letters are the same in
•-  the same column is 0.065.
•-  different columns is 0.038.
•
•The number of pairs of letters in the same column:
•
•The number of pairs of letters in different columns:
•
•The expect number A of pairs of equals letters is
•
•Since
•
•one gets the formula for l from the previous slide.
IV054
letters Sl
S1
S2
S3
. . .
Sl
x1
x2
x3
. . .
Xl
xl+1
xl+2
xl+3
X
xl+1
xl+2
xl+3
. . .
x3l
.
.
.
.

‹#›
Classical (secret-key) cryptosystems
31
Classical (secret-key) cryptosystems
ONE-TIME PAD cryptosystem – Vernam’s cipher
•Binary case:
• plaintext    w
• key   k are binary words of the same length
• cryptotext  c
•
•Encryption: c = w Ĺ k
•Decryption: w = c Ĺ k
IV054
Example:
w = 101101011
k = 011011010
c = 110110001
What happens if the same key is used twice or 3 times for encryption?
c1 = w1 Ĺ k, c2 = w2 Ĺ k, c3 = w3 Ĺ k
c1 Ĺ c2 = w1 Ĺ w2
c1 Ĺ c3 = w1 Ĺ w3
c2 Ĺ c3 = w2 Ĺ w3

‹#›
Classical (secret-key) cryptosystems
32
Classical (secret-key) cryptosystems
Perfect secret cryptosystems
•By Shanon, a cryptosystem is perfect if the knowledge of the cryptotext provides no information
whatsoever about its plaintext (with the exception of its length).
•It  follows from Shannon's results that perfect secrecy is possible if the key-space is as large
as the plaintext-space. In addition, a key has to be as long as plaintext and the same key should
not be used twice.
IV054
An example of a perfect cryptosystem ONE-TIME PAD cryptosystem (Gilbert S. Vernam (1917) - AT&T +
Major Joseph Mauborgne).
If used with the English alphabet, it is simply a polyalphabetic substitution cryptosystem of
VIGENERE with the key being a randomly chosen English word of the same length as the plaintext.
Proof of perfect secrecy: by the proper choice of the key any plaintext of the same length could
provide the given cryptotext.
Did we gain something? The problem of secure communication of the plaintext got transformed to the
problem of secure communication of the key of the same length.
Yes: 1. ONE-TIME PAD cryptosystem is used in critical applications
2. It suggests an idea how to construct practically secure cryptosystems.

‹#›
Classical (secret-key) cryptosystems
33
Classical (secret-key) cryptosystems
Transposition Cryptosystems
•The basic idea is very simple: permutate the plaintext to get the cryptotext. Less clear it is how
to specify and perform efficiently  permutations.
•One idea: choose n, write plaintext into rows, with n symbols in each row and then read it by
columns to get cryptotext.
•Example
•
•
•
•Cryptotexts obtained by transpositions, called anagrams, were popular among scientists of 17th
century. They were used also to encrypt scientific findings.
•   Newton wrote to Leibnitz
•     a7c2d2e14f2i7l3m1n8o4q3r2s4t8v12x1
•what stands for: ”data aequatione quodcumque fluentes quantitates involvente, fluxiones invenire
et vice versa”
•Example a2cdef3g2i2jkmn8o5prs2t2u3z
•
•Solution:
IV054

‹#›
Classical (secret-key) cryptosystems
34
Classical (secret-key) cryptosystems
KEYWORD CAESAR cryptosystem1
•Choose an integer 0 < k < 25 and a string, called keyword, of length at most 25 with all letters
different.
•
•The keyword is then written bellow the English alphabet letters, beginning with the k-symbol, and
the remaining letters are written in the alphabetic order and cyclicly after the keyword.
IV054
Example: keyword: HOW MANY ELKS, k = 8

‹#›
Classical (secret-key) cryptosystems
35
Classical (secret-key) cryptosystems
KEYWORD CAESAR cryptosystem
•Exercise Decrypt the following cryptotext encrypted using the KEYWORD CAESAR and determine the
keyword and k
IV054
11

‹#›
Classical (secret-key) cryptosystems
36
Classical (secret-key) cryptosystems
KEYWORD CAESAR cryptosystem
•Step 1. Make the
•frequency counts:
•
•
•
IV054
Number
Number
Number
U
32
X
8
W
3
C
31
K
7
Y
2
Q
23
N
7
G
1
F
22
E
6
H
1
V
20
M
6
J
0
P
15
R
6
L
0
T
15
B
5
O
0
I
14
Z
5
S
0
A
8
D
4
7=2.90%
180=74.69%
54=22.41%
Step 2. Cryptotext contains two one-letter words T and Q. They must be A and I. Since T occurs once
and Q three times it is likely that T is I and Q is A.
The three letter word UPC occurs 7 times and all  other 3-letter words occur only once. Hence
UPC is likely to be THE.
Let us now decrypt the remaining letters in the high frequency group: F,V,I
From the words TU, TF Þ F=S
From UV Þ V=O
From VI Þ I=N
The result after the remaining guesses

‹#›
Classical (secret-key) cryptosystems
37
Classical (secret-key) cryptosystems
UNICITY DISTANCE of CRYPTOSYSTEMS
•Redundancy of natural languages is of the key importance for cryptanalysis.
•Would all letters of a 26-symbol alphabet have the same probability, a character would carry lg 26
= 4.7 bits of Information.
•The estimated average amount of information carried per letter in a meaningful English text is 1.5
bits.
•
•The unicity distance of a cryptosystem is the minimum number of cryptotext (number of letters)
required to a computationally unlimited adversary to recover the unique encryption key.
•
•Empirical evidence indicates that if any simple cryptosystem is applied to a meaningful English
message, then about 25 cryptotext characters is enough for an experienced cryptanalyst to recover
the plaintext.
•

>

‹#›
Classical (secret-key) cryptosystems
38
Classical (secret-key) cryptosystems
ANAGRAMS - EXAMPLES
•German:
• IRI BRÄTER, GENF Briefträgerin
• FRANK PEKL, REGEN …
• PEER ASSSTIL, MELK …
• INGO DILMR, PEINE …
• EMIL REST, GERA …
• KARL SORDORT, PEINE …
IV054
English:
algorithms logarithms
antagonist   stagnation
compressed   decompress
coordinate   decoration
creativity   reactivity
deductions   discounted
descriptor   predictors
impression   permission
introduces   reductions
procedures   reproduces

‹#›
Classical (secret-key) cryptosystems
39
Classical (secret-key) cryptosystems
•                        APPENDIX

>

‹#›
Classical (secret-key) cryptosystems
40
Classical (secret-key) cryptosystems
STREAM  CRYPTOSYSTEMS
•Two basic types of cryptosystems are:
•
•Block cryptosystems (Hill cryptosystem,…) – they are used
•   to encrypt simultaneously blocks of plaintext.
•Stream cryptosystems (CAESAR, ONE-TIME PAD,…) – they
•   encrypt plaintext letter by letter, or block by block, using an encryption that may vary during
the encryption process.
•
•Stream cryptosystems are more appropriate in some applications (telecommunication), usually are
simpler to implement (also in hardware), usually are faster and  usually have no error propagation
(what is of importance when transmission errors are highly probable).
•
•Two basic types of stream cryptosystems: secret key cryptosystems
•(ONE-TIME PAD) and public-key cryptosystems (Blum-Goldwasser)
•

>

‹#›
Classical (secret-key) cryptosystems
41
Classical (secret-key) cryptosystems
Block versus stream cryptosystems
•In block cryptosystems the same key is used to encrypt arbitrarily long plaintext – block by block
- (after dividing each long plaintext w into a sequence of subplaintexts (blocks)  w1w2w3 ).
•
•In stream cryptosystems each block is encryptyd using a different key
IV054
•The fixed key k is used to encrypt all blocks. In such a case the resulting cryptotext has the
form
c = c1c2c3… = ek(w1) ek(w2) ek(w3)…
•A stream of keys is used to encrypt subplaintexts. The basic idea is to generate a key-stream
K=k1,k2,k3,… and then to compute the cryptotext as follows
c = c1c2c3 …  = ek1(w1) ek2(w2) ek3(w3).

‹#›
Classical (secret-key) cryptosystems
42
Classical (secret-key) cryptosystems
CRYPTOSYSTEMS WITH STREAMS OF KEYS
IV054
Decryption: To decrypt the cryptotext c1c2c3  … the sequence
k1, w1, k2, w2, k3, w3, …
of keys and subplaintexts is computed.
Various techniques are used to compute a sequence of keys. For example, given a key k
ki = fi (k, k1, k2, …, ki-1)
In such a case encryption and decryption processes generate the following sequences:
Encryption: To encrypt the plaintext w1w2w3 … the sequence
k1, c1, k2, c2, k3, c3, …
of keys and sub-cryptotexts is computed.

‹#›
Classical (secret-key) cryptosystems
43
Classical (secret-key) cryptosystems
EXAMPLES
•A keystream is called synchronous if it is independent of the plaintext.
•
•
•KEYWORD VIGENERE cryptosystem can be seen as an example of a synchronous keystream cryptosystem.
•
•Another type of the binary keystream cryptosystem is specified by an initial sequence of keys k1,
k2, k3 … km
•
•and a initial sequence of binary constants b1, b2, b3 … bm-1
•
•and the remaining keys are computed using the rule
•
•A keystrem is called periodic with period p if ki+p = ki for all i.
•
IV054
Example Let the keystream be generated by the rule
ki+4 = ki Ĺ ki+1
If the initial sequence of keys is (1,0,0,0), then we get the following keystream:
1,0,0,0,1,0,0,1,1,0,1,0 1,1,1, …
of period 15.

‹#›
Classical (secret-key) cryptosystems
44
Classical (secret-key) cryptosystems
PERFECT SECRECY - BASIC CONCEPTS
•Let P, K and C be sets of plaintexts, keys andcryptotexts.
•Let pK(k) be the probability that the key k is chosen from K and let a priory probability that
plaintext w is chosen is pp(w).
•
•If for a key , then for the probability PC(y) that c is the cryptotext that is transmitted it
holds
•
•
•
•For the conditional probability pc(c|w) that c is the cryptotext if w is the plaintext it holds
•
•
•Using  Bayes' conditional probability formula p(y)p(x|y) = p(x)p(y|x) we get for probability
pP(w|c) that w is the plaintext if c is the cryptotext the expression
IV054

‹#›
Classical (secret-key) cryptosystems
45
Classical (secret-key) cryptosystems
PERFECT SECRECY - BASIC RESULTS
•Definition A cryptosystem has perfect secrecy if
•
•(That is, the a posteriori probability that the plaintext is w,given that the cryptotext is c is
obtained, is the same as a priori probability that the plaintext is w.)
•Example CAESAR cryptosystem has perfect secrecy if any of the26 keys is used with the same
probability to encode any symbol of the plaintext.
•Proof Exercise.
•An analysis of perfect secrecy: The condition pP(w|c) = pP(w) is for all wÎP and cÎC equivalent to
the condition pC(c|w) = pC(c).
•
•Let us now assume that pC(c) > 0 for all cÎC.
•
•Fix wÎP. For each cÎC we have pC(c|w) = pC(c) > 0. Hence, for each c€C there must exists at least
one key k such that ek(w) = c. Consequently, |K| >= |C| >= |P|.
•
•In a special case |K| = |C| = |P|. the following nice characterization of the perfect secrecy can
be obtained:
•Theorem A cryptosystem in which |P| = |K| = |C| provides  perfect secrecy if and only if every key
is used with the same probability and for every wÎP and every c€C there is a unique key k such that
ek(w) = c.
•Proof Exercise.
IV054

‹#›
Classical (secret-key) cryptosystems
46
Classical (secret-key) cryptosystems
PRODUCT CRYPTOSYSTEMS
•A cryptosystem S = (P, K, C, e, d) with the sets of plaintexts P, keys K and cryptotexts C and
encryption (decryption) algorithms e (d) is called endomorphic if P = C.
•If S1 = (P, K1, P, e(1), d (1))  and S2 = (P, K2, P, e (2), d (2)) are endomorphic cryptosystems,
then the product cryptosystem is
•
•S1 Ä S2 = (P, K1 Ä K2, P, e, d),
•where encryption is performed  by the procedure
•e( k1, k2 )(w) = ek2(ek1(w))
•and decryption by the procedure
•d( k1, k2 )(c) = dk1(dk2(c)).
IV054
Example (Multiplicative cryptosystem):
Encryption: ea(w) = aw mod p; decryption: da(c) = a-1c mod 26.
If M denote the multiplicative cryptosystem, then clearly CAESAR × M is actually the AFFINE
cryptosystem.
Exercise Show that also M Ä CAESAR is actually the AFFINE cryptosystem.
Two cryptosystems S1 and S2 are called commutative if S1 Ä S2 = S2 Ä S1.
A cryptosystem S is called idempotent if S Ä S = S.