From 240900d3b75827d4b491dd82bb03a67d5a820001 Mon Sep 17 00:00:00 2001 From: Chris Duncan Date: Tue, 29 Sep 2026 22:02:27 -0700 Subject: [PATCH] Initialize generator scripts for group elements and point arithmetic. Bundle generator file output into index file, but comment out all except blake since they are not ready. --- package.json | 4 +- scripts/blake2b.gen.mjs | 6 +- scripts/fe.gen.mjs | 41 ++-- scripts/ge.gen.mjs | 456 ++++++++++++++++++++++++++++++++++++++++ scripts/index.mjs | 23 ++ scripts/p.gen.mjs | 262 +++++++++++++++++++++++ 6 files changed, 760 insertions(+), 32 deletions(-) create mode 100644 scripts/ge.gen.mjs create mode 100644 scripts/index.mjs create mode 100644 scripts/p.gen.mjs diff --git a/package.json b/package.json index fa9b4fb..1c177a4 100644 --- a/package.json +++ b/package.json @@ -35,9 +35,7 @@ "build:prod": "npm run clean && npm run compile && node ./esbuild/prod.mjs", "clean": "rm -rf {build,dist}", "compile": "npm run generate && asc ./src/assembly/index.ts && tsc", - "generate": "npm run generate:blake2b & npm run generate:fe", - "generate:blake2b": "node scripts/blake2b.gen.mjs", - "generate:fe": "node scripts/fe.gen.mjs", + "generate": "node scripts/index.mjs", "prepublishOnly": "npm run test:prod", "test": "npm run build && npm run test:all", "test:all": "npm run test:le && npm run test:be", diff --git a/scripts/blake2b.gen.mjs b/scripts/blake2b.gen.mjs index 1cf31c8..51710cd 100644 --- a/scripts/blake2b.gen.mjs +++ b/scripts/blake2b.gen.mjs @@ -11,8 +11,6 @@ * e.g. `wgsl-analyzer` or `asc` */ -import { writeFile } from 'node:fs/promises' - const blake2b_state = [ [0, 4, 8, 12], [1, 5, 9, 13], @@ -224,7 +222,7 @@ const COMPRESS = (() => { return output })() -const BLAKE2b = `//! SPDX-FileCopyrightText: 2026 Chris Duncan +export const BLAKE2b = `//! SPDX-FileCopyrightText: 2026 Chris Duncan //! SPDX-License-Identifier: GPL-3.0-or-later export class Blake2b { @@ -287,5 +285,3 @@ ${CLEAR()} } } ` - -await writeFile('src/assembly/ed25519/blake2b.ts', BLAKE2b) diff --git a/scripts/fe.gen.mjs b/scripts/fe.gen.mjs index ace542d..41e1b3e 100644 --- a/scripts/fe.gen.mjs +++ b/scripts/fe.gen.mjs @@ -9,11 +9,24 @@ * AssemblyScript compiler and type checker. */ -import { writeFile } from 'node:fs/promises' +/** + * Add two FieldElements and store the sum. + * + * @param {string} h Variable name of FieldElement sum destination + * @param {string} f Variable name of FieldElement summand source + * @param {string} g Variable name of FieldElement summand source + * @returns {string} Three vector addition commands + */ +export function fe_add (h, f, g) { + return ` + ${h}0 = v128.add(${f}0, ${g}0) + ${h}1 = v128.add(${f}1, ${g}1) + ${h}2 = v128.add(${f}2, ${g}2) + ` +} -const FE = `//! SPDX-FileCopyrightText: 2026 Chris Duncan +export const FE = `//! SPDX-FileCopyrightText: 2026 Chris Duncan //! SPDX-License-Identifier: GPL-3.0-or-later - /** * Arithmetic on field elements. These are integers in the range * @@ -69,24 +82,6 @@ export function fe_1 (h: FieldElement): void { store(changetype(h), 1, 0) } -/** - * Add two FieldElements and store the sum. - * - * @param h FieldElement sum destination - * @param f FieldElement summand source - * @param g FieldElement summand source - */ -//@ts-expect-error -@inline -export function fe_add (h: FieldElement, f: FieldElement, g: FieldElement): void { - const h_ptr = changetype(h) - const f_ptr = changetype(f) - const g_ptr = changetype(g) - v128.store(h_ptr, v128.add(v128.load(f_ptr, 0), v128.load(g_ptr, 0)), 0) - v128.store(h_ptr, v128.add(v128.load(f_ptr, 16), v128.load(g_ptr, 16)), 16) - v128.store_lane(h_ptr, v128.add(v128.load(f_ptr, 32), v128.load(g_ptr, 32)), 0, 32) -} - /** * Conditionally copy values from one FieldElement to another. * @@ -944,7 +939,7 @@ export function fe_sq (h: FieldElement, f: FieldElement): void { * @param hx FieldElement power destination * @param fx FieldElement base source */ -export function fe_sq_vec (hx: FieldElement, fx: FieldElement, hy: FieldElement, fy: FieldElement): void { +export function fe_sq_vec (hx: FieldElement, hy: FieldElement, fx: FieldElement, fy: FieldElement): void { const fx_ptr: usize = changetype(fx) const fy_ptr: usize = changetype(fy) const f0: v128 = i32x4(load(fx_ptr, 0), load(fy_ptr, 0), 0, 0) @@ -1472,5 +1467,3 @@ export function fe_tobytes (s: StaticArray, h: FieldElement): void { store(s_ptr, t9 >> 18, 31) } ` - -await writeFile('src/assembly/ed25519/fe.ts', FE) diff --git a/scripts/ge.gen.mjs b/scripts/ge.gen.mjs new file mode 100644 index 0000000..ee3c08f --- /dev/null +++ b/scripts/ge.gen.mjs @@ -0,0 +1,456 @@ +//! SPDX-FileCopyrightText: 2026 Chris Duncan +//! SPDX-License-Identifier: GPL-3.0-or-later +/** + * Generate Ed25519 group element operations for WebAssembly API. Specifically, + * it outputs `ge.ts`, an AssemblyScript file that must be compiled as part of a + * WASM module. + * + * The final output file should be checked separately for correctness using the + * AssemblyScript compiler and type checker. + */ + +export const GE = `//! SPDX-FileCopyrightText: 2026 Chris Duncan +//! SPDX-License-Identifier: GPL-3.0-or-later +/** + * ge means group element. + * + * Here the group is the set of pairs (x,y) of field elements satisfying + * + * -x² + y² = 1 + d x²y² + * + * where d = -121665/121666. + * + * Representations: + * - ge_p2 (projective): (X:Y:Z) satisfying x=X/Z, y=Y/Z + * - ge_p3 (extended): (X:Y:Z:T) satisfying x=X/Z, y=Y/Z, XY=ZT + * - ge_p1p1 (completed): ((X:Z),(Y:T)) satisfying x=X/Z, y=Y/T + * - ge_precomp (Duif): (y+x,y-x,2dxy) +*/ + +import { base } from './base' +import { base2 } from './base2' +import { FieldElement, fe, fe_1, fe_add, fe_cmov, fe_frombytes, fe_isnegative, fe_iszero, fe_mul, fe_neg, fe_pow22523, fe_sq, fe_sub } from './fe' +import { ge_add_cached, ge_add_precomp, ge_cached, ge_p1p1, ge_p1p1_0, ge_p1p1_to_p2, ge_p1p1_to_p3, ge_p2, ge_p2_0, ge_p2_dbl, ge_p2_to_p3, ge_p3, ge_p3_0, ge_p3_dbl, ge_p3_to_cached, ge_p3_tobytes, ge_precomp, ge_precomp_0, ge_sub_cached, ge_sub_precomp } from './p' + +/** + * √-1 + */ +const fe_sqrtm1: FieldElement = StaticArray.fromArray([ + -32595792, -7943725, 9377950, 3500415, 12389472, -272473, -25146209, -2005654, 326686, 11406482, 0, 0 +]) + +/** + * d = −121665 / 121666 + * = 37095705934669439343138083508754565189542113879843219016388785533085940283555 + */ +const ed25519_d: FieldElement = StaticArray.fromArray([ + -10913610, 13857413, -15372611, 6949391, 114729, -8787816, -6275908, -3247719, -18696448, -12055116, 0, 0 +]) + +//@ts-expect-error +@inline +function ge_cmov8_base (t: ge_precomp, bp: usize, b: i8): void { + const isbneg: i8 = (b >> 7) & 1 /* 0: positive; 1: negative */ + const babs: i8 = b - (((-isbneg) & b) * (i8(1) << 1)) + + // identity: (1, 1, 0) + // yplusx = 1 + let p0 = i32x4(1, 0, 0, 0), p1 = i32x4(0, 0, 0, 0), p2 = i32x4(0, 0, 0, 0) + // yminusx = 1 + let m0 = i32x4(1, 0, 0, 0), m1 = i32x4(0, 0, 0, 0), m2 = i32x4(0, 0, 0, 0) + // xy2d = 0 + let d0 = i32x4(0, 0, 0, 0), d1 = i32x4(0, 0, 0, 0), d2 = i32x4(0, 0, 0, 0) + + // base pointer offset += 144n = (4 bytes * 12 values * 3 fields) * n + for (let i: i8 = 1; i <= 8; i++, bp += 144) { + const isbabs: i8 = (((babs ^ i) - 1) >> 7) & 1 /* xor == 0: yes; xor == 1..255: no */ + const c = v128.splat(0 - u64(isbabs)) + p0 = v128.bitselect(v128.load(bp), p0, c) + p1 = v128.bitselect(v128.load(bp, 16), p1, c) + p2 = v128.bitselect(v128.load(bp, 32), p2, c) + m0 = v128.bitselect(v128.load(bp, 48), m0, c) + m1 = v128.bitselect(v128.load(bp, 64), m1, c) + m2 = v128.bitselect(v128.load(bp, 80), m2, c) + d0 = v128.bitselect(v128.load(bp, 96), d0, c) + d1 = v128.bitselect(v128.load(bp, 112), d1, c) + d2 = v128.bitselect(v128.load(bp, 128), d2, c) + } + + // -(x, y) == (-x, y); for -x, y+x <-> y-x and negate xy2d + const n = v128.splat(0 - u64(isbneg)) + const tp = changetype(t.yplusx) + const tm = changetype(t.yminusx) + const td = changetype(t.xy2d) + + // y+x = y-x if n, else y+x + v128.store(tp, v128.bitselect(m0, p0, n)) + v128.store(tp, v128.bitselect(m1, p1, n), 16) + v128.store_lane(tp, v128.bitselect(m2, p2, n), 0, 32) + + // y-x = y+x if n, else y-x + v128.store(tm, v128.bitselect(p0, m0, n)) + v128.store(tm, v128.bitselect(p1, m1, n), 16) + v128.store_lane(tm, v128.bitselect(p2, m2, n), 0, 32) + + // xy2d = -xy2d if n, else xy2d + v128.store(td, v128.bitselect(v128.neg(d0), d0, n)) + v128.store(td, v128.bitselect(v128.neg(d1), d1, n), 16) + v128.store_lane(td, v128.bitselect(v128.neg(d2), d2, n), 0, 32) +} + +const u: FieldElement = fe() +const v: FieldElement = fe() +const v3: FieldElement = fe() +const vxx: FieldElement = fe() +const m_root_check: FieldElement = fe() +const p_root_check: FieldElement = fe() +/** + * @returns -1 if bytes fail to decode to a point, 0 if decoding is successful + */ +export function ge_frombytes_negate_vartime (h: ge_p3, s: StaticArray): i32 { + fe_frombytes(h.Y, s) + fe_1(h.Z) + fe_sq(u, h.Y) + fe_mul(v, u, ed25519_d) + fe_sub(u, u, h.Z) /* u = y^2-1 */ + fe_add(v, v, h.Z) /* v = dy^2+1 */ + + fe_sq(v3, v) + fe_mul(v3, v3, v) /* v3 = v^3 */ + fe_sq(h.X, v3) + fe_mul(h.X, h.X, v) + fe_mul(h.X, h.X, u) /* x = uv^7 */ + + fe_pow22523(h.X, h.X) /* x = (uv^7)^((q-5)/8) */ + fe_mul(h.X, h.X, v3) + fe_mul(h.X, h.X, u) /* x = uv^3(uv^7)^((q-5)/8) */ + + fe_sq(vxx, h.X) + fe_mul(vxx, vxx, v) + fe_sub(m_root_check, vxx, u) /* vx^2-u */ + if (fe_iszero(m_root_check) == 0) { + fe_add(p_root_check, vxx, u) /* vx^2+u */ + if (fe_iszero(p_root_check) == 0) { + return -1 + } + fe_mul(h.X, h.X, fe_sqrtm1) + } + + if (fe_isnegative(h.X) == (s[31] >> 7)) { /* vartime function - compiler optimization is fine */ + fe_neg(h.X, h.X) + } + fe_mul(h.T, h.X, h.Y) + + return 0 +} + +const ge_frombytes_u: FieldElement = fe() +const ge_frombytes_v: FieldElement = fe() +const ge_frombytes_vxx: FieldElement = fe() +const ge_frombytes_m_root_check: FieldElement = fe() +const ge_frombytes_p_root_check: FieldElement = fe() +const ge_frombytes_negx: FieldElement = fe() +const ge_frombytes_x_sqrtm1: FieldElement = fe() +export function ge_frombytes (h: ge_p3, s: StaticArray): i32 { + const u = ge_frombytes_u + const v = ge_frombytes_v + const vxx = ge_frombytes_vxx + const m_root_check = ge_frombytes_m_root_check + const p_root_check = ge_frombytes_p_root_check + const negx = ge_frombytes_negx + const x_sqrtm1 = ge_frombytes_x_sqrtm1 + let has_m_root: u8 + let has_p_root: u8 + + fe_frombytes(h.Y, s) + fe_1(h.Z) + fe_sq(u, h.Y) + fe_mul(v, u, ed25519_d) + fe_sub(u, u, h.Z) /* u = y^2-1 */ + fe_add(v, v, h.Z) /* v = dy^2+1 */ + + fe_mul(h.X, u, v) + fe_pow22523(h.X, h.X) + fe_mul(h.X, u, h.X) /* u((uv)^((q-5)/8)) */ + + fe_sq(vxx, h.X) + fe_mul(vxx, vxx, v) + fe_sub(m_root_check, vxx, u) /* vx^2-u */ + fe_add(p_root_check, vxx, u) /* vx^2+u */ + has_m_root = fe_iszero(m_root_check) + has_p_root = fe_iszero(p_root_check) + fe_mul(x_sqrtm1, h.X, fe_sqrtm1) /* x*sqrt(-1) */ + fe_cmov(h.X, x_sqrtm1, 1 - has_m_root) + + fe_neg(negx, h.X) + fe_cmov(h.X, negx, fe_isnegative(h.X) ^ (s[31] >> 7)) + fe_mul(h.T, h.X, h.Y) + + return i32(has_m_root | has_p_root) - 1 +} + +const ge_has_small_order_y_sqrtm1: FieldElement = fe() +const ge_has_small_order_c: FieldElement = fe() +/** return 1 if p has small order else return 0 */ +export function ge_has_small_order (p: ge_p3): i32 { + const y_sqrtm1 = ge_has_small_order_y_sqrtm1 + const c = ge_has_small_order_c + let ret: i32 = 0 + + ret |= fe_iszero(p.X) + ret |= fe_iszero(p.Y) + ret |= fe_iszero(p.Z) + fe_mul(y_sqrtm1, p.Y, fe_sqrtm1) + fe_sub(c, y_sqrtm1, p.X) + ret |= fe_iszero(c) + fe_add(c, y_sqrtm1, p.X) + ret |= fe_iszero(c) + + return ret +} + +/** + * true if \`s < p\` + */ +export function ge_is_canonical (s: StaticArray): u8 { + let c: i32 = (s[31] & 0x7f) ^ 0x7f + for (let i = 30; i > 0; i--) { + c |= s[i] ^ 0xff + } + c = (c - 1) >> 8 + const d: i32 = (0xec - s[0]) >> 8 + return u8(1 - (c & d & 1)) +} + +const ge_scalarmult_base_e: StaticArray = new StaticArray(64) +const ge_scalarmult_base_r: ge_p1p1 = new ge_p1p1() +const ge_scalarmult_base_s: ge_p2 = new ge_p2() +const ge_scalarmult_base_t: ge_precomp = new ge_precomp() +/** + * \`h = a * B\` (with precomputation) + * + * where + * + * \`a = 256⁰a[0] + 256¹a[1] + ... + 256³¹a[31]\` + * + * B is the Ed25519 base point \`(x,⅘)\` with \`x\` positive. As bytes: + * + * \`0x5866666666666666666666666666666666666666666666666666666666666666\` + * + * Preconditions: + * - \`a[31] ≤ 127\` + */ +function ge_scalarmult_base (h: ge_p3, a: StaticArray): void { + const e = ge_scalarmult_base_e + const r = ge_scalarmult_base_r + const s = ge_scalarmult_base_s + const t = ge_scalarmult_base_t + + for (let i = 0; i < 32; ++i) { + e[(i << 1) + 0] = (a[i] >> 0) & 15 + e[(i << 1) + 1] = (a[i] >> 4) & 15 + } + /* each e[i] is between 0 and 15 */ + /* e[63] is between 0 and 7 */ + + let carry: i8 = 0 + for (let i = 0; i < 63; ++i) { + e[i] += carry + carry = e[i] + 8 + carry >>= 4 + e[i] -= carry * (i8(1) << 4) + } + e[63] += carry + /* each e[i] is between -8 and 8 */ + + ge_p3_0(h) + + // base pointer offset = 4 bytes * 12 values * 3 fe * 8 ge = 1152 bytes + for (let i = 1, bp = 0; i < 64; i += 2, bp += 1152) { + ge_cmov8_base(t, base + bp, e[i]) + ge_add_precomp(r, h, t) + ge_p1p1_to_p3(h, r) + } + + ge_p3_dbl(r, h) + ge_p1p1_to_p2(s, r) + ge_p2_dbl(r, s) + ge_p1p1_to_p2(s, r) + ge_p2_dbl(r, s) + ge_p1p1_to_p2(s, r) + ge_p2_dbl(r, s) + ge_p1p1_to_p3(h, r) + + // base pointer offset = 4 bytes * 12 values * 3 fe * 8 ge = 1152 bytes + for (let i = 0, bp = 0; i < 64; i += 2, bp += 1152) { + ge_cmov8_base(t, base + bp, e[i]) + ge_add_precomp(r, h, t) + ge_p1p1_to_p3(h, r) + } + + // clear sensitive data + e.fill(0) + ge_p1p1_0(r) + ge_p2_0(s) + ge_precomp_0(t) +} + +const ge_scalarmult_base_tobytes_h: ge_p3 = new ge_p3() +/** + * @param s 32-byte output buffer for scalar * base point + * @param a 32-byte input buffer for scalar + */ +export function ge_scalarmult_base_tobytes (s: StaticArray, a: StaticArray): void { + const h = ge_scalarmult_base_tobytes_h + ge_scalarmult_base(h, a) + ge_p3_tobytes(s, h) +} + +const ge_double_scalarmult_vartime_aslide: StaticArray = new StaticArray(256) +const ge_double_scalarmult_vartime_bslide: StaticArray = new StaticArray(256) +const ge_double_scalarmult_vartime_Ai: StaticArray = StaticArray.fromArray([ + new ge_cached(), + new ge_cached(), + new ge_cached(), + new ge_cached(), + new ge_cached(), + new ge_cached(), + new ge_cached(), + new ge_cached() +]) /* A,3A,5A,7A,9A,11A,13A,15A */ +const ge_double_scalarmult_vartime_t: ge_p1p1 = new ge_p1p1() +const ge_double_scalarmult_vartime_u: ge_p3 = new ge_p3() +const ge_double_scalarmult_vartime_A2: ge_p3 = new ge_p3() +/** + * r = a * A + b * B + * where a = a[0]+256*a[1]+...+256^31 a[31]. + * and b = b[0]+256*b[1]+...+256^31 b[31]. + * B is the Ed25519 base point (x,4/5) with x positive. + * + * Only used for signatures verification. + */ +function ge_double_scalarmult_vartime (r: ge_p2, a: StaticArray, A: ge_p3, b: StaticArray): void { + const Bi = base2 + const aslide = ge_double_scalarmult_vartime_aslide + const bslide = ge_double_scalarmult_vartime_bslide + const Ai = ge_double_scalarmult_vartime_Ai /* A,3A,5A,7A,9A,11A,13A,15A */ + const t = ge_double_scalarmult_vartime_t + const u = ge_double_scalarmult_vartime_u + const A2 = ge_double_scalarmult_vartime_A2 + let i: i32 = 0 + + slide_vartime(aslide, a) + slide_vartime(bslide, b) + + ge_p3_to_cached(Ai[0], A) + + ge_p3_dbl(t, A) + ge_p1p1_to_p3(A2, t) + + ge_add_cached(t, A2, Ai[0]) + ge_p1p1_to_p3(u, t) + ge_p3_to_cached(Ai[1], u) + + ge_add_cached(t, A2, Ai[1]) + ge_p1p1_to_p3(u, t) + ge_p3_to_cached(Ai[2], u) + + ge_add_cached(t, A2, Ai[2]) + ge_p1p1_to_p3(u, t) + ge_p3_to_cached(Ai[3], u) + + ge_add_cached(t, A2, Ai[3]) + ge_p1p1_to_p3(u, t) + ge_p3_to_cached(Ai[4], u) + + ge_add_cached(t, A2, Ai[4]) + ge_p1p1_to_p3(u, t) + ge_p3_to_cached(Ai[5], u) + + ge_add_cached(t, A2, Ai[5]) + ge_p1p1_to_p3(u, t) + ge_p3_to_cached(Ai[6], u) + + ge_add_cached(t, A2, Ai[6]) + ge_p1p1_to_p3(u, t) + ge_p3_to_cached(Ai[7], u) + + ge_p2_0(r) + + for (i = 255; i >= 0; --i) { + if (aslide[i] || bslide[i]) { + break + } + } + + for (; i >= 0; --i) { + ge_p2_dbl(t, r) + + if (aslide[i] > 0) { + ge_p1p1_to_p3(u, t) + ge_add_cached(t, u, Ai[aslide[i] / 2]) + } else if (aslide[i] < 0) { + ge_p1p1_to_p3(u, t) + ge_sub_cached(t, u, Ai[(-aslide[i]) / 2]) + } + + if (bslide[i] > 0) { + ge_p1p1_to_p3(u, t) + ge_add_precomp(t, u, Bi[bslide[i] / 2]) + } else if (bslide[i] < 0) { + ge_p1p1_to_p3(u, t) + ge_sub_precomp(t, u, Bi[(-bslide[i]) / 2]) + } + + ge_p1p1_to_p2(r, t) + } +} + +const ge_double_scalarmult_vartime_p: ge_p2 = new ge_p2() +export function ge_double_scalarmult_vartime_to_p3 (r: ge_p3, a: StaticArray, A: ge_p3, b: StaticArray): void { + const p = ge_double_scalarmult_vartime_p + ge_double_scalarmult_vartime(p, a, A, b) + ge_p2_to_p3(r, p) +} + +function slide_vartime (r: StaticArray, a: StaticArray): void { + let i: i32 + let b: i32 + let k: i32 + let ribs: i32 + let cmp: i32 + + for (i = 0; i < 256; ++i) { + r[i] = 1 & (a[i >> 3] >> i8(i & 7)) + } + for (i = 0; i < 256; ++i) { + if (!r[i]) { + continue + } + for (b = 1; b <= 6 && i + b < 256; ++b) { + if (!r[i + b]) { + continue + } + ribs = i32(r[i + b]) << b + cmp = r[i] + ribs + if (cmp <= 15) { + r[i] = i8(cmp) + r[i + b] = 0 + } else { + cmp = r[i] - ribs + if (cmp < -15) { + break + } + r[i] = i8(cmp) + for (k = i + b; k < 256; ++k) { + if (!r[k]) { + r[k] = 1 + break + } + r[k] = 0 + } + } + } + } +} +` diff --git a/scripts/index.mjs b/scripts/index.mjs new file mode 100644 index 0000000..490e3a1 --- /dev/null +++ b/scripts/index.mjs @@ -0,0 +1,23 @@ +//! SPDX-FileCopyrightText: 2026 Chris Duncan +//! SPDX-License-Identifier: GPL-3.0-or-later + +/** + * Generates AssemblyScript files implementing Ed25519 with BLAKE2b as the hash + * algorithm. Specifically, it writes AssemblyScript `.ts` source files to the + * `src/assemblyscript/ed25519/` directory. + * + * The contents of the output files must be checked separately for correctness + * using the AssemblyScript type checker and then compiled to a WASM module + * using the AssemblyScript compiler. + */ + +import { writeFile } from 'node:fs/promises' +import { BLAKE2b } from './blake2b.gen.mjs' +import { FE } from './fe.gen.mjs' +import { GE } from './ge.gen.mjs' +import { P } from './p.gen.mjs' + +await writeFile('src/assembly/ed25519/blake2b.ts', BLAKE2b) +// await writeFile('src/assembly/ed25519/fe.ts', FE) +// await writeFile('src/assembly/ed25519/ge.ts', GE) +// await writeFile('src/assembly/ed25519/p.ts', P) diff --git a/scripts/p.gen.mjs b/scripts/p.gen.mjs new file mode 100644 index 0000000..d897f98 --- /dev/null +++ b/scripts/p.gen.mjs @@ -0,0 +1,262 @@ +//! SPDX-FileCopyrightText: 2026 Chris Duncan +//! SPDX-License-Identifier: GPL-3.0-or-later +/** + * Generate Ed25519 point arithmetic for WebAssembly API. Specifically, it + * outputs `p.ts`, an AssemblyScript file that must be compiled as part of a + * WASM module. + * + * The final output file should be checked separately for correctness using the + * AssemblyScript compiler and type checker. + */ + +export const P = `//! SPDX-FileCopyrightText: 2026 Chris Duncan +//! SPDX-License-Identifier: GPL-3.0-or-later + +import { FieldElement, fe, fe_0, fe_1, fe_add, fe_copy, fe_dbl, fe_invert, fe_isnegative, fe_mul, fe_neg, fe_sq, fe_sq2, fe_sq_vec, fe_sub, fe_tobytes } from './fe' + +/** + * 2d = −121665 / 60833 + * = 16295367250680780974490674513165176452449235426866156013048779062215315747161 + */ +const ed25519_d2: FieldElement = StaticArray.fromArray([ + -21827239, -5839606, -30745221, 13898782, 229458, 15978800, -12551817, -6495438, 29715968, 9444199, 0, 0 +]) + +export class ge_p2 { + X: FieldElement = fe() + Y: FieldElement = fe() + Z: FieldElement = fe() +} + +export class ge_p1p1 extends ge_p2 { + T: FieldElement = fe() + __brand: 'ge_p1p1' = 'ge_p1p1' +} + +export class ge_p3 extends ge_p2 { + T: FieldElement = fe() + __brand: 'ge_p3' = 'ge_p3' +} +export class ge_cached { + YplusX: FieldElement = fe() + YminusX: FieldElement = fe() + Z: FieldElement = fe() + T2d: FieldElement = fe() +} + +export class ge_precomp { + yplusx: FieldElement = fe() + yminusx: FieldElement = fe() + xy2d: FieldElement = fe() +} + +//@ts-expect-error +@inline +export function ge_p2_0 (h: ge_p2): void { + fe_0(h.X) + fe_1(h.Y) + fe_1(h.Z) +} + +const ge_p2_dbl_t0: FieldElement = fe() +//@ts-expect-error +@inline +export function ge_p2_dbl (r: ge_p1p1, p: ge_p2): void { + const t0 = ge_p2_dbl_t0 + fe_sq_vec(r.X, p.X, r.Z, p.Y) + fe_sq2(r.T, p.Z) + fe_add(r.Y, p.X, p.Y) + fe_sq(t0, r.Y) + fe_add(r.Y, r.Z, r.X) + fe_sub(r.Z, r.Z, r.X) + fe_sub(r.X, t0, r.Y) + fe_sub(r.T, r.T, r.Z) +} + +/** + * r = p + */ +//@ts-expect-error +@inline +export function ge_p2_to_p3 (r: ge_p3, p: ge_p2): void { + fe_copy(r.X, p.X) + fe_copy(r.Y, p.Y) + fe_copy(r.Z, p.Z) + fe_mul(r.T, p.X, p.Y) +} + +/** + * r = p + */ +//@ts-expect-error +@inline +export function ge_p1p1_to_p2 (r: ge_p2, p: ge_p1p1): void { + fe_mul(r.X, p.X, p.T) + fe_mul(r.Y, p.Y, p.Z) + fe_mul(r.Z, p.Z, p.T) +} + +//@ts-expect-error +@inline +export function ge_p1p1_to_p3 (r: ge_p3, p: ge_p1p1): void { + fe_mul(r.X, p.X, p.T) + fe_mul(r.Y, p.Y, p.Z) + fe_mul(r.Z, p.Z, p.T) + fe_mul(r.T, p.X, p.Y) +} + +//@ts-expect-error +@inline +export function ge_p1p1_0 (h: ge_p1p1): void { + ge_p2_0(h) + fe_0(h.T) +} + +//@ts-expect-error +@inline +export function ge_p3_0 (h: ge_p3): void { + ge_p2_0(h) + fe_0(h.T) +} + +const ge_p3_dbl_q: ge_p2 = new ge_p2() +/** + * r = 2 * p + */ +export function ge_p3_dbl (r: ge_p1p1, p: ge_p3): void { + const q = ge_p3_dbl_q + fe_copy(q.X, p.X) + fe_copy(q.Y, p.Y) + fe_copy(q.Z, p.Z) + ge_p2_dbl(r, q) +} + +const ge_p3_tobytes_recip: FieldElement = fe() +const ge_p3_tobytes_x: FieldElement = fe() +const ge_p3_tobytes_y: FieldElement = fe() +export function ge_p3_tobytes (s: StaticArray, h: ge_p3): void { + const recip = ge_p3_tobytes_recip + const x = ge_p3_tobytes_x + const y = ge_p3_tobytes_y + fe_invert(recip, h.Z) + fe_mul(x, h.X, recip) + fe_mul(y, h.Y, recip) + fe_tobytes(s, y) + s[31] ^= fe_isnegative(x) << 7 +} + +/** + * r = p + */ +//@ts-expect-error +@inline +export function ge_p3_to_cached (r: ge_cached, p: ge_p3): void { + fe_add(r.YplusX, p.Y, p.X) + fe_sub(r.YminusX, p.Y, p.X) + fe_copy(r.Z, p.Z) + fe_mul(r.T2d, p.T, ed25519_d2) +} + +//@ts-expect-error +@inline +export function ge_precomp_0 (h: ge_precomp): void { + fe_1(h.yplusx) + fe_1(h.yminusx) + fe_0(h.xy2d) +} + +const ge_add_cached_t0: FieldElement = fe() +/** + * r = p + q + */ +export function ge_add_cached (r: ge_p1p1, p: ge_p3, q: ge_cached): void { + const t0 = ge_add_cached_t0 + fe_add(r.X, p.Y, p.X) + fe_sub(r.Y, p.Y, p.X) + fe_mul(r.Z, r.X, q.YplusX) + fe_mul(r.Y, r.Y, q.YminusX) + fe_mul(r.T, q.T2d, p.T) + fe_mul(r.X, p.Z, q.Z) + fe_dbl(t0, r.X) + fe_sub(r.X, r.Z, r.Y) + fe_add(r.Y, r.Z, r.Y) + fe_add(r.Z, t0, r.T) + fe_sub(r.T, t0, r.T) +} + +const ge_add_precomp_t0: FieldElement = fe() +/** + * r = p + q + */ +//@ts-expect-error +@inline +export function ge_add_precomp (r: ge_p1p1, p: ge_p3, q: ge_precomp): void { + const t0 = ge_add_precomp_t0 + fe_add(r.X, p.Y, p.X) + fe_sub(r.Y, p.Y, p.X) + fe_mul(r.Z, r.X, q.yplusx) + fe_mul(r.Y, r.Y, q.yminusx) + fe_mul(r.T, q.xy2d, p.T) + fe_dbl(t0, p.Z) + fe_sub(r.X, r.Z, r.Y) + fe_add(r.Y, r.Z, r.Y) + fe_add(r.Z, t0, r.T) + fe_sub(r.T, t0, r.T) +} + +const ge_sub_p3_q_cached = new ge_cached() +const ge_sub_p3_p1p1 = new ge_p1p1() +/* r = p-q */ +//@ts-expect-error +@inline +export function ge_sub_p3 (r: ge_p3, p: ge_p3, q: ge_p3): void { + const q_cached = ge_sub_p3_q_cached + const p1p1 = ge_sub_p3_p1p1 + + fe_neg(r.X, q.X) + fe_copy(r.Y, q.Y) + fe_copy(r.Z, q.Z) + fe_neg(r.T, q.T) + + ge_p3_to_cached(q_cached, r) + ge_add_cached(p1p1, p, q_cached) + ge_p1p1_to_p3(r, p1p1) +} + +const ge_sub_cached_t0: FieldElement = fe() +/** + * r = p - q + */ +export function ge_sub_cached (r: ge_p1p1, p: ge_p3, q: ge_cached): void { + const t0 = ge_sub_cached_t0 + fe_add(r.X, p.Y, p.X) + fe_sub(r.Y, p.Y, p.X) + fe_mul(r.Z, r.X, q.YminusX) + fe_mul(r.Y, r.Y, q.YplusX) + fe_mul(r.T, q.T2d, p.T) + fe_mul(r.X, p.Z, q.Z) + fe_dbl(t0, r.X) + fe_sub(r.X, r.Z, r.Y) + fe_add(r.Y, r.Z, r.Y) + fe_sub(r.Z, t0, r.T) + fe_add(r.T, t0, r.T) +} + +const ge_sub_precomp_t0: FieldElement = fe() +/** + * r = p - q + */ +export function ge_sub_precomp (r: ge_p1p1, p: ge_p3, q: ge_precomp): void { + const t0 = ge_sub_precomp_t0 + fe_add(r.X, p.Y, p.X) + fe_sub(r.Y, p.Y, p.X) + fe_mul(r.Z, r.X, q.yminusx) + fe_mul(r.Y, r.Y, q.yplusx) + fe_mul(r.T, q.xy2d, p.T) + fe_dbl(t0, p.Z) + fe_sub(r.X, r.Z, r.Y) + fe_add(r.Y, r.Z, r.Y) + fe_sub(r.Z, t0, r.T) + fe_add(r.T, t0, r.T) +} +` -- 2.52.0