Public-Key Encryption - Everyday Cryptography - page 172

However, a significant advantage of probabilistic encryption is that it
prevents the following attack on a public-key cryptosystem. Suppose that a
ciphertext to a known recipient has been observed by an attacker, who then
proceeds to:
1. make an informed guess as to the value of the plaintext;
2. encrypt the guessed plaintext using the known recipient's public key;
3. if the result matches the observed ciphertext then the guess was correct; if not,
try another guess of the plaintext.
This attack is particulary effective in situations where there are limited choices for
the plaintext, for example, if the plaintext is a database entry from a limited range.
In some sense, this attack could be regarded as an 'informed' exhaustive plaintext
search .
Note that this attack does not apply to symmetric cryptosystems. This is because
the encryption key is secret. Even if the attacker knows that the plaintext comes
from a small set of potential values (perhaps even just two), the attacker cannot
conduct this attack because any encryption key could have been used. This is why
the attacker has to exhaustively search through all the potential symmetric keys
instead.
Probabilistic encryption makes an exhaustive plaintext search attack impracti-
cal to conduct because the attacker now also has to guess the temporary key k that
was used in order to encrypt any plaintext guess. If k is randomly generated using
a secure process, such as those discussed in Section 8.1.4, then the attacker now
has to exhaustively try all the possible values of k for every guess of the plaintext.
This will almost certainly be infeasible.
In practice the security benefits of probabilistic encryption are sufficiently
significant that even RSA tends to be implemented in a probabilistic manner,
typically by introducing randomly generated values into the way that the plaintext
is padded prior to encryption. One well-respected scheme for doing this is known
as RSA-OAEP . The minor disadvantage of requiring random generation can be
partially offset by conducting some of this work in advance and storing the results.
For example, in ElGamal the calculation C 1 = g k does not involve the plaintext P
and thus could have been computed earlier and just looked up from a table at the
time of encryption.
MESSAGE EXPANSION
Most of the previous encryption algorithms that we have studied encrypt a
plaintext into a ciphertext of identical length. ElGamal shares the property of
homophonic encoding (see Section 2.2.3) that the ciphertext is longer than the
plaintext. We previously referred to this property as message expansion . More
precisely, an ElGamal ciphertext is twice as long as the corresponding plaintext,
since each plaintext unit is a number modulo p , while its corresponding ciphertext
consists of two numbers modulo p . This represents a potential cost in terms of
bandwidth and storage.