Cryptography Reference
In-Depth Information
uses a sufficiently good padding scheme. Indeed, by studying these attacks one develops a
better idea of what properties are required of a padding scheme.
24.4.1 The Hastad attack
We now present an attack that can be mounted on the RSA or Rabin schemes in a multi-
user situation. Note that such attacks are not covered by the standard security model for
encryption as presented in Chapter
1
.
Example 24.4.1
Suppose three users have RSA public keys
N
1
,N
2
,N
3
and all use encryp-
tion exponent
e
be a message. If
m
is encrypted to all
three users then an attacker can determine
m
from the three ciphertexts
c
1
,
c
2
and
c
3
as
follows: the attacker uses the Chinese remainder theorem to compute 1
<
c
<N
1
N
2
N
3
such that
c
=
3. Let 0
<
m
<
min
{
N
1
,N
2
,N
3
}
m
3
m
3
≡
(mod
N
i
)for1
≤
i
≤
3. It follows that
c
=
over
Z
and so one can
determine
m
using root-finding algorithms.
This attack is easily prevented by using randomised padding schemes (assuming that
the encryptor is not so lazy that they re-use the same randomness each time). Nevertheless,
this attack seems to be one of the reasons why modern systems use
e
2
16
=
65537
=
+
1
instead of
e
=
3.
Exercise 24.4.2
Show that the Hastad attack applies when the same message is sent using
textbook Rabin encryption (with any of the three redundancy schemes) to two users.
Exercise 24.4.3
Two users have Rabin public keys
N
1
=
138951937.
The same message
m
is encrypted using the “extra bits” padding scheme to the two users,
giving ciphertexts
144946313 and
N
2
=
C
1
=
(48806038
,
−
1
,
1) and
C
2
=
(14277753
,
−
1
,
1)
.
Use the Hastad attack to find the corresponding message.
24.4.2 Algebraic attacks
We already discussed a number of easy algebraic attacks on textbook RSA, all of which
boil down to exploiting the multiplicative property
m
1
m
2
≡
(
m
1
m
2
)
e
(mod
N
)
.
We also noted that, since textbook RSA is deterministic, it can be attacked by trying all
messages. Hence, if one knows that 1
m
<
2
k
(for example, if
m
is a
k
-bit symmetric
key) then one can attack the system in at most 2
k
exponentiations modulo
N
. We now show
≤
that one can improve this to roughly
√
2
k
exponentiations in many cases.
