Cryptography Reference
In-Depth Information
=
√
K
and let
L
. Then
d
p
=
d
0
+
Ld
1
where 0
≤
d
0
,d
1
<L
and, for a random integer
1
<
m
<N
, one expects
gcd(
m
ed
0
−
1
m
Led
1
−
1
,N
)
=
p.
The problem is to detect this match. The idea is to use the method of Section
2.16
for
evaluating polynomials. So, define
L
−
1
(
m
ej
−
1
x
G
(
x
)
=
−
1) (mod
N
)
.
j
=
0
This polynomial has degree
L
and can be constructed using the method in the proof
of Theorem
2.16.1
in
O
(
M
(
L
)log(
L
)
M
(log(
N
))) bit operations. The polynomial
G
(
x
)
requires
L
log
2
(
N
) bits of storage.
Now, compute
c
m
Le
(mod
N
). We wish to evaluate
G
(
c
d
1
)(mod
N
) for each of
=
the candidate values 0
d
1
<L
(to obtain a list of
L
values). This can be performed
using Theorem
2.16.1
in
O
(
L
log(
L
)
2
log(log(
L
))
M
(log(
N
))) bit operations. For each value
G
(
c
d
1
)(mod
N
) in the list we can compute
≤
gcd(
G
(
c
d
1
)
,N
)
O
(
√
K
) bit operations.
to see if we have split
N
. The total running time of the attack is
Exercise 24.5.9
(Galbraith, Heneghan and McKee [
203
]) Suppose one chooses private CRT
exponents of bit-length
n
and Hamming weight
w
. Use the ideas of this section together
with those of Section
13.6
to gi
ve
an algorithm to compute a CRT private exponent, given
n
and
w
, with complexity
O
(
√
wW
log(
W
)
2
log(log(
W
))
M
(log(
N
))) bit operations where
W
=
n/
2
w/
2
.
When
e
is also small (e.g., when using the key generation method of Exercise
24.1.4
)
then there are lattice attacks on small CRT private exponents. We refer to Bleichenbacher
and May [
64
] for details.
24.6 Digital signatures based on RSA and Rabin
There are numerous signature schemes based on RSA and Rabin. Due to lack of space we
just sketch two schemes in the random oracle model. Hohenberger and Waters [
264
]have
given an RSA signature scheme in the standard model whose security relies only on the
strong-RSA assumption.
24.6.1 Full domain hash
A simple way to design RSA signatures that are secure in the random oracle model is
to assume each user has a hash function
H
:
}
∗
→
)
∗
where
N
is their public
{
0
,
1
(
Z
/N
Z
