Cryptography Reference
In-Depth Information
generate signatures if the input is correctly padded) and that a hash function is not applied
to the messages. Suppose
m
is the target message, so we want to compute the
d
th power of
z
=
P
+
m
. The idea is to find small values
u,v,w
such that
+
≡
+
+
z
(
z
u
)
(
z
v
)(
z
w
)(mod
N
)
.
(24.2)
Then given signatures on
m
+
u,
m
+
v
and
m
+
w
(i.e.,
d
th powers of
z
+
u,z
+
v
and
z
+
w
) one can compute the signature on
m
as required.
To find small solutions to equation (
24.2
) we expand and simplify to
z
(
u
−
v
−
w
)
≡
vw
(mod
N
)
.
Running the extended Euclidean algorithm (the basic version rather than the fast version
of Algorithm
1
)on
z
and
N
gives a number of integers
s,r
such that
zs
≡
r
(mod
N
)
and
|
rs
|≈
N.
N
1
/
3
N
2
/
3
One can run Euclid until a solution with
|
s
|≈
and
|
r
|≈
is found. One then
tries to factor
r
as a product
r
vw
of numbers of a similar size. If this is feasible (for
example, if
r
has a large number of small prime factors) then set
u
=
w
and we
have a solution. This approach is reasonable as long as the messages are at least one third
of the bit-length of the modulus.
=
s
+
v
+
2
20
.
Example 24.4.10
Let
N
=
1043957
≈
2
19
Suppose
P
=
is the fixed padding and suppose messages are restricted to be 10-bit
binary strings. Thus
z
=
P
+
m
m
<
2
10
.
Suppose have access to a signing oracle and would like to forge a signature on the
message
m
≤
where 0
524791.
We apply Euclid's algorithm on
N
and
z
to solve the congruence
zs
=
503 that corresponds to
z
=
P
+
503
=
≡
r
(mod
N
) where
N
1
/
3
s
≈
≈
101.
i
q r
i
s
i
t
i
−
1
-
1043957
1
0
0
-
524791
0
1
1
1
519166
1
−
1
−
2
1
5625
1
2
−
3
92
1666
93
185
This gives the solution
−
185
z
≡
1666 (mod
N
) and
|−
185
|≈
N
1
/
3
.Soset
s
=−
185
7
2
and
r
=
1666. We try to factor
r
and are lucky that 1666
=
2
·
·
17. So choose
v
=
34
and
w
=
49. Finally, choose
u
=
v
+
w
−
185
=−
102. One can check that
z
(
z
+
u
)
≡
(
z
+
v
)(
z
+
w
)(mod
N
)
