"Fossies" - the Fresh Open Source Software Archive

Member "Atom/resources/app/apm/node_modules/ecc-jsbn/lib/ec.js" (7 Feb 2017, 15318 Bytes) of archive /windows/misc/atom-windows.zip:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) Javascript source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file.

    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