| 'use strict'; |
| |
| var utils = require('../utils'); |
| var BN = require('bn.js'); |
| var inherits = require('inherits'); |
| var Base = require('./base'); |
| |
| var assert = utils.assert; |
| |
| function EdwardsCurve(conf) { |
| // NOTE: Important as we are creating point in Base.call() |
| this.twisted = (conf.a | 0) !== 1; |
| this.mOneA = this.twisted && (conf.a | 0) === -1; |
| this.extended = this.mOneA; |
| |
| Base.call(this, 'edwards', conf); |
| |
| this.a = new BN(conf.a, 16).umod(this.red.m); |
| this.a = this.a.toRed(this.red); |
| this.c = new BN(conf.c, 16).toRed(this.red); |
| this.c2 = this.c.redSqr(); |
| this.d = new BN(conf.d, 16).toRed(this.red); |
| this.dd = this.d.redAdd(this.d); |
| |
| assert(!this.twisted || this.c.fromRed().cmpn(1) === 0); |
| this.oneC = (conf.c | 0) === 1; |
| } |
| inherits(EdwardsCurve, Base); |
| module.exports = EdwardsCurve; |
| |
| EdwardsCurve.prototype._mulA = function _mulA(num) { |
| if (this.mOneA) |
| return num.redNeg(); |
| else |
| return this.a.redMul(num); |
| }; |
| |
| EdwardsCurve.prototype._mulC = function _mulC(num) { |
| if (this.oneC) |
| return num; |
| else |
| return this.c.redMul(num); |
| }; |
| |
| // Just for compatibility with Short curve |
| EdwardsCurve.prototype.jpoint = function jpoint(x, y, z, t) { |
| return this.point(x, y, z, t); |
| }; |
| |
| EdwardsCurve.prototype.pointFromX = function pointFromX(x, odd) { |
| x = new BN(x, 16); |
| if (!x.red) |
| x = x.toRed(this.red); |
| |
| var x2 = x.redSqr(); |
| var rhs = this.c2.redSub(this.a.redMul(x2)); |
| var lhs = this.one.redSub(this.c2.redMul(this.d).redMul(x2)); |
| |
| var y2 = rhs.redMul(lhs.redInvm()); |
| var y = y2.redSqrt(); |
| if (y.redSqr().redSub(y2).cmp(this.zero) !== 0) |
| throw new Error('invalid point'); |
| |
| var isOdd = y.fromRed().isOdd(); |
| if (odd && !isOdd || !odd && isOdd) |
| y = y.redNeg(); |
| |
| return this.point(x, y); |
| }; |
| |
| EdwardsCurve.prototype.pointFromY = function pointFromY(y, odd) { |
| y = new BN(y, 16); |
| if (!y.red) |
| y = y.toRed(this.red); |
| |
| // x^2 = (y^2 - c^2) / (c^2 d y^2 - a) |
| var y2 = y.redSqr(); |
| var lhs = y2.redSub(this.c2); |
| var rhs = y2.redMul(this.d).redMul(this.c2).redSub(this.a); |
| var x2 = lhs.redMul(rhs.redInvm()); |
| |
| if (x2.cmp(this.zero) === 0) { |
| if (odd) |
| throw new Error('invalid point'); |
| else |
| return this.point(this.zero, y); |
| } |
| |
| var x = x2.redSqrt(); |
| if (x.redSqr().redSub(x2).cmp(this.zero) !== 0) |
| throw new Error('invalid point'); |
| |
| if (x.fromRed().isOdd() !== odd) |
| x = x.redNeg(); |
| |
| return this.point(x, y); |
| }; |
| |
| EdwardsCurve.prototype.validate = function validate(point) { |
| if (point.isInfinity()) |
| return true; |
| |
| // Curve: A * X^2 + Y^2 = C^2 * (1 + D * X^2 * Y^2) |
| point.normalize(); |
| |
| var x2 = point.x.redSqr(); |
| var y2 = point.y.redSqr(); |
| var lhs = x2.redMul(this.a).redAdd(y2); |
| var rhs = this.c2.redMul(this.one.redAdd(this.d.redMul(x2).redMul(y2))); |
| |
| return lhs.cmp(rhs) === 0; |
| }; |
| |
| function Point(curve, x, y, z, t) { |
| Base.BasePoint.call(this, curve, 'projective'); |
| if (x === null && y === null && z === null) { |
| this.x = this.curve.zero; |
| this.y = this.curve.one; |
| this.z = this.curve.one; |
| this.t = this.curve.zero; |
| this.zOne = true; |
| } else { |
| this.x = new BN(x, 16); |
| this.y = new BN(y, 16); |
| this.z = z ? new BN(z, 16) : this.curve.one; |
| this.t = t && new BN(t, 16); |
| if (!this.x.red) |
| this.x = this.x.toRed(this.curve.red); |
| if (!this.y.red) |
| this.y = this.y.toRed(this.curve.red); |
| if (!this.z.red) |
| this.z = this.z.toRed(this.curve.red); |
| if (this.t && !this.t.red) |
| this.t = this.t.toRed(this.curve.red); |
| this.zOne = this.z === this.curve.one; |
| |
| // Use extended coordinates |
| if (this.curve.extended && !this.t) { |
| this.t = this.x.redMul(this.y); |
| if (!this.zOne) |
| this.t = this.t.redMul(this.z.redInvm()); |
| } |
| } |
| } |
| inherits(Point, Base.BasePoint); |
| |
| EdwardsCurve.prototype.pointFromJSON = function pointFromJSON(obj) { |
| return Point.fromJSON(this, obj); |
| }; |
| |
| EdwardsCurve.prototype.point = function point(x, y, z, t) { |
| return new Point(this, x, y, z, t); |
| }; |
| |
| Point.fromJSON = function fromJSON(curve, obj) { |
| return new Point(curve, obj[0], obj[1], obj[2]); |
| }; |
| |
| Point.prototype.inspect = function inspect() { |
| if (this.isInfinity()) |
| return '<EC Point Infinity>'; |
| return '<EC Point x: ' + this.x.fromRed().toString(16, 2) + |
| ' y: ' + this.y.fromRed().toString(16, 2) + |
| ' z: ' + this.z.fromRed().toString(16, 2) + '>'; |
| }; |
| |
| Point.prototype.isInfinity = function isInfinity() { |
| // XXX This code assumes that zero is always zero in red |
| return this.x.cmpn(0) === 0 && |
| (this.y.cmp(this.z) === 0 || |
| (this.zOne && this.y.cmp(this.curve.c) === 0)); |
| }; |
| |
| Point.prototype._extDbl = function _extDbl() { |
| // hyperelliptic.org/EFD/g1p/auto-twisted-extended-1.html |
| // #doubling-dbl-2008-hwcd |
| // 4M + 4S |
| |
| // A = X1^2 |
| var a = this.x.redSqr(); |
| // B = Y1^2 |
| var b = this.y.redSqr(); |
| // C = 2 * Z1^2 |
| var c = this.z.redSqr(); |
| c = c.redIAdd(c); |
| // D = a * A |
| var d = this.curve._mulA(a); |
| // E = (X1 + Y1)^2 - A - B |
| var e = this.x.redAdd(this.y).redSqr().redISub(a).redISub(b); |
| // G = D + B |
| var g = d.redAdd(b); |
| // F = G - C |
| var f = g.redSub(c); |
| // H = D - B |
| var h = d.redSub(b); |
| // X3 = E * F |
| var nx = e.redMul(f); |
| // Y3 = G * H |
| var ny = g.redMul(h); |
| // T3 = E * H |
| var nt = e.redMul(h); |
| // Z3 = F * G |
| var nz = f.redMul(g); |
| return this.curve.point(nx, ny, nz, nt); |
| }; |
| |
| Point.prototype._projDbl = function _projDbl() { |
| // hyperelliptic.org/EFD/g1p/auto-twisted-projective.html |
| // #doubling-dbl-2008-bbjlp |
| // #doubling-dbl-2007-bl |
| // and others |
| // Generally 3M + 4S or 2M + 4S |
| |
| // B = (X1 + Y1)^2 |
| var b = this.x.redAdd(this.y).redSqr(); |
| // C = X1^2 |
| var c = this.x.redSqr(); |
| // D = Y1^2 |
| var d = this.y.redSqr(); |
| |
| var nx; |
| var ny; |
| var nz; |
| if (this.curve.twisted) { |
| // E = a * C |
| var e = this.curve._mulA(c); |
| // F = E + D |
| var f = e.redAdd(d); |
| if (this.zOne) { |
| // X3 = (B - C - D) * (F - 2) |
| nx = b.redSub(c).redSub(d).redMul(f.redSub(this.curve.two)); |
| // Y3 = F * (E - D) |
| ny = f.redMul(e.redSub(d)); |
| // Z3 = F^2 - 2 * F |
| nz = f.redSqr().redSub(f).redSub(f); |
| } else { |
| // H = Z1^2 |
| var h = this.z.redSqr(); |
| // J = F - 2 * H |
| var j = f.redSub(h).redISub(h); |
| // X3 = (B-C-D)*J |
| nx = b.redSub(c).redISub(d).redMul(j); |
| // Y3 = F * (E - D) |
| ny = f.redMul(e.redSub(d)); |
| // Z3 = F * J |
| nz = f.redMul(j); |
| } |
| } else { |
| // E = C + D |
| var e = c.redAdd(d); |
| // H = (c * Z1)^2 |
| var h = this.curve._mulC(this.z).redSqr(); |
| // J = E - 2 * H |
| var j = e.redSub(h).redSub(h); |
| // X3 = c * (B - E) * J |
| nx = this.curve._mulC(b.redISub(e)).redMul(j); |
| // Y3 = c * E * (C - D) |
| ny = this.curve._mulC(e).redMul(c.redISub(d)); |
| // Z3 = E * J |
| nz = e.redMul(j); |
| } |
| return this.curve.point(nx, ny, nz); |
| }; |
| |
| Point.prototype.dbl = function dbl() { |
| if (this.isInfinity()) |
| return this; |
| |
| // Double in extended coordinates |
| if (this.curve.extended) |
| return this._extDbl(); |
| else |
| return this._projDbl(); |
| }; |
| |
| Point.prototype._extAdd = function _extAdd(p) { |
| // hyperelliptic.org/EFD/g1p/auto-twisted-extended-1.html |
| // #addition-add-2008-hwcd-3 |
| // 8M |
| |
| // A = (Y1 - X1) * (Y2 - X2) |
| var a = this.y.redSub(this.x).redMul(p.y.redSub(p.x)); |
| // B = (Y1 + X1) * (Y2 + X2) |
| var b = this.y.redAdd(this.x).redMul(p.y.redAdd(p.x)); |
| // C = T1 * k * T2 |
| var c = this.t.redMul(this.curve.dd).redMul(p.t); |
| // D = Z1 * 2 * Z2 |
| var d = this.z.redMul(p.z.redAdd(p.z)); |
| // E = B - A |
| var e = b.redSub(a); |
| // F = D - C |
| var f = d.redSub(c); |
| // G = D + C |
| var g = d.redAdd(c); |
| // H = B + A |
| var h = b.redAdd(a); |
| // X3 = E * F |
| var nx = e.redMul(f); |
| // Y3 = G * H |
| var ny = g.redMul(h); |
| // T3 = E * H |
| var nt = e.redMul(h); |
| // Z3 = F * G |
| var nz = f.redMul(g); |
| return this.curve.point(nx, ny, nz, nt); |
| }; |
| |
| Point.prototype._projAdd = function _projAdd(p) { |
| // hyperelliptic.org/EFD/g1p/auto-twisted-projective.html |
| // #addition-add-2008-bbjlp |
| // #addition-add-2007-bl |
| // 10M + 1S |
| |
| // A = Z1 * Z2 |
| var a = this.z.redMul(p.z); |
| // B = A^2 |
| var b = a.redSqr(); |
| // C = X1 * X2 |
| var c = this.x.redMul(p.x); |
| // D = Y1 * Y2 |
| var d = this.y.redMul(p.y); |
| // E = d * C * D |
| var e = this.curve.d.redMul(c).redMul(d); |
| // F = B - E |
| var f = b.redSub(e); |
| // G = B + E |
| var g = b.redAdd(e); |
| // X3 = A * F * ((X1 + Y1) * (X2 + Y2) - C - D) |
| var tmp = this.x.redAdd(this.y).redMul(p.x.redAdd(p.y)).redISub(c).redISub(d); |
| var nx = a.redMul(f).redMul(tmp); |
| var ny; |
| var nz; |
| if (this.curve.twisted) { |
| // Y3 = A * G * (D - a * C) |
| ny = a.redMul(g).redMul(d.redSub(this.curve._mulA(c))); |
| // Z3 = F * G |
| nz = f.redMul(g); |
| } else { |
| // Y3 = A * G * (D - C) |
| ny = a.redMul(g).redMul(d.redSub(c)); |
| // Z3 = c * F * G |
| nz = this.curve._mulC(f).redMul(g); |
| } |
| return this.curve.point(nx, ny, nz); |
| }; |
| |
| Point.prototype.add = function add(p) { |
| if (this.isInfinity()) |
| return p; |
| if (p.isInfinity()) |
| return this; |
| |
| if (this.curve.extended) |
| return this._extAdd(p); |
| else |
| return this._projAdd(p); |
| }; |
| |
| Point.prototype.mul = function mul(k) { |
| if (this._hasDoubles(k)) |
| return this.curve._fixedNafMul(this, k); |
| else |
| return this.curve._wnafMul(this, k); |
| }; |
| |
| Point.prototype.mulAdd = function mulAdd(k1, p, k2) { |
| return this.curve._wnafMulAdd(1, [ this, p ], [ k1, k2 ], 2, false); |
| }; |
| |
| Point.prototype.jmulAdd = function jmulAdd(k1, p, k2) { |
| return this.curve._wnafMulAdd(1, [ this, p ], [ k1, k2 ], 2, true); |
| }; |
| |
| Point.prototype.normalize = function normalize() { |
| if (this.zOne) |
| return this; |
| |
| // Normalize coordinates |
| var zi = this.z.redInvm(); |
| this.x = this.x.redMul(zi); |
| this.y = this.y.redMul(zi); |
| if (this.t) |
| this.t = this.t.redMul(zi); |
| this.z = this.curve.one; |
| this.zOne = true; |
| return this; |
| }; |
| |
| Point.prototype.neg = function neg() { |
| return this.curve.point(this.x.redNeg(), |
| this.y, |
| this.z, |
| this.t && this.t.redNeg()); |
| }; |
| |
| Point.prototype.getX = function getX() { |
| this.normalize(); |
| return this.x.fromRed(); |
| }; |
| |
| Point.prototype.getY = function getY() { |
| this.normalize(); |
| return this.y.fromRed(); |
| }; |
| |
| Point.prototype.eq = function eq(other) { |
| return this === other || |
| this.getX().cmp(other.getX()) === 0 && |
| this.getY().cmp(other.getY()) === 0; |
| }; |
| |
| Point.prototype.eqXToP = function eqXToP(x) { |
| var rx = x.toRed(this.curve.red).redMul(this.z); |
| if (this.x.cmp(rx) === 0) |
| return true; |
| |
| var xc = x.clone(); |
| var t = this.curve.redN.redMul(this.z); |
| for (;;) { |
| xc.iadd(this.curve.n); |
| if (xc.cmp(this.curve.p) >= 0) |
| return false; |
| |
| rx.redIAdd(t); |
| if (this.x.cmp(rx) === 0) |
| return true; |
| } |
| }; |
| |
| // Compatibility with BaseCurve |
| Point.prototype.toP = Point.prototype.normalize; |
| Point.prototype.mixedAdd = Point.prototype.add; |