5.6.2 RSA Algorithm

The RSA algorithm, developed by Ronald L. Rivest, Adi Shamir, and Leonard Adleman in 1977, remains the most widely used public-key encryption and digital-signature system. Its security is widely believed to be computationally equivalent to the difficulty of factoring large integers.

To generate a pair of RSA keys, the first step is to choose two large prime numbers, p and q. Let:

n = p \times q

(5.3)

and calculate the Euler totient function, φ(n), which is the number of positive integers less than or equal to integer n that are coprime to n (that is, have their greatest common divisor (gcd) = 1):

φ (n) = (p - 1) (q - 1)

(5.4)

Next, choose an integer e such that $1 < e < φ (n)$ and $g c d (e, φ (n)) = 1$ . Then determine the private exponent d as the multiplicative inverse of e modulo $φ (n)$ , such that:

(e \times d) m o d ((p - 1) (q - 1)) = 1

(5.5)

where “mod” denotes the remainder when one integer is divided by another. That is, d is the multiplicative inverse of e mod φ(n).

The public key is the pair (e, n); the private key is d. Publication of e and n does not compromise d, because computing d requires knowledge of φ(n), which in turn requires factorization of n.

Both encryption and decryption in RSA involve modular exponentiation to find the remainder. Encryption of a message m with public key (e and n) is performed by:

c = m^{e} m o d n

(5.6)

Decryption of the cipher text c with the private key (d):

m = c^{d} m o d n

(5.7)

It can be shown (using Euler’s theorem) that m^ed≡ m (mod m) ensuring that the recovered plaintext is identical to the original message.

In practice, RSA is used both for encryption and for digital signatures. For confidentiality, encryption is performed with the recipient’s public key and decryption with the private key. For authentication and integrity, a signature is generated using the sender’s private key and verified using the corresponding public key. Modern implementations employ standardized padding schemes (e.g., OAEP and PSS) to ensure security against chosen-ciphertext and related attacks.

5.6.2.1 RSA Implementation Issues

RSA’s computational cost lies primarily in the modular exponentiation operations of Equations (5.6) and (5.7), which are far more complex than the simple substitutions and bitwise operations used in block ciphers such as DES or AES. The exponentiation process produces very large intermediate numbers—often thousands of bits long—requiring the use of modular reduction techniques or multi-precision arithmetic to prevent overflow and maintain efficiency.

Because of this computational overhead, RSA is rarely used to encrypt bulk data directly. Instead, it is typically employed to encrypt a short, random session key that is then used with a faster symmetric algorithm (for example, AES) to protect the main data stream. This hybrid approach combines the performance advantages of symmetric encryption with the secure key-exchange capability of asymmetric cryptography.

Advantages of RSA. The RSA algorithm remains one of the most enduring cryptographic systems in use and has a number of advantages in that it is based on the well-studied integer-factorization problem, with no known polynomial-time solution. It is conceptually straightforward; widely standardized and implemented in virtually all software libraries, and is supported universally across browsers, servers, and PKI infrastructures.

Disadvantages of RSA. The algorithm is, however, computationally intensive such that encryption and signature operations are slower than elliptic-curve equivalents and large key sizes (>2,048 bits) impose higher processing and transmission overhead. The most significant problem with RSA is that it is particularly susceptible to advances in factoring algorithms or quantum computing (see Section 5.7).

Application of RSA. Modern systems employing RSA include TLS 1.2 for HTTPS key exchange, Pretty Good Privacy (PGP) for secure email, and software-signing frameworks such as Microsoft Authenticode and Apple Developer ID.

5.6.2.2 RSA Example

To illustrate the RSA algorithm, consider the following simplified example. In practice, the prime numbers used must be extremely large (typically hundreds of digits) to ensure security; the small values below are chosen only for clarity of computation.

To generate the key, choose two prime numbers p = 5 and q = 19:

n = p \times q = 95

(5.8)

and then compute the modulus:

φ (n) = (p - 1) (q - 1) = 4 \times 18 = 72

(5.9)

Next, choose an integer e such that $1 < e < φ (n)$ and $g c d (e, φ (n)) = 1$ . Selecting e = 7 satisfies these conditions, since $g c d (7,72) = 1$ .

Then determine the private exponent d as the multiplicative inverse of e modulo $φ (n)$ , such that:

(e \times d) m o d φ (n) = 1

(5.10)

Selecting d = 31 satisfies this requirement because:

7 \times 31 = 217 a n d 217 m o d (72) = 1

(5.11)

Thus, the public key is therefore (e, n) = (7, 95) and the private key is d = 31.

To encrypt a plaintext message m = 52, the ciphertext c is computed as:

c = m^{e} m o d (n) = 52^{7} m o d (95) = 3

(5.12)

At the receiver, decryption is performed using the private key d:

m = c^{d} m o d (n) = 3^{31} m o d (95) = 52

(5.13)

The decrypted plaintext m is identical to the original value, confirming correct operation of the RSA algorithm.

Although this small-scale example demonstrates the principle, it provides no practical security—since the modulus n = 95 can be easily factored into 5 × 19. In real systems, the primes are chosen so that the modulus n is typically at least 2,048 bits in length, in accordance with contemporary NIST recommendations. Larger key sizes (for example 3,072 bits or more) are recommended for long-term security.

An alternative to RSA that achieves comparable security with much shorter key lengths is elliptic-curve cryptography (ECC), described next.