Cryptography Reference
In-Depth Information
always returns the square root that really represents the original plaintext message.
This means that for c
x 2 (mod n ) and m = O Rabin ( c ), the only solution is
m = x . In this case, however, one cannot find p or q . Consequently, if the plaintext
message has to be of a special form, then Theorem 14.1 does no longer apply,
meaning that breaking this modified Rabin asymmetric encryption system is no
longer computationally equivalent to solving the IFP.
Theorem 14.1 is important from a security point of view. It suggests that
breaking the Rabin asymmetric encryption system is computationally equivalent
to solving the IFP, and hence that the Rabin system can be broken if and only if
the corresponding modulus n can be factorized. Unfortunately, the theorem and its
proof also suggest that the Rabin system is vulnerable to chosen-ciphertext attacks.
An adversary who can perform a chosen-ciphertext attack has access to a Rabin
oracle O Rabin —that is, he or she can select x
x 2 (mod n ),
and ask the oracle for m = O Rabin ( c ). According to the proof of Theorem 14.1,
the adversary can then use c and m to factorize n with a success probability of
1 / 2. So the construction used in the proof of Theorem 14.1 can also be employed
by an adversary to break the Rabin system with a chosen-ciphertext attack. On the
other hand, if one employs redundancy to protect the Rabin system against chosen-
ciphertext attacks, then one can no longer prove that breaking the Rabin system is
computationally equivalent to solving the IFP. So the user of the Rabin asymmetric
encryption system has the choice:
R
Z n , compute c
Either he or she goes for a system that is provably as difficult to break as it is
to solve the IFP, but that is vulnerable to chosen-ciphertext attacks;
Or he or she goes for a system that is not provably as difficult to break as it is
to solve the IFP, but that is also not vulnerable to chosen-ciphertext attacks (at
least not the one described earlier).
This choice is not an easy one. From a practical point of view, however, the
use of redundancy to automate the decryption process is often preferred.
14.2.3
ElGamal
As already mentioned in Section 1.3, Diffie and Hellman introduced public key
cryptography in 1976 [12]. In Section 16.3, we overview and discuss the protocol
they proposed to have two entities agree on a secret key over a public channel. In
its native form, the Diffie-Hellman key exchange protocol can be used neither to
encrypt and decrypt data nor to digitally sign messages and verify digital signatures.
It was not until 1984 that Taher ElGamal 12
found a way to turn the Diffie-Hellman
12
Taher ElGamal was a Ph.D. student of Hellman at Stanford University.
Search WWH ::




Custom Search