Cryptography Reference
In-Depth Information
2
10
. Hence, if one obtains
and that
z
+
u,z
+
v
and
z
+
w
are all between
P
and
P
+
signatures
s
1
,
s
2
,
s
3
on
m
+
u
=
401
,
m
+
v
=
537 and
m
+
w
=
552 then one has the
signature on
z
as
s
2
s
3
s
−
1
1
(mod
N
).
The success of this attack depends on the cost of factoring
r
and the probability that it
can be written as a product of integers of similar size. Hence, the attack has subexponential
complexity. For fixed
m
the attack may not succeed (since
r
might not factor as a product
of integers of the required size). On the other hand, if
m
can vary a little (this is now more
like an existential forgery) then the attack should succeed. A method for existential forgery
that does not require factoring is given in Example
24.4.13
.
Exercise 24.4.11
Give a variant of the above attack for the case where messages can be of
size
N
1
/
2
and for which it is only necessary to obtain signatures on two messages.
Exercise 24.4.12
One could consider affine padding
A
m
m
, where
A
and
B
are fixed integers and
m
is small. Show that, from the point of view of attacks, the
two padding schemes are equivalent.
+
B
instead of
P
+
Example 24.4.13
We sketch the existential forgery from [
99
]. As before, we seek messages
m
1
,...,
m
4
of size
N
1
/
3
such that
(
P
+
m
1
)(
P
+
m
2
)
≡
(
P
+
m
3
)(
P
+
m
4
)(mod
N
)
.
Writing
m
1
=
x
+
t,
m
2
=
y
+
t,
m
3
=
t
and
m
4
=
x
+
y
+
z
+
t
the equation is seen to
be equivalent to
Pz
≡
xy
−
tz
(mod
N
). One again uses Euclid to find
s
≈
N
1
/
3
,r
≈
N
2
/
3
such that
Ps
≡
r
(mod
N
). One sets
z
=
s
and then wants to find
x,y,t
such that
xy
=
tz
. To do this choose a random integer
N
1
/
3
<y<
2
N
1
/
3
such that gcd(
y,z
)
r
+
=
1 and
z
−
1
r
(mod
y
). One then easily solves for the remaining values and one can check
that the
m
i
are roughly of the right size.
set
t
≡−
For further details and results we refer to Brier, Clavier, Coron and Naccache [
99
] and
Lenstra and Shparlinski [
336
].
This idea, together with other techniques, has been used to cryptanalyse the ISO/IEC
9796-1 signature standard with great success. We refer to Coppersmith, Coron, Grieu,
Halevi, Jutla, Naccache and Stern [
133
].
24.5 Attacks on RSA parameters
In this section we briefly recall some attacks on certain choices of RSA public key.
24.5.1 Wiener attack on small private exponent RSA
One proposal to speed-up RSA decryption is to choose
d
to be a small integer. Key
generation is performed by first choosing
d
and then setting
e
d
−
1
=
(mod
λ
(
N
)). This is
