Skip to content

Instantly share code, notes, and snippets.

@abacabadabacaba

abacabadabacaba/.gitignore Secret

Last active August 3, 2021 11:01
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 1 You must be signed in to fork a gist
  • Save abacabadabacaba/cb927b5ebe6db63f00b98902503ffc76 to your computer and use it in GitHub Desktop.
Save abacabadabacaba/cb927b5ebe6db63f00b98902503ffc76 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
.gitignore
/verifier.sol
/tests.json
Raw
generate-verifier.js
"use strict";
const assert = require("assert").strict;
const {writeFileSync} = require("fs");
const {feAdd, feD, feDiv, feI, feMul, feP, feSub, geG, geMul, scL} = require("./lib.js");
const primes = [];
p: for (let p = 2n; primes.length < 80; p++) {
for (let q of primes) {
if (p % q == 0) {
continue p;
}
}
primes.push(p);
}
function binsearch(l, r, f) {
while (l < r) {
let m = (l + r) / 2n;
if (f(m)) {
r = m;
} else {
l = m + 1n;
}
}
return l;
}
const init = [];
for (let i = 0; i < 8; i++) {
const p = primes[i] << 128n;
init.push(BigInt.asUintN(64, binsearch(0n, p, v => v * v > p) - 1n));
}
const round = [];
for (let i = 0; i < 80; i++) {
let p = primes[i] << 192n;
round.push(BigInt.asUintN(64, binsearch(0n, p, v => v * v * v > p) - 1n));
}
const mask = BigInt.asUintN(64, -1n);
const mask2 = mask << 64n;
const mask4 = mask << 128n;
const mask5 = mask4 | mask;
const mask8 = mask << 192n;
const mask9 = (mask << 192n) | mask;
const maskA = mask5 << 64n;
const [maskL, maskH] =
Array.from({length: 2},
(_, b) => Array.from({length: 4},
(_, i) => Array.from({length: 256}).reduce(
(a, _, j) => ((j >> (3 + i)) & 1) == b ? a + (1n << BigInt(j)) : a, 0n
)
)
);
const messageLength = 41n;
const totalLength = 64n + messageLength;
const padding = (1n << (1023n - 8n * totalLength)) | (8n * totalLength);
const gv1 = [], gv2 = [], gv3 = [];
const inv8modL = (3n * scL + 1n) / 8n;
for (let i = 0n; i < 8n; i++) {
let {x, y} = geMul(geG, ((8n + i) * inv8modL) % scL);
gv1.push(feDiv(feAdd(y, x), 2n));
gv2.push(feDiv(feSub(y, x), 2n));
gv3.push(feMul(feMul(x, y), feD));
}
function bi2s(v) {
let vs = v.toString(16);
let p = (vs.length - 1) % 8 + 1;
v = "0x" + vs.substring(0, p);
while (p < vs.length) {
v += "_" + vs.substring(p, p += 8);
}
return v;
}
function w(template, ...args) {
let l = template.length - 1;
for (let i = 0; i < l; i++) {
let s = template[i];
if (i == 0) {
assert(s.startsWith("\n"));
s = s.substring(1);
}
res += s;
let v = args[i];
res += (typeof v == "bigint" ? bi2s : String)(v);
}
let s = template[l];
if (l == 0) {
assert(s.startsWith("\n"));
s = s.substring(1);
}
let m = /\n *$/s.exec(s);
assert(m);
res += s.substring(0, m.index + 1);
}
function wSqr(r, a, n, decl = false) {
w`
${decl ? "uint256 " : ""}${r} = mulmod(${a}, ${a}, ${feP});
`;
for (let i = 1; i < n; i++) {
w`
${r} = mulmod(${r}, ${r}, ${feP});
`;
}
}
function wBswap(v, level, indent, bytes) {
indent = " ".repeat(indent);
let [vin, pre, post] = bytes ? [`uint256(${v})`, "bytes32(", ")"] : [v, "", ""];
for (let i = 0; i < level; i++) {
if (i == 4) {
w`
${indent}${v} = ${pre}(${vin} << 128) | (${vin} >> 128)${post};
`;
} else {
w`
${indent}${v} = ${pre}((${vin} & ${maskL[i]}) << ${8 << i}) | ((${vin} & ${maskH[i]}) >> ${8 << i})${post};
`;
}
}
}
function wDbl(x, u, y, v, indent) {
indent = " ".repeat(indent);
w`
${indent}{
${indent} uint256 xx = mulmod(${x}, ${v}, ${feP});
${indent} uint256 yy = mulmod(${y}, ${u}, ${feP});
${indent} uint256 zz = mulmod(${u}, ${v}, ${feP});
${indent} uint256 xx2 = mulmod(xx, xx, ${feP});
${indent} uint256 yy2 = mulmod(yy, yy, ${feP});
${indent} uint256 xxyy = mulmod(xx, yy, ${feP});
${indent} uint256 zz2 = mulmod(zz, zz, ${feP});
${indent} ${x} = xxyy + xxyy;
${indent} ${u} = yy2 - xx2 + ${feP};
${indent} ${y} = xx2 + yy2;
${indent} ${v} = addmod(zz2 + zz2, ${2n * feP} - ${u}, ${feP});
${indent}}
`;
}
function wMain() {
w`
pragma solidity >=0.5;
library Ed25519 {
// Computes (v^(2^250-1), v^11) mod p
function pow22501(uint256 v) private pure returns (uint256 p22501, uint256 p11) {
p11 = mulmod(v, v, ${feP});
p22501 = mulmod(p11, p11, ${feP});
p22501 = mulmod(mulmod(p22501, p22501, ${feP}), v, ${feP});
p11 = mulmod(p22501, p11, ${feP});
p22501 = mulmod(mulmod(p11, p11, ${feP}), p22501, ${feP});
`;
wSqr("a", "p22501", 5, true);
w`
p22501 = mulmod(p22501, a, ${feP});
`;
wSqr("a", "p22501", 10);
w`
a = mulmod(p22501, a, ${feP});
`;
wSqr("b", "a", 20, true);
w`
a = mulmod(a, b, ${feP});
`;
wSqr("a", "a", 10);
w`
p22501 = mulmod(p22501, a, ${feP});
`;
wSqr("a", "p22501", 50);
w`
a = mulmod(p22501, a, ${feP});
`;
wSqr("b", "a", 100);
w`
a = mulmod(a, b, ${feP});
`;
wSqr("a", "a", 50);
w`
p22501 = mulmod(p22501, a, ${feP});
}
function check(bytes32 k, bytes32 r, bytes32 s, bytes32 m1, bytes9 m2) internal pure returns (bool) {
uint256 hh;
// Step 1: compute SHA-512(R, A, M)
{
uint256[5][16] memory kk = [${Array.from({length: 16}, (_, i) => `[${Array.from({length: 5}, (_, j) => `uint256(${bi2s(round[16 * j + i])})`).join(", ")}]`).join(", ")}];
uint256 w0 = (uint256(r) & ${mask9}) | ((uint256(r) & ${mask4}) >> 64) | ((uint256(r) & ${mask2}) << 64);
uint256 w1 = (uint256(k) & ${mask9}) | ((uint256(k) & ${mask4}) >> 64) | ((uint256(k) & ${mask2}) << 64);
uint256 w2 = (uint256(m1) & ${mask9}) | ((uint256(m1) & ${mask4}) >> 64) | ((uint256(m1) & ${mask2}) << 64);
uint256 w3 = (uint256(bytes32(m2)) & ${mask8}) | ((uint256(bytes32(m2)) & ${mask4}) >> 64) | ${(padding & mask9) | ((padding & mask4) >> 64n) | ((padding & mask2) << 64n)};
`;
for (let i = 0; i < 8; i++) {
w`
uint256 ${String.fromCharCode(97 + i)} = ${init[i]};
`;
}
w`
for (uint256 i = 0;; i++) {
`;
for (let i = 0; i < 16; i++) {
w`
// Round 16 * i${i ? ` + ${i}` : ""}
{
uint256 temp1;
uint256 temp2;
e &= ${mask};
{
uint256 ss = e | (e << 64);
uint256 s1 = (ss >> 14) ^ (ss >> 18) ^ (ss >> 41);
uint256 ch = (e & (f ^ g)) ^ g;
temp1 = h + s1 + ch;
}
temp1 += kk[${i}][i];
temp1 += w${(i >> 2) & 3}${(i & 3) == 3 ? "" : ` >> ${[192, 64, 128][i & 3]}`};
a &= ${mask};
{
uint256 ss = a | (a << 64);
uint256 s0 = (ss >> 28) ^ (ss >> 34) ^ (ss >> 39);
uint256 maj = (a & (b | c)) | (b & c);
temp2 = s0 + maj;
}
h = g;
g = f;
f = e;
e = d + temp1;
d = c;
c = b;
b = a;
a = temp1 + temp2;
}
`;
}
w`
if (i == 4) {
break;
}
// Message expansion
uint256 t0 = w0;
uint256 t1 = w1;
{
uint256 t2 = w2;
uint256 t3 = w3;
`;
for (let j = 0; j < 4; j++) {
let t0 = `t${j}`, t1 = `t${(j + 1) & 3}`, t2 = `t${(j + 2) & 3}`, t3 = `t${(j + 3) & 3}`;
w`
{
uint256 n1 = ${t0} & ${maskA};
n1 += ((${t2} & ${mask2}) << 128) | ((${t2} & ${mask4}) >> 64);
{
uint256 u1 = ((${t0} & ${mask2}) << 64) | ((${t0} & ${mask4}) >> 128);
uint256 uu1 = u1 | (u1 << 64);
n1 += ((uu1 << 63) ^ (uu1 << 56) ^ (u1 << 57)) & ${maskA};
}
{
uint256 v1 = ${t3} & ${mask5};
uint256 vv1 = v1 | (v1 << 64);
n1 += ((vv1 << 45) ^ (vv1 << 3) ^ (v1 << 58)) & ${maskA};
}
n1 &= ${maskA};
uint256 n2 = ${t0} & ${mask5};
n2 += ((${t2} & ${mask}) << 128) | (${t3} >> 192);
{
uint256 u2 = ((${t0} & ${mask}) << 128) | (${t1} >> 192);
uint256 uu2 = u2 | (u2 << 64);
n2 += ((uu2 >> 1) ^ (uu2 >> 8) ^ (u2 >> 7)) & ${mask5};
}
{
uint256 vv2 = n1 | (n1 >> 64);
n2 += ((vv2 >> 19) ^ (vv2 >> 61) ^ (n1 >> 70)) & ${mask5};
}
n2 &= ${mask5};
t${j} = n1 | n2;
}
`;
}
w`
w3 = t3;
w2 = t2;
}
w1 = t1;
w0 = t0;
}
`;
w`
uint256 h0 = ((a + ${init[0]}) & ${mask}) | (((b + ${init[1]}) & ${mask}) << 64) | (((c + ${init[2]}) & ${mask}) << 128) | ((d + ${init[3]}) << 192);
`;
wBswap("h0", 3, 3, false);
w`
uint256 h1 = ((e + ${init[4]}) & ${mask}) | (((f + ${init[5]}) & ${mask}) << 64) | (((g + ${init[6]}) & ${mask}) << 128) | ((h + ${init[7]}) << 192);
`;
wBswap("h1", 3, 3, false);
w`
hh = addmod(h0, mulmod(h1, ${(1n << 256n) % scL}, ${scL}), ${scL});
}
// Step 2: unpack k
`;
wBswap("k", 5, 2, true);
w`
uint256 ky = uint256(k) & ${(1n << 255n) - 1n};
uint256 kx;
{
uint256 ky2 = mulmod(ky, ky, ${feP});
uint256 u = addmod(ky2, ${feP - 1n}, ${feP});
uint256 v = mulmod(ky2, ${feD}, ${feP}) + 1;
uint256 t = mulmod(u, v, ${feP});
(kx, ) = pow22501(t);
kx = mulmod(kx, kx, ${feP});
kx = mulmod(u, mulmod(mulmod(kx, kx, ${feP}), t, ${feP}), ${feP});
t = mulmod(mulmod(kx, kx, ${feP}), v, ${feP});
if (t != u) {
if (t != ${feP} - u) {
return false;
}
kx = mulmod(kx, ${feI}, ${feP});
}
}
if ((kx & 1) != uint256(k) >> 255) {
kx = ${feP} - kx;
}
// Verify s
`;
wBswap("s", 5, 2, true);
w`
if (uint256(s) >= ${scL}) {
return false;
}
uint256 vx;
uint256 vu;
uint256 vy;
uint256 vv;
// Step 3: compute multiples of k
uint256[8][3][2] memory tables;
{
uint256 ks = ky + kx;
uint256 kd = ky + ${feP} - kx;
uint256 k2dt = mulmod(mulmod(kx, ky, ${feP}), ${feMul(2n, feD)}, ${feP});
uint256 kky = ky;
uint256 kkx = kx;
uint256 kku = 1;
uint256 kkv = 1;
`;
wDbl("kkx", "kku", "kky", "kkv", 3);
wDbl("kkx", "kku", "kky", "kkv", 3);
wDbl("kkx", "kku", "kky", "kkv", 3);
w`
uint256 cprod = 1;
uint256[8][3][2] memory tables_ = tables;
for (uint256 i = 0;; i++) {
uint256 cs;
uint256 cd;
uint256 ct;
uint256 c2z;
{
uint256 cx = mulmod(kkx, kkv, ${feP});
uint256 cy = mulmod(kky, kku, ${feP});
uint256 cz = mulmod(kku, kkv, ${feP});
ct = mulmod(kkx, kky, ${feP});
cs = cy + cx;
cd = cy - cx + ${feP};
c2z = cz + cz;
}
tables_[1][0][i] = cs;
tables_[1][1][i] = cd;
tables_[1][2][i] = mulmod(ct, ${feMul(2n, feD)}, ${feP});
tables_[0][0][i] = c2z;
tables_[0][1][i] = cprod;
cprod = mulmod(cprod, c2z, ${feP});
if (i == 7) {
break;
}
uint256 ab = mulmod(cs, ks, ${feP});
uint256 aa = mulmod(cd, kd, ${feP});
uint256 ac = mulmod(ct, k2dt, ${feP});
kkx = ab - aa + ${feP};
kku = addmod(c2z, ac, ${feP});
kky = ab + aa;
kkv = addmod(c2z, ${feP} - ac, ${feP});
}
uint256 t;
(cprod, t) = pow22501(cprod);
`;
wSqr("cprod", "cprod", 5);
w`
cprod = mulmod(cprod, t, ${feP});
for (uint256 i = 7;; i--) {
uint256 cinv = mulmod(cprod, tables_[0][1][i], ${feP});
tables_[1][0][i] = mulmod(tables_[1][0][i], cinv, ${feP});
tables_[1][1][i] = mulmod(tables_[1][1][i], cinv, ${feP});
tables_[1][2][i] = mulmod(tables_[1][2][i], cinv, ${feP});
if (i == 0) {
break;
}
cprod = mulmod(cprod, tables_[0][0][i], ${feP});
}
tables_[0] = [[${gv1.map(bi2s).join(", ")}], [${gv2.map(bi2s).join(", ")}], [${gv3.map(bi2s).join(", ")}]];
}
// Step 4: compute s*G - h*A
{
uint256 ss = uint256(s) << 3;
uint256 hhh = hh + ${8n * scL - 8n};
uint256 vvx = 0;
uint256 vvu = 1;
uint256 vvy = 1;
uint256 vvv = 1;
for (uint256 i = 252;; i--) {
uint256 bit = 8 << i;
if ((ss & bit) != 0) {
uint256 ws;
uint256 wd;
uint256 wz;
uint256 wt;
{
uint256 wx = mulmod(vvx, vvv, ${feP});
uint256 wy = mulmod(vvy, vvu, ${feP});
ws = wy + wx;
wd = wy - wx + ${feP};
wz = mulmod(vvu, vvv, ${feP});
wt = mulmod(vvx, vvy, ${feP});
}
uint256 j = (ss >> i) & 7;
ss &= ~(7 << i);
uint256[8][3][2] memory tables_ = tables;
uint256 aa = mulmod(wd, tables_[0][1][j], ${feP});
uint256 ab = mulmod(ws, tables_[0][0][j], ${feP});
uint256 ac = mulmod(wt, tables_[0][2][j], ${feP});
vvx = ab - aa + ${feP};
vvu = wz + ac;
vvy = ab + aa;
vvv = wz - ac + ${feP};
}
if ((hhh & bit) != 0) {
uint256 ws;
uint256 wd;
uint256 wz;
uint256 wt;
{
uint256 wx = mulmod(vvx, vvv, ${feP});
uint256 wy = mulmod(vvy, vvu, ${feP});
ws = wy + wx;
wd = wy - wx + ${feP};
wz = mulmod(vvu, vvv, ${feP});
wt = mulmod(vvx, vvy, ${feP});
}
uint256 j = (hhh >> i) & 7;
hhh &= ~(7 << i);
uint256[8][3][2] memory tables_ = tables;
uint256 aa = mulmod(wd, tables_[1][0][j], ${feP});
uint256 ab = mulmod(ws, tables_[1][1][j], ${feP});
uint256 ac = mulmod(wt, tables_[1][2][j], ${feP});
vvx = ab - aa + ${feP};
vvu = wz - ac + ${feP};
vvy = ab + aa;
vvv = wz + ac;
}
if (i == 0) {
uint256 ws;
uint256 wd;
uint256 wz;
uint256 wt;
{
uint256 wx = mulmod(vvx, vvv, ${feP});
uint256 wy = mulmod(vvy, vvu, ${feP});
ws = wy + wx;
wd = wy - wx + ${feP};
wz = mulmod(vvu, vvv, ${feP});
wt = mulmod(vvx, vvy, ${feP});
}
uint256 j = hhh & 7;
uint256[8][3][2] memory tables_ = tables;
uint256 aa = mulmod(wd, tables_[1][0][j], ${feP});
uint256 ab = mulmod(ws, tables_[1][1][j], ${feP});
uint256 ac = mulmod(wt, tables_[1][2][j], ${feP});
vvx = ab - aa + ${feP};
vvu = wz - ac + ${feP};
vvy = ab + aa;
vvv = wz + ac;
break;
}
`;
wDbl("vvx", "vvu", "vvy", "vvv", 4);
w`
}
vx = vvx;
vu = vvu;
vy = vvy;
vv = vvv;
}
// Step 5: compare the points
(uint256 vi, uint256 vj) = pow22501(mulmod(vu, vv, ${feP}));
`;
wSqr("vi", "vi", 5);
w`
vi = mulmod(vi, vj, ${feP});
vx = mulmod(vx, mulmod(vi, vv, ${feP}), ${feP});
vy = mulmod(vy, mulmod(vi, vu, ${feP}), ${feP});
bytes32 v = bytes32(vy | (vx << 255));
`;
wBswap("v", 5, 2, true);
w`
return v == r;
}
}
`;
}
let res = "";
wMain();
writeFileSync("verifier.sol", res);
Raw
lib.js
"use strict";
const feP = 2n**255n - 19n;
const feI = feAbs(fePow(2n, (feP - 1n) / 4n));
const feD = feDiv(-121665n, 121666n);
function feReduce(a) {
if (a < 0 || a >= feP) {
a %= feP;
}
if (a < 0) {
a += feP;
}
return a;
}
function feAdd(a, b) {
return feReduce(a + b);
}
function feSub(a, b) {
return feReduce(a - b);
}
function feMul(a, b) {
return feReduce(a * b);
}
function fePow(a, n) {
a = feReduce(a);
if (a == 0) {
return 0n;
}
if (n < 0 || n >= feP - 1n) {
n %= feP - 1n;
}
if (n < 0) {
n += feP - 1n;
}
if (n == 0) {
return 1n;
}
let r = a;
for (let i = n.toString(2).length - 2; i >= 0; i--) {
r = feMul(r, r);
if ((n & (1n << BigInt(i))) != 0) {
r = feMul(r, a);
}
}
return r;
}
function feInv(a) {
return fePow(a, feP - 2n);
}
function feDiv(a, b) {
return feMul(a, feInv(b));
}
function feNeg(a) {
a = feReduce(a);
if (a != 0) {
a = feP - a;
}
return a;
}
function feAbs(a) {
a = feReduce(a);
if ((a & 1n) != 0) {
a = feP - a;
}
return a;
}
function feSqrt(a, neg = false) {
a = feReduce(a);
let b = fePow(a, (feP + 3n) / 8n);
let t = (b * b) % feP;
if (t != a) {
if (t != feP - a) {
return null;
}
b = (b * feI) % feP;
}
b = feAbs(b);
if (neg) {
b = feNeg(b);
}
return b;
}
const geZero = {x: 0n, y: 1n};
const geG = geUnpack(feDiv(4n, 5n), false);
const geI = geUnpack(feSqrt(feDiv(feSub(feSqrt(feAdd(feD, 1n), true), 1n), feD)), false);
function geAdd({x: ax, y: ay}, {x: bx, y: by}) {
let rx = feDiv(feAdd(feMul(ax, by), feMul(bx, ay)), feAdd(1n, feMul(feMul(feMul(feMul(feD, ax), ay), bx), by)));
let ry = feDiv(feAdd(feMul(ay, by), feMul(ax, bx)), feSub(1n, feMul(feMul(feMul(feMul(feD, ax), ay), bx), by)));
return {x: rx, y: ry};
}
function geSub(a, {x: bx, y: by}) {
return geAdd(a, {x: -bx, y: by});
}
function geMul(a, n) {
if (n < 0) {
a = {x: -a.x, y: a.y};
n = -n;
}
if (n == 0) {
return geZero;
}
let r = a;
for (let i = n.toString(2).length - 2; i >= 0; i--) {
r = geAdd(r, r);
if ((n & (1n << BigInt(i))) != 0) {
r = geAdd(r, a);
}
}
return r;
}
function geNeg({x, y}) {
return {x: feNeg(x), y};
}
function geUnpack(y, xNeg) {
y = feReduce(y);
let x = feSqrt(feDiv(feSub(feMul(y, y), 1n), feAdd(feMul(feD, feMul(y, y)), 1n)));
if (x == null) {
return null;
}
if (!(x & 1n) != !xNeg) {
if (x == 0) {
return null;
}
x = feP - x;
}
return {x, y};
}
const scL = 2n**252n + 27742317777372353535851937790883648493n;
module.exports = {
feP, feI, feD, feReduce, feAdd, feSub, feMul, fePow, feInv, feDiv, feNeg, feAbs, feSqrt,
geZero, geG, geI, geAdd, geSub, geMul, geNeg, geUnpack,
scL};
Raw
test.js
"use strict";
const assert = require("assert").strict;
const {readFileSync} = require("fs");
const Web3 = require("web3");
const ganache = require("ganache-cli");
const abi = JSON.parse(readFileSync("Ed25519Test.abi"));
const code = readFileSync("Ed25519Test.bin");
const tests = JSON.parse(readFileSync("tests.json"));
(async () => {
let web3 = new Web3(ganache.provider({gasLimit: 1e9}));
let addr = (await web3.eth.personal.getAccounts())[0];
let contract = await new web3.eth.Contract(abi).deploy({data: code}).send({from: addr, gas: 1e7});
let goodMethod = null;
let invocations = [];
for (let {k, msg, sig, valid} of tests) {
let [r, s] = [sig.substring(0, 64), sig.substring(64)];
let [m1, m2] = [msg.substring(0, 64), msg.substring(64)];
let method = contract.methods.check(`0x${k}`, `0x${r}`, `0x${s}`, `0x${m1}`, `0x${m2}`);
invocations.push(method.call());
if (!goodMethod && valid) {
goodMethod = method;
}
}
for (let i = 0; i < tests.length; i++) {
if (tests[i].valid != await invocations[i]) {
console.log(`Test failed: ${tests[i].description}`);
}
}
let receipt = await goodMethod.send({from: addr, gas: 1000000});
console.log(`Gas used: ${receipt.gasUsed}`);
})();
Raw
test.sol
pragma solidity >=0.5;
import {Ed25519} from "verifier.sol";
contract Ed25519Test {
function check(bytes32 k, bytes32 r, bytes32 s, bytes32 m1, bytes9 m2) external pure returns (bool) {
return Ed25519.check(k, r, s, m1, m2);
}
}
Raw
testgen.js
"use strict";
const {Buffer} = require("buffer");
const {createHash, randomBytes} = require("crypto");
const {writeFileSync} = require("fs");
const {feP, geAdd, geG, geI, geMul, geNeg, geUnpack, geZero, scL} = require("./lib.js");
function bi2buf(v) {
let buf = Buffer.alloc(32);
for (let i = 0; i < 32; i++) {
buf[i] = Number((v >> BigInt(8 * i)) & 255n);
}
return buf;
}
function p2buf({x = 0n, y}) {
return bi2buf(y + ((x & 1n) << 255n));
}
function buf2bi(buf) {
let v = 0n;
for (let i = 0; i < buf.length; i++) {
v += BigInt(buf[i]) << BigInt(8 * i);
}
return v;
}
function rand() {
return buf2bi(randomBytes(32));
}
function randP() {
let s = (rand() % scL) * 8n;
return {p: geMul(geG, s % scL), s};
}
function randNongroupP() {
while (true) {
let s = rand() % (8n * scL);
if ((s & 7n) != 0) {
return {p: geMul(geAdd(geG, geI), s), s};
}
}
}
function invalidP() {
while (true) {
let v = rand();
if (!geUnpack(v & ((1n << 255n) - 1n), Boolean(v >> 255n))) {
return {p: {y: v}};
}
}
}
const specialPoints = [];
for (let i = 0n; i < 8n; i++) {
let {x, y} = geMul(geI, i);
let s = (i * 5n * scL) % (8n * scL);
specialPoints.push({p: {x, y}, s, canonical: true});
if (x == 0) {
specialPoints.push({p: {x: 1n, y}, s});
}
if (y < 19) {
specialPoints.push({p: {x, y: y + feP}, s});
if (x == 0) {
specialPoints.push({p: {x: 1n, y: y + feP}, s});
}
}
}
const pointGens = [
Object.assign(randP, {desc: "regular", normal: true, inSubgroup: true, canonical: true}),
Object.assign(randNongroupP, {desc: "nonstandard", normal: true, canonical: true}),
Object.assign(invalidP, {desc: "invalid", invalid: true}),
...specialPoints.map(p =>
Object.assign(() => p, {desc: p.canonical ? "small-order" : "noncanonical",
inSubgroup: (p.s & 7n) == 0, canonical: p.canonical}))];
function calcS(k, r, h) {
return (r + k * h) % scL;
}
function sStrict(k, r, h) {
return ((r + k * h) & 7n) == 0 ? calcS(k, r, h) : null;
}
function sNonStrict(k, r, h) {
return ((r + k * h) & 7n) != 0 ? calcS(k, r, h) : null;
}
function sRandom() {
return rand() % scL;
}
const sGens = [
Object.assign(sStrict, {desc: "valid strict"}),
Object.assign(sNonStrict, {desc: "valid non-strict"}),
Object.assign(sRandom, {desc: "invalid"})];
const sGensInvalid = Array(8).fill(sRandom);
function testgen(len, {checkK = false, checkR = true, checkS = true, strict = true, rejectSmallOrderK = false, rejectSmallOrderR = false} = {}) {
let tests = [];
// Encodings of k and r
for (let k of pointGens) {
for (let r of pointGens) {
if (k.normal || r.normal || (k.invalid && r.invalid)) {
for (let s of k.invalid || r.invalid ? sGensInvalid : sGens) {
if (!(k.inSubgroup && s == (r.inSubgroup ? sNonStrict : sStrict))) {
test(`${k.desc} k, ${r.desc} r, ${s.desc}`, {k, r, s}, s != sRandom &&
(k.normal || !rejectSmallOrderK) && (k.canonical || !checkK) &&
(r.normal || !rejectSmallOrderR) && (r.canonical || !checkR) &&
(s == sStrict || !strict));
}
}
}
}
}
// Encodings of s
test("s = l - 1", {k: () => ({p: geZero}), r: () => ({p: geNeg(geG)}), s: () => scL - 1n}, !rejectSmallOrderK);
test("s = l", {k: () => ({p: geZero}), r: () => ({p: geZero}), s: () => scL}, !rejectSmallOrderK && !rejectSmallOrderR && !checkS);
test("s >= l", {s: (...a) => calcS(...a) + scL}, !checkS);
test("s < 0", {s: (...a) => calcS(...a) + (1n << 256n) - scL}, false);
for (let i = 1n; i < 8n; i++) {
test("s has higher bits set", {s: (...a) => calcS(...a) + (i << 253n)}, false);
}
return tests;
function test(description, fs, valid) {
while (true) {
let {p: kp, s: ks} = (fs.k || randP)();
let msg = randomBytes(len);
let {p: rp, s: rs} = (fs.r || randP)();
let h = createHash("sha512");
h.update(rp = p2buf(rp));
h.update(kp = p2buf(kp));
h.update(msg);
let s = (fs.s || calcS)(ks, rs, buf2bi(h.digest()) % scL);
if (s != null) {
tests.push({description, k: kp.toString("hex"), msg: msg.toString("hex"), sig: rp.toString("hex") + bi2buf(s).toString("hex"), valid});
break;
}
}
}
}
writeFileSync("tests.json", JSON.stringify(testgen(41)));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment