JSBN vs SJCL ECC (v4)

Revision 4 of this benchmark created by justmoon on

Description

Comparison of ECC performance between JSBN and SJCL

Preparation HTML

<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="https://raw.github.com/bitwiseshiftleft/sjcl/master/sjcl.js"></script>
<script src="https://raw.github.com/bitwiseshiftleft/sjcl/master/core/bn.js"></script>
<script src="https://raw.github.com/bitwiseshiftleft/sjcl/master/core/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>

Test runner

Ready to run.

Testing in
TestOps/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);
ready
SJCL
var keys = sjcl.ecc.ecdsa.generateKeys(256,0);
ready
SJCL w/ Endomorphism
var keys = sjcl.ecc.ecdsa.generateKeysEndo(256,0);
ready

Revisions

You can edit these tests or add more tests to this page by appending /edit to the URL.