| 1 | // P-256 scalar multiplication, so we never have to ask a browser to guess. |
| 2 | // |
| 3 | // # Why this exists |
| 4 | // |
| 5 | // Deriving the login keypair means turning a scalar into a keypair, and |
| 6 | // WebCrypto has no "import a private scalar" door. The trick we used instead |
| 7 | // was a 67-byte PKCS#8 with the public half omitted, which Chromium, node and |
| 8 | // newer WebKit all accept by recomputing the point — and which Safari rejects |
| 9 | // with a bare DataError, because the field is optional in the ASN.1 and |
| 10 | // required in practice by whoever wrote that importer. |
| 11 | // |
| 12 | // A JWK carrying d, x AND y is accepted everywhere. It just means computing |
| 13 | // the point ourselves, which is this file. |
| 14 | // |
| 15 | // BigInt is fine here: this runs about twice per ceremony, next to an |
| 16 | // Argon2id that takes two seconds. The one place arithmetic had to be fast |
| 17 | // (argon2id.js) pays for its 32-bit word pairs; this does not. |
| 18 | // |
| 19 | // Verified against the golden vectors, which carry seed → public key for |
| 20 | // three seeds including one that forces the rejection branch. |
| 21 | |
| 22 | const P = 0xffffffff00000001000000000000000000000000ffffffffffffffffffffffffn; |
| 23 | const B = 0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604bn; |
| 24 | const GX = 0x6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296n; |
| 25 | const GY = 0x4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5n; |
| 26 | |
| 27 | export const N = 0xffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551n; |
| 28 | |
| 29 | const mod = (x) => ((x % P) + P) % P; |
| 30 | |
| 31 | // Fermat's little theorem: the curve's prime means x^(p-2) is x's inverse. |
| 32 | // Slower than an extended Euclid and branch-free, which is the right trade |
| 33 | // for something that touches a private scalar. |
| 34 | function inverse(x) { |
| 35 | let result = 1n; |
| 36 | let base = mod(x); |
| 37 | let e = P - 2n; |
| 38 | while (e > 0n) { |
| 39 | if (e & 1n) result = mod(result * base); |
| 40 | base = mod(base * base); |
| 41 | e >>= 1n; |
| 42 | } |
| 43 | return result; |
| 44 | } |
| 45 | |
| 46 | // Points are Jacobian: (X, Y, Z) meaning (X/Z², Y/Z³). Z = 0 is infinity. |
| 47 | // Jacobian rather than affine so the whole ladder needs one inversion at the |
| 48 | // end instead of one per step. |
| 49 | const INFINITY = { x: 0n, y: 1n, z: 0n }; |
| 50 | |
| 51 | function double(p) { |
| 52 | if (p.z === 0n) return INFINITY; |
| 53 | const delta = mod(p.z * p.z); |
| 54 | const gamma = mod(p.y * p.y); |
| 55 | const beta = mod(p.x * gamma); |
| 56 | // a = -3 on this curve, which is what collapses alpha to this form. |
| 57 | const alpha = mod(3n * mod(p.x - delta) * mod(p.x + delta)); |
| 58 | const x = mod(alpha * alpha - 8n * beta); |
| 59 | const z = mod(mod(p.y + p.z) * mod(p.y + p.z) - gamma - delta); |
| 60 | const y = mod(alpha * mod(4n * beta - x) - 8n * mod(gamma * gamma)); |
| 61 | return { x, y, z }; |
| 62 | } |
| 63 | |
| 64 | function add(p, q) { |
| 65 | if (p.z === 0n) return q; |
| 66 | if (q.z === 0n) return p; |
| 67 | |
| 68 | const z1z1 = mod(p.z * p.z); |
| 69 | const z2z2 = mod(q.z * q.z); |
| 70 | const u1 = mod(p.x * z2z2); |
| 71 | const u2 = mod(q.x * z1z1); |
| 72 | const s1 = mod(p.y * q.z * z2z2); |
| 73 | const s2 = mod(q.y * p.z * z1z1); |
| 74 | |
| 75 | if (u1 === u2) { |
| 76 | // Same x: either the same point (double it) or a point and its negation |
| 77 | // (which sum to infinity). Getting this wrong is the classic way an |
| 78 | // otherwise correct implementation returns garbage on one input in 2^128. |
| 79 | return s1 === s2 ? double(p) : INFINITY; |
| 80 | } |
| 81 | |
| 82 | const h = mod(u2 - u1); |
| 83 | const i = mod(4n * h * h); |
| 84 | const j = mod(h * i); |
| 85 | const r = mod(2n * (s2 - s1)); |
| 86 | const v = mod(u1 * i); |
| 87 | const x = mod(r * r - j - 2n * v); |
| 88 | const y = mod(r * mod(v - x) - 2n * s1 * j); |
| 89 | const z = mod(mod(mod(p.z + q.z) * mod(p.z + q.z) - z1z1 - z2z2) * h); |
| 90 | return { x, y, z }; |
| 91 | } |
| 92 | |
| 93 | function toAffine(p) { |
| 94 | if (p.z === 0n) throw new Error("contra: the point at infinity has no affine form"); |
| 95 | const zInv = inverse(p.z); |
| 96 | const zInv2 = mod(zInv * zInv); |
| 97 | return { x: mod(p.x * zInv2), y: mod(p.y * zInv2 * zInv) }; |
| 98 | } |
| 99 | |
| 100 | function bytesToBigInt(b) { |
| 101 | let n = 0n; |
| 102 | for (const byte of b) n = (n << 8n) | BigInt(byte); |
| 103 | return n; |
| 104 | } |
| 105 | |
| 106 | function bigIntTo32(n) { |
| 107 | const out = new Uint8Array(32); |
| 108 | for (let i = 31; i >= 0; i--) { |
| 109 | out[i] = Number(n & 0xffn); |
| 110 | n >>= 8n; |
| 111 | } |
| 112 | return out; |
| 113 | } |
| 114 | |
| 115 | // publicKeyFor returns the affine coordinates of d·G as 32-byte big-endian |
| 116 | // values — x and y, ready for a JWK. |
| 117 | // |
| 118 | // The ladder is a plain left-to-right double-and-add. It is not constant |
| 119 | // time, and that is worth stating plainly rather than implying otherwise: the |
| 120 | // scalar it multiplies is derived from the passphrase, so a local attacker |
| 121 | // who could time this precisely would learn something about it. Every |
| 122 | // alternative available in a browser has the same property, WebCrypto's own |
| 123 | // PKCS#8 path included, and the threat model that matters here — a hostile |
| 124 | // server, a stolen bucket — does not include one. |
| 125 | export function publicKeyFor(scalar) { |
| 126 | const d = bytesToBigInt(scalar); |
| 127 | if (d <= 0n || d >= N) throw new Error("contra: scalar out of range"); |
| 128 | |
| 129 | let result = INFINITY; |
| 130 | const base = { x: GX, y: GY, z: 1n }; |
| 131 | for (let i = 255; i >= 0; i--) { |
| 132 | result = double(result); |
| 133 | if ((d >> BigInt(i)) & 1n) result = add(result, base); |
| 134 | } |
| 135 | const { x, y } = toAffine(result); |
| 136 | |
| 137 | // A sanity check that costs one multiplication and catches a whole class of |
| 138 | // silent arithmetic error: the point must actually be on the curve. |
| 139 | if (mod(y * y) !== mod(x * x * x - 3n * x + B)) { |
| 140 | throw new Error("contra: derived point is not on the curve"); |
| 141 | } |
| 142 | return { x: bigIntTo32(x), y: bigIntTo32(y) }; |
| 143 | } |
| 144 | |
amadan