Cryptography Reference
In-Depth Information
1.1.4 Vernam Cipher
With the industrial revolution, communications became automatic (with telegraph,
radio, etc.). Encryption and decryption had to be performed by a cryptographic device.
The telewriter used the Baudot code for which all characters are encoded into 5 bits.
The Vernam cipher (1926) is defined by
the plaintext is a bitstring: an element of
n
the secret key is a uniformly distributed element of
{
0
,
1
}
n
{
0
,
1
}
the ciphertext is C K ( X )
=
X
K where
is the bitwise XOR
The key is aimed at being used for only one plaintext. For this reason this cipher is also
known as one-time pad . It was published in 1926 by Gilbert Vernam, from AT&T. (It
was actually invented at the end of the First World War, but since the war was over,
people did not get any more interest in it until 1926.) The security was formally proven
by Shannon, by using the notion of perfect secrecy. Later on, the Vernam cipher was
used for the red telephone between Moscow and Washington.
Note that the Vernam cipher uses a keyed substitution. It is a kind of Vigenere
cipher with a binary alphabet and a one-time key.
The drawbacks of this cipher are that
the key must be at least as long as the message,
it becomes insecure if a key is used twice,
the security result makes sense only when the key source is truly random,
some pseudorandom keys may lead to insecure implementations,
randomness is expensive.
The security of the Vernam cipher is indeed critically sensitive to the freshness require-
ment on the secret key. In the forties, the Soviet intelligence agency KGB was using
the Vernam cipher, but was reusing some fragments of keys several times. This led the
American counterpart NSA to decrypt messages in the famous VERONA project.
This cipher notably illustrates in a very nice visual way as shown by Moni Naor
and Adi Shamir in Ref. [137]. Let us assume that the plaintext, the ciphertext, and the
key are black-and-white images. These are indeed sequences of bits: a white pixel is
a 0 bit and a black pixel is a 1 bit. We assume that we perform the encryption on a
computer and that we next print the ciphertext and the key by representing bits with
special square black-and-white patterns. We use a balanced black-and-white pattern,
e.g. a 2
2 array with two white cells and two black cells. This pattern is used in order
to represent 0 bit. The complement pattern is used in order to represent 1 bit. This step
is called “pixel coding” (see Fig. 1.2). Now we can overlay the key onto the ciphertext.
Nonoverlapping patterns will be complement patterns and will look completely black.
As a matter of fact, they correspond to complement bits whose XOR is 1. Overlapping
patterns will look gray from far away (see Fig. 1.3). They correspond to equal bits
×
Search WWH ::




Custom Search