python-montgomery-ladder-x25519-constant-time
Done. The solution is complete and verified.
~)| File | Purpose |
|---|---|
SOLUTION.md |
The markdown deliverable: title, problem, root-cause analysis, exact fix (full code, byte-identical to the module), verification section |
x25519.py |
Constant-time X25519 implementation (16×16-bit limb field, car25519 carries, sel25519 cswap, p−2 exponentiation, branch-free canonicality check) |
test_x25519.py |
16-test verification suite |
deep_diff.py / deep_diff.out |
Extended differential (2000-iteration ladder vs cryptography) |
%, /, //, pow, divmod — reduction is a fixed carry chain (2^256 ≡ 38 mod p folds the top limb); inversion is a fixed square-and-multiply-always chain over the public constant p−2 (multiply skipped only at e ∈ {2,4}, branches on public bits only).mask = ~(bit−1) cswap; all 255 iterations are branch-free and index only by public loop counters.u < p → ValueError on non-canonical u ≥ p (the problem's requirement; X25519_loose offers the RFC-literal accept-and-reduce variant since RFC text says "MUST accept").u=0 → ladder leaves z2=0 and 0^(p−2)=0 → all-zero secret.X25519(a,9)=8520f009…, X25519(b,9)=de9edb7d…, shared secret 4a5d9d5b…), and the iterated ladder (1 → 422c8e7a…, 1000 → 684cf59b…, 1,000,000 → 7c3911e0… confirmed via cryptography's C implementation).cryptography byte-for-byte (dbaf93a6…, MATCH).p arithmetic; _invert ≡ pow(a, p−2, p); pack/unpack round-trips; canonical output for values up to 2^256−1._carry/_mul/_invert/_pack/_canonical/_sel/X25519 contain no Mod/FloorDiv/Pow/Div operators or pow()/divmod() calls.ast.parse(feature_version=(3,11))); ~57 ms per X25519 call.# Evidence - Problem class: python-montgomery-ladder-x25519-constant-time - Model: openrouter/deepseek/deepseek-v4-flash-0731 - Solved: 2026-09-01T22:38:27.802Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "Implement X25519 from scratch: field arithmetic modulo 2^255-19 with a limb/carry representation, a constant-time Montgomery ladder with cswap, and inversion via exponentiation by p-2 \u2014 no secret-dependent branches, indexing, or variable-time division anywhere. Decode/clamp little-endian u-coordinates, match all RFC 7748 test vectors, and correctly produce the all-zero shared secret for low-order public keys while rejecting non-canonical encodings.", "environment": "python3", "language": "python", "model": "openrouter/deepseek/deepseek-v4-flash-0731", "problem_class": "python-montgomery-ladder-x25519-constant-time", "provider": "openrouter", "solved_at": "2026-09-01T22:38:27.802Z", "version": "3.11"}Done. The solution is complete and verified.
~)| File | Purpose |
|---|---|
SOLUTION.md |
The markdown deliverable: title, problem, root-cause analysis, exact fix (full code, byte-identical to the module), verification section |
x25519.py |
Constant-time X25519 implementation (16×16-bit limb field, car25519 carries, sel25519 cswap, p−2 exponentiation, branch-free canonicality check) |
test_x25519.py |
16-test verification suite |
deep_diff.py / deep_diff.out |
Extended differential (2000-iteration ladder vs cryptography) |
%, /, //, pow, divmod — reduction is a fixed carry chain (2^256 ≡ 38 mod p folds the top limb); inversion is a fixed square-and-multiply-always chain over the public constant p−2 (multiply skipped only at e ∈ {2,4}, branches on public bits only).mask = ~(bit−1) cswap; all 255 iterations are branch-free and index only by public loop counters.u < p → ValueError on non-canonical u ≥ p (the problem's requirement; X25519_loose offers the RFC-literal accept-and-reduce variant since RFC text says "MUST accept").u=0 → ladder leaves z2=0 and 0^(p−2)=0 → all-zero secret.X25519(a,9)=8520f009…, X25519(b,9)=de9edb7d…, shared secret 4a5d9d5b…), and the iterated ladder (1 → 422c8e7a…, 1000 → 684cf59b…, 1,000,000 → 7c3911e0… confirmed via cryptography's C implementation).cryptography byte-for-byte (dbaf93a6…, MATCH).p arithmetic; _invert ≡ pow(a, p−2, p); pack/unpack round-trips; canonical output for values up to 2^256−1._carry/_mul/_invert/_pack/_canonical/_sel/X25519 contain no Mod/FloorDiv/Pow/Div operators or pow()/divmod() calls.ast.parse(feature_version=(3,11))); ~57 ms per X25519 call.# Evidence - Problem class: python-montgomery-ladder-x25519-constant-time - Model: openrouter/deepseek/deepseek-v4-flash-0731 - Solved: 2026-09-01T22:38:27.802Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "Implement X25519 from scratch: field arithmetic modulo 2^255-19 with a limb/carry representation, a constant-time Montgomery ladder with cswap, and inversion via exponentiation by p-2 \u2014 no secret-dependent branches, indexing, or variable-time division anywhere. Decode/clamp little-endian u-coordinates, match all RFC 7748 test vectors, and correctly produce the all-zero shared secret for low-order public keys while rejecting non-canonical encodings.", "environment": "python3", "language": "python", "model": "openrouter/deepseek/deepseek-v4-flash-0731", "problem_class": "python-montgomery-ladder-x25519-constant-time", "provider": "openrouter", "solved_at": "2026-09-01T22:38:27.802Z", "version": "3.11"}