RSA Encryption & Decryption Tool

Understanding RSA Cryptography: A Comprehensive Guide

RSA (Rivest–Shamir–Adleman) is one of the first public-key cryptosystems and is widely used for secure data transmission. Its security relies on the practical difficulty of factoring the product of two large prime numbers. This guide dives deep into the mathematics, security considerations, and real-world applications of RSA.

1. Historical Background

In 1977, Ron Rivest, Adi Shamir, and Leonard Adleman at MIT developed the RSA algorithm, which became the first practical implementation of public-key cryptography as proposed by Diffie and Hellman in 1976. The trio's work earned them the Turing Award in 2002. RSA was patented in 1983, and the patent expired in 2000, allowing widespread adoption.

2. Number Theory Foundations

RSA relies on several key concepts from number theory:

• Modular arithmetic: Operations are performed modulo n, where numbers wrap around after reaching n.
• Prime numbers: Integers greater than 1 that have no positive divisors other than 1 and themselves.
• Euler's totient function φ(n): For n = p × q (with p and q prime), φ(n) = (p-1)(q-1).
• Euler's theorem: a^φ(n) ≡ 1 (mod n) if a and n are coprime.
• Modular inverse: For given e and φ(n), there exists d such that e·d ≡ 1 (mod φ(n)).

3. Key Generation in Detail

1. Choose two distinct primes p and q. They should be roughly the same size and randomly chosen. For security, they must be kept secret. The product n = p × q becomes the modulus for both public and private keys.
2. Compute φ(n) = (p-1)(q-1). This value is used to derive the private exponent.
3. Select public exponent e. Typically 65537 (2¹⁶+1) because it has a good balance of security and performance. It must satisfy 1 < e < φ(n) and gcd(e, φ(n)) = 1.
4. Compute private exponent d. d is the modular multiplicative inverse of e modulo φ(n): d ≡ e⁻¹ (mod φ(n)). This means e·d = 1 + k·φ(n) for some integer k.
5. The public key is (n, e). The private key is (n, d). In practice, private keys also include p, q, and other values to speed up decryption using the Chinese Remainder Theorem.

4. Encryption and Decryption

To encrypt a message m, it must be represented as an integer in the range [0, n-1]. Long messages are split and often combined with symmetric encryption (hybrid cryptosystem).

• Encryption: ciphertext c = m^e mod n.
• Decryption: message m = c^d mod n.

The correctness follows from Euler's theorem: m^e·d ≡ m^1+kφ(n) ≡ m (mod n) when m is coprime to n; special cases handle multiples of p or q.

5. Why RSA is Secure

Given the public key (n, e), an attacker wanting to recover the private key d would need to compute φ(n) or factor n into p and q. Factoring a 2048-bit integer is currently infeasible with classical computers. The best known factoring algorithm, the General Number Field Sieve (GNFS), has sub-exponential complexity. For 2048-bit RSA, it is estimated to require millions of years with current technology.

However, RSA is vulnerable to:

• Factoring breakthroughs: If a practical quantum computer emerges, Shor's algorithm could factor large integers efficiently, breaking RSA.
• Poor random number generation: If primes are predictable, factoring becomes easy.
• Side-channel attacks: Timing, power, or electromagnetic leaks can reveal private key information.
• Chosen ciphertext attacks: Without proper padding, an attacker might decrypt messages by manipulating ciphertexts.

6. Key Lengths and Security Levels

The table below compares RSA key sizes with equivalent symmetric key security (as estimated by NIST):

RSA key size (bits)	Symmetric equivalent (bits)	Security lifetime
1024	80	Deprecated (broken by academic efforts)
2048	112	Secure until ~2030
3072	128	Recommended for long-term security
4096	152	Overkill for most applications; slower

Larger keys provide more security but require more computational power for encryption/decryption and key generation. For most purposes, 2048 or 3072 bits are recommended.

7. Padding Schemes – Why They Are Essential

RSA without padding is deterministic: the same message always produces the same ciphertext, making it vulnerable to chosen-plaintext attacks. Padding adds randomness and structure.

• PKCS#1 v1.5: An older padding scheme that adds random bytes. It is still widely used but has known weaknesses (Bleichenbacher attack).
• OAEP (Optimal Asymmetric Encryption Padding): Recommended for new applications. It uses a Feistel network with a hash function to provide security against chosen-ciphertext attacks. RSA with OAEP is proven secure in the random oracle model.

JSEncrypt uses PKCS#1 v1.5 padding by default. For production, prefer OAEP.

8. Real-World Applications

• SSL/TLS: RSA is used to negotiate symmetric keys during the handshake (though ephemeral Diffie-Hellman is now preferred for forward secrecy).
• Digital signatures: A message hash is signed with the private key; anyone with the public key can verify authenticity. Used in code signing, email (S/MIME), and certificates.
• SSH: RSA keys are commonly used for user authentication.
• PGP/GPG: RSA is an option for encrypting and signing emails and files.
• Cryptocurrencies: Some early cryptocurrencies used RSA, but most now use ECDSA or Schnorr signatures.

9. Performance Considerations

RSA encryption is relatively fast (exponentiation with a small public exponent e), but decryption is slower because the private exponent d is large. To speed up decryption, the Chinese Remainder Theorem (CRT) is used, leveraging p and q separately. This makes decryption about 4 times faster. Key generation is the slowest operation because it requires finding large primes.

10. Hybrid Encryption

Because RSA can only encrypt messages up to the key size minus padding overhead (e.g., about 190 bytes for 2048-bit RSA with PKCS#1), it is never used to encrypt bulk data. Instead, a hybrid approach is employed: a random symmetric key (e.g., AES-256) is generated, the data is encrypted with that key, and the symmetric key itself is encrypted with RSA. This combines the efficiency of symmetric cryptography with the convenience of public-key distribution.

11. Quantum Threat and Post-Quantum Cryptography

Shor's algorithm, when run on a sufficiently large quantum computer, can factor integers and compute discrete logarithms in polynomial time, rendering RSA and ECC obsolete. The cryptographic community is actively developing post-quantum algorithms (e.g., lattice-based, code-based, multivariate). NIST is in the process of standardizing several candidates. For now, RSA remains safe, but long-term secrets should consider future quantum risks.

12. Summary

RSA is a foundational public-key cryptosystem that enabled the modern secure internet. Understanding its mathematical underpinnings, proper use of padding, and appropriate key sizes is essential for any security practitioner. This tool allows you to experiment with different key lengths and observe the resulting PEM formats, ciphertexts, and the importance of using the correct key for decryption.

Frequently Asked Questions