Cryptography Reference
In-Depth Information
additional condition that the key is never repeated, i.e., a new key is used for each
new message. But even this is not enough, for a key with regularities might make the
system susceptible to statistical analysis and the security would be compromised. To
avoid this, the cryptanalyst should not be able, given a portion of the key, to obtain any
information about the remaining part, i.e., the sequence of characters constituting the
key should be completely random. This way, one uses a new shift for each character,
and this shift is unpredictable even if one knows the remaining ones. The idea of
such an encryption scheme was first proposed by Vernam (an engineer working for
the AT&T company) in 1917, and then Mauborgne recognized the importance of the
key being random, for which the invention of this scheme can be attributed to both
Vernam and Mauborgne. It is known as the
Vernam cipher
or
one-time pad
, the latter
name coming from the fact that the (same portion of the) key is used just once, and
a new one is used for each new message.
In the notation introduced above, the one-time pad can be defined as follows. For
convenience, this cipher is usually described by using the binary alphabet but, of
course, any other alphabet can be used without changing the cryptologic properties
of the system.
Definition 3.2
The
one-time pad
is the following encryption scheme, where
n
≥
1:
n
for some integer
n
(so that these sets are all equal to the
set of binary strings of length
n
).
•
M
=
C
=
K
={
,
}
0
1
n
according to the uniform
•
The key generation algorithm chooses keys from
{
0
,
1
}
distribution.
•
If
k
=
(
k
1
,...,
k
n
)
∈
K
then
Enc
k
((
i
1
,...,
i
n
)
:=
(
i
1
+
k
1
,...,
i
n
+
k
n
)
mod 2
and
Dec
k
=
Enc
k
. In other words, both the encryption and decryption algorithms
act by performing the bitwise exclusive-or with the key string so that, denoting
the Xor operation by
⊕
,
Enc
k
(
m
)
=
k
⊕
m
.
When the one-time pad was introduced, there was no notion of perfect secrecy
as this concept would only be introduced by Shannon some 30 years later. However,
it was already intuitively clear that the one-time pad did not allow an adversary to
obtain any information about a plaintext from the observation of the corresponding
ciphertext. Thus it did not come as a surprise that Shannon proved it to be perfectly
secret:
Theorem 3.2
The one-time pad is perfectly secret.
Proof
This is a direct consequence of Shannon's theorem.
Remarks 3.1
In the one-time pad the key must be as long as the message and keys
should be chosen at random, all with equal probability. These conditions must be
satisfied by any perfectly secret encryption scheme as a consequence of Shannon's
theorem (note that the first of themmust hold if the keys and the messages have fixed
length and the key space is at least as large as the message space). In fact, it can be
asserted that, in some sense, the one-time pad is essentially the only perfectly secret
encryption scheme (ignoring trivial differences such as the use of different alphabets
