CM30173/50210 Cryptography
CM30173/50210
Cryptography
Key ideas
Classical
cryptography
Key ideas
Classical cryptography
Part I
Introduction to the problem
CM30173/50210 Cryptography
CM30173/50210
Cryptography
Key ideas
Classical
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
Oscar
PlaintextPlaintext
Encryption Decryption
Unsecured channel
ek(x) = y dk(y) = x
CM30173/50210
Cryptography
Key ideas
Classical
cryptography
Key ideas
Classical cryptography
Cryptosystem
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
rule dk 2 D, dk : C ! P such that
dk(ek(x)) = x
for all plaintext elements x 2 P .
CM30173/50210 Cryptography
CM30173/50210
Cryptography
Key ideas
Classical
cryptography
Key ideas
Classical cryptography
Important properties
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
CM30173/50210
Cryptography
Key ideas
Classical
cryptography
Key ideas
Classical cryptography
The substitution cipher
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
d⇡(y) = ⇡
�1(y)
where ⇡�1 is the inverse permutation.
CM30173/50210 Cryptography
CM30173/50210
Cryptography
Key ideas
Classical
cryptography
Key ideas
Classical cryptography
The shift cipher
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
CM30173/50210
Cryptography
Key ideas
Classical
cryptography
Key ideas
Classical cryptography
The Vigenère cipher
(Due to Giovan Bellasco.)
Cryptosystem
P = C = (Z26)m where m 2 Z, 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
CM30173/50210
Cryptography
Key ideas
Classical
cryptography
Key ideas
Classical cryptography
The permutation cipher
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
Key ideas
Classical cryptography