ed25519.mjs raw
1 // ed25519.mjs — Ed25519 signatures (RFC 8032) using JS BigInt.
2 // Twisted Edwards curve: -x² + y² = 1 + d·x²·y² over GF(2²⁵⁵ − 19).
3
4 import { Slice } from './builtin.mjs';
5
6 // --- Constants ---
7
8 const P = (1n << 255n) - 19n;
9 const L = (1n << 252n) + 27742317777372353535851937790883648493n;
10 const D = 37095705934669439343138083508754565189542113879843219016388785533085940283555n;
11 const I = 19681161376707505956807079304988542015446066515923890162744021073123829784752n; // sqrt(-1) mod p
12 const Bx = 15112221349535400772501151409588531511454012693041857206046113283949847762202n;
13 const By = 46316835694926478169428394003475163141307993866256225615783033603165251855960n;
14
15 // --- Field arithmetic mod P ---
16
17 function modP(x) { return ((x % P) + P) % P; }
18
19 function modPow(base, exp) {
20 let r = 1n;
21 base = modP(base);
22 while (exp > 0n) {
23 if (exp & 1n) r = r * base % P;
24 exp >>= 1n;
25 base = base * base % P;
26 }
27 return r;
28 }
29
30 function modInv(a) { return modPow(a, P - 2n); }
31
32 // --- Extended twisted Edwards point arithmetic ---
33 // Representation: [X, Y, Z, T] where x=X/Z, y=Y/Z, T=X·Y/Z.
34 // Identity: [0, 1, 1, 0].
35
36 function extDbl(p) {
37 const [X, Y, Z] = p;
38 const A = modP(X * X);
39 const B = modP(Y * Y);
40 const C = modP(2n * Z * Z);
41 // a = -1: D = a*A = -A. EFD dbl-2008-hwcd formulas.
42 const E = modP(modP((X + Y) * (X + Y)) - A - B);
43 const G = modP(B - A); // D + B where D = -A
44 const F = modP(G - C); // G - C
45 const H = modP(-A - B); // D - B where D = -A
46 return [modP(E * F), modP(G * H), modP(F * G), modP(E * H)];
47 }
48
49 function extAdd(p1, p2) {
50 const [X1, Y1, Z1, T1] = p1;
51 const [X2, Y2, Z2, T2] = p2;
52 const A = modP((Y1 - X1) * (Y2 - X2));
53 const B = modP((Y1 + X1) * (Y2 + X2));
54 const C = modP(T1 * 2n * D * T2);
55 const E = modP(B - A);
56 const DD = modP(Z1 * 2n * Z2);
57 const F = modP(DD - C);
58 const G = modP(DD + C);
59 const H = modP(B + A);
60 return [modP(E * F), modP(G * H), modP(F * G), modP(E * H)];
61 }
62
63 function scalarMult(k, p) {
64 let r = [0n, 1n, 1n, 0n];
65 let q = p;
66 k = ((k % L) + L) % L;
67 while (k > 0n) {
68 if (k & 1n) r = extAdd(r, q);
69 q = extDbl(q);
70 k >>= 1n;
71 }
72 return r;
73 }
74
75 const B = [Bx, By, 1n, modP(Bx * By)];
76
77 function scalarMultBase(k) { return scalarMult(k, B); }
78
79 // --- Point encoding / decoding ---
80
81 function encodePoint(p) {
82 const zi = modInv(p[2]);
83 const x = modP(p[0] * zi);
84 const y = modP(p[1] * zi);
85 const out = new Uint8Array(32);
86 let yy = y;
87 for (let i = 0; i < 32; i++) { out[i] = Number(yy & 0xFFn); yy >>= 8n; }
88 if (x & 1n) out[31] |= 0x80;
89 return out;
90 }
91
92 function decodePoint(bytes) {
93 let y = 0n;
94 for (let i = 31; i >= 0; i--) y = (y << 8n) | BigInt(bytes[i]);
95 const sign = (y >> 255n) & 1n;
96 y &= (1n << 255n) - 1n;
97 if (y >= P) return null;
98
99 const y2 = modP(y * y);
100 const u = modP(y2 - 1n);
101 const v = modP(D * y2 + 1n);
102
103 // x = u·v³ · (u·v⁷)^((p-5)/8)
104 const v3 = modP(v * v * v);
105 const uv3 = modP(u * v3);
106 const uv7 = modP(uv3 * modP(v3 * v));
107 let x = modP(uv3 * modPow(uv7, (P - 5n) / 8n));
108
109 if (modP(x * x * v - u) !== 0n) {
110 x = modP(x * I);
111 if (modP(x * x * v - u) !== 0n) return null;
112 }
113
114 if ((x & 1n) !== sign) x = modP(P - x);
115 if (x === 0n && sign) return null;
116
117 return [x, y, 1n, modP(x * y)];
118 }
119
120 // --- SHA-512 (inline, BigInt-based for 64-bit words) ---
121
122 const K512 = [
123 0x428a2f98d728ae22n, 0x7137449123ef65cdn, 0xb5c0fbcfec4d3b2fn, 0xe9b5dba58189dbbcn,
124 0x3956c25bf348b538n, 0x59f111f1b605d019n, 0x923f82a4af194f9bn, 0xab1c5ed5da6d8118n,
125 0xd807aa98a3030242n, 0x12835b0145706fben, 0x243185be4ee4b28cn, 0x550c7dc3d5ffb4e2n,
126 0x72be5d74f27b896fn, 0x80deb1fe3b1696b1n, 0x9bdc06a725c71235n, 0xc19bf174cf692694n,
127 0xe49b69c19ef14ad2n, 0xefbe4786384f25e3n, 0x0fc19dc68b8cd5b5n, 0x240ca1cc77ac9c65n,
128 0x2de92c6f592b0275n, 0x4a7484aa6ea6e483n, 0x5cb0a9dcbd41fbd4n, 0x76f988da831153b5n,
129 0x983e5152ee66dfabn, 0xa831c66d2db43210n, 0xb00327c898fb213fn, 0xbf597fc7beef0ee4n,
130 0xc6e00bf33da88fc2n, 0xd5a79147930aa725n, 0x06ca6351e003826fn, 0x142929670a0e6e70n,
131 0x27b70a8546d22ffcn, 0x2e1b21385c26c926n, 0x4d2c6dfc5ac42aedn, 0x53380d139d95b3dfn,
132 0x650a73548baf63den, 0x766a0abb3c77b2a8n, 0x81c2c92e47edaee6n, 0x92722c851482353bn,
133 0xa2bfe8a14cf10364n, 0xa81a664bbc423001n, 0xc24b8b70d0f89791n, 0xc76c51a30654be30n,
134 0xd192e819d6ef5218n, 0xd69906245565a910n, 0xf40e35855771202an, 0x106aa07032bbd1b8n,
135 0x19a4c116b8d2d0c8n, 0x1e376c085141ab53n, 0x2748774cdf8eeb99n, 0x34b0bcb5e19b48a8n,
136 0x391c0cb3c5c95a63n, 0x4ed8aa4ae3418acbn, 0x5b9cca4f7763e373n, 0x682e6ff3d6b2b8a3n,
137 0x748f82ee5defb2fcn, 0x78a5636f43172f60n, 0x84c87814a1f0ab72n, 0x8cc702081a6439ecn,
138 0x90befffa23631e28n, 0xa4506cebde82bde9n, 0xbef9a3f7b2c67915n, 0xc67178f2e372532bn,
139 0xca273eceea26619cn, 0xd186b8c721c0c207n, 0xeada7dd6cde0eb1en, 0xf57d4f7fee6ed178n,
140 0x06f067aa72176fban, 0x0a637dc5a2c898a6n, 0x113f9804bef90daen, 0x1b710b35131c471bn,
141 0x28db77f523047d84n, 0x32caab7b40c72493n, 0x3c9ebe0a15c9bebcn, 0x431d67c49c100d4cn,
142 0x4cc5d4becb3e42b6n, 0x597f299cfc657e2an, 0x5fcb6fab3ad6faecn, 0x6c44198c4a475817n,
143 ];
144 const M64 = 0xFFFFFFFFFFFFFFFFn;
145 function rotr64(x, n) { const b = BigInt(n); return ((x >> b) | (x << (64n - b))) & M64; }
146
147 function sha512(data) {
148 const len = data.length;
149 const bitLen = BigInt(len) * 8n;
150 const padLen = ((112 - (len + 1) % 128) + 128) % 128;
151 const buf = new Uint8Array(len + 1 + padLen + 16);
152 buf.set(data);
153 buf[len] = 0x80;
154 const dv = new DataView(buf.buffer);
155 dv.setUint32(buf.length - 8, Number((bitLen >> 32n) & 0xFFFFFFFFn), false);
156 dv.setUint32(buf.length - 4, Number(bitLen & 0xFFFFFFFFn), false);
157
158 let h0=0x6a09e667f3bcc908n, h1=0xbb67ae8584caa73bn, h2=0x3c6ef372fe94f82bn, h3=0xa54ff53a5f1d36f1n;
159 let h4=0x510e527fade682d1n, h5=0x9b05688c2b3e6c1fn, h6=0x1f83d9abfb41bd6bn, h7=0x5be0cd19137e2179n;
160
161 function rd64(o) { return (BigInt(dv.getUint32(o, false)) << 32n) | BigInt(dv.getUint32(o+4, false)); }
162 const W = new Array(80);
163 for (let off = 0; off < buf.length; off += 128) {
164 for (let i = 0; i < 16; i++) W[i] = rd64(off + i * 8);
165 for (let i = 16; i < 80; i++) {
166 const s0 = rotr64(W[i-15],1) ^ rotr64(W[i-15],8) ^ (W[i-15] >> 7n);
167 const s1 = rotr64(W[i-2],19) ^ rotr64(W[i-2],61) ^ (W[i-2] >> 6n);
168 W[i] = (W[i-16] + s0 + W[i-7] + s1) & M64;
169 }
170 let a=h0, b=h1, c=h2, d=h3, e=h4, f=h5, g=h6, h=h7;
171 for (let i = 0; i < 80; i++) {
172 const S1 = rotr64(e,14) ^ rotr64(e,18) ^ rotr64(e,41);
173 const ch = (e & f) ^ ((~e & M64) & g);
174 const t1 = (h + S1 + ch + K512[i] + W[i]) & M64;
175 const S0 = rotr64(a,28) ^ rotr64(a,34) ^ rotr64(a,39);
176 const maj = (a & b) ^ (a & c) ^ (b & c);
177 const t2 = (S0 + maj) & M64;
178 h=g; g=f; f=e; e=(d+t1)&M64; d=c; c=b; b=a; a=(t1+t2)&M64;
179 }
180 h0=(h0+a)&M64; h1=(h1+b)&M64; h2=(h2+c)&M64; h3=(h3+d)&M64;
181 h4=(h4+e)&M64; h5=(h5+f)&M64; h6=(h6+g)&M64; h7=(h7+h)&M64;
182 }
183
184 const out = new Uint8Array(64);
185 const ov = new DataView(out.buffer);
186 function wr64(o, v) { ov.setUint32(o, Number(v >> 32n), false); ov.setUint32(o+4, Number(v & 0xFFFFFFFFn), false); }
187 wr64(0,h0); wr64(8,h1); wr64(16,h2); wr64(24,h3);
188 wr64(32,h4); wr64(40,h5); wr64(48,h6); wr64(56,h7);
189 return out;
190 }
191
192 // --- Scalar helpers ---
193
194 function clampScalar(h) {
195 const a = new Uint8Array(32);
196 for (let i = 0; i < 32; i++) a[i] = h[i];
197 a[0] &= 248;
198 a[31] &= 127;
199 a[31] |= 64;
200 let s = 0n;
201 for (let i = 31; i >= 0; i--) s = (s << 8n) | BigInt(a[i]);
202 return s;
203 }
204
205 function bytesToScalarLE(h) {
206 let s = 0n;
207 for (let i = h.length - 1; i >= 0; i--) s = (s << 8n) | BigInt(h[i]);
208 return ((s % L) + L) % L;
209 }
210
211 function scalarToBytes(s) {
212 const out = new Uint8Array(32);
213 for (let i = 0; i < 32; i++) { out[i] = Number(s & 0xFFn); s >>= 8n; }
214 return out;
215 }
216
217 // --- Slice conversions ---
218
219 function sliceToU8(s) {
220 if (s instanceof Uint8Array) return s;
221 if (typeof s === 'string') return new TextEncoder().encode(s);
222 const u = new Uint8Array(s.$length);
223 for (let i = 0; i < s.$length; i++) u[i] = s.$array[s.$offset + i];
224 return u;
225 }
226
227 function u8ToSlice(u8) {
228 const arr = new Array(u8.length);
229 for (let i = 0; i < u8.length; i++) arr[i] = u8[i];
230 return new Slice(arr, 0, u8.length, u8.length);
231 }
232
233 // --- Exports ---
234
235 // NewKeyFromSeed derives the 32-byte public key from a 32-byte seed.
236 export function NewKeyFromSeed(seed) {
237 const s = sliceToU8(seed);
238 const h = sha512(s);
239 const a = clampScalar(h);
240 return u8ToSlice(encodePoint(scalarMultBase(a)));
241 }
242
243 // Sign produces a 64-byte Ed25519 signature of message using a 32-byte seed.
244 export function Sign(seed, message) {
245 const s = sliceToU8(seed);
246 const msg = sliceToU8(message);
247 const h = sha512(s);
248 const a = clampScalar(h);
249 const A = encodePoint(scalarMultBase(a));
250
251 // r = SHA-512(h[32:64] || msg) mod L
252 const rBuf = new Uint8Array(32 + msg.length);
253 for (let i = 0; i < 32; i++) rBuf[i] = h[32 + i];
254 rBuf.set(msg, 32);
255 const r = bytesToScalarLE(sha512(rBuf));
256
257 // R = r·B
258 const R = encodePoint(scalarMultBase(r));
259
260 // S = (r + SHA-512(R || A || msg) · a) mod L
261 const hramBuf = new Uint8Array(32 + 32 + msg.length);
262 hramBuf.set(R);
263 hramBuf.set(A, 32);
264 hramBuf.set(msg, 64);
265 const hram = bytesToScalarLE(sha512(hramBuf));
266 const S = ((r + hram * a) % L + L) % L;
267
268 const sig = new Uint8Array(64);
269 sig.set(R);
270 sig.set(scalarToBytes(S), 32);
271 return u8ToSlice(sig);
272 }
273
274 // Verify checks a 64-byte Ed25519 signature of message against a 32-byte public key.
275 export function Verify(pubkey, message, sig) {
276 const pkBytes = sliceToU8(pubkey);
277 const msg = sliceToU8(message);
278 const sigBytes = sliceToU8(sig);
279 if (sigBytes.length !== 64 || pkBytes.length !== 32) return false;
280
281 const A = decodePoint(pkBytes);
282 if (!A) return false;
283 const Rpt = decodePoint(sigBytes.slice(0, 32));
284 if (!Rpt) return false;
285
286 let S = 0n;
287 for (let i = 31; i >= 0; i--) S = (S << 8n) | BigInt(sigBytes[32 + i]);
288 if (S >= L) return false;
289
290 // h = SHA-512(R || A || msg) mod L
291 const hBuf = new Uint8Array(32 + 32 + msg.length);
292 hBuf.set(sigBytes.slice(0, 32));
293 hBuf.set(pkBytes, 32);
294 hBuf.set(msg, 64);
295 const h = bytesToScalarLE(sha512(hBuf));
296
297 // Check: S·B = R + h·A
298 const lhs = scalarMultBase(S);
299 const rhs = extAdd(Rpt, scalarMult(h, A));
300
301 const lhsEnc = encodePoint(lhs);
302 const rhsEnc = encodePoint(rhs);
303 for (let i = 0; i < 32; i++) if (lhsEnc[i] !== rhsEnc[i]) return false;
304 return true;
305 }
306