Cryptography Reference
In-Depth Information
m
e
(mod
N
) where 1
m
<
2
k
.
Exercise 24.4.4
(Boneh, Joux, Nguyen [
77
]) Suppose
c
=
≤
Show that if
m
m
1
m
2
for two integers 1
<
m
1
,
m
2
<B
then one can determine
m
in
O
(
B
)
exponentiations modulo
N
.If
B
=
2
k/
2
+
then the probability that
m
splits in this way is
=
noticeable.
24.4.3 Desmedt-Odlyzko attack
This is a “lunchtime attack” proposed by Desmedt and Odlyzko in [
157
] on textbook RSA
signatures. It can produce more forgeries than calls to the signing oracle. The basic idea
is to query the signing oracle on the first
r
prime numbers
p
1
,...,p
r
to get signatures
s
1
,...,
s
r
. Then, for any message
m
,if
m
is a product of powers of the first
r
primes
m
=
r
i
=
1
p
f
i
then the corresponding signature is
i
r
s
f
i
.
=
s
i
=
1
This attack is not feasible if messages are random elements between 1 and
N
(as the
probability of smoothness is usually negligible) but it can be effective if messages in the
system are rather small.
Exercise 24.4.5
Let
N
7 be an RSA public key. Suppose
one learns that the signatures of 2, 3 and 5 are 872240067492, 6442782604386 and
1813566093366 respectively. Determine the signatures for messages
m
=
9178628368309 and
e
=
=
6
,
15
,
12 and
100.
An analogous attack applies to encryption: ask for decryptions of the first
r
primes
(treating them as ciphertexts) and then, given a challenge ciphertext
c
,if
c
≡
r
i
=
1
p
e
i
i
then
one can work out the decryption of
c
. Since ciphertexts (even of small messages) are of
size up to
N
this attack is usually not faster than factoring the modulus.
This idea, together with a number of other techniques, has been used by Coron, Naccache,
Tibouchi and Weinmann [
142
] to attack real-world signature proposals.
24.4.4 Related message attacks
This attack is due to Franklin and Reiter.
7
Consider textbook RSA with small exponent
e
or textbook Rabin (
e
2). Suppose we obtain ciphertexts
c
1
and
c
2
(with respect to
the same public key (
N,e
)) for messages
m
and
m
=
a
for some known integer
a
. Then
m
is a common root modulo
N
of the two polynomials
F
1
(
x
)
+
x
e
=
−
c
1
and
F
2
(
x
)
=
a
)
e
(2
l
(
x
1)
2
(
x
+
−
c
2
(for Rabin we may have polynomials like
F
1
(
x
)
=
+
1)
−
−
c
1
or
1))
2
F
1
(
x
)
=
(2(2
x
+
−
C
1
). Hence, one can run Euclid's algorithm on
F
1
(
x
) and
F
2
(
x
)in
(
Z
/N
Z
)[
x
] and this will either lead to a factor of
N
(since performing polynomial division
7
The idea was presented at the “rump session” of CRYPTO 1995.
