Public-Key Cryptography - A Classical Introduction to Cryptography: Applications for Communications Security - page 236

9.3.3 Attacks on Broadcast Encryption with Low Exponent

Although the RSA cryptosystem is believed to be quite strong, there are many ways to
use it insecurely. One of it is the broadcast encryption with low encryption exponent.
Let us assume that one sender wants to broadcast the same message x to n different
parties who have public keys ( e , N 1 ) ,..., ( e , N n ) with the same low exponent e . (In

many applications, e = 3 is suggested, so this hypothesis seems reasonable.) The sender

x e

has to send y i = mod N i to the i -th receiver for i = 1 ,..., n .

Assuming that we have n > e , it becomes fairly easy to decrypt all the correspond-

ing ciphertexts y 1 ,..., y n : Let us assume that all N i are pairwise relatively primes,

which means that no prime factor is used in two different moduli N i and N j . (If this
does not hold, then the system has indeed other weaknesses.) Let N be the product of
all N i . Due to the Chinese Remainder Theorem, we can compute y such that y < N

and y x e

(mod N ). However, the natural integer x e is less than N because x is less than all N i
and N is the product of more than e integers N i . Since y

≡ y i (mod N i ) for all i . This way we have y ≡ x e (mod N i ) for all i , thus y ≡

< N as well, we have indeed

x e . Then it becomes trivial to extract the e -th root over the natural integers in order
to compute x . 6

y =

9.3.4 Attacks on Low Exponent

Low exponents have several drawbacks. We distinguish low e 's from low d 's .

When e is low, there exist efficient attacks due to Don Coppersmith against various
uses of RSA (see Ref. [49]). More precisely, there exists an efficient algorithm in log N
which finds roots of a modulo N polynomial equation of degree e as long as one of it is
less than N e . As an application, if a fraction of

2
3

of the bits of the plaintext are known

and e 3, then one can decrypt efficiently. As another application, if two plaintexts

differ only in a (known) windown of length one ninth of the full length and e

=

= 3, one

can decrypt the two corresponding ciphertexts.

When d is low, there exists an efficient algorithm due to Michael Wiener which
enables the recovery of the secret ke y (see Ref. [185]). It works in typical cases (with
p and q of same size) with d

√ N . This bound can further be improved by using the
LLL lattice reduction algorithm.

<

4

9.3.5 Side Channel Attacks

There are several ways to get “side information” in order to be able to break RSA.
As a first example we mention the differential fault analysis . We assume that we
can play with the decryptor device as with a black box and we want to retrieve the

6

This simple attack is due to Johan Hastad. See Ref. [87].