Cryptography Reference
In-Depth Information
in (
)[
x
] involves computing inverses modulo
N
) or will output, with high probability,
a linear polynomial
G
(
x
)
Z
/N
Z
m
.
Euclid's algorithm for polynomials of degree
e
has complexity
O
(
e
2
M
(log(
N
))) or
O
(
M
(
e
) log(
e
)
M
(log(
N
))) bit operations. Hence, this method is feasible only when
e
is
rather small (e.g.,
e<
2
30
).
=
x
−
Exercise 24.4.6
Extend the Franklin-Reiter attack to ciphertexts
c
1
and
c
2
(again, for the
same public key) where
c
1
is an encrypion of
m
and
c
2
is an encryption of
a
m
+
b
for
known integers
a
and
b
.
=
=
Exercise 24.4.7
Let
N
2157212598407 and
e
3. Suppose we have ciphertexts
c
1
=
and
c
2
=
1429779991932
655688908482
+
2
10
. Determine the
such that
c
1
is the encryption of
m
and
c
2
is the encryption of
m
message
m
.
These ideas have been extended by Coppersmith, Franklin, Patarin and Reiter [
134
].
Among other things they study how to break related encryptions for any polynomial relation
by using resultants (see Exercise
24.4.8
).
m
1
Exercise 24.4.8
Let (
N,e
) be an RSA key. Suppose one is given
c
1
=
(mod
N
),
m
2
c
2
=
0(mod
N
).
Let
d
be a bound on the total degree of
P
(
x,y
). Show how to compute
m
1
and
m
2
in
O
((
d
(mod
N
) and a polynomial
P
(
x,y
)
∈ Z
[
x,y
] such that
P
(
m
1
,
m
2
)
≡
e
)
3
d
2
M
(log(
N
))) bit operations.
+
24.4.5 Fixed pattern RSA signature forgery
The aim of this section is to present a simple padding scheme, often called
fixed pattern
padding
for RSA. We then sketch why this approach may not be sufficient to obtain RSA
signatures secure against adaptive attackers. These ideas originate in the work of De Jonge
and Chaum and later work by Girault and Misarsky. We present the more recent attacks by
Brier, Clavier, Coron and Naccache [
99
]. An attack on RSA encryption with fixed padding
is given in Section
19.4.1
.
Example 24.4.9
Suppose we are using moduli of length 3072 bits and that messages (or
message digests)
m
are of length at most 1000 bits.
The padding scheme uses a fixed value
P
2
3071
=
and the signature on the message
m
<
2
1000
)is
digest
m
(such that 0
≤
m
)
d
(mod
N
)
.
=
(
P
+
s
The verifier computes
s
e
(mod
N
) and checks if it is of the correct form
P
+
m
with
m
<
2
1000
.
0
≤
The following method (from [
99
]) forges signatures if messages are roughly
N
1
/
3
in
size. We assume that a signing oracle is available (we assume the signing oracle will only
