elliptic - npm Package Compare versions

Comparing version 0.15.1 to 0.15.2

lib/elliptic/curve/base.js

@@ -6,2 +6,3 @@ var assert = require('assert');
 var getNAF = elliptic.utils.getNAF;
+var getJSF = elliptic.utils.getJSF;
 
@@ -25,8 +26,6 @@ function BaseCurve(type, conf) {
   // Temporary arrays
-  this.t1 = new Array(4);
-  this.t2 = new Array(4);
-  this.t3 = new Array(4);
-  this.t4 = new Array(4);
-  this.t5 = new Array(4);
-  this.t6 = new Array(4);
+  this._wnafT1 = new Array(4);
+  this._wnafT2 = new Array(4);
+  this._wnafT3 = new Array(4);
+  this._wnafT4 = new Array(4);
 }
@@ -46,3 +45,3 @@ module.exports = BaseCurve;
 
-  var naf = getNAF(k, 2);
+  var naf = getNAF(k, 1);
   var I = (1 << (doubles.step + 1)) - (doubles.step % 2 === 0 ? 2 : 1);
@@ -117,9 +116,11 @@ I /= 3;
 
-BaseCurve.prototype._wnafMulAdd = function _wnafMulAdd(points, coeffs, len) {
-  var wndWidth = this.t1;
-  var wnd = this.t2;
-  var naf = this.t3;
+BaseCurve.prototype._wnafMulAdd = function _wnafMulAdd(defW,
+                                                       points,
+                                                       coeffs,
+                                                       len) {
+  var wndWidth = this._wnafT1;
+  var wnd = this._wnafT2;
+  var naf = this._wnafT3;
 
   // Fill all arrays
-  var defW = 2;
   var max = 0;
@@ -131,9 +132,63 @@ for (var i = 0; i < len; i++) {
     wnd[i] = nafPoints.points;
-    naf[i] = getNAF(coeffs[i], nafPoints.wnd);
+  }
 
-    max = Math.max(naf[i].length, max);
+  // Comb small window NAFs
+  for (var i = len - 1; i >= 1; i -= 2) {
+    var a = i - 1;
+    var b = i;
+    if (wndWidth[a] !== 1 || wndWidth[b] !== 1) {
+      naf[a] = getNAF(coeffs[a], wndWidth[a]);
+      naf[b] = getNAF(coeffs[b], wndWidth[b]);
+      max = Math.max(naf[a].length, max);
+      max = Math.max(naf[b].length, max);
+      continue;
+    }
+
+    var comb = [
+      points[a], /* 1 */
+      null, /* 3 */
+      null, /* 5 */
+      points[b] /* 7 */
+    ];
+
+    // Try to avoid Projective points, if possible
+    if (points[a].y.cmp(points[b].y) === 0) {
+      comb[1] = points[a].add(points[b]);
+      comb[2] = points[a].toJ().mixedAdd(points[b].neg());
+    } else if (points[a].y.cmp(points[b].y.redNeg()) === 0) {
+      comb[1] = points[a].toJ().mixedAdd(points[b]);
+      comb[2] = points[a].add(points[b].neg());
+    } else {
+      comb[1] = points[a].toJ().mixedAdd(points[b]);
+      comb[2] = points[a].toJ().mixedAdd(points[b].neg());
+    }
+
+    var index = [
+      -3, /* -1 -1 */
+      -1, /* -1 0 */
+      -5, /* -1 1 */
+      -7, /* 0 -1 */
+      0, /* 0 0 */
+      7, /* 0 1 */
+      5, /* 1 -1 */
+      1, /* 1 0 */
+      3  /* 1 1 */
+    ];
+
+    var jsf = getJSF(coeffs[a], coeffs[b]);
+    max = Math.max(jsf[0].length, max);
+    naf[a] = new Array(max);
+    naf[b] = new Array(max);
+    for (var j = 0; j < max; j++) {
+      var ja = jsf[0][j] | 0;
+      var jb = jsf[1][j] | 0;
+
+      naf[a][j] = index[(ja + 1) * 3 + (jb + 1)];
+      naf[b][j] = 0;
+      wnd[a] = comb;
+    }
   }
 
   var acc = this.jpoint(null, null, null);
-  var tmp = this.t4;
+  var tmp = this._wnafT4;
   for (var i = max; i >= 0; i--) {
@@ -145,3 +200,3 @@ var k = 0;
       for (var j = 0; j < len; j++) {
-        tmp[j] = naf[j][i];
+        tmp[j] = naf[j][i] | 0;
         if (tmp[j] !== 0)
@@ -161,10 +216,21 @@ zero = false;
 
-    for (var j = 0; j < tmp.length; j++) {
+    for (var j = 0; j < len; j++) {
       var z = tmp[j];
-      if (z > 0)
-        acc = acc.mixedAdd(wnd[j][(z - 1) >> 1]);
+      var p;
+      if (z === 0)
+        continue;
+      else if (z > 0)
+        p = wnd[j][(z - 1) >> 1];
       else if (z < 0)
-        acc = acc.mixedAdd(wnd[j][(-z - 1) >> 1].neg());
+        p = wnd[j][(-z - 1) >> 1].neg();
+
+      if (p.type === 'affine')
+        acc = acc.mixedAdd(p);
+      else
+        acc = acc.add(p);
     }
   }
+  // Zeroify references
+  for (var i = 0; i < len; i++)
+    wnd[i] = null;
   return acc.toP();
@@ -224,3 +290,3 @@ };
   var res = [ this ];
-  var max = (1 << (wnd - 1)) - 1;
+  var max = (1 << wnd) - 1;
   var dbl = max === 1 ? null : this.dbl();
@@ -236,29 +302,3 @@ for (var i = 1; i < max; i++)
 BasePoint.prototype._getBeta = function _getBeta() {
-  if (this.curve.type !== 'short' || !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;
-    function endoMul(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;
+  return null;
 };
@@ -265,0 +305,0 @@

lib/elliptic/curve/edwards.js

@@ -324,3 +324,3 @@ var assert = require('assert');
 Point.prototype.mulAdd = function mulAdd(k1, p, k2) {
-  return this.curve._wnafMulAdd([ this, p ], [ k1, k2 ], 2);
+  return this.curve._wnafMulAdd(1, [ this, p ], [ k1, k2 ], 2);
 };
@@ -327,0 +327,0 @@

lib/elliptic/curve/short.js

@@ -22,2 +22,4 @@ var assert = require('assert');
   this.endo = this._getEndomorphism(conf);
+  this._endoWnafT1 = new Array(4);
+  this._endoWnafT2 = new Array(4);
 }
@@ -29,10 +31,28 @@ inherits(ShortCurve, Base);
   // No efficient endomorphism
-  if (!this.zeroA || !this.n || this.p.modn(3) !== 1)
+  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 = conf.beta ? new bn(conf.beta, 16).toRed(this.red) :
-      this._getEndoRoot(this.p).toRed(this.red);
-  var lambda = conf.lambda ? new bn(conf.lambda, 16) :
-      this.n && this._getEndoRoot(this.n);
+  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);
+    }
+  }
 
@@ -59,5 +79,5 @@ // Get basis vectors, used for balanced length-two representation
 
-ShortCurve.prototype._getEndoRoot = function _getEndoRoot(num) {
-  // Need to find smallest root for x^2 + x + 1 in F
-  // Lambda = (-1 +- Sqrt(-3)) / 2
+ShortCurve.prototype._getEndoRoots = function _getEndoRoots(num) {
+  // Find roots of for x^2 + x + 1 in F
+  // Root = (-1 +- Sqrt(-3)) / 2
   //
@@ -71,10 +91,5 @@ var red = num === this.p ? this.red : bn.mont(num);
 
-  // XXX: This seems to be a bit wrong... It should verify that
-  // lambda and beta are actually from one endomorphism
   var l1 = ntinv.redAdd(s).fromRed();
   var l2 = ntinv.redSub(s).fromRed();
-  if (l1.cmp(l2) < 0)
-    return l1;
-  else
-    return l2;
+  return [ l1, l2 ];
 };
@@ -217,4 +232,4 @@
 ShortCurve.prototype._endoWnafMulAdd = function _endoWnafMulAdd(points, coeffs) {
-  var npoints = this.t5;
-  var ncoeffs = this.t6;
+  var npoints = this._endoWnafT1;
+  var ncoeffs = this._endoWnafT2;
   for (var i = 0; i < points.length; i++) {
@@ -233,2 +248,3 @@ var split = this._endoSplit(coeffs[i]);
     }
+
     npoints[i * 2] = p;
@@ -239,3 +255,10 @@ npoints[i * 2 + 1] = beta;
   }
-  return this._wnafMulAdd(npoints, ncoeffs, points.length * 2);
+  var res = this._wnafMulAdd(1, npoints, ncoeffs, i * 2);
+
+  // Clean-up references to points and coefficients
+  for (var j = 0; j < i * 2; j++) {
+    npoints[j] = null;
+    ncoeffs[j] = null;
+  }
+  return res;
 };
@@ -266,2 +289,32 @@
 
+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;
+    function endoMul(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() {
@@ -341,3 +394,5 @@ if (!this.precomputed)
 
-  var c = this.y.redSub(p.y).redMul(this.x.redSub(p.x).redInvm());
+  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);
@@ -495,6 +550,8 @@ var ny = c.redMul(this.x.redSub(nx)).redISub(this.y);
 Point.prototype.mulAdd = function mulAdd(k1, p2, k2) {
+  var points = [ this, p2 ];
+  var coeffs = [ k1, k2 ];
   if (this.curve.endo)
-    return this.curve._endoWnafMulAdd([ this, p2 ], [ k1, k2 ]);
+    return this.curve._endoWnafMulAdd(points, coeffs);
   else
-    return this.curve._wnafMulAdd([ this, p2 ], [ k1, k2 ], 2);
+    return this.curve._wnafMulAdd(1, points, coeffs, 2);
 };
@@ -501,0 +558,0 @@

lib/elliptic/curves.js

@@ -413,3 +413,3 @@ var curves = exports;
       'naf': {
-        'wnd': 8,
+        'wnd': 7,
         'points': [
@@ -416,0 +416,0 @@ [

lib/elliptic/utils.js

 var assert = require('assert');
+var bn = require('bn.js');
 
@@ -60,6 +61,6 @@ var utils = exports;
 
+// Represent num in a w-NAF form
 function getNAF(num, w) {
-  // Represent k in a w-NAF form
   var naf = [];
-  var ws = 1 << w;
+  var ws = 1 << (w + 1);
   var k = num.clone();
@@ -81,3 +82,3 @@ while (k.cmpn(1) >= 0) {
     // Optimization, shift by word if possible
-    var shift = (k.cmpn(0) !== 0 && k.andln(ws - 1) === 0) ? w : 1;
+    var shift = (k.cmpn(0) !== 0 && k.andln(ws - 1) === 0) ? (w + 1) : 1;
     for (var i = 1; i < shift; i++)
@@ -91,1 +92,58 @@ naf.push(0);
 utils.getNAF = getNAF;
+
+// Represent k1, k2 in a Joint Sparse Form
+function getJSF(k1, k2) {
+  var jsf = [
+    [],
+    []
+  ];
+
+  k1 = k1.clone();
+  k2 = k2.clone();
+  var d1 = 0;
+  var d2 = 0;
+  while (k1.cmpn(-d1) > 0 || k2.cmpn(-d2) > 0) {
+
+    // First phase
+    var m14 = (k1.andln(3) + d1) & 3;
+    var m24 = (k2.andln(3) + d2) & 3;
+    if (m14 === 3)
+      m14 = -1;
+    if (m24 === 3)
+      m24 = -1;
+    var u1;
+    if ((m14 & 1) === 0) {
+      u1 = 0;
+    } else {
+      var m8 = (k1.andln(7) + d1) & 7;
+      if ((m8 === 3 || m8 === 5) && m24 === 2)
+        u1 = -m14;
+      else
+        u1 = m14;
+    }
+    jsf[0].push(u1);
+
+    var u2;
+    if ((m24 & 1) === 0) {
+      u2 = 0;
+    } else {
+      var m8 = (k2.andln(7) + d2) & 7;
+      if ((m8 === 3 || m8 === 5) && m14 === 2)
+        u2 = -m24;
+      else
+        u2 = m24;
+    }
+    jsf[1].push(u2);
+
+    // Second phase
+    if (2 * d1 === u1 + 1)
+      d1 = 1 - d1;
+    if (2 * d2 === u2 + 1)
+      d2 = 1 - d2;
+    k1.ishrn(1);
+    k2.ishrn(1);
+  }
+
+  return jsf;
+}
+utils.getJSF = getJSF;

package.json

 {
   "name": "elliptic",
-  "version": "0.15.1",
+  "version": "0.15.2",
   "description": "EC cryptography",
@@ -5,0 +5,0 @@ "main": "lib/elliptic.js",

test/curve-test.js

@@ -42,3 +42,7 @@ var assert = require('assert');
       n: 'ffffffff ffffffff ffffffff fffffffe ' +
-             'baaedce6 af48a03b bfd25e8c d0364141'
+             'baaedce6 af48a03b bfd25e8c d0364141',
+      g: [
+        '79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798',
+        '483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8'
+      ]
     });
@@ -45,0 +49,0 @@

New alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Fixed alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Improved metrics

Total package byte prevSize

137088

increased by2.76%

Lines of code

3680

increased by4.07%

No dependency changes