Cryptography Reference
In-Depth Information
In this section we will discuss a cryptosystem that can be
proven
to be
unbreakable. We will even see that an exhaustive key search is of limited use
against this cryptosystem.
3.1.1
Perfect secrecy
The notion of a cryptosystem being 'unbreakable' is modeled by the concept of
perfect secrecy
.
MOTIVATING PERFECT SECRECY
An exhaustive key search can always be launched against any cryptosystem.
However, there is an even more basic attack that can also always be conducted
against a cryptosystem that does not even involve trying to obtain the decryption
key: an attacker can simply try to
guess
the plaintext.
Guessing the plaintext is an attack that can never be prevented. Of course, for
long and complicated plaintexts it is very unlikely that an interceptor will be able
to guess the plaintext correctly, but there will always be a
chance
(ideally a very
small one) that they could. Note that guessing the plaintext becomes a much more
plausible attack when the number of possible plaintexts is small, such as when the
plaintext is a four-digit PIN or a short password.
DEFINING PERFECT SECRECY
It is thus useful to come up with a notion of security in which guessing the
plaintext is essentially the best attack that the interceptor can deploy. We say that
a cryptosystem has
perfect secrecy
if, after seeing the ciphertext, an interceptor
gets
no extra information about the plaintext other than what was known before the
ciphertext was observed
.
This can be a slightly confusing concept when met for the first time, so it is
worth reading it again and then noting the following:
• We are not saying that in a cryptosystem with perfect secrecy the interceptor
has
no information
about the plaintext. For example, the interceptor may
already know that the next ciphertext sent will represent the encryption of
a four digit PIN. What we are saying, however, is that the interceptor does not
learn any
more
information about the plaintext from seeing the ciphertext. In
other words, after seeing the ciphertext representing the four-digit PIN, the
interceptor will still only know that it represents a four-digit PIN, and will have
gained no other information about the value of the PIN. On the other hand, had
a symmetric encryption algorithm with just 50 keys been used, then, on seeing
the ciphertext, the interceptor would be able to deduce that the PIN was one
of 50 different possible PINs simply by trying out the 50 possible decryption
keys. In this case, by seeing the ciphertext, the interceptor would have learnt
some useful information about the plaintext.
