After completing this tutorial, you should be able to:
RSA (Rivest-Shamir-Adleman) is the most widely used public-key cryptosystem in the world. Named after its inventors Ron Rivest, Adi Shamir, and Leonard Adleman, who first publicly described the algorithm in 1978, RSA is based on the practical difficulty of factoring the product of two large prime numbers. It can be used for both encryption (providing confidentiality) and digital signatures (providing authentication and non-repudiation).
RSA's security relies on the integer factorization problem: given a composite number n that is the product of two large primes p and q, it is computationally infeasible to find p and q. This problem has been studied for centuries, and no efficient factoring algorithm exists for sufficiently large numbers. As computational power increases, so do the recommended key sizes—today, 2048-bit RSA is considered the minimum, with 3072-bit or 4096-bit recommended for high-security applications.
In this tutorial, we will explore RSA in depth. We begin with the historical context and the mathematical foundations—Euler's theorem, modular arithmetic, and the totient function. We then walk through the key generation, encryption, and decryption processes with worked examples. We prove the correctness of RSA and analyze its security properties. We examine the importance of padding schemes, including PKCS#1 v1.5 and OAEP, and we discuss the differences between RSA for encryption and RSA for signatures. We also survey known attacks on RSA and consider implementation best practices. Finally, we look at standards and real-world applications of RSA.
In Tutorial 2.11, we introduced public-key cryptography fundamentals. This tutorial provides a deep dive into RSA, the most important public-key algorithm. Tutorial 2.13 will cover Diffie-Hellman key exchange, and Tutorial 2.14 will cover Elliptic Curve Cryptography. Tutorial 2.15 will cover digital signatures and PKI.
The RSA algorithm was developed in 1977 at the Massachusetts Institute of Technology (MIT) by Ron Rivest, Adi Shamir, and Leonard Adleman. The three researchers were working on a problem proposed by their colleague, who had read about the concept of public-key cryptography introduced by Diffie and Hellman in 1976.
Rivest, Shamir, and Adleman spent a year trying to find a practical one-way function for public-key encryption. After many failed attempts, they finally succeeded with a system based on the difficulty of factoring large composite numbers. Their algorithm was published in the Communications of the ACM in 1978 under the title "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems."
Key Milestones:
Patents and Legal Issues: RSA was patented in the United States, which limited its use for many years. The patent expired in 2000, allowing for widespread and free use of the algorithm.
RSA relies on several key mathematical concepts from number theory. These were introduced in Tutorial 2.3, but we review them here.
RSA operations are performed modulo n. All computations use modular exponentiation: ab mod n.
RSA uses two large prime numbers p and q. Their product n = p·q is the modulus. The security of RSA depends on the difficulty of factoring n into p and q.
For n = p·q with p and q prime:
φ(n) = (p−1)(q−1)
φ(n) counts the numbers in {1, 2, …, n} that are relatively prime to n.
For any a coprime to n:
aφ(n) ≡ 1 (mod n)
An integer d is the modular inverse of e modulo φ(n) if:
e·d ≡ 1 (mod φ(n))
The inverse exists if gcd(e, φ(n)) = 1 and can be found using the extended Euclidean algorithm.
From Euler's theorem, if e·d ≡ 1 (mod φ(n)), then for any message M (with gcd(M, n) = 1):
(Me)d = Med = M1 + k·φ(n) = M · (Mφ(n))k ≡ M (mod n)
This is the fundamental equation that makes RSA work.
RSA key generation involves creating a public key (used for encryption and signature verification) and a private key (used for decryption and signature generation).
The exponent e is often chosen as a small prime for efficiency, with e = 65537 (216+1) being the most common choice. This value has good cryptographic properties:
Other common choices include e = 3 and e = 17, but these are less secure due to small exponent attacks.
To encrypt a message M (represented as an integer less than n):
C = Me mod n
To decrypt ciphertext C:
M = Cd mod n
Messages must be encoded as integers less than n. In practice, messages are converted to byte arrays and then to integers using a standardized encoding (e.g., PKCS#1). If the message is longer than n, it must be split into blocks, each encrypted separately—but this is rarely done; instead, RSA is used as part of a hybrid cryptosystem.
We prove that RSA decryption correctly recovers the original plaintext.
RSA security is based on the assumption that factoring n = p·q is computationally infeasible for sufficiently large n. The best known factoring algorithms (General Number Field Sieve) have subexponential complexity. For a 2048-bit RSA modulus, the estimated factoring time is measured in billions of years with current technology.
| Security Level (bits) | RSA Key Size (bits) | Comparable Symmetric Key |
|---|---|---|
| 80 | 1024 | 80-bit (insecure) |
| 112 | 2048 | 112-bit |
| 128 | 3072 | 128-bit |
| 192 | 7680 | 192-bit |
| 256 | 15360 | 256-bit |
Current Recommendations:
RSA has a good security margin. The best attacks are still far from practical for recommended key sizes. However, advances in factoring algorithms and quantum computing pose long-term threats.
Textbook RSA (without padding) is insecure for several reasons:
PKCS#1 v1.5 was the first widely used padding scheme for RSA. It adds random padding bytes before the message:
Encrypted Block = 0x00 || 0x02 || PS || 0x00 || Message
Where PS (padding string) consists of random non-zero bytes. This scheme provides semantic security and prevents small message attacks.
Vulnerability: PKCS#1 v1.5 is vulnerable to the Bleichenbacher attack (padding oracle attack), where an attacker can decrypt ciphertext by repeatedly modifying it and observing whether the padding is valid. This attack was used against SSL/TLS (the ROBOT attack).
OAEP (Optimal Asymmetric Encryption Padding) is a more modern padding scheme defined in PKCS#1 v2.0 and later. It uses a cryptographic hash function and a random seed to add both randomness and a "masking" effect.
Figure 1: OAEP padding structure.
Advantages of OAEP:
RSA can also be used for digital signatures. The process is the inverse of encryption:
To sign a message M (or more commonly, the hash of a message):
σ = H(M)d mod n
To verify the signature:
H(M) = σe mod n
PSS (Probabilistic Signature Scheme) is the recommended padding for RSA signatures (PKCS#1 v2.x). It uses a random salt and is provably secure.
If an attacker can factor n into p and q, they can compute φ(n) and d, breaking the system.
Shor's algorithm on a sufficiently large quantum computer can factor n in polynomial time. This would break RSA. Post-quantum cryptography (PQC) is being developed to address this threat.
RSA encryption and decryption use modular exponentiation. Efficient algorithms include:
Instead of computing M = Cd mod n, compute:
d_p = d mod (p−1)
d_q = d mod (q−1)
M_p = C mod p
M_q = C mod q
M_p' = M_p^{d_p} mod p
M_q' = M_q^{d_q} mod q
M = M_q' + q * ((M_p' − M_q') * q^{-1} mod p)
This is about 4 times faster than direct exponentiation.
Blinding randomizes the input to prevent side-channel attacks:
r = random(1, n−1)
C' = C * r^e mod n
M' = C'^d mod n
M = M' * r^{-1} mod n
This ensures that the attacker cannot correlate the computation with the actual key.
Private keys must be stored securely:
| Application | RSA Usage |
|---|---|
| TLS/SSL | Server authentication, key exchange (RSA), certificate signatures |
| SSH | Host authentication, user authentication (RSA keys) |
| PGP/GPG | Encryption, signing, key verification |
| Digital certificates (X.509) | Certificate signing, key verification |
| Code signing | Authenticating software publishers |
| IPsec | Authentication and key exchange |
In 1998, Daniel Bleichenbacher discovered a padding oracle attack against PKCS#1 v1.5. The attack exploited the fact that many SSL/TLS implementations would reveal whether the padding of a decrypted ciphertext was valid. By repeatedly modifying the ciphertext and observing the response, an attacker could decrypt the message in about 220 queries. This attack demonstrated the importance of using secure padding schemes and robust error handling.
The ROCA vulnerability affected RSA keys generated by certain Infineon hardware RNGs. The vulnerability allowed the factorization of the modulus with a significant speedup (from 21024 to 2512). Millions of devices (including smart cards and government ID documents) were affected. This highlighted the importance of verifying the quality of key generation.
As discussed in Tutorial 2.8, the Debian OpenSSL RNG vulnerability reduced the entropy of generated keys to about 215 possibilities. This affected RSA keys generated on Debian/Ubuntu systems from 2006 to 2008. Thousands of SSH and SSL keys had to be revoked and regenerated.
The RSA Factoring Challenge, run by RSA Security, offered prizes for factoring numbers of increasing sizes. The largest factored number was RSA-768 (232 digits, 768 bits) in 2009. RSA-1024 (309 digits, 1024 bits) remains unfactored, but is considered within reach of government-level actors. RSA-2048 (617 digits) is considered secure against factoring with current technology.
Let p = 13 and q = 19. Compute n, φ(n), choose e = 5 (verify it's valid), and compute d. Show all steps.
p = 13, q = 19
n = 13·19 = 247
φ(n) = 12·18 = 216
e = 5, gcd(5,216) = 1 (valid)
Find d: 5·d ≡ 1 (mod 216). Extended Euclidean: 216 = 43·5 + 1, so 1 = 216 − 43·5. Thus 5·(−43) ≡ 1 (mod 216), so d = 216 − 43 = 173.
Public key: (247, 5). Private key: (247, 173).
Using the key pair from Exercise 1 (n=247, e=5, d=173), encrypt the message M = 100 and decrypt the resulting ciphertext.
Encrypt: C = 1005 mod 247
1002 = 10000 mod 247 = 10000 − 247·40 = 10000 − 9880 = 120
1004 = 1202 = 14400 mod 247 = 14400 − 247·58 = 14400 − 14326 = 74
1005 = 1004 · 100 = 74·100 = 7400 mod 247 = 7400 − 247·29 = 7400 − 7163 = 237
C = 237
Decrypt: M = 237173 mod 247 = 100 (by correctness of RSA)
Using the private key from Exercise 1 (n=247, d=173), sign the message hash H = 55 (a hash value). Verify the signature using the public key.
Sign: σ = 55173 mod 247
Since decryption and signing use the same exponent d, this is similar to decryption. The result is some value σ.
Verify: H = σ5 mod 247. By RSA correctness, σ5 = 55 (mod 247).
Note: In practice, a hash function is used, and the hash value should be computed using a secure hash algorithm (e.g., SHA-256).
Explain why textbook RSA (without padding) is insecure. Give an example of an attack that can be performed against it.
Textbook RSA is insecure because:
Example: If M is small (e.g., "YES" as an integer), and e is small (e.g., 3), then M3 < n, so an attacker can take the cube root of C to recover M.
A system uses 1024-bit RSA keys. Explain why this is considered insecure today. What is the estimated factoring time for a 1024-bit RSA modulus with current technology?
1024-bit RSA keys are considered insecure because:
Estimated factoring time for 1024-bit RSA with current technology is on the order of millions of dollars of computing power and months to years of time. The recommendation is to use at least 2048-bit RSA keys.
Research the RSA Factoring Challenge. Write a 500-word report that covers:
Complete answer would cover the RSA Factoring Challenge sponsored by RSA Security, the factoring of RSA-768 (2009), the General Number Field Sieve as the primary method, the current status (RSA-1024 and above remain unfactored), and the conclusion that 2048-bit RSA is secure against current factoring capabilities but larger keys are recommended for long-term security.
Write a 500-word report comparing RSA and ECC (Elliptic Curve Cryptography). Address:
Complete answer would show that ECC provides equivalent security to RSA with much smaller keys (e.g., 256-bit ECC ≈ 3072-bit RSA), making ECC more efficient for constrained devices. ECC is faster for key generation and signature generation, but RSA is often faster for signature verification. Both are widely adopted, with ECC increasingly favored in TLS 1.3 and other protocols. Both are vulnerable to quantum attacks, requiring post-quantum solutions.
Research a real-world RSA implementation (e.g., OpenSSL, a hardware security module, or a smart card implementation). Write a report that addresses:
Complete answer would discuss OpenSSL's implementation of RSA, including its use of CRT, blinding (for side-channel resistance), and the availability of constant-time operations. It would also mention the use of PKCS#1 padding and the importance of secure random number generation.
Design a secure communication protocol that uses RSA for key exchange and AES for bulk encryption. Specify:
Complete answer would describe a hybrid cryptosystem: Alice generates a random AES key, encrypts it with Bob's RSA public key (using OAEP), sends the encrypted key and the AES-encrypted message. Bob decrypts the key with his private key, then decrypts the message. Authentication is provided by using digital signatures (Bob signs his public key, or a certificate is used). The protocol is secure against eavesdropping and man-in-the-middle attacks if the public keys are authentic.
Implement RSA key generation, encryption, and decryption with CRT optimization in your preferred language. Test with small primes (e.g., 64-bit) and then with larger primes (e.g., 512-bit). Report on:
Complete answer would include source code, performance measurements showing CRT's speedup (about 4× faster for decryption), test results verifying correctness, and a discussion of implementation challenges (modular exponentiation algorithms, prime generation, and handling of large integers).
This tutorial has provided a comprehensive examination of the RSA cryptosystem. We began with the historical context of its invention and the mathematical foundations—Euler's theorem, modular arithmetic, and the totient function—that make RSA possible. We walked through the key generation process, encryption, and decryption with detailed worked examples.
We proved the correctness of RSA using Euler's theorem and analyzed its security, which is based on the difficulty of factoring large composite numbers. We discussed the importance of padding schemes, emphasizing that textbook RSA is insecure and that OAEP and PSS (as specified in PKCS#1 v2.x) must be used for encryption and signatures, respectively.
We explored the use of RSA for digital signatures, which provide authentication and non-repudiation, and we distinguished between encryption and signing. We surveyed attacks on RSA, including factoring attacks, small exponent attacks, padding oracle attacks (Bleichenbacher), side-channel attacks, and the quantum threat from Shor's algorithm.
We considered practical implementation considerations: prime generation, modular exponentiation, CRT optimization, blinding, and secure key storage. We reviewed the relevant standards (PKCS#1, FIPS 186-4) and real-world applications (TLS, SSH, PGP, digital certificates). The case studies highlighted the importance of secure implementation and the consequences of vulnerabilities.
With this knowledge, you are now prepared to understand the design, security, and implementation of RSA in real-world systems.
In Tutorial 2.13: Diffie-Hellman Key Exchange, we will explore another fundamental public-key primitive. While RSA provides encryption and signatures, Diffie-Hellman enables two parties to establish a shared secret over an insecure channel. Understanding both RSA and Diffie-Hellman is essential for understanding modern secure protocols like TLS.