CM30173/50210: Cryptography Part I \(cont.\)
CM30173/50210:
Cryptography
Part I (cont.)
A fundamental
assumption
Attack models
Security
One-time pad Part I
Introduction to the problem (cont.)
CM30173/50210:
Cryptography
Part I (cont.)
A fundamental
assumption
Attack models
Security
One-time pad
A fundamental assumption
Attack models
Security
One-time pad
CM30173/50210:
Cryptography
Part I (cont.)
A fundamental
assumption
Attack models
Security
One-time pad
Computational security
Definition
A cryptosystem is computationally secure if the best
algorithm for breaking it requires a computational e!ort
which is greater than the computational resources of the
assumed attacker.
We need a measure of the computational e!ort to
break the cryptosystem.
We can’t prove a system is computationally secure
against all attacks.
CM30173/50210:
Cryptography
Part I (cont.)
A fundamental
assumption
Attack models
Security
One-time pad
Provable security
For some cryptosystems that provide confidentiality we
can provide evidence that the system is secure by
proving a theorem of the form:
If the cryptosystem can be broken then we can
e”ciently solve problem A, where problem A is
Well studied
Thought to be “di”cult”
This is not an absolute proof of security but a proof of
the security relative to another problem.
CM30173/50210:
Cryptography
Part I (cont.)
A fundamental
assumption
Attack models
Security
One-time pad
Unconditional security
Definition
A cryptosystem is said to be unconditionally secure if an
attacker with infinite computational resources cannot
break the system.
CM30173/50210:
Cryptography
Part I (cont.)
A fundamental
assumption
Attack models
Security
One-time pad
Vernam cipher: a stream cipher
Cryptosystem
P = C = Z2
K = Z2 and we generate a keystream k1k2k3 . . .
with ki ! K.
We encrypt plaintext x = x1x2x3 . . . with the
keystream thus
eki(xi) = (xi + ki) mod 2
(the exclusive-or of xi and ki this is also written
xi ” ki) and decrypt
dki(yi) = (yi + ki) mod 2
CM30173/50210:
Cryptography
Part I (cont.)
A fundamental
assumption
Attack models
Security
One-time pad
The one-time pad
Definition
The Vernam cipher is referred to as a one-time pad if
the key stream k1k2k3 . . . is
Randomly chosen
Never used again
CM30173/50210:
Cryptography
Part I (cont.)
A fundamental
assumption
Attack models
Security
One-time pad
An unconditionally secure cryptosystem
In 1949 Shannon proved that the one-time pad is
unconditionally secure.
Theorem
Suppose (P, C,K, E ,D) is a cryptosystem where
|K| = |C| = |P|. Then the cryptosystem provides
perfect secrecy if and only if every key is used with
equal probability 1/|K|, and for every x ! P and every
y ! C, there is a unique key such that ek(x) = y.
(as stated in Cryptography Theory and Practice)
CM30173/50210:
Cryptography
Part I (cont.)
A fundamental
assumption
Attack models
Security
One-time pad
Instead of aiming for unconditional security researchers
have tried to develop cryptosystems where one shared
key can be used to send many messages between to
entities while still maintaining computational security.
This is our next topic: private-key cryptography
Introduction to the problem (cont.)
A fundamental assumption
Attack models
Security
One-time pad