Cryptography Reference
In-Depth Information
keyspace. If,
by chance
, the same key is selected on two different occasions then
that is fine, since an attacker cannot predict when this might happen.
Note that these three properties do not
define
a one-time pad since there are
cryptosystems that have these properties but do not have perfect secrecy. The
property that defines a one-time pad is perfect secrecy. However, if a cryptosystem
is a one-time pad then it must have these three properties.
In two seminal papers in the late 1940's, Claude Shannon demonstrated that
one-time pads are essentially the only cryptosystems with perfect secrecy. There
are, however, various different ways of describing a one-time pad. We will look at
three of them.
ONE-TIME PAD FROM THE VIGENÈRE CIPHER
Recall that at the end of Section 2.2.4 we commented that there is one special
circumstance under which the Vigenère Cipher is a secure cryptosystem. Under
this special circumstance it is a cryptosystem with perfect secrecy, in other words
it is a one-time pad. This is when:
1. the length of the keyword is the same as the length of the plaintext;
2. the keyword is a randomly generated string of letters;
3. the keyword is used only once.
If these three conditions all hold then it should be clear that the three properties
of a one-time pad are met by this special Vigenère Cipher. To see that the first
one-time pad property holds, note that if the keyword consists of
n
randomly
generated letters then there are 26
n
possible keys. On the other hand there are at
most 26
n
possible plaintexts. If the plaintext is in a language such as English there
will be considerably fewer than 26
n
possible plaintexts, since many strings of
n
letters will not be meaningful.
Using this interpretation of a one-time pad we can demonstrate the power of
this cryptosystem. Suppose that this one-time pad is used to send the plaintext
LEOPARD using keyword CABBDFA. From our description of the Vigenère
Cipher in Section 2.2.4, we can easily establish that the resulting ciphertext is
NEPQDWD.
Now cast ourselves in the role of the adversary. We see ciphertext NEPQDWD
and we know that a Vigenère one-time pad was used. Since the keyword has length
seven and was chosen at random, we are in a very poor position because for
every
possible seven-letter plaintext there exists a keyword that could have been used.
Even if we already know that the plaintext is the name of a species of wild cat
whose name consists of seven letters, it could still be:
• CHEETAH (keyword LXLMKWW);
• PANTHER (keyword YECXWSN);
• CARACAL (keyword KEYQBWS).
