www.aleph1.co.uk Git - yaffs-website/blob - node_modules/ecc-jsbn/lib/ec.js

   1 // Basic Javascript Elliptic Curve implementation
   2 // Ported loosely from BouncyCastle's Java EC code
   3 // Only Fp curves implemented for now
   4
   5 // Requires jsbn.js and jsbn2.js
   6 var BigInteger = require('jsbn').BigInteger
   7 var Barrett = BigInteger.prototype.Barrett
   8
   9 // ----------------
  10 // ECFieldElementFp
  11
  12 // constructor
  13 function ECFieldElementFp(q,x) {
  14     this.x = x;
  15     // TODO if(x.compareTo(q) >= 0) error
  16     this.q = q;
  17 }
  18
  19 function feFpEquals(other) {
  20     if(other == this) return true;
  21     return (this.q.equals(other.q) && this.x.equals(other.x));
  22 }
  23
  24 function feFpToBigInteger() {
  25     return this.x;
  26 }
  27
  28 function feFpNegate() {
  29     return new ECFieldElementFp(this.q, this.x.negate().mod(this.q));
  30 }
  31
  32 function feFpAdd(b) {
  33     return new ECFieldElementFp(this.q, this.x.add(b.toBigInteger()).mod(this.q));
  34 }
  35
  36 function feFpSubtract(b) {
  37     return new ECFieldElementFp(this.q, this.x.subtract(b.toBigInteger()).mod(this.q));
  38 }
  39
  40 function feFpMultiply(b) {
  41     return new ECFieldElementFp(this.q, this.x.multiply(b.toBigInteger()).mod(this.q));
  42 }
  43
  44 function feFpSquare() {
  45     return new ECFieldElementFp(this.q, this.x.square().mod(this.q));
  46 }
  47
  48 function feFpDivide(b) {
  49     return new ECFieldElementFp(this.q, this.x.multiply(b.toBigInteger().modInverse(this.q)).mod(this.q));
  50 }
  51
  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;
  60
  61 // ----------------
  62 // ECPointFp
  63
  64 // constructor
  65 function ECPointFp(curve,x,y,z) {
  66     this.curve = curve;
  67     this.x = x;
  68     this.y = y;
  69     // Projective coordinates: either zinv == null or z * zinv == 1
  70     // z and zinv are just BigIntegers, not fieldElements
  71     if(z == null) {
  72       this.z = BigInteger.ONE;
  73     }
  74     else {
  75       this.z = z;
  76     }
  77     this.zinv = null;
  78     //TODO: compression flag
  79 }
  80
  81 function pointFpGetX() {
  82     if(this.zinv == null) {
  83       this.zinv = this.z.modInverse(this.curve.q);
  84     }
  85     var r = this.x.toBigInteger().multiply(this.zinv);
  86     this.curve.reduce(r);
  87     return this.curve.fromBigInteger(r);
  88 }
  89
  90 function pointFpGetY() {
  91     if(this.zinv == null) {
  92       this.zinv = this.z.modInverse(this.curve.q);
  93     }
  94     var r = this.y.toBigInteger().multiply(this.zinv);
  95     this.curve.reduce(r);
  96     return this.curve.fromBigInteger(r);
  97 }
  98
  99 function pointFpEquals(other) {
 100     if(other == this) return true;
 101     if(this.isInfinity()) return other.isInfinity();
 102     if(other.isInfinity()) return this.isInfinity();
 103     var u, v;
 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);
 110 }
 111
 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);
 115 }
 116
 117 function pointFpNegate() {
 118     return new ECPointFp(this.curve, this.x, this.y.negate(), this.z);
 119 }
 120
 121 function pointFpAdd(b) {
 122     if(this.isInfinity()) return b;
 123     if(b.isInfinity()) return this;
 124
 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);
 129
 130     if(BigInteger.ZERO.equals(v)) {
 131         if(BigInteger.ZERO.equals(u)) {
 132             return this.twice(); // this == b, so double
 133         }
 134         return this.curve.getInfinity(); // this = -b, so infinity
 135     }
 136
 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();
 142
 143     var v2 = v.square();
 144     var v3 = v2.multiply(v);
 145     var x1v2 = x1.multiply(v2);
 146     var zu2 = u.square().multiply(this.z);
 147
 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);
 154
 155     return new ECPointFp(this.curve, this.curve.fromBigInteger(x3), this.curve.fromBigInteger(y3), z3);
 156 }
 157
 158 function pointFpTwice() {
 159     if(this.isInfinity()) return this;
 160     if(this.y.toBigInteger().signum() == 0) return this.curve.getInfinity();
 161
 162     // TODO: optimized handling of constants
 163     var THREE = new BigInteger("3");
 164     var x1 = this.x.toBigInteger();
 165     var y1 = this.y.toBigInteger();
 166
 167     var y1z1 = y1.multiply(this.z);
 168     var y1sqz1 = y1z1.multiply(y1).mod(this.curve.q);
 169     var a = this.curve.a.toBigInteger();
 170
 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));
 175     }
 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);
 184
 185     return new ECPointFp(this.curve, this.curve.fromBigInteger(x3), this.curve.fromBigInteger(y3), z3);
 186 }
 187
 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();
 193
 194     var e = k;
 195     var h = e.multiply(new BigInteger("3"));
 196
 197     var neg = this.negate();
 198     var R = this;
 199
 200     var i;
 201     for(i = h.bitLength() - 2; i > 0; --i) {
 202         R = R.twice();
 203
 204         var hBit = h.testBit(i);
 205         var eBit = e.testBit(i);
 206
 207         if (hBit != eBit) {
 208             R = R.add(hBit ? this : neg);
 209         }
 210     }
 211
 212     return R;
 213 }
 214
 215 // Compute this*j + x*k (simultaneous multiplication)
 216 function pointFpMultiplyTwo(j,x,k) {
 217   var i;
 218   if(j.bitLength() > k.bitLength())
 219     i = j.bitLength() - 1;
 220   else
 221     i = k.bitLength() - 1;
 222
 223   var R = this.curve.getInfinity();
 224   var both = this.add(x);
 225   while(i >= 0) {
 226     R = R.twice();
 227     if(j.testBit(i)) {
 228       if(k.testBit(i)) {
 229         R = R.add(both);
 230       }
 231       else {
 232         R = R.add(this);
 233       }
 234     }
 235     else {
 236       if(k.testBit(i)) {
 237         R = R.add(x);
 238       }
 239     }
 240     --i;
 241   }
 242
 243   return R;
 244 }
 245
 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;
 255
 256 // ----------------
 257 // ECCurveFp
 258
 259 // constructor
 260 function ECCurveFp(q,a,b) {
 261     this.q = q;
 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);
 266 }
 267
 268 function curveFpGetQ() {
 269     return this.q;
 270 }
 271
 272 function curveFpGetA() {
 273     return this.a;
 274 }
 275
 276 function curveFpGetB() {
 277     return this.b;
 278 }
 279
 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));
 283 }
 284
 285 function curveFpGetInfinity() {
 286     return this.infinity;
 287 }
 288
 289 function curveFpFromBigInteger(x) {
 290     return new ECFieldElementFp(this.q, x);
 291 }
 292
 293 function curveReduce(x) {
 294     this.reducer.reduce(x);
 295 }
 296
 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
 300     case 0:
 301         return this.infinity;
 302     case 2:
 303     case 3:
 304         // point compression not supported yet
 305         return null;
 306     case 4:
 307     case 6:
 308     case 7:
 309         var len = (s.length - 2) / 2;
 310         var xHex = s.substr(2, len);
 311         var yHex = s.substr(len+2, len);
 312
 313         return new ECPointFp(this,
 314                              this.fromBigInteger(new BigInteger(xHex, 16)),
 315                              this.fromBigInteger(new BigInteger(yHex, 16)));
 316
 317     default: // unsupported
 318         return null;
 319     }
 320 }
 321
 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) {
 329                 xHex = "0" + xHex;
 330         }
 331         while (yHex.length < oLen) {
 332                 yHex = "0" + yHex;
 333         }
 334         return "04" + xHex + yHex;
 335 }
 336
 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;
 346
 347 // from: https://github.com/kaielvin/jsbn-ec-point-compression
 348 ECCurveFp.prototype.decodePointHex = function(s)
 349 {
 350         var yIsEven;
 351     switch(parseInt(s.substr(0,2), 16)) { // first byte
 352     case 0:
 353         return this.infinity;
 354     case 2:
 355         yIsEven = false;
 356     case 3:
 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();
 363
 364     if (beta == null) throw "Invalid point compression";
 365
 366     var betaValue = beta.toBigInteger();
 367     if (betaValue.testBit(0) != yIsEven)
 368     {
 369         // Use the other root
 370         beta = this.fromBigInteger(this.getQ().subtract(betaValue));
 371     }
 372     return new ECPointFp(this,x,beta);
 373     case 4:
 374     case 6:
 375     case 7:
 376         var len = (s.length - 2) / 2;
 377         var xHex = s.substr(2, len);
 378         var yHex = s.substr(len+2, len);
 379
 380         return new ECPointFp(this,
 381                              this.fromBigInteger(new BigInteger(xHex, 16)),
 382                              this.fromBigInteger(new BigInteger(yHex, 16)));
 383
 384     default: // unsupported
 385         return null;
 386     }
 387 }
 388 ECCurveFp.prototype.encodeCompressedPointHex = function(p)
 389 {
 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)
 395                 xHex = "0" + xHex;
 396         var yPrefix;
 397         if(p.getY().toBigInteger().isEven()) yPrefix = "02";
 398         else                                 yPrefix = "03";
 399
 400         return yPrefix + xHex;
 401 }
 402
 403
 404 ECFieldElementFp.prototype.getR = function()
 405 {
 406         if(this.r != undefined) return this.r;
 407
 408     this.r = null;
 409     var bitLength = this.q.bitLength();
 410     if (bitLength > 128)
 411     {
 412         var firstWord = this.q.shiftRight(bitLength - 64);
 413         if (firstWord.intValue() == -1)
 414         {
 415             this.r = BigInteger.ONE.shiftLeft(bitLength).subtract(this.q);
 416         }
 417     }
 418     return this.r;
 419 }
 420 ECFieldElementFp.prototype.modMult = function(x1,x2)
 421 {
 422     return this.modReduce(x1.multiply(x2));
 423 }
 424 ECFieldElementFp.prototype.modReduce = function(x)
 425 {
 426     if (this.getR() != null)
 427     {
 428         var qLen = q.bitLength();
 429         while (x.bitLength() > (qLen + 1))
 430         {
 431             var u = x.shiftRight(qLen);
 432             var v = x.subtract(u.shiftLeft(qLen));
 433             if (!this.getR().equals(BigInteger.ONE))
 434             {
 435                 u = u.multiply(this.getR());
 436             }
 437             x = u.add(v);
 438         }
 439         while (x.compareTo(q) >= 0)
 440         {
 441             x = x.subtract(q);
 442         }
 443     }
 444     else
 445     {
 446         x = x.mod(q);
 447     }
 448     return x;
 449 }
 450 ECFieldElementFp.prototype.sqrt = function()
 451 {
 452     if (!this.q.testBit(0)) throw "unsupported";
 453
 454     // p mod 4 == 3
 455     if (this.q.testBit(1))
 456     {
 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;
 459     }
 460
 461     // p mod 4 == 1
 462     var qMinusOne = this.q.subtract(BigInteger.ONE);
 463
 464     var legendreExponent = qMinusOne.shiftRight(1);
 465     if (!(this.x.modPow(legendreExponent, this.q).equals(BigInteger.ONE)))
 466     {
 467         return null;
 468     }
 469
 470     var u = qMinusOne.shiftRight(2);
 471     var k = u.shiftLeft(1).add(BigInteger.ONE);
 472
 473     var Q = this.x;
 474     var fourQ = modDouble(modDouble(Q));
 475
 476     var U, V;
 477     do
 478     {
 479         var P;
 480         do
 481         {
 482             P = new BigInteger(this.q.bitLength(), new SecureRandom());
 483         }
 484         while (P.compareTo(this.q) >= 0
 485             || !(P.multiply(P).subtract(fourQ).modPow(legendreExponent, this.q).equals(qMinusOne)));
 486
 487         var result = this.lucasSequence(P, Q, k);
 488         U = result[0];
 489         V = result[1];
 490
 491         if (this.modMult(V, V).equals(fourQ))
 492         {
 493             // Integer division by 2, mod q
 494             if (V.testBit(0))
 495             {
 496                 V = V.add(q);
 497             }
 498
 499             V = V.shiftRight(1);
 500
 501             return new ECFieldElementFp(q,V);
 502         }
 503     }
 504     while (U.equals(BigInteger.ONE) || U.equals(qMinusOne));
 505
 506     return null;
 507 }
 508 ECFieldElementFp.prototype.lucasSequence = function(P,Q,k)
 509 {
 510     var n = k.bitLength();
 511     var s = k.getLowestSetBit();
 512
 513     var Uh = BigInteger.ONE;
 514     var Vl = BigInteger.TWO;
 515     var Vh = P;
 516     var Ql = BigInteger.ONE;
 517     var Qh = BigInteger.ONE;
 518
 519     for (var j = n - 1; j >= s + 1; --j)
 520     {
 521         Ql = this.modMult(Ql, Qh);
 522
 523         if (k.testBit(j))
 524         {
 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)));
 529         }
 530         else
 531         {
 532             Qh = Ql;
 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)));
 536         }
 537     }
 538
 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);
 544
 545     for (var j = 1; j <= s; ++j)
 546     {
 547         Uh = this.modMult(Uh, Vl);
 548         Vl = this.modReduce(Vl.multiply(Vl).subtract(Ql.shiftLeft(1)));
 549         Ql = this.modMult(Ql, Ql);
 550     }
 551
 552     return [ Uh, Vl ];
 553 }
 554
 555 var exports = {
 556   ECCurveFp: ECCurveFp,
 557   ECPointFp: ECPointFp,
 558   ECFieldElementFp: ECFieldElementFp
 559 }
 560
 561 module.exports = exports