RSA & Ed25519

This page answers one question: how can two parties that never met trust each other over a public network? The answer is public-key cryptography, and you use it every time a service in this course talks to another one: HTTPS at the gateway (TLS²⁴), the JWT that the auth service signs and every other service checks²³, the SSH key that opens a server or a Git repository²⁵, the certificates a Kubernetes cluster uses inside. We build RSA from small numbers, see why its textbook form is unsafe, and then meet Ed25519, the modern alternative.

Why public-key cryptography

With symmetric encryption (AES, ChaCha20), the same key encrypts and decrypts. It is fast, but both sides must already share the key, and sending it over the network is exactly what an eavesdropper hopes for. It also does not scale: with one key per pair, N parties need N(N − 1)/2 keys, so 100 microservices would need 4,950 shared secrets.

In 1976 Diffie and Hellman proposed a way out⁹: give each party two keys, one public and one private, so that what the public key does only the private key can undo. In 1978 Rivest, Shamir and Adleman published the first practical scheme, RSA¹⁸. Each party now publishes one key and keeps one secret: N parties need N key pairs, and nothing secret ever travels.

The key pair

The two keys are used in two directions, for two different jobs:

flowchart LR
    subgraph enc ["Encryption: anyone → owner"]
        a([sender]) -->|"encrypt with the<br/>owner's PUBLIC key"| c[ciphertext]:::comp
        c -->|"decrypt with the<br/>owner's PRIVATE key"| o([owner])
    end
    subgraph sig ["Signature: owner → anyone"]
        o2([owner]) -->|"sign with the<br/>owner's PRIVATE key"| s[message + signature]:::comp
        s -->|"verify with the<br/>owner's PUBLIC key"| v([anyone])
    end

Encryption gives confidentiality (only the owner reads it). A signature gives authenticity and integrity (only the owner could have produced it, and the message was not changed); it does not hide the message.

The maths, with small numbers

RSA rests on modular arithmetic and on one asymmetry: multiplying two large primes is fast, but factoring the product back into those primes is infeasible at real key sizes⁷. Key generation takes five steps; the column on the right follows them with toy numbers.

Step 5 is the extended Euclidean algorithm: divide φ(n) by e, then the divisor by the remainder, and so on, writing each remainder as a multiple of e modulo φ(n). When the remainder reaches 1, its coefficient is d. The same divisions check step 4: the last nonzero remainder is gcd(e, φ(n)). The simulator shows each division.

A few facts the toy example hides:

• Real sizes. p and q are random primes of about 1024 bits each (a 2048-bit n) or more, and e is almost always 65537 (2¹⁶ + 1, a prime with only two 1 bits, so encryption is fast).
• λ instead of φ. The standard (RFC 8017¹⁸) computes d modulo λ(n) = lcm(p − 1, q − 1), which gives a smaller d that works the same: here λ(n) = 780 and d = 413.
• The primes are kept, secretly. The private key file also stores p, q and a few values derived from them, so that decryption can use the Chinese remainder theorem and run several times faster. Anyone who learns p or q can recompute d, so they are as secret as d itself.
• Why it works. (mᵉ)ᵈ = m^(ed) = m^(1 + k·φ(n)) ≡ m (mod n), by Euler's theorem² when m shares no factor with n (and by the Chinese remainder theorem for every other m < n).

Encrypt and decrypt

A message is first turned into an integer m with 0 ≤ m < n. Then:

• Encrypt with the public key: c = mᵉ mod n
• Decrypt with the private key: m = cᵈ mod n

With the key above, 65¹⁷ mod 3233 = 2790 and 2790²⁷⁵³ mod 3233 = 65.

Nobody computes 2790²⁷⁵³ by multiplying 2,752 times. Square-and-multiply reads the exponent in binary: one squaring per bit, plus one multiplication per 1 bit. 17 = 10001₂ takes 4 squarings and 1 multiplication; a 2048-bit d takes about 2,048 squarings, not 2²⁰⁴⁸ multiplications. Reducing mod n after each step keeps every number below n².

Applying the formula directly, as above, is called textbook RSA, and it is unsafe:

• Deterministic. The same m always gives the same c. An attacker who can guess the possible messages ("yes" or "no", a grade from A to F) encrypts each guess with the public key and compares: a dictionary attack. Letter by letter, it is a plain substitution cipher.
• Malleable. Multiplying a ciphertext by 2ᵉ mod n doubles the hidden plaintext: in the example, 2790 × 2¹⁷ mod 3233 decrypts to 130 = 2 × 65. An attacker can change a message they cannot read.
• Small messages leak. With e = 3 and a short message, m³ can be smaller than n: then no reduction happens, and an ordinary cube root recovers m.

The fix is padding with randomness before the exponentiation, covered below.

Digital signatures

The same maths with the keys swapped gives signatures. In practice what is signed is a hash of the message, h = H(m): a hash fits below n, and signing it is as good as signing the whole message.

• Sign with the private key: s = hᵈ mod n
• Verify with the public key: check that sᵉ mod n = h

With the key above, h = 123 gives s = 123²⁷⁵³ mod 3233 = 2746, and 2746¹⁷ mod 3233 = 123. Change one bit of the message or of s and the check fails; producing a valid s for another message requires d.

This is how a JWT signed with RS256 or PS256 works²³: the auth service signs header.payload with its private key, and any service holding the public key verifies the token without being able to issue new ones. The public keys are usually published as a JWK Set (RFC 7517²²) at the URL the identity provider announces as jwks_uri.

sequenceDiagram
    participant U as Client
    participant A as auth service
    participant G as API gateway
    U->>A: POST /login (credentials)
    A->>A: sign header.payload with the PRIVATE key (RS256 / PS256)
    A-->>U: JWT = header.payload.signature
    U->>G: GET /orders, Authorization: Bearer JWT
    G->>A: fetch the public keys (jwks_uri), then cache them
    G->>G: verify the signature with the PUBLIC key
    G-->>U: 200 OK, or 401 if the signature does not match

Hybrid encryption

RSA is not used to encrypt bulk data. Each operation is a full modular exponentiation on 2048-bit numbers, orders of magnitude slower than AES, which modern CPUs run in hardware. And one operation carries very little: with OAEP and SHA-256, a 2048-bit key encrypts at most 256 − 2 × 32 − 2 = 190 bytes (RFC 8017, §7.1.1¹⁸).

So systems combine both kinds of cryptography, a pattern called hybrid encryption: a fresh random symmetric key encrypts the data, and the public-key algorithm protects only that small key.

flowchart LR
    doc([document]) --> aes["AES-256-GCM<br/>with key K"]:::comp
    k([random key K]) --> aes
    k --> oaep["RSA-OAEP with the<br/>recipient's public key"]:::comp
    aes --> ct([encrypted document])
    oaep --> wk([K, wrapped])
    ct --> msg["message = wrapped K + encrypted document"]
    wk --> msg

The recipient unwraps K with the private key and decrypts the document with K. JWE (alg: RSA-OAEP-256, enc: A256GCM)²³, OpenPGP²⁷ and the "envelope encryption" of cloud key-management services all work this way.

How TLS 1.3 uses it

TLS 1.2 could do exactly the above: the client encrypted a random secret with the server's RSA key. That mode has a flaw: whoever records the traffic today and steals the server's private key later decrypts every recorded session, because one key protected them all (no forward secrecy). TLS 1.3 removed it²⁴. The handshake still uses both kinds of cryptography, but each for a different job:

• an ephemeral Diffie–Hellman exchange (usually X25519) agrees on a fresh secret per connection, never sent over the wire;
• the server's certificate key (RSA-PSS, ECDSA or Ed25519) only signs the handshake, proving who is on the other side;
• symmetric AEAD ciphers (AES-GCM or ChaCha20-Poly1305) encrypt the data.

sequenceDiagram
    participant C as Client
    participant S as Server
    C->>S: ClientHello + key_share (client's ephemeral X25519 public value)
    S->>C: ServerHello + key_share (server's ephemeral X25519 public value)
    Note over C,S: both derive the same secret (ECDHE), then the handshake keys (HKDF)
    S->>C: Certificate (server's public key, signed by a CA)
    S->>C: CertificateVerify: signature over the handshake with the PRIVATE key
    S->>C: Finished (MAC over the handshake)
    C->>S: Finished
    C->>S: HTTP request, encrypted with AES-GCM
    S-->>C: HTTP response, encrypted with AES-GCM

Padding: OAEP and PSS

Padding fixes textbook RSA by mixing randomness and structure into the number before the exponentiation. There are two standard schemes, both in PKCS #1 v2.2 / RFC 8017¹⁸, one for each use.

OAEP — for encryption

OAEP (Optimal Asymmetric Encryption Padding), proposed by Bellare and Rogaway¹⁰, combines the message with a random seed through two masks made by MGF1, a mask generation function built on a hash such as SHA-256 (RFC 8017, §7.1.1):

flowchart TD
    L([label, usually empty]) --> LH["lHash = SHA-256(label)"]
    M([message]) --> DB["DB = lHash ‖ zero bytes ‖ 0x01 ‖ message"]
    LH --> DB
    S([random seed]) --> G1["MGF1(seed)"]
    G1 --> X1["maskedDB = DB ⊕ MGF1(seed)"]
    DB --> X1
    X1 --> G2["MGF1(maskedDB)"]
    G2 --> X2["maskedSeed = seed ⊕ MGF1(maskedDB)"]
    S --> X2
    X1 --> EM["EM = 0x00 ‖ maskedSeed ‖ maskedDB"]
    X2 --> EM
    EM --> E["RSA: c = EMᵉ mod n"]:::comp
    E --> C([ciphertext])

• Randomised: encrypting the same message twice gives different ciphertexts, so the dictionary attack fails. The seed is as long as the hash (32 bytes with SHA-256), far too many values to try.
• All-or-nothing: changing any bit of the ciphertext scrambles the whole padded block, and the decryption check rejects it, so malleability is gone.
• Proven: RSA-OAEP is secure against chosen-ciphertext attacks (IND-CCA2) in the random-oracle model.

PSS — for signatures

PSS (Probabilistic Signature Scheme), also by Bellare and Rogaway¹¹, adds a random salt to the message's hash before the private-key operation (RFC 8017, §9.1.1):

flowchart TD
    M([message]) --> MH["mHash = SHA-256(message)"]
    SA([random salt]) --> MP["M' = 8 zero bytes ‖ mHash ‖ salt"]
    MH --> MP
    MP --> H["H = SHA-256(M')"]
    SA --> DB["DB = zero bytes ‖ 0x01 ‖ salt"]
    H --> G["MGF1(H)"]
    G --> X["maskedDB = DB ⊕ MGF1(H)"]
    DB --> X
    X --> EM["EM = maskedDB ‖ H ‖ 0xbc"]
    H --> EM
    EM --> RS["RSA: s = EMᵈ mod n"]:::comp
    RS --> SIG([signature])

• Randomised: with the salt, signing the same message twice gives different signatures, unlike the deterministic PKCS#1 v1.5 signatures.
• Proven: PSS was designed with a tight security proof that reduces forging a signature to breaking RSA itself.
• In the protocols: TLS 1.3 accepts RSA handshake signatures only with PSS (v1.5 survives only inside certificates)²⁴; in JWT, PS256 is PSS and RS256 is v1.5. RS256 has no known practical attack and is the most widely supported, but prefer PS256 (or Ed25519) for new systems.

Ed25519

Ed25519⁵¹⁵ is an elliptic-curve signature algorithm, standardised in RFC 8032¹⁹. It is not RSA and it does not encrypt, but for signatures it does the same job with much smaller keys, and it is now the preferred choice in many protocols.

Why elliptic curves

RSA's security comes from the difficulty of factoring. Elliptic-curve cryptography (ECC)⁶ uses another hard problem, the elliptic-curve discrete logarithm: given the points B and A = a · B on a curve, find a³⁵. The best known attacks on it are much slower than those on factoring, so a far smaller key gives the same security. ECDSA³³, used by Bitcoin and by many TLS certificates, is the older elliptic-curve signature; Ed25519 is its modern successor.

The RSA and P-256 rows follow NIST SP 800-57²⁹; the Ed25519 and Ed448 levels are those stated in RFC 8032¹⁹. A 256-bit Ed25519 key matches a 3072-bit RSA key.

How Ed25519 works

Ed25519 works on the twisted Edwards curve edwards25519, birationally equivalent to Bernstein's Montgomery curve Curve25519⁴¹⁴ (the same curve in other coordinates):

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

Key generation (RFC 8032, §5.1.5):

1. The private key k is 32 random bytes.
2. Hash it: SHA-512(k) gives 64 bytes. The first 32 are "clamped" (a few bits fixed) and read as the secret scalar a; the last 32 are a prefix kept for signing.
3. The public key is the curve point A = a · B, where B is the curve's fixed base point, encoded in 32 bytes.

Signing a message m (§5.1.6):

1. Derive a deterministic nonce r = SHA-512(prefix ‖ m).
2. Compute R = r · B.
3. Compute S = (r + SHA-512(R ‖ A ‖ m) · a) mod ℓ, where ℓ is the order of the base point.
4. The signature is (R, S): 64 bytes.

Verification checks that S · B = R + SHA-512(R ‖ A ‖ m) · A. For a deeper treatment, see the IEEE S&P talk on Ed25519 in theory and practice³⁴.

Ed25519 compared with RSA

Determinism, a trade-off

Ed25519 derives its nonce from the private key and the message instead of asking a random-number generator. That removes a whole class of catastrophic bugs: in 2010, Sony's PlayStation 3 signed its firmware with ECDSA using the same nonce every time, and two signatures were enough to compute the private key¹⁶. The price is that a device whose computation can be physically disturbed (a fault injected while it signs the same message twice) can leak its key¹⁷; that matters for smart cards and embedded hardware, not for servers.

Where Ed25519 is used

• SSH: ssh-ed25519 keys (RFC 8709²⁶); since OpenSSH 9.5 (2023), ssh-keygen generates Ed25519 keys by default²⁸.
• TLS 1.3: ed25519 is one of the handshake signature schemes²⁴, although most public certificates still use RSA or ECDSA.
• JWT: alg: "EdDSA" with an OKP key and crv: "Ed25519" (RFC 8037²⁰); RFC 9864 deprecates the generic EdDSA in favour of the explicit alg: "Ed25519"²¹.
• Git: commits and tags can be signed with an Ed25519 SSH key (git config gpg.format ssh) or an OpenPGP Ed25519 key.
• X25519, Ed25519's sibling on the same curve, does key agreement: the TLS 1.3 handshake above, WireGuard, Signal and age.

Which to use

Generating keys:

ssh-keygen -t ed25519 -C "you@example.com"                                 # SSH key pair
openssl genpkey -algorithm ED25519 -out ed25519.pem                        # Ed25519 private key
openssl genpkey -algorithm RSA -pkeyopt rsa_keygen_bits:3072 -out rsa.pem  # RSA private key
openssl pkey -in rsa.pem -pubout -out rsa.pub.pem                          # its public key

Videos

Eddie Woo works through RSA by hand, the same way as the simulator above:

Key takeaways