How does SSH work?

I’ve been using SSH for years and never really stopped to ask what’s happening when I type ssh user@host and get a shell back. The hand-wavy mental model — “I have a private key, the server has my public key, magic” — got me through every day of my career, but it falls apart the moment you push on it. Why does the server also have a keypair? What does “encrypt with the private key” mean for an algorithm that can’t encrypt? This post is me writing down what I worked out.

The Ubuntu wiki page on SSH/OpenSSH/Keys is a good starting reference if you want the operational side.

Who holds which key?

The first thing that surprised me: in SSH, both sides have their own keypair. They’re not playing the same role — they exist for different reasons.

The server’s keypair lives on the server, typically at /etc/ssh/ssh_host_ed25519_key and .pub. The private half stays on the server. The public half is what your client sees the very first time you connect — that The authenticity of host 'X' can't be established prompt — and then caches in ~/.ssh/known_hosts. Its job is to prove to you that the server is the one you think it is. Without it, anything between you and the server could pretend to be the server.

Your keypair lives on your laptop, typically at ~/.ssh/id_ed25519 and .pub. The private half stays with you. The public half gets copied onto the server, into the target account’s ~/.ssh/authorized_keys. Its job is to prove to the server that you are who you claim to be — the alternative to typing a password.

So during a key-based login, two separate authentications happen, in opposite directions:

  1. Server proves itself to client. The server signs a challenge with its private key; the client verifies the signature against the public key cached in known_hosts.
  2. Client proves itself to server. The client signs a challenge with its private key; the server verifies the signature against the public key in authorized_keys.

Same mechanism, mirrored. Once I saw it that way, the rest of SSH stopped feeling mysterious.

What does “signing a challenge” actually mean?

This is where my intuition was wrong for a long time. The folk story goes: “you encrypt with the private key, and anyone with the public key can decrypt it — that proves you have the private key.” It’s a satisfying story. It’s also misleading.

That story only really makes sense for textbook RSA, where the math happens to be symmetric — encrypt and decrypt are the same modular exponentiation with the exponents swapped. Even there, cryptographers don’t call the private-key operation “encryption,” because the goal isn’t confidentiality (anyone with the public key can reverse it). The goal is authenticity.

For other algorithms — ECDSA, Ed25519, DSA — you literally cannot “encrypt with the private key.” These are signature-only schemes. The math doesn’t support encryption at all. So the “encrypt with private, decrypt with public” mental model isn’t just imprecise; for the algorithm SSH actually defaults to in 2026, it’s wrong.

The correct mental model is sign and verify, which are a related-but-distinct pair of operations:

  1. Hash the message with something like SHA-256 to get a fixed-size digest.
  2. Run a signing algorithm: (digest, private_key) → signature.
  3. Send (message, signature) to the verifier.
  4. The verifier runs a separate verification algorithm: (message, signature, public_key) → true | false.

Verification is not “decryption that recovers the original message.” It’s a different algorithm whose only output is a boolean. The reason cryptographers insist on the sign/verify vocabulary is that it’s the one framing that survives across all algorithms.

Why a “challenge” and not just any message?

If the server let the client sign anything the client liked, two things go wrong. First, an attacker could trick the client into signing arbitrary attacker-chosen data — useful for replay or impersonation in some other protocol. Second, a captured signature could be replayed later to log in again.

So the server doesn’t let the client pick. The client signs a value derived from the live handshake — the session ID plus fresh random nonces from both sides. Any signature produced is bound to this session, and a captured one is useless for any future login.

A toy RSA example, end to end

I find signing easier to believe in once I’ve done the arithmetic, so here’s a tiny RSA worked example. Real keys are ~2048 bits; we’ll use primes you can compute in your head.

Pick p = 5, q = 11. Then:

  • n = p × q = 55
  • φ(n) = (p−1)(q−1) = 40
  • Pick a public exponent e = 3 (coprime to 40)
  • Find the private exponent d such that e × d ≡ 1 (mod 40) → d = 27 (since 3 × 27 = 81 = 2×40 + 1)

So public key (n = 55, e = 3) and private key (n = 55, d = 27).

Signing

Suppose the server’s challenge is 17. The client computes:

s = 17^27 mod 55

By repeated squaring, mod 55:

  • 17² = 289 ≡ 14
  • 17⁴ = 14² ≡ 31
  • 17⁸ = 31² ≡ 26
  • 17¹⁶ = 26² ≡ 16
  • 17²⁷ = 17¹⁶ × 17⁸ × 17² × 17¹ = 16 × 26 × 14 × 17 ≡ 8

The signature is s = 8.

Verifying

The server computes s^e mod n = 8³ mod 55 = 512 mod 55 = 17. That matches the original challenge, so the signature is valid — only someone holding d could have produced it.

Why this proves anything

Two things make the round-trip work. First, Euler’s theorem guarantees (s^d)^e ≡ s (mod n) because d and e are inverses mod φ(n) — so signing and verifying compose to the identity. Second, going the other direction — finding s from the challenge and the public key alone — is the RSA problem, which is infeasible for real-world key sizes.

That asymmetry between “trivial if you have d” and “hopeless if you don’t” is the whole game.

The takeaway

For RSA specifically, the folk story “sign = encrypt with the private key” is roughly accurate mechanically, even if cryptographers wince at the framing.

For Ed25519 — what most modern SSH installations actually use — signing is an entirely different operation involving hashing and elliptic-curve math. The private key can only sign; it can’t encrypt anything. But from the outside, the protocol role is identical: produce a signature only the private-key holder could have made, and let anyone with the public key verify it.

That’s why the right mental model for SSH isn’t “two sides encrypting things to each other.” It’s two sides, each with their own keypair, each signing a fresh challenge, each verifying the other’s signature. Once you have that, every weird detail — known_hosts, authorized_keys, the first-connection prompt — slots into place.