| 'use strict'; |
| |
| var utils = require('../utils'); |
| var BN = require('bn.js'); |
| var inherits = require('inherits'); |
| var Base = require('./base'); |
| |
| var assert = utils.assert; |
| |
| function ShortCurve(conf) { |
| Base.call(this, 'short', conf); |
| |
| this.a = new BN(conf.a, 16).toRed(this.red); |
| this.b = new BN(conf.b, 16).toRed(this.red); |
| this.tinv = this.two.redInvm(); |
| |
| this.zeroA = this.a.fromRed().cmpn(0) === 0; |
| this.threeA = this.a.fromRed().sub(this.p).cmpn(-3) === 0; |
| |
| // If the curve is endomorphic, precalculate beta and lambda |
| this.endo = this._getEndomorphism(conf); |
| this._endoWnafT1 = new Array(4); |
| this._endoWnafT2 = new Array(4); |
| } |
| inherits(ShortCurve, Base); |
| module.exports = ShortCurve; |
| |
| ShortCurve.prototype._getEndomorphism = function _getEndomorphism(conf) { |
| // No efficient endomorphism |
| if (!this.zeroA || !this.g || !this.n || this.p.modn(3) !== 1) |
| return; |
| |
| // Compute beta and lambda, that lambda * P = (beta * Px; Py) |
| var beta; |
| var lambda; |
| if (conf.beta) { |
| beta = new BN(conf.beta, 16).toRed(this.red); |
| } else { |
| var betas = this._getEndoRoots(this.p); |
| // Choose the smallest beta |
| beta = betas[0].cmp(betas[1]) < 0 ? betas[0] : betas[1]; |
| beta = beta.toRed(this.red); |
| } |
| if (conf.lambda) { |
| lambda = new BN(conf.lambda, 16); |
| } else { |
| // Choose the lambda that is matching selected beta |
| var lambdas = this._getEndoRoots(this.n); |
| if (this.g.mul(lambdas[0]).x.cmp(this.g.x.redMul(beta)) === 0) { |
| lambda = lambdas[0]; |
| } else { |
| lambda = lambdas[1]; |
| assert(this.g.mul(lambda).x.cmp(this.g.x.redMul(beta)) === 0); |
| } |
| } |
| |
| // Get basis vectors, used for balanced length-two representation |
| var basis; |
| if (conf.basis) { |
| basis = conf.basis.map(function(vec) { |
| return { |
| a: new BN(vec.a, 16), |
| b: new BN(vec.b, 16) |
| }; |
| }); |
| } else { |
| basis = this._getEndoBasis(lambda); |
| } |
| |
| return { |
| beta: beta, |
| lambda: lambda, |
| basis: basis |
| }; |
| }; |
| |
| ShortCurve.prototype._getEndoRoots = function _getEndoRoots(num) { |
| // Find roots of for x^2 + x + 1 in F |
| // Root = (-1 +- Sqrt(-3)) / 2 |
| // |
| var red = num === this.p ? this.red : BN.mont(num); |
| var tinv = new BN(2).toRed(red).redInvm(); |
| var ntinv = tinv.redNeg(); |
| |
| var s = new BN(3).toRed(red).redNeg().redSqrt().redMul(tinv); |
| |
| var l1 = ntinv.redAdd(s).fromRed(); |
| var l2 = ntinv.redSub(s).fromRed(); |
| return [ l1, l2 ]; |
| }; |
| |
| ShortCurve.prototype._getEndoBasis = function _getEndoBasis(lambda) { |
| // aprxSqrt >= sqrt(this.n) |
| var aprxSqrt = this.n.ushrn(Math.floor(this.n.bitLength() / 2)); |
| |
| // 3.74 |
| // Run EGCD, until r(L + 1) < aprxSqrt |
| var u = lambda; |
| var v = this.n.clone(); |
| var x1 = new BN(1); |
| var y1 = new BN(0); |
| var x2 = new BN(0); |
| var y2 = new BN(1); |
| |
| // NOTE: all vectors are roots of: a + b * lambda = 0 (mod n) |
| var a0; |
| var b0; |
| // First vector |
| var a1; |
| var b1; |
| // Second vector |
| var a2; |
| var b2; |
| |
| var prevR; |
| var i = 0; |
| var r; |
| var x; |
| while (u.cmpn(0) !== 0) { |
| var q = v.div(u); |
| r = v.sub(q.mul(u)); |
| x = x2.sub(q.mul(x1)); |
| var y = y2.sub(q.mul(y1)); |
| |
| if (!a1 && r.cmp(aprxSqrt) < 0) { |
| a0 = prevR.neg(); |
| b0 = x1; |
| a1 = r.neg(); |
| b1 = x; |
| } else if (a1 && ++i === 2) { |
| break; |
| } |
| prevR = r; |
| |
| v = u; |
| u = r; |
| x2 = x1; |
| x1 = x; |
| y2 = y1; |
| y1 = y; |
| } |
| a2 = r.neg(); |
| b2 = x; |
| |
| var len1 = a1.sqr().add(b1.sqr()); |
| var len2 = a2.sqr().add(b2.sqr()); |
| if (len2.cmp(len1) >= 0) { |
| a2 = a0; |
| b2 = b0; |
| } |
| |
| // Normalize signs |
| if (a1.negative) { |
| a1 = a1.neg(); |
| b1 = b1.neg(); |
| } |
| if (a2.negative) { |
| a2 = a2.neg(); |
| b2 = b2.neg(); |
| } |
| |
| return [ |
| { a: a1, b: b1 }, |
| { a: a2, b: b2 } |
| ]; |
| }; |
| |
| ShortCurve.prototype._endoSplit = function _endoSplit(k) { |
| var basis = this.endo.basis; |
| var v1 = basis[0]; |
| var v2 = basis[1]; |
| |
| var c1 = v2.b.mul(k).divRound(this.n); |
| var c2 = v1.b.neg().mul(k).divRound(this.n); |
| |
| var p1 = c1.mul(v1.a); |
| var p2 = c2.mul(v2.a); |
| var q1 = c1.mul(v1.b); |
| var q2 = c2.mul(v2.b); |
| |
| // Calculate answer |
| var k1 = k.sub(p1).sub(p2); |
| var k2 = q1.add(q2).neg(); |
| return { k1: k1, k2: k2 }; |
| }; |
| |
| ShortCurve.prototype.pointFromX = function pointFromX(x, odd) { |
| x = new BN(x, 16); |
| if (!x.red) |
| x = x.toRed(this.red); |
| |
| var y2 = x.redSqr().redMul(x).redIAdd(x.redMul(this.a)).redIAdd(this.b); |
| var y = y2.redSqrt(); |
| if (y.redSqr().redSub(y2).cmp(this.zero) !== 0) |
| throw new Error('invalid point'); |
| |
| // XXX Is there any way to tell if the number is odd without converting it |
| // to non-red form? |
| var isOdd = y.fromRed().isOdd(); |
| if (odd && !isOdd || !odd && isOdd) |
| y = y.redNeg(); |
| |
| return this.point(x, y); |
| }; |
| |
| ShortCurve.prototype.validate = function validate(point) { |
| if (point.inf) |
| return true; |
| |
| var x = point.x; |
| var y = point.y; |
| |
| var ax = this.a.redMul(x); |
| var rhs = x.redSqr().redMul(x).redIAdd(ax).redIAdd(this.b); |
| return y.redSqr().redISub(rhs).cmpn(0) === 0; |
| }; |
| |
| ShortCurve.prototype._endoWnafMulAdd = |
| function _endoWnafMulAdd(points, coeffs, jacobianResult) { |
| var npoints = this._endoWnafT1; |
| var ncoeffs = this._endoWnafT2; |
| for (var i = 0; i < points.length; i++) { |
| var split = this._endoSplit(coeffs[i]); |
| var p = points[i]; |
| var beta = p._getBeta(); |
| |
| if (split.k1.negative) { |
| split.k1.ineg(); |
| p = p.neg(true); |
| } |
| if (split.k2.negative) { |
| split.k2.ineg(); |
| beta = beta.neg(true); |
| } |
| |
| npoints[i * 2] = p; |
| npoints[i * 2 + 1] = beta; |
| ncoeffs[i * 2] = split.k1; |
| ncoeffs[i * 2 + 1] = split.k2; |
| } |
| var res = this._wnafMulAdd(1, npoints, ncoeffs, i * 2, jacobianResult); |
| |
| // Clean-up references to points and coefficients |
| for (var j = 0; j < i * 2; j++) { |
| npoints[j] = null; |
| ncoeffs[j] = null; |
| } |
| return res; |
| }; |
| |
| function Point(curve, x, y, isRed) { |
| Base.BasePoint.call(this, curve, 'affine'); |
| if (x === null && y === null) { |
| this.x = null; |
| this.y = null; |
| this.inf = true; |
| } else { |
| this.x = new BN(x, 16); |
| this.y = new BN(y, 16); |
| // Force redgomery representation when loading from JSON |
| if (isRed) { |
| this.x.forceRed(this.curve.red); |
| this.y.forceRed(this.curve.red); |
| } |
| if (!this.x.red) |
| this.x = this.x.toRed(this.curve.red); |
| if (!this.y.red) |
| this.y = this.y.toRed(this.curve.red); |
| this.inf = false; |
| } |
| } |
| inherits(Point, Base.BasePoint); |
| |
| ShortCurve.prototype.point = function point(x, y, isRed) { |
| return new Point(this, x, y, isRed); |
| }; |
| |
| ShortCurve.prototype.pointFromJSON = function pointFromJSON(obj, red) { |
| return Point.fromJSON(this, obj, red); |
| }; |
| |
| Point.prototype._getBeta = function _getBeta() { |
| if (!this.curve.endo) |
| return; |
| |
| var pre = this.precomputed; |
| if (pre && pre.beta) |
| return pre.beta; |
| |
| var beta = this.curve.point(this.x.redMul(this.curve.endo.beta), this.y); |
| if (pre) { |
| var curve = this.curve; |
| var endoMul = function(p) { |
| return curve.point(p.x.redMul(curve.endo.beta), p.y); |
| }; |
| pre.beta = beta; |
| beta.precomputed = { |
| beta: null, |
| naf: pre.naf && { |
| wnd: pre.naf.wnd, |
| points: pre.naf.points.map(endoMul) |
| }, |
| doubles: pre.doubles && { |
| step: pre.doubles.step, |
| points: pre.doubles.points.map(endoMul) |
| } |
| }; |
| } |
| return beta; |
| }; |
| |
| Point.prototype.toJSON = function toJSON() { |
| if (!this.precomputed) |
| return [ this.x, this.y ]; |
| |
| return [ this.x, this.y, this.precomputed && { |
| doubles: this.precomputed.doubles && { |
| step: this.precomputed.doubles.step, |
| points: this.precomputed.doubles.points.slice(1) |
| }, |
| naf: this.precomputed.naf && { |
| wnd: this.precomputed.naf.wnd, |
| points: this.precomputed.naf.points.slice(1) |
| } |
| } ]; |
| }; |
| |
| Point.fromJSON = function fromJSON(curve, obj, red) { |
| if (typeof obj === 'string') |
| obj = JSON.parse(obj); |
| var res = curve.point(obj[0], obj[1], red); |
| if (!obj[2]) |
| return res; |
| |
| function obj2point(obj) { |
| return curve.point(obj[0], obj[1], red); |
| } |
| |
| var pre = obj[2]; |
| res.precomputed = { |
| beta: null, |
| doubles: pre.doubles && { |
| step: pre.doubles.step, |
| points: [ res ].concat(pre.doubles.points.map(obj2point)) |
| }, |
| naf: pre.naf && { |
| wnd: pre.naf.wnd, |
| points: [ res ].concat(pre.naf.points.map(obj2point)) |
| } |
| }; |
| return res; |
| }; |
| |
| 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) + '>'; |
| }; |
| |
| Point.prototype.isInfinity = function isInfinity() { |
| return this.inf; |
| }; |
| |
| Point.prototype.add = function add(p) { |
| // O + P = P |
| if (this.inf) |
| return p; |
| |
| // P + O = P |
| if (p.inf) |
| return this; |
| |
| // P + P = 2P |
| if (this.eq(p)) |
| return this.dbl(); |
| |
| // P + (-P) = O |
| if (this.neg().eq(p)) |
| return this.curve.point(null, null); |
| |
| // P + Q = O |
| if (this.x.cmp(p.x) === 0) |
| return this.curve.point(null, null); |
| |
| var c = this.y.redSub(p.y); |
| if (c.cmpn(0) !== 0) |
| c = c.redMul(this.x.redSub(p.x).redInvm()); |
| var nx = c.redSqr().redISub(this.x).redISub(p.x); |
| var ny = c.redMul(this.x.redSub(nx)).redISub(this.y); |
| return this.curve.point(nx, ny); |
| }; |
| |
| Point.prototype.dbl = function dbl() { |
| if (this.inf) |
| return this; |
| |
| // 2P = O |
| var ys1 = this.y.redAdd(this.y); |
| if (ys1.cmpn(0) === 0) |
| return this.curve.point(null, null); |
| |
| var a = this.curve.a; |
| |
| var x2 = this.x.redSqr(); |
| var dyinv = ys1.redInvm(); |
| var c = x2.redAdd(x2).redIAdd(x2).redIAdd(a).redMul(dyinv); |
| |
| var nx = c.redSqr().redISub(this.x.redAdd(this.x)); |
| var ny = c.redMul(this.x.redSub(nx)).redISub(this.y); |
| return this.curve.point(nx, ny); |
| }; |
| |
| Point.prototype.getX = function getX() { |
| return this.x.fromRed(); |
| }; |
| |
| Point.prototype.getY = function getY() { |
| return this.y.fromRed(); |
| }; |
| |
| Point.prototype.mul = function mul(k) { |
| k = new BN(k, 16); |
| if (this.isInfinity()) |
| return this; |
| else if (this._hasDoubles(k)) |
| return this.curve._fixedNafMul(this, k); |
| else if (this.curve.endo) |
| return this.curve._endoWnafMulAdd([ this ], [ k ]); |
| else |
| return this.curve._wnafMul(this, k); |
| }; |
| |
| Point.prototype.mulAdd = function mulAdd(k1, p2, k2) { |
| var points = [ this, p2 ]; |
| var coeffs = [ k1, k2 ]; |
| if (this.curve.endo) |
| return this.curve._endoWnafMulAdd(points, coeffs); |
| else |
| return this.curve._wnafMulAdd(1, points, coeffs, 2); |
| }; |
| |
| Point.prototype.jmulAdd = function jmulAdd(k1, p2, k2) { |
| var points = [ this, p2 ]; |
| var coeffs = [ k1, k2 ]; |
| if (this.curve.endo) |
| return this.curve._endoWnafMulAdd(points, coeffs, true); |
| else |
| return this.curve._wnafMulAdd(1, points, coeffs, 2, true); |
| }; |
| |
| Point.prototype.eq = function eq(p) { |
| return this === p || |
| this.inf === p.inf && |
| (this.inf || this.x.cmp(p.x) === 0 && this.y.cmp(p.y) === 0); |
| }; |
| |
| Point.prototype.neg = function neg(_precompute) { |
| if (this.inf) |
| return this; |
| |
| var res = this.curve.point(this.x, this.y.redNeg()); |
| if (_precompute && this.precomputed) { |
| var pre = this.precomputed; |
| var negate = function(p) { |
| return p.neg(); |
| }; |
| res.precomputed = { |
| naf: pre.naf && { |
| wnd: pre.naf.wnd, |
| points: pre.naf.points.map(negate) |
| }, |
| doubles: pre.doubles && { |
| step: pre.doubles.step, |
| points: pre.doubles.points.map(negate) |
| } |
| }; |
| } |
| return res; |
| }; |
| |
| Point.prototype.toJ = function toJ() { |
| if (this.inf) |
| return this.curve.jpoint(null, null, null); |
| |
| var res = this.curve.jpoint(this.x, this.y, this.curve.one); |
| return res; |
| }; |
| |
| function JPoint(curve, x, y, z) { |
| Base.BasePoint.call(this, curve, 'jacobian'); |
| if (x === null && y === null && z === null) { |
| this.x = this.curve.one; |
| this.y = this.curve.one; |
| this.z = new BN(0); |
| } else { |
| this.x = new BN(x, 16); |
| this.y = new BN(y, 16); |
| this.z = new BN(z, 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); |
| |
| this.zOne = this.z === this.curve.one; |
| } |
| inherits(JPoint, Base.BasePoint); |
| |
| ShortCurve.prototype.jpoint = function jpoint(x, y, z) { |
| return new JPoint(this, x, y, z); |
| }; |
| |
| JPoint.prototype.toP = function toP() { |
| if (this.isInfinity()) |
| return this.curve.point(null, null); |
| |
| var zinv = this.z.redInvm(); |
| var zinv2 = zinv.redSqr(); |
| var ax = this.x.redMul(zinv2); |
| var ay = this.y.redMul(zinv2).redMul(zinv); |
| |
| return this.curve.point(ax, ay); |
| }; |
| |
| JPoint.prototype.neg = function neg() { |
| return this.curve.jpoint(this.x, this.y.redNeg(), this.z); |
| }; |
| |
| JPoint.prototype.add = function add(p) { |
| // O + P = P |
| if (this.isInfinity()) |
| return p; |
| |
| // P + O = P |
| if (p.isInfinity()) |
| return this; |
| |
| // 12M + 4S + 7A |
| var pz2 = p.z.redSqr(); |
| var z2 = this.z.redSqr(); |
| var u1 = this.x.redMul(pz2); |
| var u2 = p.x.redMul(z2); |
| var s1 = this.y.redMul(pz2.redMul(p.z)); |
| var s2 = p.y.redMul(z2.redMul(this.z)); |
| |
| var h = u1.redSub(u2); |
| var r = s1.redSub(s2); |
| if (h.cmpn(0) === 0) { |
| if (r.cmpn(0) !== 0) |
| return this.curve.jpoint(null, null, null); |
| else |
| return this.dbl(); |
| } |
| |
| var h2 = h.redSqr(); |
| var h3 = h2.redMul(h); |
| var v = u1.redMul(h2); |
| |
| var nx = r.redSqr().redIAdd(h3).redISub(v).redISub(v); |
| var ny = r.redMul(v.redISub(nx)).redISub(s1.redMul(h3)); |
| var nz = this.z.redMul(p.z).redMul(h); |
| |
| return this.curve.jpoint(nx, ny, nz); |
| }; |
| |
| JPoint.prototype.mixedAdd = function mixedAdd(p) { |
| // O + P = P |
| if (this.isInfinity()) |
| return p.toJ(); |
| |
| // P + O = P |
| if (p.isInfinity()) |
| return this; |
| |
| // 8M + 3S + 7A |
| var z2 = this.z.redSqr(); |
| var u1 = this.x; |
| var u2 = p.x.redMul(z2); |
| var s1 = this.y; |
| var s2 = p.y.redMul(z2).redMul(this.z); |
| |
| var h = u1.redSub(u2); |
| var r = s1.redSub(s2); |
| if (h.cmpn(0) === 0) { |
| if (r.cmpn(0) !== 0) |
| return this.curve.jpoint(null, null, null); |
| else |
| return this.dbl(); |
| } |
| |
| var h2 = h.redSqr(); |
| var h3 = h2.redMul(h); |
| var v = u1.redMul(h2); |
| |
| var nx = r.redSqr().redIAdd(h3).redISub(v).redISub(v); |
| var ny = r.redMul(v.redISub(nx)).redISub(s1.redMul(h3)); |
| var nz = this.z.redMul(h); |
| |
| return this.curve.jpoint(nx, ny, nz); |
| }; |
| |
| JPoint.prototype.dblp = function dblp(pow) { |
| if (pow === 0) |
| return this; |
| if (this.isInfinity()) |
| return this; |
| if (!pow) |
| return this.dbl(); |
| |
| if (this.curve.zeroA || this.curve.threeA) { |
| var r = this; |
| for (var i = 0; i < pow; i++) |
| r = r.dbl(); |
| return r; |
| } |
| |
| // 1M + 2S + 1A + N * (4S + 5M + 8A) |
| // N = 1 => 6M + 6S + 9A |
| var a = this.curve.a; |
| var tinv = this.curve.tinv; |
| |
| var jx = this.x; |
| var jy = this.y; |
| var jz = this.z; |
| var jz4 = jz.redSqr().redSqr(); |
| |
| // Reuse results |
| var jyd = jy.redAdd(jy); |
| for (var i = 0; i < pow; i++) { |
| var jx2 = jx.redSqr(); |
| var jyd2 = jyd.redSqr(); |
| var jyd4 = jyd2.redSqr(); |
| var c = jx2.redAdd(jx2).redIAdd(jx2).redIAdd(a.redMul(jz4)); |
| |
| var t1 = jx.redMul(jyd2); |
| var nx = c.redSqr().redISub(t1.redAdd(t1)); |
| var t2 = t1.redISub(nx); |
| var dny = c.redMul(t2); |
| dny = dny.redIAdd(dny).redISub(jyd4); |
| var nz = jyd.redMul(jz); |
| if (i + 1 < pow) |
| jz4 = jz4.redMul(jyd4); |
| |
| jx = nx; |
| jz = nz; |
| jyd = dny; |
| } |
| |
| return this.curve.jpoint(jx, jyd.redMul(tinv), jz); |
| }; |
| |
| JPoint.prototype.dbl = function dbl() { |
| if (this.isInfinity()) |
| return this; |
| |
| if (this.curve.zeroA) |
| return this._zeroDbl(); |
| else if (this.curve.threeA) |
| return this._threeDbl(); |
| else |
| return this._dbl(); |
| }; |
| |
| JPoint.prototype._zeroDbl = function _zeroDbl() { |
| var nx; |
| var ny; |
| var nz; |
| // Z = 1 |
| if (this.zOne) { |
| // hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-0.html |
| // #doubling-mdbl-2007-bl |
| // 1M + 5S + 14A |
| |
| // XX = X1^2 |
| var xx = this.x.redSqr(); |
| // YY = Y1^2 |
| var yy = this.y.redSqr(); |
| // YYYY = YY^2 |
| var yyyy = yy.redSqr(); |
| // S = 2 * ((X1 + YY)^2 - XX - YYYY) |
| var s = this.x.redAdd(yy).redSqr().redISub(xx).redISub(yyyy); |
| s = s.redIAdd(s); |
| // M = 3 * XX + a; a = 0 |
| var m = xx.redAdd(xx).redIAdd(xx); |
| // T = M ^ 2 - 2*S |
| var t = m.redSqr().redISub(s).redISub(s); |
| |
| // 8 * YYYY |
| var yyyy8 = yyyy.redIAdd(yyyy); |
| yyyy8 = yyyy8.redIAdd(yyyy8); |
| yyyy8 = yyyy8.redIAdd(yyyy8); |
| |
| // X3 = T |
| nx = t; |
| // Y3 = M * (S - T) - 8 * YYYY |
| ny = m.redMul(s.redISub(t)).redISub(yyyy8); |
| // Z3 = 2*Y1 |
| nz = this.y.redAdd(this.y); |
| } else { |
| // hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-0.html |
| // #doubling-dbl-2009-l |
| // 2M + 5S + 13A |
| |
| // A = X1^2 |
| var a = this.x.redSqr(); |
| // B = Y1^2 |
| var b = this.y.redSqr(); |
| // C = B^2 |
| var c = b.redSqr(); |
| // D = 2 * ((X1 + B)^2 - A - C) |
| var d = this.x.redAdd(b).redSqr().redISub(a).redISub(c); |
| d = d.redIAdd(d); |
| // E = 3 * A |
| var e = a.redAdd(a).redIAdd(a); |
| // F = E^2 |
| var f = e.redSqr(); |
| |
| // 8 * C |
| var c8 = c.redIAdd(c); |
| c8 = c8.redIAdd(c8); |
| c8 = c8.redIAdd(c8); |
| |
| // X3 = F - 2 * D |
| nx = f.redISub(d).redISub(d); |
| // Y3 = E * (D - X3) - 8 * C |
| ny = e.redMul(d.redISub(nx)).redISub(c8); |
| // Z3 = 2 * Y1 * Z1 |
| nz = this.y.redMul(this.z); |
| nz = nz.redIAdd(nz); |
| } |
| |
| return this.curve.jpoint(nx, ny, nz); |
| }; |
| |
| JPoint.prototype._threeDbl = function _threeDbl() { |
| var nx; |
| var ny; |
| var nz; |
| // Z = 1 |
| if (this.zOne) { |
| // hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html |
| // #doubling-mdbl-2007-bl |
| // 1M + 5S + 15A |
| |
| // XX = X1^2 |
| var xx = this.x.redSqr(); |
| // YY = Y1^2 |
| var yy = this.y.redSqr(); |
| // YYYY = YY^2 |
| var yyyy = yy.redSqr(); |
| // S = 2 * ((X1 + YY)^2 - XX - YYYY) |
| var s = this.x.redAdd(yy).redSqr().redISub(xx).redISub(yyyy); |
| s = s.redIAdd(s); |
| // M = 3 * XX + a |
| var m = xx.redAdd(xx).redIAdd(xx).redIAdd(this.curve.a); |
| // T = M^2 - 2 * S |
| var t = m.redSqr().redISub(s).redISub(s); |
| // X3 = T |
| nx = t; |
| // Y3 = M * (S - T) - 8 * YYYY |
| var yyyy8 = yyyy.redIAdd(yyyy); |
| yyyy8 = yyyy8.redIAdd(yyyy8); |
| yyyy8 = yyyy8.redIAdd(yyyy8); |
| ny = m.redMul(s.redISub(t)).redISub(yyyy8); |
| // Z3 = 2 * Y1 |
| nz = this.y.redAdd(this.y); |
| } else { |
| // hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html#doubling-dbl-2001-b |
| // 3M + 5S |
| |
| // delta = Z1^2 |
| var delta = this.z.redSqr(); |
| // gamma = Y1^2 |
| var gamma = this.y.redSqr(); |
| // beta = X1 * gamma |
| var beta = this.x.redMul(gamma); |
| // alpha = 3 * (X1 - delta) * (X1 + delta) |
| var alpha = this.x.redSub(delta).redMul(this.x.redAdd(delta)); |
| alpha = alpha.redAdd(alpha).redIAdd(alpha); |
| // X3 = alpha^2 - 8 * beta |
| var beta4 = beta.redIAdd(beta); |
| beta4 = beta4.redIAdd(beta4); |
| var beta8 = beta4.redAdd(beta4); |
| nx = alpha.redSqr().redISub(beta8); |
| // Z3 = (Y1 + Z1)^2 - gamma - delta |
| nz = this.y.redAdd(this.z).redSqr().redISub(gamma).redISub(delta); |
| // Y3 = alpha * (4 * beta - X3) - 8 * gamma^2 |
| var ggamma8 = gamma.redSqr(); |
| ggamma8 = ggamma8.redIAdd(ggamma8); |
| ggamma8 = ggamma8.redIAdd(ggamma8); |
| ggamma8 = ggamma8.redIAdd(ggamma8); |
| ny = alpha.redMul(beta4.redISub(nx)).redISub(ggamma8); |
| } |
| |
| return this.curve.jpoint(nx, ny, nz); |
| }; |
| |
| JPoint.prototype._dbl = function _dbl() { |
| var a = this.curve.a; |
| |
| // 4M + 6S + 10A |
| var jx = this.x; |
| var jy = this.y; |
| var jz = this.z; |
| var jz4 = jz.redSqr().redSqr(); |
| |
| var jx2 = jx.redSqr(); |
| var jy2 = jy.redSqr(); |
| |
| var c = jx2.redAdd(jx2).redIAdd(jx2).redIAdd(a.redMul(jz4)); |
| |
| var jxd4 = jx.redAdd(jx); |
| jxd4 = jxd4.redIAdd(jxd4); |
| var t1 = jxd4.redMul(jy2); |
| var nx = c.redSqr().redISub(t1.redAdd(t1)); |
| var t2 = t1.redISub(nx); |
| |
| var jyd8 = jy2.redSqr(); |
| jyd8 = jyd8.redIAdd(jyd8); |
| jyd8 = jyd8.redIAdd(jyd8); |
| jyd8 = jyd8.redIAdd(jyd8); |
| var ny = c.redMul(t2).redISub(jyd8); |
| var nz = jy.redAdd(jy).redMul(jz); |
| |
| return this.curve.jpoint(nx, ny, nz); |
| }; |
| |
| JPoint.prototype.trpl = function trpl() { |
| if (!this.curve.zeroA) |
| return this.dbl().add(this); |
| |
| // hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-0.html#tripling-tpl-2007-bl |
| // 5M + 10S + ... |
| |
| // XX = X1^2 |
| var xx = this.x.redSqr(); |
| // YY = Y1^2 |
| var yy = this.y.redSqr(); |
| // ZZ = Z1^2 |
| var zz = this.z.redSqr(); |
| // YYYY = YY^2 |
| var yyyy = yy.redSqr(); |
| // M = 3 * XX + a * ZZ2; a = 0 |
| var m = xx.redAdd(xx).redIAdd(xx); |
| // MM = M^2 |
| var mm = m.redSqr(); |
| // E = 6 * ((X1 + YY)^2 - XX - YYYY) - MM |
| var e = this.x.redAdd(yy).redSqr().redISub(xx).redISub(yyyy); |
| e = e.redIAdd(e); |
| e = e.redAdd(e).redIAdd(e); |
| e = e.redISub(mm); |
| // EE = E^2 |
| var ee = e.redSqr(); |
| // T = 16*YYYY |
| var t = yyyy.redIAdd(yyyy); |
| t = t.redIAdd(t); |
| t = t.redIAdd(t); |
| t = t.redIAdd(t); |
| // U = (M + E)^2 - MM - EE - T |
| var u = m.redIAdd(e).redSqr().redISub(mm).redISub(ee).redISub(t); |
| // X3 = 4 * (X1 * EE - 4 * YY * U) |
| var yyu4 = yy.redMul(u); |
| yyu4 = yyu4.redIAdd(yyu4); |
| yyu4 = yyu4.redIAdd(yyu4); |
| var nx = this.x.redMul(ee).redISub(yyu4); |
| nx = nx.redIAdd(nx); |
| nx = nx.redIAdd(nx); |
| // Y3 = 8 * Y1 * (U * (T - U) - E * EE) |
| var ny = this.y.redMul(u.redMul(t.redISub(u)).redISub(e.redMul(ee))); |
| ny = ny.redIAdd(ny); |
| ny = ny.redIAdd(ny); |
| ny = ny.redIAdd(ny); |
| // Z3 = (Z1 + E)^2 - ZZ - EE |
| var nz = this.z.redAdd(e).redSqr().redISub(zz).redISub(ee); |
| |
| return this.curve.jpoint(nx, ny, nz); |
| }; |
| |
| JPoint.prototype.mul = function mul(k, kbase) { |
| k = new BN(k, kbase); |
| |
| return this.curve._wnafMul(this, k); |
| }; |
| |
| JPoint.prototype.eq = function eq(p) { |
| if (p.type === 'affine') |
| return this.eq(p.toJ()); |
| |
| if (this === p) |
| return true; |
| |
| // x1 * z2^2 == x2 * z1^2 |
| var z2 = this.z.redSqr(); |
| var pz2 = p.z.redSqr(); |
| if (this.x.redMul(pz2).redISub(p.x.redMul(z2)).cmpn(0) !== 0) |
| return false; |
| |
| // y1 * z2^3 == y2 * z1^3 |
| var z3 = z2.redMul(this.z); |
| var pz3 = pz2.redMul(p.z); |
| return this.y.redMul(pz3).redISub(p.y.redMul(z3)).cmpn(0) === 0; |
| }; |
| |
| JPoint.prototype.eqXToP = function eqXToP(x) { |
| var zs = this.z.redSqr(); |
| var rx = x.toRed(this.curve.red).redMul(zs); |
| if (this.x.cmp(rx) === 0) |
| return true; |
| |
| var xc = x.clone(); |
| var t = this.curve.redN.redMul(zs); |
| 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; |
| } |
| }; |
| |
| JPoint.prototype.inspect = function inspect() { |
| if (this.isInfinity()) |
| return '<EC JPoint Infinity>'; |
| return '<EC JPoint x: ' + this.x.toString(16, 2) + |
| ' y: ' + this.y.toString(16, 2) + |
| ' z: ' + this.z.toString(16, 2) + '>'; |
| }; |
| |
| JPoint.prototype.isInfinity = function isInfinity() { |
| // XXX This code assumes that zero is always zero in red |
| return this.z.cmpn(0) === 0; |
| }; |