JSBN vs SJCL ECC vs Elliptic.js

JavaScript performance comparison

Revision 14 of this test case created by Fedor Indutny

Info

Comparison of ECC performance between JSBN, SJCL, and Elliptic.JS

Preparation code

<script src="https://cdn.rawgit.com/indutny/elliptic/v0.15.2/dist/elliptic.js"></script>
<script src="http://www-cs-students.stanford.edu/~tjw/jsbn/jsbn.js"></script>
<script src="http://www-cs-students.stanford.edu/~tjw/jsbn/jsbn2.js"></script>
<script src="http://www-cs-students.stanford.edu/~tjw/jsbn/prng4.js"></script>
<script src="http://www-cs-students.stanford.edu/~tjw/jsbn/rng.js"></script>
<script src="http://www-cs-students.stanford.edu/~tjw/jsbn/ec.js"></script>
<script src="http://www-cs-students.stanford.edu/~tjw/jsbn/sec.js"></script>
<script src="http://www2.bitcoinjs.org/files/2012/sjcl/sjcl.js"></script>
<script src="http://www2.bitcoinjs.org/files/2012/sjcl/bn.js"></script>
<script src="http://www2.bitcoinjs.org/files/2012/sjcl/ecc.js"></script>
<script type="text/javascript">
function secp256k1() {
    // p = 2^256 - 2^32 - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1
    var p = fromHex("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F");
    var a = BigInteger.ZERO;
    var b = fromHex("7");
    //byte[] S = null;
    var n = fromHex("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141");
    var h = BigInteger.ONE;
    var curve = new ECCurveFp(p, a, b);
    var G = curve.decodePointHex("04"
                + "79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798"
                + "483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8");
    return new X9ECParameters(curve, G, n, h);
}

var ecparams = secp256k1()
var rng = new SecureRandom();
var n = ecparams.getN();
var n1 = n.subtract(BigInteger.ONE);
var G = ecparams.getG();

// Overwrite NIST-P256 with secp256k1 so we're on even footing
sjcl.ecc.curves.c256 = new sjcl.ecc.curve(
    sjcl.bn.pseudoMersennePrime(256, [[0,-1],[4,-1],[6,-1],[7,-1],[8,-1],[9,-1],[32,-1]]),
    "0x14551231950b75fc4402da1722fc9baee",
    0,
    7,
    "0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798",
    "0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8"
);

// Replace point addition and doubling algorithms
// NIST-P256 is a=-3, we need algorithms for a=0
sjcl.ecc.pointJac.prototype.add = function(T) {
  var S = this;
  if (S.curve !== T.curve) {
    throw("sjcl.ecc.add(): Points must be on the same curve to add them!");
  }

  if (S.isIdentity) {
    return T.toJac();
  } else if (T.isIdentity) {
    return S;
  }

  var z1z1 = S.z.square();
  var h = T.x.mul(z1z1).subM(S.x);
  var s2 = T.y.mul(S.z).mul(z1z1);

  if (h.equals(0)) {
    if (S.y.equals(T.y.mul(z1z1.mul(S.z)))) {
      // same point
      return S.doubl();
    } else {
      // inverses
      return new sjcl.ecc.pointJac(S.curve);
    }
  }

  var hh = h.square();
  var i = hh.copy().doubleM().doubleM();
  var j = h.mul(i);
  var r = s2.sub(S.y).doubleM();
  var v = S.x.mul(i);
 
  var x = r.square().subM(j).subM(v.copy().doubleM());
  var y = r.mul(v.sub(x)).subM(S.y.mul(j).doubleM());
  var z = S.z.add(h).square().subM(z1z1).subM(hh);

  return new sjcl.ecc.pointJac(this.curve,x,y,z);
};

sjcl.ecc.pointJac.prototype.doubl = function () {
  if (this.isIdentity) { return this; }

  var a = this.x.square();
  var b = this.y.square();
  var c = b.square();
  var d = this.x.add(b).square().subM(a).subM(c).doubleM();
  var e = a.mul(3);
  var f = e.square();
  var x = f.sub(d.copy().doubleM());
  var y = e.mul(d.sub(x)).subM(c.doubleM().doubleM().doubleM());
  var z = this.y.mul(this.z).doubleM();
  return new sjcl.ecc.pointJac(this.curve, x, y, z);
};


// Constants courtesy of Hal Finney
var lambda = new sjcl.bn("0x5363ad4cc05c30e0a5261c028812645a122e22ea20816678df02967c1b23bd72");
var beta = new sjcl.bn("0x7ae96a2b657c07106e64479eac3434e99cf0497512f58995c1396c28719501ee");

var a1 = new sjcl.bn("0x3086d221a7d46bcde86c90e49284eb15");
var b1 = new sjcl.bn("0xe4437ed6010e88286f547fa90abfe4c3"); // -b1
var a2 = new sjcl.bn("0x0114ca50f7a8e2f3f657c1108d9d44cfd8");
var b2 = a1;

sjcl.bn.ZERO = new sjcl.bn(0);

sjcl.bn.prototype.sign = function () {
  return this.greaterEquals(sjcl.bn.ZERO) ? 1 : -1;
};

/** -this */
sjcl.bn.prototype.neg = function () {
  return sjcl.bn.ZERO.sub(this);
};

/** |this| */
sjcl.bn.prototype.abs = function () {
  if (this.sign() === -1) {
    return this.neg();
  } else return this;
};

/** this / that. */
sjcl.bn.prototype.divRem = function (that) {
  if (typeof(that) !== "object") { that = new this._class(that); }
  var thisa = this.abs(), thata = that.abs(), quot = new this._class(0),
      ci = 0;
  if (!thisa.greaterEquals(thata)) {
    this.initWith(0);
    return this;
  } else if (thisa.equals(thata)) {
    this.initWith(sign);
    return this;
  }
 
  for (; thisa.greaterEquals(thata); ci++) {
    thata.doubleM();
  }
  for (; ci > 0; ci--) {
    quot.doubleM();
    thata.halveM();
    if (thisa.greaterEquals(thata)) {
      quot.addM(1);
      thisa.subM(that).normalize();
    }
  }
  return [quot, thisa];
};

/** this /= that (rounded to nearest int) */
sjcl.bn.prototype.divRound = function (that) {
  var dr = this.divRem(that), quot = dr[0], rem = dr[1];
 
  if (rem.doubleM().greaterEquals(that)) {
    quot.addM(1);
  }

  return quot;
};

/**
 * Returns this point multiplied with lambda.
 */

sjcl.ecc.point.prototype.multLambda = function () {
  if (this._lambdam === undefined) {
    var x = this.x.mul(beta);
    this._lambdam = new sjcl.ecc.point(this.curve, x, this.y)
  }
  return this._lambdam;
};

/**
 * Returns the additive inverse of this point.
 */

sjcl.ecc.point.prototype.inverse = function () {
  if (this._inversem === undefined) {
    var y = new this.curve.field(0).sub(this.y);
    this._inversem = new sjcl.ecc.point(this.curve, this.x, y)
  }
  return this._inversem;
};

sjcl.ecc.point.prototype.multEndo = function (k) {
  var Q1 = this;
  var Q2 = this.multLambda();
  var c1 = b2.mul(k).divRound(this.curve.r);
  var c2 = b1.mul(k).divRound(this.curve.r); // Our b1 constant is actually -b1
  var k1 = new sjcl.bn(k).subM(c1.mul(a1)).subM(c2.mul(a2)).normalize();
  var k2 = new sjcl.bn(0).addM(c1.mul(b1)).subM(c2.mul(b2));
 
  // If k1 or k2 are negative we have to multiply them with the inverse of Q1
  // or Q2 respectively.
  //
  // However, if we took this naive approach, we would need to precompute
  // multiples for the inverses of both Q1 and Q2. Instead, if k2 is negative,
  // we choose to invert the result. Then if k1 is not negative, we invert Q1.
  var invertResult = false;
  if (!k2.greaterEquals(0)) {
    invertResult = true;
    k2 = k2.abs();
   
    if (!k1.greaterEquals(0)) {
      k1 = k1.abs();
    } else {
      Q1 = Q1.inverse();
    }
  } else if (!k1.greaterEquals(0)) {
    k1 = k1.abs();
    Q1 = Q1.inverse();
  }
 
  k1.fullReduce().trim();
  k2.fullReduce().trim();
 
  var P = Q1.mult2(k1, k2, Q2);
 
  if (invertResult) {
    P = P.inverse();
  }
 
  return P;
};

sjcl.ecc.ecdsa.generateKeysEndo = function (curve, paranoia) {
  if (curve === undefined) {
    curve = 256;
  }
  if (typeof curve === "number") {
    curve = sjcl.ecc.curves['c'+curve];
    if (curve === undefined) {
      throw new sjcl.exception.invalid("no such curve");
    }
  }
  var sec = sjcl.bn.random(curve.r, paranoia), pub = curve.G.multEndo(sec);
  return { pub: new sjcl.ecc.ecdsa.publicKey(curve, pub),
           sec: new sjcl.ecc.ecdsa.secretKey(curve, sec) };
};

sjcl.ecc.curves.c256.G.multiples();
sjcl.ecc.curves.c256.G.inverse().multiples();
sjcl.ecc.curves.c256.G.multLambda().multiples();
</script>
<script>
Benchmark.prototype.setup = function() {
    var ellipticEcdsa = new ellipticjs.ec('secp256k1');
};
</script>

Preparation code output

Test runner

Warning! For accurate results, please disable Firebug before running the tests. (Why?)

Java applet disabled.

Testing in unknown unknown
Test Ops/sec
JSBN
var r = new BigInteger(n.bitLength(), rng);

var privateKey = r.mod(n1).add(BigInteger.ONE);

// Generate public key
var publicPoint = G.multiply(privateKey);
pending…
SJCL
var keys = sjcl.ecc.ecdsa.generateKeys(256,0);
pending…
SJCL w/ Endomorphism
var keys = sjcl.ecc.ecdsa.generateKeysEndo(256,0);
pending…
Elliptic.js
var keys = ellipticEcdsa.genKeyPair().getPublic();
pending…

Compare results of other browsers

Revisions

You can edit these tests or add even more tests to this page by appending /edit to the URL. Here’s a list of current revisions for this page:

0 comments

Add a comment