256-bit Modular Exponentiation
Algorithms & Data
A 256-bit Diffie-Hellman key exchange — g^a, g^b, shared secret
B^a == A^b — built from 32-bit limbs and 64-bit multiply-accumulate. This
is compiler stress-test #104: it runs the exact 64-bit code paths a real
llvm-mos crash once hit
(patch 0017), hundreds of times over at heavy register pressure, and
confirms the fix holds.
Self-running — the 256-bit shared secret, computed once, shown as a colour field.
Click the screen to focus, then watch. Tab away and it pauses.
What it is
Public-key crypto leans on modular exponentiation of big integers. Here the integers are 256 bits — far past any native type on a 16-bit machine — so they are assembled from smaller limbs, and every operation bottoms out in 64-bit arithmetic. The exchange is small but the 64-bit traffic is enormous.
// a 256-bit number is eight 32-bit limbs; multiply is schoolbook, // each partial product accumulated in a 64-bit column with carry uint64_t cur = (uint64_t)p[i+j] + (uint64_t)a[i]*(uint64_t)b[j] + carry; p[i+j] = (uint32_t)cur; carry = cur >> 32; // 64-bit math the whole way // reduce mod (2^256 - 189): fold the high half back in (2^256 ≡ 189) // Diffie-Hellman: A = g^a, B = g^b, shared = B^a == A^b (must be equal)
The gate folds the shared secret, plus the difference between the two ways of computing it, into a CRC. The picture is the proof: a single wrong 64-bit limb breaks the Diffie-Hellman equality and changes the CRC.
Compiler stress-test #104 — Round 6: hardening the fixes
| Item | What it exercises |
|---|---|
| 256-bit from 64-bit pieces | The 65816 has no 128- or 256-bit type — so a 256-bit number is built as eight 32-bit limbs, and every multiply, add, shift, and compare runs through 64-bit arithmetic. A single 256×256 multiply is dozens of 64-bit multiply-accumulates; a full modular exponentiation is thousands. That is the point: it runs the 64-bit code paths at volume. |
| the bug this guards (#61, patch 0017) | A 64-bit Diffie-Hellman demo once crashed this backend — it had no rule to split a 64-bit value into 16-bit lanes, nor to multiply two 64-bit values without ballooning to 128 bits. Patch 0017 taught it both. This demo hammers that same 64-bit glue hundreds of times over, at heavy register pressure, and confirms it still holds. |
| Diffie-Hellman as a self-check | Two parties pick secret exponents a and b; one computes A = g^a, the other B = g^b; the shared secret is B^a on one side and A^b on the other. These are always equal, because (g^a)^b = g^(ab) = (g^b)^a. The demo computes both and folds their difference into the CRC — so a single wrong 64-bit limb breaks the equality and the check. |
| no prime needed | The Diffie-Hellman equality holds for any modulus, not just a prime — it is pure exponent commutativity. So the demo uses 2^256 − 189, a modulus whose shape makes reduction cheap: since 2^256 ≡ 189, the high half of a product folds back into the low half with one small multiply. |
| checked against a reference | The 256-bit modular arithmetic was cross-checked against Python’s arbitrary-precision integers: the C result for g^7 mod (2^256 − 189) matches pow(g, 7, m) bit for bit. So the on-device result has a known-correct ground truth, not just internal consistency. |
| result: bit-exact, and the visual | 256-bit integer modexp is exact, so it is identical on host and SNES: host == default == +mos-a16 == +mos-xy16 on both MAME and bsnes-jg, -verify-machineinstrs clean. The shared secret is heavy to compute, so it is worked out once at startup and shown as a 16×16 field coloured from its 256 bits, with a slow palette drift. (The compute takes a beat — that is thousands of 64-bit operations running.) |
Written in C with the llvm-mos 65816 toolchain and verified against bsnes-jg and MAME.
Hit Verify fidelity to reproduce the build gate's WRAM assert
(gate CRC 0x31D4 — a fold of the 256-bit shared secret; give it a few seconds, the
256-bit modexp is heavy) live in this tab.
No far pointers — host == default == +mos-a16 == +mos-xy16,
-verify clean.