ec.js - twitst4tz - twitter statistics web application

ec.js (15318B)
      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
	twitst4tz twitter statistics web application
	Log \| Files \| Refs \| README \| LICENSE