Skip to content

Instantly share code, notes, and snippets.

@paulmillr paulmillr/edwards.ts
Created Apr 23, 2020

Embed
What would you like to do?
// Default Point works in default aka affine coordinates: (x, y)
// Extended Point works in extended coordinates: (x, y, z, t) ∋ (x=x/z, y=y/z, t=xy)
// https://en.wikipedia.org/wiki/Twisted_Edwards_curve#Extended_coordinates
class BaseExtendedPoint {
constructor(public x: bigint, public y: bigint, public z: bigint, public t: bigint) {}
static BASE = new ExtendedPoint(CURVE.Gx, CURVE.Gy, 1n, mod(CURVE.Gx * CURVE.Gy));
static ZERO = new ExtendedPoint(0n, 1n, 1n, 0n);
static fromAffine(p: Point): ExtendedPoint {
if (!(p instanceof Point)) {
throw new TypeError('ExtendedPoint#fromAffine: expected Point');
}
if (p.equals(Point.ZERO)) return ExtendedPoint.ZERO;
return new ExtendedPoint(p.x, p.y, 1n, mod(p.x * p.y));
}
// Takes a bunch of Jacobian Points but executes only one
// invert on all of them. invert is very slow operation,
// so this improves performance massively.
static toAffineBatch(points: ExtendedPoint[]): Point[] {
const toInv = invertBatch(points.map((p) => p.z));
return points.map((p, i) => p.toAffine(toInv[i]));
}
static normalizeZ(points: ExtendedPoint[]): ExtendedPoint[] {
return this.toAffineBatch(points).map(this.fromAffine);
}
// Compare one point to another.
equals(other: ExtendedPoint): boolean {
const a = this;
const b = other;
const [T1, T2, Z1, Z2] = [a.t, b.t, a.z, b.z];
return mod(T1 * Z2) === mod(T2 * Z1);
}
// Inverses point to one corresponding to (x, -y) in Affine coordinates.
negate(): ExtendedPoint {
return new ExtendedPoint(mod(-this.x), this.y, this.z, mod(-this.t));
}
subtract(other: ExtendedPoint): ExtendedPoint {
return this.add(other.negate());
}
// Non-constant-time multiplication. Uses double-and-add algorithm.
// It's faster, but should only be used when you don't care about
// an exposed private key e.g. sig verification.
multiplyUnsafe(scalar: bigint): ExtendedPoint {
if (typeof scalar !== 'number' && typeof scalar !== 'bigint') {
throw new TypeError('Point#multiply: expected number or bigint');
}
let n = mod(BigInt(scalar), CURVE.n);
if (n <= 0) {
throw new Error('Point#multiply: invalid scalar, expected positive integer');
}
let p = ExtendedPoint.ZERO;
let d: ExtendedPoint = this;
while (n > 0n) {
if (n & 1n) p = p.add(d);
d = d.double();
n >>= 1n;
}
return p;
}
private precomputeWindow(W: number): ExtendedPoint[] {
const windows = 256 / W + 1;
let points: ExtendedPoint[] = [];
let p: ExtendedPoint = this;
let base = p;
for (let window = 0; window < windows; window++) {
base = p;
points.push(base);
for (let i = 1; i < 2 ** (W - 1); i++) {
base = base.add(p);
points.push(base);
}
p = base.double();
}
return points;
}
private wNAF(n: bigint, affinePoint?: Point): [ExtendedPoint, ExtendedPoint] {
if (!affinePoint && this.equals(ExtendedPoint.BASE)) affinePoint = Point.BASE;
const W = (affinePoint && affinePoint._WINDOW_SIZE) || 1;
if (256 % W) {
throw new Error('Point#wNAF: Invalid precomputation window, must be power of 2');
}
let precomputes = affinePoint && pointPrecomputes.get(affinePoint);
if (!precomputes) {
precomputes = this.precomputeWindow(W);
if (affinePoint && W !== 1) {
precomputes = ExtendedPoint.normalizeZ(precomputes);
pointPrecomputes.set(affinePoint, precomputes);
}
}
let p = ExtendedPoint.ZERO;
let f = ExtendedPoint.ZERO;
const windows = 256 / W + 1;
const windowSize = 2 ** (W - 1);
const mask = BigInt(2 ** W - 1); // Create mask with W ones: 0b1111 for W=4 etc.
const maxNumber = 2 ** W;
const shiftBy = BigInt(W);
for (let window = 0; window < windows; window++) {
const offset = window * windowSize;
// Extract W bits.
let wbits = Number(n & mask);
// Shift number by W bits.
n >>= shiftBy;
// If the bits are bigger than max size, we'll split those.
// +224 => 256 - 32
if (wbits > windowSize) {
wbits -= maxNumber;
n += 1n;
}
// Check if we're onto Zero point.
// Add random point inside current window to f.
if (wbits === 0) {
f = f.add(window % 2 ? precomputes[offset].negate() : precomputes[offset]);
} else {
const cached = precomputes[offset + Math.abs(wbits) - 1];
p = p.add(wbits < 0 ? cached.negate() : cached);
}
}
return [p, f];
}
// Constant time multiplication.
// Uses wNAF method. Windowed method may be 10% faster,
// but takes 2x longer to generate and consumes 2x memory.
multiply(scalar: number | bigint, affinePoint?: Point): ExtendedPoint {
if (typeof scalar !== 'number' && typeof scalar !== 'bigint') {
throw new TypeError('Point#multiply: expected number or bigint');
}
const n = mod(BigInt(scalar), CURVE.n);
if (n <= 0) {
throw new Error('Point#multiply: invalid scalar, expected positive integer');
}
return ExtendedPoint.normalizeZ(this.wNAF(n, affinePoint))[0];
}
// Converts Extended point to default (x, y) coordinates.
// Can accept precomputed Z^-1 - for example, from invertBatch.
toAffine(invZ: bigint = invert(this.z)): Point {
const x = mod(this.x * invZ);
const y = mod(this.y * invZ);
return new Point(x, y);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.