Cryptography Reference
In-Depth Information
(
,
,
)
polynomial-time algorithm that on input
gives as output the prime factors
of
n
. Summing up, all the attempts to break the RSA hypothesis so far led to algo-
rithms that are also able to efficiently factor the modulus and so it is still possible
that the RSA problem is as hard as factoring, although in [38] some results are given
that suggest that the RSA problem might be easier than factoring when the exponent
e
is small (such as, for example,
e
n
e
d
=
3or
e
=
17).
8.3.2 Plain RSA
We are now ready to introduce the RSA encryption scheme. We will first describe
'plain RSA'
(often also called 'textbook RSA') which is exactly the system introduced
by its inventors in 1978. This scheme is deterministic and hence it is not CPA secure
which, nowadays, is a minimal security requirement. However, the analysis of its
security properties will serve as a starting point to consider more secure variants of
the scheme.
Definition 8.12
Plain RSA
is the public-key encryption scheme RSA
=
(
Gen
,
Enc
,
Dec
)
defined by the following algorithms:
Gen
: On input 1
k
, run the RSA instance generator to obtain
•
(
n
,
e
,
d
)
←
Gen
RSA
.
Then set
pk
:=
(
n
,
e
)
and
sk
:=
(
n
,
d
)
. The output of the algorithm is then
1
k
(
,
)
←
(
)
pk
sk
Gen
, where
pk
is the public key and
sk
is the private key.
•
=
(
,
)
∈ Z
n
(
Z
n
is the plaintext
Enc
: On input a public key
pk
n
e
and a message
m
space associated with the modulus
n
), compute the ciphertext:
m
e
mod
n
c
:=
Enc
(
pk
,
m
)
=
RSA
)
(
m
)
=
∈ Z
n
.
(
n
,
e
•
Dec
: On input a private key
sk
=
(
n
,
d
)
and a ciphertext
c
∈ Z
n
, compute the
message:
c
d
mod
n
m
:=
Dec
(
sk
,
c
)
=
RSA
)
(
c
)
=
∈ Z
n
.
(
n
,
d
Remarks 8.6
1. As in other public-key encryption schemes, each user should run
Gen
to obtain
her public and private keys or, alternatively, these keys may be obtained from
a trusted third party. As already mentioned,
n
is called the RSA
modulus
and,
similarly,
e
is the
encryption exponent
and
d
is the
decryption exponent
.
2. Sometimes the primes
p
pq
are considered as part of the private key because, as we will see, they can be
used to speed up decryption. This is a convenience issue but the primes are not
necessary for decryption so they can also be discarded after running
Gen
.On
the other hand, the only part of the private key
,
q
used by
Gen
RSA
to build the modulus
n
=
that must remain secret is
the decryption exponent
d
, as the modulus is also part of the public key. Because
of this it can also be considered that the private key is just
d
.
(
n
,
d
)
