RSA Algorithm

RSA Algorithm

RSA (Rivest–Shamir–Adleman)¹⁸ is one of the oldest and most widely used asymmetric cryptographic algorithms. Unlike symmetric algorithms, which use the same key for both encryption and decryption, RSA uses a key pair: a public key that anyone can know, and a private key that must remain secret. The idea of public-key cryptography itself was introduced by Diffie and Hellman in 1976⁹.

Its security rests on a simple mathematical asymmetry: multiplying two large prime numbers together is fast, but factoring the result back into those primes is computationally infeasible at sufficient key sizes (2048-bit or larger).

RSA is foundational to many protocols you already use, including TLS/HTTPS²⁰, SSH²¹, PGP²², and JWT signing with RS256¹⁹.

Core Concepts

Key Pair

The two keys are mathematically linked: a message encrypted with the public key can only be decrypted with the corresponding private key, and vice versa.

Mathematical Foundation

RSA is built on modular arithmetic and Euler's theorem². The key steps are:

1. Choose two large prime numbers p and q.
2. Compute n = p × q (the modulus, public).
3. Compute Euler's totient: φ(n) = (p − 1)(q − 1).
4. Choose e such that 1 < e < φ(n) and gcd(e, φ(n)) = 1 (commonly e = 65537).
5. Compute d as the modular inverse of e modulo φ(n), i.e. d × e ≡ 1 (mod φ(n)).

The public key is (e, n). The private key is (d, n). The primes p and q are discarded after key generation.

Encryption & Decryption

Given a message m (as an integer, where m < n):

• Encrypt: c = m^e mod n
• Decrypt: m = c^d mod n

The correctness follows from Euler's theorem: (m^e)^d ≡ m (mod n).

Digital Signatures

RSA can also be used to sign data, reversing the role of the keys:

• Sign (with private key): s = m^d mod n
• Verify (with public key): check that s^e mod n = m

This is how JWT tokens signed with RS256 work: the server signs the token with its private key; any client holding the public key can verify it without being able to forge a new one.

Why Not Use RSA for Everything?

RSA is slow compared to symmetric algorithms like AES. In practice, RSA is used only to exchange or protect a symmetric key (a pattern called hybrid encryption). The symmetric key then handles the bulk of the data encryption. TLS does exactly this.

Additionally, raw RSA without padding is insecure. Modern usage requires padding schemes such as OAEP (for encryption) or PSS (for signatures).

Padding Schemes

Raw RSA — applying the mathematical formula directly to a message — is textbook RSA and is broken in practice. Without padding, it leaks structure: encrypting the same message always produces the same ciphertext, and an attacker can manipulate ciphertexts algebraically. Two standardised padding schemes fix this, one for each use case.

OAEP — Optimal Asymmetric Encryption Padding

OAEP (defined in PKCS#1 v2 / RFC 8017¹⁶, originally proposed by Bellare and Rogaway¹⁰) is the correct padding to use when encrypting data with RSA. Before the modular exponentiation, the plaintext is combined with a random seed through a pair of mask generation functions (MGF1, typically built on SHA-256):

flowchart TD
    M([message])
    L([label])
    S([random seed])
    H1["hash(label)"]
    MGF["MGF1 masks"]
    P["padded block"]
    E["RSA encrypt\nc = m^e mod n"]
    C([ciphertext])

    M --> P
    L --> H1 --> P
    S --> MGF --> P
    P --> E --> C

    style M fill:#ddf,stroke:#99b
    style C fill:#dfd,stroke:#9b9
    style S fill:#ffd,stroke:#bb9

Key properties:

• Randomised — encrypting the same plaintext twice produces different ciphertexts, preventing pattern analysis.
• All-or-nothing — a single flipped bit in the ciphertext causes decryption to fail completely rather than silently producing garbled output.
• IND-CCA2 secure — resistant to chosen-ciphertext attacks in the random-oracle model.

PSS — Probabilistic Signature Scheme

PSS (also defined in PKCS#1 v2 / RFC 8017¹⁶, introduced by Bellare and Rogaway¹¹) is the correct padding to use when signing data with RSA. It works similarly — a random salt is hashed together with the message digest before the private-key operation — making each signature unique even for the same message.

flowchart TD
    M([message])
    SH["SHA-256\ndigest"]
    SA([random salt])
    MGF["MGF1 masks\n+ hash output"]
    EM["encoded message"]
    RS["RSA sign\ns = m^d mod n"]
    SIG([signature])

    M --> SH
    SH --> MGF
    SA --> MGF
    MGF --> EM --> RS --> SIG

    style M fill:#ddf,stroke:#99b
    style SIG fill:#dfd,stroke:#9b9
    style SA fill:#ffd,stroke:#bb9

Key properties:

• Randomised — the salt means that signing the same message twice gives different signatures, unlike the deterministic PKCS1v15 signature scheme.
• Tight security proof — PSS has a provable reduction to the hardness of RSA, whereas PKCS#1 v1.5 signatures do not.
• Standard identifiers — RS256 (PKCS#1 v1.5) vs. PS256 (PSS with SHA-256) in JWT; prefer PS256 for new systems.

Ed25519 — A Modern Alternative

Ed25519⁵¹⁴ is an elliptic-curve signature algorithm based on the Edwards curve Curve25519⁴¹³, standardised in RFC 8032¹⁷. It is not RSA, but it serves the same purpose — asymmetric digital signatures — and is increasingly the preferred choice in modern protocols.

Why Elliptic Curves?

RSA's security comes from the difficulty of integer factorisation⁷. Elliptic-curve cryptography (ECC)⁶ uses a different hard problem: the elliptic-curve discrete logarithm problem (ECDLP). ECDLP is harder per bit, which means much smaller keys can achieve the same security level:

A 256-bit Ed25519 key is roughly equivalent in security to a 3072-bit RSA key, while being far smaller and faster.

How Ed25519 Works

Ed25519 is defined over the twisted Edwards curve:

-x² + y² = 1 − (121665/121666)·x²·y²  (mod p),   p = 2²⁵⁵ − 19

Key generation:

1. Choose a 32-byte random private key k.
2. Hash k with SHA-512 to produce a 64-byte seed; the lower 32 bytes are clamped and used as the scalar a.
3. The public key is the curve point A = a · B, where B is the curve's base point.

Signing a message m:

1. Derive a deterministic nonce r = hash(second_half_of_seed || m).
2. Compute R = r · B.
3. Compute S = (r + hash(R || A || m) · a) mod ℓ, where ℓ is the curve order.
4. The signature is (R, S) — 64 bytes total.

Verification checks that S · B == R + hash(R || A || m) · A.

Key Advantages over RSA

Determinism — a Double-Edged Sword

Ed25519 signatures are deterministic: the nonce r is derived from the private key and the message, not from an external random source. This eliminates an entire class of catastrophic bugs — notably the Sony PlayStation 3 ECDSA failure¹⁵, where a constant nonce exposed the private key. The downside is that if the hash function is broken, determinism could theoretically help an attacker; in practice this is not a concern for SHA-512.

Where Ed25519 Is Used

• SSH — ssh-keygen -t ed25519 is now the recommended key type²¹.
• TLS 1.3 — supported as a signature algorithm²⁰.
• JWT — EdDSA algorithm identifier (alg: "EdDSA" with crv: "Ed25519")¹⁹¹⁸.
• Git — GPG commit signing via an Ed25519 subkey.
• Signal, WireGuard, age — all use Curve25519-family keys.

Generating the RSA Keys