Cryptography Reference
In-Depth Information
7.1 Introduction
The RSA crypto scheme, sometimes referred to as the Rivest-Shamir-Adleman al-
gorithm, is currently the most widely used asymmetric cryptographic scheme, even
though elliptic curves and discrete logarithm schemes are gaining ground. RSA was
patented in the USA (but not in the rest of the world) until 2000.
There are many applications for RSA, but in practice it is most often used for:
encryption of small pieces of data, especially for key transport
digital signatures, which is discussed in Chap. 10, e.g., for digital certificates on
the Internet
However, it should be noted that RSA encryption is not meant to replace sym-
metric ciphers because it is several times slower than ciphers such as AES. This
is because of the many computations involved in performing RSA (or any other
public-key algorithm) as we learn later in this chapter. Thus, the main use of the
encryption feature is to securely exchange a key for a symmetric cipher (key trans-
port). In practice, RSA is often used together with a symmetric cipher such as AES,
where the symmetric cipher does the actual bulk data encryption.
The underlying one-way function of RSA is the integer factorization problem:
Multiplying two large primes is computationally easy (in fact, you can do it with
paper and pencil), but factoring the resulting product is very hard. Euler's theorem
(Theorem 6.3.3) and Euler's phi function play important roles in RSA. In the fol-
lowing, we first describe how encryption, decryption and key generation work, then
we talk about practical aspects of RSA.
7.2 Encryption and Decryption
RSA encryption and decryption is done in the integer ring
Z
n
and modular com-
putations play a central role. Recall that rings and modular arithmetic in rings were
introduced in Sect. 1.4.2. RSA encrypts plaintexts
x
, where we consider the bit string
representing
x
to be an element in
. As a consequence the bi-
nary value of the plaintext
x
must be less than
n
. The same holds for the ciphertext.
Encryption with the public key and decryption with the private key are as shown
below:
Z
n
=
{
0
,
1
,...,
n
−
1
}
RSA Encryption
Given the public key (
n
,
e
)=
k
pub
and the plaintext
x
,the
encryption function is:
x
e
≡
y
=
e
k
pub
(
x
)
mod
n
(7.1)
where
x
,
y
∈
Z
n
.
