CM30173/50210 Cryptography
Key ideas
Classical cryptography
Part I
Introduction to the problem
Key ideas Classical cryptography
CM30173/50210 Cryptography
Key ideas
Classical cryptography
CM30173/50210 Cryptography
Key ideas
Classical cryptography
1 Key ideas
2 Classical cryptography
CM30173/50210 Cryptography
CM30173/50210 Cryptography
Key ideas
Classical cryptography
Secure communication
Alice
Bob Plaintext
Plaintext
Encryption
ek(x) = y
Oscar
Decryption
dk(y) = x
Unsecured channel
Key ideas
Classical cryptography
Cryptosystem
Cryptography
CM30173/50210
Key ideas
Classical cryptography
Definition
A cryptosystem is a five-tuple (P, C, K, E, D), where
1 P is a finite set of possible plaintexts
2 C is a finite set of possible ciphertexts
3 K is a finite set of possible keys called the keyspace
4 For each key k 2 K there is an encryption rule
ek 2 E, ek : P ! C and a corresponding decryption ruledk 2D,dk :C!P suchthat
dk(ek(x)) = x for all plaintext elements x 2 P.
CM30173/50210 Cryptography
Key ideas
Classical cryptography
Important properties
Cryptography
CM30173/50210
Key ideas
Classical cryptography
For a cryptosystem to be useful in practice, we need:
1 to be able to e ciently compute the encryption and the decryption functions
2 that an unauthorised party should not be able to determine the key or the plaintext
CM30173/50210 Cryptography
Key ideas
Classical cryptography
The substitution cipher
Cryptography
CM30173/50210
Key ideas
Classical cryptography
Cryptosystem
P = C = Z26
K is the set of all permutations of the 26 symbols
0,1,…,25
For each permutation ⇡ 2 K
e⇡(x) = ⇡(x)
and
where ⇡ 1 is the inverse permutation.
d⇡(y) = ⇡ 1(y)
CM30173/50210 Cryptography
Key ideas
Classical cryptography
The shift cipher
Cryptography
CM30173/50210
Key ideas
Classical cryptography
The shift cipher is a special case of the substitution cipher and was used by Julius Caesar.
Instead of forming any permutation we allow only those that “shift” the alphabet by a specific o↵set. The o↵set is the key 0 k 25.
CM30173/50210 Cryptography
Key ideas
Classical cryptography
The Vigen`ere cipher
Cryptography
CM30173/50210
Key ideas
Classical cryptography
(Due to Giovan Bellasco.)
Cryptosystem
P=C=(Z26)m wherem2Z,m>0 K is the set of keys k = (k1,k2,…,km) For each key k we have
ek(x1,x2,…,xm) = (x1+k1,x2+k2,…,xm+km) and
dk(y1,y2,…,ym) = (y1 k1,y2 k2,…,ym km) (operations are modular 26, that is, in Z26).
CM30173/50210 Cryptography
Key ideas
Classical cryptography
The permutation cipher
Cryptography
CM30173/50210
Key ideas
Classical cryptography
Cryptosystem
P = C = (Z26)m, m 2 Z, m > 0
K is the set of permutations of {1,…,m} For each permutation ⇡ (the key) we have
e⇡(x1,…,xm) = (x⇡(1),…x⇡(m)) and
d⇡(y1,…,ym) = (y⇡ 1(1),…,y⇡ 1(m)) where ⇡ 1 is the inverse permutation.
CM30173/50210 Cryptography