Cryptography Reference
In-Depth Information
8.3.4.1 Wiener's Low Exponent Attack
This attack was presented by M.J. Wiener in 1990 and it uses the theory of continued
fractions to compute the decryption exponent
d
efficiently from the public key (
n
,
e
)
.
n
1
/
4
The attack assumes that
d
2
p
, where
p
and
q
are the
prime factors of
n
(note that the latter hypothesis is commonly satisfied by RSAkeys).
Since
ed
<
/
3 and that
p
<
q
<
≡
1
(
mod
φ(
n
))
, there exists an integer
t
<
d
such that
ed
=
1
+
t
φ(
n
)
.
3
n
1
/
2
.
Moreover, the hypothesis on the prime factors of
n
implies that
p
+
q
<
3
p
<
Thus, bearing in mind that
φ(
n
)
=
n
−
(
p
+
q
)
+
1, we have:
=
=
≤
<
=
.
3
tn
1
/
2
nd
e
n
−
t
d
ed
−
tn
1
+
t
(φ(
n
)
−
n
)
t
(
p
+
q
)
3
t
n
1
/
2
d
nd
nd
nd
n
1
/
4
n
1
/
4
and, since
t
Now, since
d
<
/
3 by hypothesis, we have that 3
d
<
<
d
,
n
1
/
4
. This implies that
<
3
t
n
1
/
2
d
1
n
1
/
4
d
<
we also have that 3
t
, and combining these
inequalities we obtain:
<
.
e
n
−
t
d
1
3
d
2
t
d
e
This inequality says that
n
and then the theory of
continuous fractions allows the computation of
d
in polynomial time. We refer to
[101,169] for more detailed explanations. There is a lattice-based extension of this
attack due to Boneh and Durfee, with an efficient variant of Blömer and May that can
recover the RSA decryption exponent
d
provided that
d
is a close approximation of
n
0
.
292
. These attacks, for
which we refer again to [101], are heuristic but work well in practice and hence this
bound should not be violated when choosing RSA keys. If the encryption exponent
is chosen first then the probability that
d
turns out to be less than this bound is very
small and if
e
<
2
16
=
+
1 (or some other small exponent), as is often the case, then
the size of
d
will surely be much larger than this bound because
ed
>φ(
)
n
and the
size of
φ(
n
)
is very close to that of
n
.
8.3.4.2 Some Reasons Why Plain RSA is Insecure
We will now deal with plain RSA because, although its security level is very weak,
knowledge of its weaknesses provides helpful information in the quest for more
secure schemes. We have seen that plain RSA is OW-CPA secure but now we explic-
itly show the reasons why this is a very weak security notion.
Example 8.5
Suppose that Alice sends the following ciphertext to Bob, whose public
RSA key is
pk
in Example 8.2.
