Cryptography Reference
In-Depth Information
8.3.4.4 Håstad's Broadcast Attack
One of the simplest attacks of this type arises when a small encryption exponent is
used. As we have mentioned, this was quite common in the early years of RSA usage
when, in order to gain efficiency, 3 was frequently used as encryption exponent.
Observe first that if
m
∈ Z
n
is a message such that
m
e
n
, then the ciphertext
c
corresponding to
m
is actually the
e
th power of
m
in the integers and so
m
can
be computed from
c
by extracting an integer
e
th root, for which there are efficient
algorithms. It is clear that for the condition
m
e
<
<
n
to be satisfied, a small exponent
is required (since we may assume that
m
1, otherwise decrypting
c
is easy no
matter what the exponent is). For example, when
e
=
0
,
=
3, any message
m
∈ Z
n
such
n
1
/
3
will satisfy this condition and hence will be easily recoverable. Of
course, this problem is easily prevented by not allowingmessages to be very small but
there is a generalized attack that works even with arbitrary length messages provided
that the same plaintext is encrypted with different RSA keys that use the same small
encryption exponent. This attack is the following:
that
m
<
Proposition 8.4
(Håstad's broadcast attack)
Let
(
n
1
,
e
), (
n
2
,
e
), . . . , (
n
t
,
e
)
, with
=
i
=
1
n
i
.
t
≥
e, be public RSA keys with pairwise relatively prime moduli and let n
Then, if m is a plaintext such that m
<
min
(
n
1
,...,
n
t
)
, there is an algorithm that,
m
e
mod
n
i
and the keys
on input the ciphertexts c
i
=
(
n
i
,
e
i
)
, computes m in
polynomial time.
Proof
Since the
n
i
are pairwise relatively prime, the system of congruences:
⎫
⎬
x
≡
c
1
(
mod
n
1
)
x
≡
c
2
(
mod
n
2
)
.
(8.2)
⎭
x
≡
c
t
(
mod
n
t
)
has, by the Chinese remainder theorem (Theorem 2.12) a unique solution in
Z
n
,say
2
C
, and this solution may be computed in time
O
(
len
(
n
)
)
. But, by definition of the
c
i
,
m
e
t
,
m
e
is a solution of the system and, since
m
<
min
(
n
1
,...,
n
t
)
and
e
≤
∈ Z
n
.
Thus
m
e
C
, so in order to compute
m
it only remains to compute the
e
th root of
C
over the integers, which can also be done in time polynomial in len
=
(
n
)
.
Remark 8.2
Observe that the requirement that the moduli of the keys be pair-
wise relatively prime is not restrictive (assuming the keys are distinct). Indeed, if
gcd
(
n
i
,
n
j
)
=
1, then this gives the factorization of
n
i
and
n
j
.
The next function implements Håstad's broadcast attack in Maple. There are two
input parameters which accept a list of public keys and a list of ciphertexts; both lists
should have the same length and the ciphertexts should all be obtained froma common
plaintext and should correspond, in order, to the keys in the list. Both public keys and
ciphertexts should be in the decimal format provided by the functions
RSAKeyGen
and
RSAEncrypt
, respectively. It is a trivial matter to modify the function to also
