1 // Basic Javascript Elliptic Curve implementation
2 // Ported loosely from BouncyCastle's Java EC code
3 // Only Fp curves implemented for now
5 // Requires jsbn.js and jsbn2.js
6 var BigInteger = require('jsbn').BigInteger
7 var Barrett = BigInteger.prototype.Barrett
13 function ECFieldElementFp(q,x) {
15 // TODO if(x.compareTo(q) >= 0) error
19 function feFpEquals(other) {
20 if(other == this) return true;
21 return (this.q.equals(other.q) && this.x.equals(other.x));
24 function feFpToBigInteger() {
28 function feFpNegate() {
29 return new ECFieldElementFp(this.q, this.x.negate().mod(this.q));
33 return new ECFieldElementFp(this.q, this.x.add(b.toBigInteger()).mod(this.q));
36 function feFpSubtract(b) {
37 return new ECFieldElementFp(this.q, this.x.subtract(b.toBigInteger()).mod(this.q));
40 function feFpMultiply(b) {
41 return new ECFieldElementFp(this.q, this.x.multiply(b.toBigInteger()).mod(this.q));
44 function feFpSquare() {
45 return new ECFieldElementFp(this.q, this.x.square().mod(this.q));
48 function feFpDivide(b) {
49 return new ECFieldElementFp(this.q, this.x.multiply(b.toBigInteger().modInverse(this.q)).mod(this.q));
52 ECFieldElementFp.prototype.equals = feFpEquals;
53 ECFieldElementFp.prototype.toBigInteger = feFpToBigInteger;
54 ECFieldElementFp.prototype.negate = feFpNegate;
55 ECFieldElementFp.prototype.add = feFpAdd;
56 ECFieldElementFp.prototype.subtract = feFpSubtract;
57 ECFieldElementFp.prototype.multiply = feFpMultiply;
58 ECFieldElementFp.prototype.square = feFpSquare;
59 ECFieldElementFp.prototype.divide = feFpDivide;
65 function ECPointFp(curve,x,y,z) {
69 // Projective coordinates: either zinv == null or z * zinv == 1
70 // z and zinv are just BigIntegers, not fieldElements
72 this.z = BigInteger.ONE;
78 //TODO: compression flag
81 function pointFpGetX() {
82 if(this.zinv == null) {
83 this.zinv = this.z.modInverse(this.curve.q);
85 var r = this.x.toBigInteger().multiply(this.zinv);
87 return this.curve.fromBigInteger(r);
90 function pointFpGetY() {
91 if(this.zinv == null) {
92 this.zinv = this.z.modInverse(this.curve.q);
94 var r = this.y.toBigInteger().multiply(this.zinv);
96 return this.curve.fromBigInteger(r);
99 function pointFpEquals(other) {
100 if(other == this) return true;
101 if(this.isInfinity()) return other.isInfinity();
102 if(other.isInfinity()) return this.isInfinity();
104 // u = Y2 * Z1 - Y1 * Z2
105 u = other.y.toBigInteger().multiply(this.z).subtract(this.y.toBigInteger().multiply(other.z)).mod(this.curve.q);
106 if(!u.equals(BigInteger.ZERO)) return false;
107 // v = X2 * Z1 - X1 * Z2
108 v = other.x.toBigInteger().multiply(this.z).subtract(this.x.toBigInteger().multiply(other.z)).mod(this.curve.q);
109 return v.equals(BigInteger.ZERO);
112 function pointFpIsInfinity() {
113 if((this.x == null) && (this.y == null)) return true;
114 return this.z.equals(BigInteger.ZERO) && !this.y.toBigInteger().equals(BigInteger.ZERO);
117 function pointFpNegate() {
118 return new ECPointFp(this.curve, this.x, this.y.negate(), this.z);
121 function pointFpAdd(b) {
122 if(this.isInfinity()) return b;
123 if(b.isInfinity()) return this;
125 // u = Y2 * Z1 - Y1 * Z2
126 var u = b.y.toBigInteger().multiply(this.z).subtract(this.y.toBigInteger().multiply(b.z)).mod(this.curve.q);
127 // v = X2 * Z1 - X1 * Z2
128 var v = b.x.toBigInteger().multiply(this.z).subtract(this.x.toBigInteger().multiply(b.z)).mod(this.curve.q);
130 if(BigInteger.ZERO.equals(v)) {
131 if(BigInteger.ZERO.equals(u)) {
132 return this.twice(); // this == b, so double
134 return this.curve.getInfinity(); // this = -b, so infinity
137 var THREE = new BigInteger("3");
138 var x1 = this.x.toBigInteger();
139 var y1 = this.y.toBigInteger();
140 var x2 = b.x.toBigInteger();
141 var y2 = b.y.toBigInteger();
144 var v3 = v2.multiply(v);
145 var x1v2 = x1.multiply(v2);
146 var zu2 = u.square().multiply(this.z);
148 // x3 = v * (z2 * (z1 * u^2 - 2 * x1 * v^2) - v^3)
149 var x3 = zu2.subtract(x1v2.shiftLeft(1)).multiply(b.z).subtract(v3).multiply(v).mod(this.curve.q);
150 // y3 = z2 * (3 * x1 * u * v^2 - y1 * v^3 - z1 * u^3) + u * v^3
151 var y3 = x1v2.multiply(THREE).multiply(u).subtract(y1.multiply(v3)).subtract(zu2.multiply(u)).multiply(b.z).add(u.multiply(v3)).mod(this.curve.q);
152 // z3 = v^3 * z1 * z2
153 var z3 = v3.multiply(this.z).multiply(b.z).mod(this.curve.q);
155 return new ECPointFp(this.curve, this.curve.fromBigInteger(x3), this.curve.fromBigInteger(y3), z3);
158 function pointFpTwice() {
159 if(this.isInfinity()) return this;
160 if(this.y.toBigInteger().signum() == 0) return this.curve.getInfinity();
162 // TODO: optimized handling of constants
163 var THREE = new BigInteger("3");
164 var x1 = this.x.toBigInteger();
165 var y1 = this.y.toBigInteger();
167 var y1z1 = y1.multiply(this.z);
168 var y1sqz1 = y1z1.multiply(y1).mod(this.curve.q);
169 var a = this.curve.a.toBigInteger();
171 // w = 3 * x1^2 + a * z1^2
172 var w = x1.square().multiply(THREE);
173 if(!BigInteger.ZERO.equals(a)) {
174 w = w.add(this.z.square().multiply(a));
176 w = w.mod(this.curve.q);
177 //this.curve.reduce(w);
178 // x3 = 2 * y1 * z1 * (w^2 - 8 * x1 * y1^2 * z1)
179 var x3 = w.square().subtract(x1.shiftLeft(3).multiply(y1sqz1)).shiftLeft(1).multiply(y1z1).mod(this.curve.q);
180 // y3 = 4 * y1^2 * z1 * (3 * w * x1 - 2 * y1^2 * z1) - w^3
181 var y3 = w.multiply(THREE).multiply(x1).subtract(y1sqz1.shiftLeft(1)).shiftLeft(2).multiply(y1sqz1).subtract(w.square().multiply(w)).mod(this.curve.q);
182 // z3 = 8 * (y1 * z1)^3
183 var z3 = y1z1.square().multiply(y1z1).shiftLeft(3).mod(this.curve.q);
185 return new ECPointFp(this.curve, this.curve.fromBigInteger(x3), this.curve.fromBigInteger(y3), z3);
188 // Simple NAF (Non-Adjacent Form) multiplication algorithm
189 // TODO: modularize the multiplication algorithm
190 function pointFpMultiply(k) {
191 if(this.isInfinity()) return this;
192 if(k.signum() == 0) return this.curve.getInfinity();
195 var h = e.multiply(new BigInteger("3"));
197 var neg = this.negate();
201 for(i = h.bitLength() - 2; i > 0; --i) {
204 var hBit = h.testBit(i);
205 var eBit = e.testBit(i);
208 R = R.add(hBit ? this : neg);
215 // Compute this*j + x*k (simultaneous multiplication)
216 function pointFpMultiplyTwo(j,x,k) {
218 if(j.bitLength() > k.bitLength())
219 i = j.bitLength() - 1;
221 i = k.bitLength() - 1;
223 var R = this.curve.getInfinity();
224 var both = this.add(x);
246 ECPointFp.prototype.getX = pointFpGetX;
247 ECPointFp.prototype.getY = pointFpGetY;
248 ECPointFp.prototype.equals = pointFpEquals;
249 ECPointFp.prototype.isInfinity = pointFpIsInfinity;
250 ECPointFp.prototype.negate = pointFpNegate;
251 ECPointFp.prototype.add = pointFpAdd;
252 ECPointFp.prototype.twice = pointFpTwice;
253 ECPointFp.prototype.multiply = pointFpMultiply;
254 ECPointFp.prototype.multiplyTwo = pointFpMultiplyTwo;
260 function ECCurveFp(q,a,b) {
262 this.a = this.fromBigInteger(a);
263 this.b = this.fromBigInteger(b);
264 this.infinity = new ECPointFp(this, null, null);
265 this.reducer = new Barrett(this.q);
268 function curveFpGetQ() {
272 function curveFpGetA() {
276 function curveFpGetB() {
280 function curveFpEquals(other) {
281 if(other == this) return true;
282 return(this.q.equals(other.q) && this.a.equals(other.a) && this.b.equals(other.b));
285 function curveFpGetInfinity() {
286 return this.infinity;
289 function curveFpFromBigInteger(x) {
290 return new ECFieldElementFp(this.q, x);
293 function curveReduce(x) {
294 this.reducer.reduce(x);
297 // for now, work with hex strings because they're easier in JS
298 function curveFpDecodePointHex(s) {
299 switch(parseInt(s.substr(0,2), 16)) { // first byte
301 return this.infinity;
304 // point compression not supported yet
309 var len = (s.length - 2) / 2;
310 var xHex = s.substr(2, len);
311 var yHex = s.substr(len+2, len);
313 return new ECPointFp(this,
314 this.fromBigInteger(new BigInteger(xHex, 16)),
315 this.fromBigInteger(new BigInteger(yHex, 16)));
317 default: // unsupported
322 function curveFpEncodePointHex(p) {
323 if (p.isInfinity()) return "00";
324 var xHex = p.getX().toBigInteger().toString(16);
325 var yHex = p.getY().toBigInteger().toString(16);
326 var oLen = this.getQ().toString(16).length;
327 if ((oLen % 2) != 0) oLen++;
328 while (xHex.length < oLen) {
331 while (yHex.length < oLen) {
334 return "04" + xHex + yHex;
337 ECCurveFp.prototype.getQ = curveFpGetQ;
338 ECCurveFp.prototype.getA = curveFpGetA;
339 ECCurveFp.prototype.getB = curveFpGetB;
340 ECCurveFp.prototype.equals = curveFpEquals;
341 ECCurveFp.prototype.getInfinity = curveFpGetInfinity;
342 ECCurveFp.prototype.fromBigInteger = curveFpFromBigInteger;
343 ECCurveFp.prototype.reduce = curveReduce;
344 //ECCurveFp.prototype.decodePointHex = curveFpDecodePointHex;
345 ECCurveFp.prototype.encodePointHex = curveFpEncodePointHex;
347 // from: https://github.com/kaielvin/jsbn-ec-point-compression
348 ECCurveFp.prototype.decodePointHex = function(s)
351 switch(parseInt(s.substr(0,2), 16)) { // first byte
353 return this.infinity;
357 if(yIsEven == undefined) yIsEven = true;
358 var len = s.length - 2;
359 var xHex = s.substr(2, len);
360 var x = this.fromBigInteger(new BigInteger(xHex,16));
361 var alpha = x.multiply(x.square().add(this.getA())).add(this.getB());
362 var beta = alpha.sqrt();
364 if (beta == null) throw "Invalid point compression";
366 var betaValue = beta.toBigInteger();
367 if (betaValue.testBit(0) != yIsEven)
369 // Use the other root
370 beta = this.fromBigInteger(this.getQ().subtract(betaValue));
372 return new ECPointFp(this,x,beta);
376 var len = (s.length - 2) / 2;
377 var xHex = s.substr(2, len);
378 var yHex = s.substr(len+2, len);
380 return new ECPointFp(this,
381 this.fromBigInteger(new BigInteger(xHex, 16)),
382 this.fromBigInteger(new BigInteger(yHex, 16)));
384 default: // unsupported
388 ECCurveFp.prototype.encodeCompressedPointHex = function(p)
390 if (p.isInfinity()) return "00";
391 var xHex = p.getX().toBigInteger().toString(16);
392 var oLen = this.getQ().toString(16).length;
393 if ((oLen % 2) != 0) oLen++;
394 while (xHex.length < oLen)
397 if(p.getY().toBigInteger().isEven()) yPrefix = "02";
400 return yPrefix + xHex;
404 ECFieldElementFp.prototype.getR = function()
406 if(this.r != undefined) return this.r;
409 var bitLength = this.q.bitLength();
412 var firstWord = this.q.shiftRight(bitLength - 64);
413 if (firstWord.intValue() == -1)
415 this.r = BigInteger.ONE.shiftLeft(bitLength).subtract(this.q);
420 ECFieldElementFp.prototype.modMult = function(x1,x2)
422 return this.modReduce(x1.multiply(x2));
424 ECFieldElementFp.prototype.modReduce = function(x)
426 if (this.getR() != null)
428 var qLen = q.bitLength();
429 while (x.bitLength() > (qLen + 1))
431 var u = x.shiftRight(qLen);
432 var v = x.subtract(u.shiftLeft(qLen));
433 if (!this.getR().equals(BigInteger.ONE))
435 u = u.multiply(this.getR());
439 while (x.compareTo(q) >= 0)
450 ECFieldElementFp.prototype.sqrt = function()
452 if (!this.q.testBit(0)) throw "unsupported";
455 if (this.q.testBit(1))
457 var z = new ECFieldElementFp(this.q,this.x.modPow(this.q.shiftRight(2).add(BigInteger.ONE),this.q));
458 return z.square().equals(this) ? z : null;
462 var qMinusOne = this.q.subtract(BigInteger.ONE);
464 var legendreExponent = qMinusOne.shiftRight(1);
465 if (!(this.x.modPow(legendreExponent, this.q).equals(BigInteger.ONE)))
470 var u = qMinusOne.shiftRight(2);
471 var k = u.shiftLeft(1).add(BigInteger.ONE);
474 var fourQ = modDouble(modDouble(Q));
482 P = new BigInteger(this.q.bitLength(), new SecureRandom());
484 while (P.compareTo(this.q) >= 0
485 || !(P.multiply(P).subtract(fourQ).modPow(legendreExponent, this.q).equals(qMinusOne)));
487 var result = this.lucasSequence(P, Q, k);
491 if (this.modMult(V, V).equals(fourQ))
493 // Integer division by 2, mod q
501 return new ECFieldElementFp(q,V);
504 while (U.equals(BigInteger.ONE) || U.equals(qMinusOne));
508 ECFieldElementFp.prototype.lucasSequence = function(P,Q,k)
510 var n = k.bitLength();
511 var s = k.getLowestSetBit();
513 var Uh = BigInteger.ONE;
514 var Vl = BigInteger.TWO;
516 var Ql = BigInteger.ONE;
517 var Qh = BigInteger.ONE;
519 for (var j = n - 1; j >= s + 1; --j)
521 Ql = this.modMult(Ql, Qh);
525 Qh = this.modMult(Ql, Q);
526 Uh = this.modMult(Uh, Vh);
527 Vl = this.modReduce(Vh.multiply(Vl).subtract(P.multiply(Ql)));
528 Vh = this.modReduce(Vh.multiply(Vh).subtract(Qh.shiftLeft(1)));
533 Uh = this.modReduce(Uh.multiply(Vl).subtract(Ql));
534 Vh = this.modReduce(Vh.multiply(Vl).subtract(P.multiply(Ql)));
535 Vl = this.modReduce(Vl.multiply(Vl).subtract(Ql.shiftLeft(1)));
539 Ql = this.modMult(Ql, Qh);
540 Qh = this.modMult(Ql, Q);
541 Uh = this.modReduce(Uh.multiply(Vl).subtract(Ql));
542 Vl = this.modReduce(Vh.multiply(Vl).subtract(P.multiply(Ql)));
543 Ql = this.modMult(Ql, Qh);
545 for (var j = 1; j <= s; ++j)
547 Uh = this.modMult(Uh, Vl);
548 Vl = this.modReduce(Vl.multiply(Vl).subtract(Ql.shiftLeft(1)));
549 Ql = this.modMult(Ql, Ql);
556 ECCurveFp: ECCurveFp,
557 ECPointFp: ECPointFp,
558 ECFieldElementFp: ECFieldElementFp
561 module.exports = exports