RSA (Rivest-Shamir-Adleman)

Overview

RSA is an asymmetric cryptographic algorithm named after its inventors: Ron Rivest, Adi Shamir, and Leonard Adleman. It's one of the first public-key cryptosystems and is widely used for secure data transmission, digital signatures, and key exchange.

RSA's security is based on the mathematical difficulty of factoring large composite numbers into their prime factors. The algorithm uses a public key for encryption and a private key for decryption, enabling secure communication without sharing secret keys.

How It Works

  1. Key Generation:
    • Choose two large prime numbers p and q
    • Calculate n = p × q
    • Calculate φ(n) = (p-1) × (q-1)
    • Choose e such that 1 < e < φ(n) and gcd(e, φ(n)) = 1
    • Calculate d such that (d × e) mod φ(n) = 1
    • Public key: (n, e), Private key: (n, d)
  2. Encryption: c = m^e mod n
  3. Decryption: m = c^d mod n

Important: what is written above is textbook RSA, and textbook RSA is insecure. It is deterministic, so identical messages produce identical ciphertexts and an attacker can simply encrypt guesses and compare. It is also malleable: multiplying a ciphertext by se multiplies the plaintext by s, without the key. Real RSA encryption always applies a randomized padding scheme — OAEP — and real RSA signatures use PSS. Never implement the bare modular exponentiation above and ship it.

One further note on the maths: modern standards (FIPS 186-5, PKCS#1 v2.2) compute d using the Carmichael function λ(n) = lcm(p−1, q−1) rather than Euler's φ(n). Both yield a working key; λ(n) gives the smallest valid d.

RSA Algorithm


RSA_KeyGeneration():
    p, q = generate_large_primes()
    n = p * q
    φ(n) = (p - 1) * (q - 1)
    e = choose_public_exponent(φ(n))
    d = modular_inverse(e, φ(n))
    return (n, e), (n, d)

RSA_Encrypt(message, public_key):
    (n, e) = public_key
    return message^e mod n

RSA_Decrypt(ciphertext, private_key):
    (n, d) = private_key
    return ciphertext^d mod n

Implementation


from cryptography.hazmat.primitives.asymmetric import rsa, padding
from cryptography.hazmat.primitives import hashes

def generate_rsa_keys(key_size=2048):
    """Generate RSA key pair"""
    private_key = rsa.generate_private_key(
        public_exponent=65537,
        key_size=key_size,
    )
    public_key = private_key.public_key()
    return private_key, public_key

def rsa_encrypt(message, public_key):
    """Encrypt message using RSA public key"""
    ciphertext = public_key.encrypt(
        message,
        padding.OAEP(
            mgf=padding.MGF1(algorithm=hashes.SHA256()),
            algorithm=hashes.SHA256(),
            label=None
        )
    )
    return ciphertext

def rsa_decrypt(ciphertext, private_key):
    """Decrypt message using RSA private key"""
    plaintext = private_key.decrypt(
        ciphertext,
        padding.OAEP(
            mgf=padding.MGF1(algorithm=hashes.SHA256()),
            algorithm=hashes.SHA256(),
            label=None
        )
    )
    return plaintext

# Example usage
private_key, public_key = generate_rsa_keys()
message = b"Hello, RSA Encryption!"
ciphertext = rsa_encrypt(message, public_key)
decrypted = rsa_decrypt(ciphertext, private_key)

Security

RSA security depends on:

  • Key Size: Larger keys provide more security but slower operations
  • Prime Generation: Primes must be truly random and large
  • Implementation: Proper padding (OAEP) is essential

Recommended key sizes:

  • 1024 bits: disallowed. Not a "minimum" — NIST SP 800-131A Rev. 2 withdrew it for signature generation after 2013, and SP 800-57 Part 1 Rev. 5 sets 2048 as the floor. Treat a 1024-bit key as broken.
  • 2048 bits: today's minimum, roughly 112 bits of security. NIST IR 8547 (draft) proposes deprecating RSA-2048 after 2030 and disallowing it after 2035.
  • 3072 bits: ~128 bits of security. The right choice for anything that must stay secure past 2030.
  • 4096 bits: higher classical margin, but note that RSA operations scale badly — doubling the modulus roughly eight-folds the private-key cost.

No RSA key size is quantum-resistant. Shor's algorithm factors integers in polynomial time, so a sufficiently large quantum computer breaks RSA-4096 as readily as RSA-2048. Calling large keys "future-proof" is misleading. The migration path is post-quantum cryptography — see the post-quantum section in the encryption overview.

Applications

  • Digital signatures: the main modern use. Certificate signing, code signing, document authentication — use RSA-PSS for new designs.
  • TLS certificates: RSA still signs a large share of the web's certificates.
  • Email encryption: PGP, S/MIME.
  • Legacy key transport: older protocols encrypt a symmetric key under an RSA public key.

RSA is no longer used for key exchange in modern TLS. TLS 1.3 (RFC 8446, 2018) removed RSA key transport entirely, because it provides no forward secrecy: anyone who later obtains the server's private key can decrypt every past session they recorded. TLS 1.3 key agreement is ephemeral Diffie-Hellman — ECDHE, in practice X25519 — and browsers now default to the hybrid post-quantum group X25519MLKEM768. RSA's role in a modern handshake is to sign, not to transport keys.

RSA also cannot encrypt bulk data. A 2048-bit key with OAEP-SHA256 can encrypt at most 190 bytes. Real systems use hybrid encryption: generate a random AES key, encrypt the data with AES-GCM, and encrypt only that key with RSA.

Related Algorithms

Explore other encryption algorithms: