Cryptography Reference
In-Depth Information
RSA Decryption
Given the private key
d
=
k
pr
and the ciphertext
y
,the
decryption function is:
y
d
x
=
d
k
pr
(
y
)
≡
mod
n
(7.2)
where
x
,
y
∈
Z
n
.
In practice,
x
,
y
,
n
and
d
are very long numbers, usually 1024 bit long or more.
The value
e
is sometimes referred to as
encryption exponent
or
public exponent
, and
the private key
d
is sometimes called
decryption exponent
or
private exponent
.If
Alice wants to send an encrypted message to Bob, Alice needs to have his public
key (
n
,
e
), and Bob decrypts with his private key
d
. We discuss in Sect. 7.3 how
these three crucial parameters
d
,
e
, and
n
are generated.
Even without knowing more details, we can already state a few requirements for
the RSA cryptosystem:
1. Since an attacker has access to the public key, it must be computationally infea-
sible to determine the private-key
d
given the public-key values
e
and
n
.
2. Since
x
is only unique up to the size of the modulus
n
, we cannot encrypt more
than
l
bits with one RSA encryption, where
l
is the bit length of
n
.
3. It should be relatively easy to calculate
x
e
mod
n
, i.e., to encrypt, and
y
d
mod
n
,
i.e., to decrypt. This means we need a method for fast exponentiation with very
long numbers.
4. For a given
n
, there should be many private-key/public-key pairs, otherwise an
attacker might be able to perform a brute-force attack. (It turns out that this re-
quirement is easy to satisfy.)
7.3 Key Generation and Proof of Correctness
A distinctive feature of all asymmetric schemes is that there is a set-up phase dur-
ing which the public and private key are computed. Depending on the public-key
scheme, key generation can be quite complex. As a remark, we note that key gener-
ation is usually not an issue for block or stream ciphers.
Here are the steps involved in computing the public and private-key for an RSA
cryptosystem.
