--- title: 'Key Exchange' source: 'https://academia.sh/en/courses/identity-and-cryptography/key-exchange' course: 'Identity, Access and Cryptography' language: en updated: '2026-09-26T03:02:53+00:00' license: 'CC BY-SA 4.0' objectives: - 'Runs key exchange with small parameters and shows that both sides produce the same shared secret' - "Separates the items in the eavesdropper's hands from the items sufficient for the shared secret and counts their intersection" - "Determines ephemeral exchange's effect on the retroactive-opening count and the unverified item" --- # Key Exchange Running shared-secret generation over an insecure channel with small parameters: both sides reaching the same shared secret without ever sending their secret exponent, the intersection of the 4 items crossing the channel and the 3 items sufficient for the secret being zero, ephemeral key exchange dropping the number of retroactively opened sessions from 52,560 to 0, and the exchange verifying two of its three items while not verifying the other side's identity. In the previous lesson, the hybrid path transported the key, but the side that sent the transported key chose it. This had two consequences. First, the session key's quality depended entirely on that side's generator. Second, and heavier: recorded encrypted traffic can be stored, and if the private key leaks years later, every session key up to that point is extracted back out of its envelope. This lesson takes up the method that removes both at once. The two sides reach the same shared secret without ever sending their secret values; the shared secret never crosses the channel and neither side determines it on its own. The method will actually be run with small parameters, then the items left in the eavesdropper's hands will be counted one by one. ## The Secret That Does Not Cross the Channel **CF17:** two sides can produce a shared secret without ever sending their secret exponent; there is no direct computational path between the items crossing the channel and the shared secret. **CF18:** the shared secret is formed by both sides' contribution; neither side determines it on its own. The method is this. The sides openly agree on a prime `p` and a generator `g`. Each side picks a secret exponent, computes `g` to that exponent modulo `p`, and sends the **result** to the other side. Both sides, raising the value received from the other side to their own secret exponent, land on the same value, because exponentiation does not depend on order. The parameters below are teaching-sized and are not used in a real deployment. ```js // exchange/dh.mjs — key exchange is actually run with small parameters. p and g are // small fictional values chosen for teaching; they are not used in a real deployment. // The secret exponents are fixed so the output stays the same run to run. No randomness. import { hkdfSync, createCipheriv, createDecipheriv } from "node:crypto"; // CF17: two sides can produce a shared secret without ever sending their secret exponent; // there is no direct computational path from the items crossing the channel to the shared secret. // CF18: the shared secret is formed by both sides' contribution; neither side determines it on its own. const p = 65267n, g = 2n; // fictional, teaching-sized prime and generator const power = (t, u, m) => { let r = 1n; t %= m; while (u > 0n) { if (u & 1n) r = r * t % m; t = t * t % m; u >>= 1n; } return r; }; const a = 6421n, b = 8973n; // fictional secret exponents: branch and center const A = power(g, a, p), B = power(g, b, p); // public values crossing the channel const branchSecret = power(B, a, p), centerSecret = power(A, b, p); console.log(`items crossing the channel : p=${p} g=${g} A=${A} B=${B}`); console.log("item not crossing the channel: a and b (the two secret exponents)"); console.log("branch shared secret :", String(branchSecret)); console.log("center shared secret :", String(centerSecret)); console.log("did both sides produce the same secret:", branchSecret === centerSecret ? "yes" : "no"); console.log("did the shared secret cross the channel:", [p, g, A, B].includes(branchSecret) ? "yes" : "no"); // The shared secret is not used directly as a key; key derivation pulls it to a fixed size. const raw = Buffer.from(branchSecret.toString(16).padStart(4, "0"), "hex"); const key = Buffer.from(hkdfSync("sha256", raw, Buffer.alloc(16, 9), "measurement-net-session", 32)); const nonce = Buffer.alloc(12, 4), READING = "SAY-4417|2026-03-01T06:00Z|41982"; const cipher = createCipheriv("aes-256-gcm", key, nonce); const body = Buffer.concat([cipher.update(READING, "utf8"), cipher.final()]), tag = cipher.getAuthTag(); const decipher = createDecipheriv("aes-256-gcm", Buffer.from(hkdfSync("sha256", Buffer.from(centerSecret.toString(16).padStart(4, "0"), "hex"), Buffer.alloc(16, 9), "measurement-net-session", 32)), nonce); decipher.setAuthTag(tag); console.log("derived key length :", key.length, "bytes"); console.log("center decrypted branch's packet:", Buffer.concat([decipher.update(body), decipher.final()]).toString() === READING ? "yes" : "no"); ``` ``` items crossing the channel : p=65267 g=2 A=10224 B=40077 item not crossing the channel: a and b (the two secret exponents) branch shared secret : 41173 center shared secret : 41173 did both sides produce the same secret: yes did the shared secret cross the channel: no derived key length : 32 bytes center decrypted branch's packet: yes ``` The fifth line is the whole method: the branch reached 41173, the center reached 41173, and that value was never sent. Only 65267, 2, 10224, and 40077 crossed the channel. The last two lines show how the shared secret is used. The raw shared secret is not used directly as a key — it is a numeric value, its length depends on the parameter, and its distribution is not the distribution expected of a key. The key derivation step turns it into a fixed-size, well-distributed key. The packet encrypted with the derived key can be decrypted by the other side with the key it derives from its own shared secret; the chain works end to end. ## The Items in the Eavesdropper's Hands What the method rests on is that going from `g^a mod p` back to `a` — the discrete logarithm, for short — is expensive. The count below writes this out item by item. ```js // exchange/item.mjs — key exchange's item count (model): the items in the eavesdropper's // hands, candidate exponent count by parameter size, the number of retroactively opened // sessions, and the number of verified items. Fictional regional measurement network numbers are used. // CF19: key exchange produces a shared secret but does not verify the other side's identity; // in an unverified exchange, two sides can each agree on two separate secrets. const printRow = (g, ...s) => console.log(s.map((v, i) => (g[i] < 0 ? String(v).padEnd(-g[i]) : String(v).padStart(g[i]))).join("")); console.log("items in the eavesdropper's hands:"); const A = [-29, 12, 19]; printRow(A, "item", "on channel", "enough for secret"); for (const [name, channel, enough] of [ ["prime p", "yes", "no"], ["generator g", "yes", "no"], ["branch's public value A", "yes", "no"], ["center's public value B", "yes", "no"], ["branch's secret exponent a", "no", "yes"], ["center's secret exponent b", "no", "yes"], ["shared secret", "no", "yes"], ]) printRow(A, name, channel, enough); console.log("items on the channel: 4, items sufficient for the secret: 3, their intersection: 0"); console.log("\ncandidate exponent count by parameter size:"); const B = [10, 22, 26]; printRow(B, "p bits", "candidate exponents", "fictional-network trial"); for (const bit of [16, 32, 64, 2048]) printRow(B, bit, bit <= 32 ? (2 ** bit).toLocaleString("en-US") : "2^" + bit, bit <= 32 ? "countable" : "uncountable"); const BRANCHES = 6, SESSIONS_PER_YEAR = 24 * 365; // fictional: hourly sessions per branch console.log(`\nretroactive opening (fictional ${BRANCHES} branches, ${SESSIONS_PER_YEAR} sessions/year per branch):`); const C = [-32, -23, 16]; printRow(C, "scheme", "secret determined by", "sessions opened"); printRow(C, "asymmetric envelope transport", "the sender", (BRANCHES * SESSIONS_PER_YEAR).toLocaleString("en-US")); printRow(C, "ephemeral key exchange", "both sides together", 0); console.log("\nitem the exchange verifies:"); const D = [-39, 13]; printRow(D, "item", "verified"); for (const [name, v] of [["the shared secret's secrecy", "yes"], ["both sides producing the same secret", "yes"], ["the other side's identity", "no"]]) printRow(D, name, v); console.log("2 of 3 items are verified; the unverified item leaves the door open for a"); console.log("party in the middle to run two separate exchanges (model, 2 separate shared secrets)."); ``` ``` items in the eavesdropper's hands: item on channel enough for secret prime p yes no generator g yes no branch's public value A yes no center's public value B yes no branch's secret exponent a no yes center's secret exponent b no yes shared secret no yes items on the channel: 4, items sufficient for the secret: 3, their intersection: 0 candidate exponent count by parameter size: p bits candidate exponents fictional-network trial 16 65,536 countable 32 4,294,967,296 countable 64 2^64 uncountable 2048 2^2048 uncountable retroactive opening (fictional 6 branches, 8760 sessions/year per branch): scheme secret determined by sessions opened asymmetric envelope transport the sender 52,560 ephemeral key exchange both sides together 0 item the exchange verifies: item verified the shared secret's secrecy yes both sides producing the same secret yes the other side's identity no 2 of 3 items are verified; the unverified item leaves the door open for a party in the middle to run two separate exchanges (model, 2 separate shared secrets). ``` The first table's last line is the method's essence: the **intersection** of the four items crossing the channel and the three items sufficient for the secret **is zero**. The eavesdropper records all four items, and none of them carries it into the third set. This is the numerical equivalent of the statement "the eavesdropper cannot reach the secret." The second table shows what this separation depends on. Going from the items crossing the channel back to the secret exponent is not impossible — it is only expensive, and the expense is set by the parameter size. For this lesson's 16-bit prime, the candidate exponent count is 65,536, and that is a set an ordinary machine can enumerate. That is why it was chosen as the teaching parameter; the running example is fast because it is small, not because it is secure. The size used in real deployments is 2048 bits and up; the candidate count there is 2^2048. The same method can also be built with an operation defined over an elliptic curve instead of exponentiation, and the logic does not change: each side picks a secret value, sends its counterpart, and processes what comes from the other side with its own secret value. The only thing that changes is the parameter size needed for the same security. According to the previous lesson's table, a 3072-bit prime's equivalent is a 256-bit curve parameter; that is, the public value carried each round drops from 384 bytes to 32 bytes. In the fictional measurement network, this difference writes straight into the traffic. If 297,600 rounds a day carry a 384-byte public value per round, the daily load is roughly 109 MiB; with a 32-byte public value, the same load drops to 9.1 MiB. That twelvefold difference decides whether the exchange is feasible at all on constrained endpoints. ## Two Consequences, Two Separate Numbers The third table closes the previous lesson's second problem. When the key is transported in an asymmetric envelope, the sender decides the session key, and the envelope is opened with the long-lived private key. If a party holding recorded traffic reaches that private key years later, it opens every one of the fictional network's 52,560 sessions; it makes no difference when the sessions took place. The assumption underneath this line is that encrypted traffic can be recorded. Recording is cheap, and the cost of breaking it can be deferred; in the fictional network, a whole year's sessions fit into an archive of a few hundred gigabytes. That is why the "the key has not leaked" condition is not measured against today's question, but against the archive's lifetime. In ephemeral key exchange, the number is zero. New secret exponents are chosen for every session, the shared secret is limited to that session, and the exponents are deleted when the session ends. The long-lived key leaking later opens no session retroactively, because past sessions' secrets are not stored anywhere. This property carries the name **forward secrecy**, and its cost is generating a pair of exponents per session plus one extra round of exchange. ## The Chain's Seven Items The answer to how many items of this mechanism have to be correct at the same time is seven, and six of them are inside the mechanism itself. The first and second are the parameters: `p` has to actually be prime and large enough, `g` has to be a proper generator for that prime. The parameters are not secret and are usually constants shared by both sides; that makes them easy to audit, but it also carries a flawed parameter set into every session. A badly chosen prime drops the candidate exponent count far below the table's 2^2048 value, and this produces no symptom at runtime — the exchange still works, and still yields the same secret. The third and fourth items are the two secret exponents. The fifth item is the exponents being renewed every session; when they are not renewed, the zero in the forward-secrecy table reverts to the session count. The sixth item is the derivation step: if the raw shared secret is used as the key, the distribution stays broken, and the rest of the chain is built on top of that broken key. The seventh item is outside the mechanism and is the subject of the next section. Even if all six of the six items are correct, who the other side is is not determined in any way inside this method. Its cost is countable too. The exchange adds at least one extra round to connection setup and requires an exponentiation computation on both sides. In the fictional measurement network, if 12,400 endpoints open a session once an hour, that is 297,600 extra rounds a day and the same number of exponentiation operations. What is gained in return is the retroactive closing of the third table's 52,560 sessions. ## The Unverified Item The fourth table is this lesson's boundary. The exchange verifies two of three items: the shared secret stays secret, and both sides produce the same secret. The third item — the other side's identity — is not verified. The consequence can be written as a number. A party that gets between the exchange's two ends can run two separate exchanges: one shared secret with one side, another shared secret with the other side. Both ends see that things worked correctly, because each produced a valid secret on its own side. The verified item count is two, the item left open is one, and the number of shared secrets that come out of it is two. This is not a configuration flaw; identity is not within the exchange method's scope. Agreeing on the parameters is itself inside the same gap. Since `p` and `g` cross the channel openly, which parameters the two sides agree on is also an unverified item; a party in the middle can steer both ends into picking the smallest parameter set each supports, and the table's 2^2048 value silently drops to 2^32. The exchange still completes, both sides still produce the same secret, and no symptom appears. That is why deployments write the smallest accepted parameter size down separately as a policy item — it is not left to negotiation. The method's name itself carries this boundary: key **exchange**, not identity verification. In the fictional measurement network, an exchange between a branch and the center does not say the other side is really the center — it only says a secret was shared with whoever was on the other end of the conversation. ## Summary - Both sides reach the same shared secret without ever sending their secret exponent: in the running example, both sides landed on 41173, and that value never crossed the channel. - The intersection of the 4 items crossing the channel and the 3 items sufficient for the secret is zero; the eavesdropper cannot get from the items it recorded to the shared secret. - Security depends on parameter size: for a 16-bit prime, the candidate exponent count is 65,536 and countable; the teaching example is fast because it is small, not because it is secure. - The raw shared secret is not used directly as a key; key derivation turns it into a fixed-size, well-distributed key. - In ephemeral exchange, the long-lived key leaking opens 0 sessions retroactively; in asymmetric envelope transport, the same leak opens every one of the fictional network's 52,560 sessions. - The exchange verifies two of three items; the other side's identity is not verified, and an unverified exchange can produce two separate shared secrets. ## Next Step The unverified item pushes one step further back. If the exchange itself cannot give the other side's identity, an outside proof is needed, and that proof was already seen once, in the fifth lesson: an operation done with the private key is reversed with the public key, and being reversible showed the source. The next lesson takes up this direction in its own form — a signature is produced and verified, the count of how verification drops when a single bit of the signed data is flipped is measured, and the items the signature proves and the items it does not prove are written down separately. The difference between integrity and non-repudiation is also tied to a number there. The topic does not close with this lesson; the real gap will surface at the end of the seventh lesson.