Cryptography Reference
In-Depth Information
Last but not least, there is another low exponent attack if a plaintext message
m
is encrypted for multiple recipients that share a common public exponent
e
(with
different moduli). More specifically, let
m
be a plaintext message that is encrypted
r
2 times and all
r
recipients have the same public exponent
e
(but different
moduli
n
i
for
i
=1
,...,r
). Then an adversary who knows the ciphertexts
c
i
≡
m
e
(mod
n
i
) for
i
=1
,...,r
can use the CRT to compute
c
with
c
≥
≡
c
i
(mod
n
i
)
c<
i
=1
n
i
. Obviously,
c
is equal to
m
e
,so
m
can be
efficiently determined by computing the
e
th
root of
c
. The low exponent attack is
relevant only for small values of
e
. If, for example,
e
=3,
n
1
= 143,
n
2
= 391,
n
3
= 899,and
m
= 135, then the adversary can solve the following system of three
equivalences:
for
i
=1
,...,r
and 0
≤
m
e
(mod
n
1
) = 135
3
(mod 143) = 60
c
1
≡
m
e
(mod
n
2
) = 135
3
(mod 391) = 203
c
2
≡
m
e
(mod
n
3
) = 135
3
(mod 899) = 711
c
3
≡
Using the CRT, he or she can compute
c
=2
,
460
,
375, and hence
m
=
√
2
,
460
,
375 = 135. There are several generalizations of this attack.
Conclusions and Recommendations
The question that is most frequently asked when it comes to an implementation or
use of the RSA asymmetric encryption system is related to the size of the modulus
n
. Obviously,
n
must be at least as large as to make it impossible to use an existing
algorithm to factorize
n
. As of this writing, there is general consensus that at least
1,024-bit moduli should be used (this recommendation is also supported by the
NIST). Note, however, that the value of the data must be taken into account when
one recommends specific security parameters. So it is not uncommon to recommend
2,048-bit moduli for the asymmetric encryption of more valuable data. If one has
fixed the size of the modulus, then one has implicitly also fixed the size of the prime
factors
p
and
q
(because they should be of roughly similar size). If, for example, one
wants to work with a 1,024-bit modulus
n
,then
p
and
q
must be about 512 bits long
each. Unless one uses short moduli (where Pollard's P
1 algorithm can be applied),
there is no urgent need to work only with strong primes.
The question that is less frequently asked (but is also important from a security
viewpoint) is related to the size of the public and private exponents. As discussed
earlier, working with small private exponents is dangerous. So
d
should not be
smaller than a certain threshold (i.e.,
d<N
0
.
292
according to [10]). If, for example,
n
is 1,024 bits long, then
d
should not be smaller than 300 bits. On the other hand, it
−
