Cryptography Reference
In-Depth Information
already mentioned, it is not known whether the factoring assumption implies the
RSA assumption and hence whether the presumed hardness of factoring is sufficient
to guarantee even this weakest form of security. But, since the factoring problem has
been intensively studied, it is convenient to take it as a reference point and hence
a minimal security requirement for RSA is to try to ensure that it is infeasible in
practice to factor the modulus generated by
Gen
. Obtaining estimates for key sizes
that provide this kind of short-term security is relatively easy but it is very difficult for
long-term periods because of the many variables involved, not to mention the possi-
bility that an efficient factoring algorithmmight be found, in which case RSA—in all
its variants—would be definitely broken. As mentioned when discussing the integer
factorization problem, the current RSA factorization record is a 768-bit modulus
and 1024-bit moduli are already regarded as insecure even for short-term use, so the
recommended sizes start at 2048 bits and go up to 4096 bits and beyond. Of course,
using a longer key length entails an efficiency loss and, in practical applications,
there is always a trade-off between security and performance. Some estimates about
the possible evolution of factoring in the future are given in [151] and also, within
the more general framework of cryptographic key sizes in general, in [128].
Exercise 8.5
Consider the 2048-bit RSA modulus
n
obtained in Maple as follows:
> n := nextprime(2ˆ1023+2ˆ1022)*nextprime(2ˆ1024):
Explain whether
n
can be factored in practice with Fermat's method and discuss
whether
n
is a good RSA modulus.
Exercise 8.6
(i) Show that if
(
n
,
e
)
is an RSA public key and
m
∈ Z
n
, then there exists a
positive integer
k
such that
RSA
k
(
)
(
m
)
=
m
(where the exponent
k
indicates
n
,
e
k
iterations of the RSA function).
(ii) Indicate how this gives a method to recover the plaintext
m
from the ciphertext
c
(this is a so-called
cycling attack
which, as shown in [165],
has negligible probability of success when
n
is a product of two sufficiently
large random primes and, in fact, by [78], has expected complexity similar to
that of factoring the modulus by trial division).
(iii) Use Maple to find the minimum value of
k
such that
RSA
k
(
=
RSA
)
(
m
)
(
n
,
e
,
e
)
(
m
)
=
m
for
143
all
m
∈ Z
143
and all possible values of the encryption exponent
e
.
8.3.2.1 Plain RSA in Practice
We are going to implement plain RSA inMaple but before doing so we shall discuss a
few points that are relevant for any implementation. In relation to the key generation
algorithm, two primes of length
k
should be randomly chosen (or they can be chosen
so that one of them has
k
bits and the other one
k
1 bits). In our implementation
we will settle for choosing them pseudo-randomly using a variant of the function
+
