Cryptography Reference
In-Depth Information
Because breaking the ElGamal asymmetric encryption system is computation-
ally equivalent to solving the DHP, we know from Section 7.4.3 that we must work
with moduli that are at least 1,024 bits long. Furthermore, special care must be taken
not to use primes with special properties (i.e., properties for which discrete loga-
rithms are known to be efficiently computable in the corresponding cyclic groups).
14.3
SECURE SYSTEMS
In Section 14.1, we looked at different notions of security for asymmetric encryption
systems, and we introduced and briefly discussed the notion of semantic security. In
this section, we elaborate on two asymmetric encryption systems that can be shown
to be semantically secure: probabilistic encryption and OAEP (as already mentioned
in Section 14.2.1.4).
14.3.1
Probabilistic Encryption
The notion of probabilistic encryption was developed and proposed in the early
1980s by Shafi Goldwasser and Silvio Micali at MIT [2]. The implementation they
suggested is based on the QRP (see Definition 3.32). It is widely believed that the
QRP is computationally equivalent to the IFP and hence that solving the QRP is
computationally intractable for sufficiently large integers n .
In Section 3.3.7, we said that
x
p
=1
x
QR p
for every prime number p . So if we work with a prime number p , then the Legendre
symbol of x modulo p is 1 if and only if x is a quadratic residue modulo p .Wealso
said that the Legendre symbol of x modulo p can be efficiently computed using, for
example, Euler's criterion (see Theorem 3.9).
Things are more involved if one does not work with prime numbers. In fact, if
we work with a composite integer n ,then
x
n
=1
x
QR n
but
x
n
=1 .
x
QR n
Search WWH ::




Custom Search