123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561 |
- var BigInteger = require('jsbn').BigInteger
- var Barrett = BigInteger.prototype.Barrett
- function ECFieldElementFp(q,x) {
- this.x = x;
-
- this.q = q;
- }
- function feFpEquals(other) {
- if(other == this) return true;
- return (this.q.equals(other.q) && this.x.equals(other.x));
- }
- function feFpToBigInteger() {
- return this.x;
- }
- function feFpNegate() {
- return new ECFieldElementFp(this.q, this.x.negate().mod(this.q));
- }
- function feFpAdd(b) {
- return new ECFieldElementFp(this.q, this.x.add(b.toBigInteger()).mod(this.q));
- }
- function feFpSubtract(b) {
- return new ECFieldElementFp(this.q, this.x.subtract(b.toBigInteger()).mod(this.q));
- }
- function feFpMultiply(b) {
- return new ECFieldElementFp(this.q, this.x.multiply(b.toBigInteger()).mod(this.q));
- }
- function feFpSquare() {
- return new ECFieldElementFp(this.q, this.x.square().mod(this.q));
- }
- function feFpDivide(b) {
- return new ECFieldElementFp(this.q, this.x.multiply(b.toBigInteger().modInverse(this.q)).mod(this.q));
- }
- ECFieldElementFp.prototype.equals = feFpEquals;
- ECFieldElementFp.prototype.toBigInteger = feFpToBigInteger;
- ECFieldElementFp.prototype.negate = feFpNegate;
- ECFieldElementFp.prototype.add = feFpAdd;
- ECFieldElementFp.prototype.subtract = feFpSubtract;
- ECFieldElementFp.prototype.multiply = feFpMultiply;
- ECFieldElementFp.prototype.square = feFpSquare;
- ECFieldElementFp.prototype.divide = feFpDivide;
- function ECPointFp(curve,x,y,z) {
- this.curve = curve;
- this.x = x;
- this.y = y;
-
-
- if(z == null) {
- this.z = BigInteger.ONE;
- }
- else {
- this.z = z;
- }
- this.zinv = null;
-
- }
- function pointFpGetX() {
- if(this.zinv == null) {
- this.zinv = this.z.modInverse(this.curve.q);
- }
- var r = this.x.toBigInteger().multiply(this.zinv);
- this.curve.reduce(r);
- return this.curve.fromBigInteger(r);
- }
- function pointFpGetY() {
- if(this.zinv == null) {
- this.zinv = this.z.modInverse(this.curve.q);
- }
- var r = this.y.toBigInteger().multiply(this.zinv);
- this.curve.reduce(r);
- return this.curve.fromBigInteger(r);
- }
- function pointFpEquals(other) {
- if(other == this) return true;
- if(this.isInfinity()) return other.isInfinity();
- if(other.isInfinity()) return this.isInfinity();
- var u, v;
-
- u = other.y.toBigInteger().multiply(this.z).subtract(this.y.toBigInteger().multiply(other.z)).mod(this.curve.q);
- if(!u.equals(BigInteger.ZERO)) return false;
-
- v = other.x.toBigInteger().multiply(this.z).subtract(this.x.toBigInteger().multiply(other.z)).mod(this.curve.q);
- return v.equals(BigInteger.ZERO);
- }
- function pointFpIsInfinity() {
- if((this.x == null) && (this.y == null)) return true;
- return this.z.equals(BigInteger.ZERO) && !this.y.toBigInteger().equals(BigInteger.ZERO);
- }
- function pointFpNegate() {
- return new ECPointFp(this.curve, this.x, this.y.negate(), this.z);
- }
- function pointFpAdd(b) {
- if(this.isInfinity()) return b;
- if(b.isInfinity()) return this;
-
- var u = b.y.toBigInteger().multiply(this.z).subtract(this.y.toBigInteger().multiply(b.z)).mod(this.curve.q);
-
- var v = b.x.toBigInteger().multiply(this.z).subtract(this.x.toBigInteger().multiply(b.z)).mod(this.curve.q);
- if(BigInteger.ZERO.equals(v)) {
- if(BigInteger.ZERO.equals(u)) {
- return this.twice();
- }
- return this.curve.getInfinity();
- }
- var THREE = new BigInteger("3");
- var x1 = this.x.toBigInteger();
- var y1 = this.y.toBigInteger();
- var x2 = b.x.toBigInteger();
- var y2 = b.y.toBigInteger();
- var v2 = v.square();
- var v3 = v2.multiply(v);
- var x1v2 = x1.multiply(v2);
- var zu2 = u.square().multiply(this.z);
-
- var x3 = zu2.subtract(x1v2.shiftLeft(1)).multiply(b.z).subtract(v3).multiply(v).mod(this.curve.q);
-
- 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);
-
- var z3 = v3.multiply(this.z).multiply(b.z).mod(this.curve.q);
- return new ECPointFp(this.curve, this.curve.fromBigInteger(x3), this.curve.fromBigInteger(y3), z3);
- }
- function pointFpTwice() {
- if(this.isInfinity()) return this;
- if(this.y.toBigInteger().signum() == 0) return this.curve.getInfinity();
-
- var THREE = new BigInteger("3");
- var x1 = this.x.toBigInteger();
- var y1 = this.y.toBigInteger();
- var y1z1 = y1.multiply(this.z);
- var y1sqz1 = y1z1.multiply(y1).mod(this.curve.q);
- var a = this.curve.a.toBigInteger();
-
- var w = x1.square().multiply(THREE);
- if(!BigInteger.ZERO.equals(a)) {
- w = w.add(this.z.square().multiply(a));
- }
- w = w.mod(this.curve.q);
-
-
- var x3 = w.square().subtract(x1.shiftLeft(3).multiply(y1sqz1)).shiftLeft(1).multiply(y1z1).mod(this.curve.q);
-
- var y3 = w.multiply(THREE).multiply(x1).subtract(y1sqz1.shiftLeft(1)).shiftLeft(2).multiply(y1sqz1).subtract(w.square().multiply(w)).mod(this.curve.q);
-
- var z3 = y1z1.square().multiply(y1z1).shiftLeft(3).mod(this.curve.q);
- return new ECPointFp(this.curve, this.curve.fromBigInteger(x3), this.curve.fromBigInteger(y3), z3);
- }
- function pointFpMultiply(k) {
- if(this.isInfinity()) return this;
- if(k.signum() == 0) return this.curve.getInfinity();
- var e = k;
- var h = e.multiply(new BigInteger("3"));
- var neg = this.negate();
- var R = this;
- var i;
- for(i = h.bitLength() - 2; i > 0; --i) {
- R = R.twice();
- var hBit = h.testBit(i);
- var eBit = e.testBit(i);
- if (hBit != eBit) {
- R = R.add(hBit ? this : neg);
- }
- }
- return R;
- }
- function pointFpMultiplyTwo(j,x,k) {
- var i;
- if(j.bitLength() > k.bitLength())
- i = j.bitLength() - 1;
- else
- i = k.bitLength() - 1;
- var R = this.curve.getInfinity();
- var both = this.add(x);
- while(i >= 0) {
- R = R.twice();
- if(j.testBit(i)) {
- if(k.testBit(i)) {
- R = R.add(both);
- }
- else {
- R = R.add(this);
- }
- }
- else {
- if(k.testBit(i)) {
- R = R.add(x);
- }
- }
- --i;
- }
- return R;
- }
- ECPointFp.prototype.getX = pointFpGetX;
- ECPointFp.prototype.getY = pointFpGetY;
- ECPointFp.prototype.equals = pointFpEquals;
- ECPointFp.prototype.isInfinity = pointFpIsInfinity;
- ECPointFp.prototype.negate = pointFpNegate;
- ECPointFp.prototype.add = pointFpAdd;
- ECPointFp.prototype.twice = pointFpTwice;
- ECPointFp.prototype.multiply = pointFpMultiply;
- ECPointFp.prototype.multiplyTwo = pointFpMultiplyTwo;
- function ECCurveFp(q,a,b) {
- this.q = q;
- this.a = this.fromBigInteger(a);
- this.b = this.fromBigInteger(b);
- this.infinity = new ECPointFp(this, null, null);
- this.reducer = new Barrett(this.q);
- }
- function curveFpGetQ() {
- return this.q;
- }
- function curveFpGetA() {
- return this.a;
- }
- function curveFpGetB() {
- return this.b;
- }
- function curveFpEquals(other) {
- if(other == this) return true;
- return(this.q.equals(other.q) && this.a.equals(other.a) && this.b.equals(other.b));
- }
- function curveFpGetInfinity() {
- return this.infinity;
- }
- function curveFpFromBigInteger(x) {
- return new ECFieldElementFp(this.q, x);
- }
- function curveReduce(x) {
- this.reducer.reduce(x);
- }
- function curveFpDecodePointHex(s) {
- switch(parseInt(s.substr(0,2), 16)) {
- case 0:
- return this.infinity;
- case 2:
- case 3:
-
- return null;
- case 4:
- case 6:
- case 7:
- var len = (s.length - 2) / 2;
- var xHex = s.substr(2, len);
- var yHex = s.substr(len+2, len);
- return new ECPointFp(this,
- this.fromBigInteger(new BigInteger(xHex, 16)),
- this.fromBigInteger(new BigInteger(yHex, 16)));
- default:
- return null;
- }
- }
- function curveFpEncodePointHex(p) {
- if (p.isInfinity()) return "00";
- var xHex = p.getX().toBigInteger().toString(16);
- var yHex = p.getY().toBigInteger().toString(16);
- var oLen = this.getQ().toString(16).length;
- if ((oLen % 2) != 0) oLen++;
- while (xHex.length < oLen) {
- xHex = "0" + xHex;
- }
- while (yHex.length < oLen) {
- yHex = "0" + yHex;
- }
- return "04" + xHex + yHex;
- }
- ECCurveFp.prototype.getQ = curveFpGetQ;
- ECCurveFp.prototype.getA = curveFpGetA;
- ECCurveFp.prototype.getB = curveFpGetB;
- ECCurveFp.prototype.equals = curveFpEquals;
- ECCurveFp.prototype.getInfinity = curveFpGetInfinity;
- ECCurveFp.prototype.fromBigInteger = curveFpFromBigInteger;
- ECCurveFp.prototype.reduce = curveReduce;
- ECCurveFp.prototype.encodePointHex = curveFpEncodePointHex;
- ECCurveFp.prototype.decodePointHex = function(s)
- {
- var yIsEven;
- switch(parseInt(s.substr(0,2), 16)) {
- case 0:
- return this.infinity;
- case 2:
- yIsEven = false;
- case 3:
- if(yIsEven == undefined) yIsEven = true;
- var len = s.length - 2;
- var xHex = s.substr(2, len);
- var x = this.fromBigInteger(new BigInteger(xHex,16));
- var alpha = x.multiply(x.square().add(this.getA())).add(this.getB());
- var beta = alpha.sqrt();
- if (beta == null) throw "Invalid point compression";
- var betaValue = beta.toBigInteger();
- if (betaValue.testBit(0) != yIsEven)
- {
-
- beta = this.fromBigInteger(this.getQ().subtract(betaValue));
- }
- return new ECPointFp(this,x,beta);
- case 4:
- case 6:
- case 7:
- var len = (s.length - 2) / 2;
- var xHex = s.substr(2, len);
- var yHex = s.substr(len+2, len);
- return new ECPointFp(this,
- this.fromBigInteger(new BigInteger(xHex, 16)),
- this.fromBigInteger(new BigInteger(yHex, 16)));
- default:
- return null;
- }
- }
- ECCurveFp.prototype.encodeCompressedPointHex = function(p)
- {
- if (p.isInfinity()) return "00";
- var xHex = p.getX().toBigInteger().toString(16);
- var oLen = this.getQ().toString(16).length;
- if ((oLen % 2) != 0) oLen++;
- while (xHex.length < oLen)
- xHex = "0" + xHex;
- var yPrefix;
- if(p.getY().toBigInteger().isEven()) yPrefix = "02";
- else yPrefix = "03";
- return yPrefix + xHex;
- }
- ECFieldElementFp.prototype.getR = function()
- {
- if(this.r != undefined) return this.r;
- this.r = null;
- var bitLength = this.q.bitLength();
- if (bitLength > 128)
- {
- var firstWord = this.q.shiftRight(bitLength - 64);
- if (firstWord.intValue() == -1)
- {
- this.r = BigInteger.ONE.shiftLeft(bitLength).subtract(this.q);
- }
- }
- return this.r;
- }
- ECFieldElementFp.prototype.modMult = function(x1,x2)
- {
- return this.modReduce(x1.multiply(x2));
- }
- ECFieldElementFp.prototype.modReduce = function(x)
- {
- if (this.getR() != null)
- {
- var qLen = q.bitLength();
- while (x.bitLength() > (qLen + 1))
- {
- var u = x.shiftRight(qLen);
- var v = x.subtract(u.shiftLeft(qLen));
- if (!this.getR().equals(BigInteger.ONE))
- {
- u = u.multiply(this.getR());
- }
- x = u.add(v);
- }
- while (x.compareTo(q) >= 0)
- {
- x = x.subtract(q);
- }
- }
- else
- {
- x = x.mod(q);
- }
- return x;
- }
- ECFieldElementFp.prototype.sqrt = function()
- {
- if (!this.q.testBit(0)) throw "unsupported";
-
- if (this.q.testBit(1))
- {
- var z = new ECFieldElementFp(this.q,this.x.modPow(this.q.shiftRight(2).add(BigInteger.ONE),this.q));
- return z.square().equals(this) ? z : null;
- }
-
- var qMinusOne = this.q.subtract(BigInteger.ONE);
- var legendreExponent = qMinusOne.shiftRight(1);
- if (!(this.x.modPow(legendreExponent, this.q).equals(BigInteger.ONE)))
- {
- return null;
- }
- var u = qMinusOne.shiftRight(2);
- var k = u.shiftLeft(1).add(BigInteger.ONE);
- var Q = this.x;
- var fourQ = modDouble(modDouble(Q));
- var U, V;
- do
- {
- var P;
- do
- {
- P = new BigInteger(this.q.bitLength(), new SecureRandom());
- }
- while (P.compareTo(this.q) >= 0
- || !(P.multiply(P).subtract(fourQ).modPow(legendreExponent, this.q).equals(qMinusOne)));
- var result = this.lucasSequence(P, Q, k);
- U = result[0];
- V = result[1];
- if (this.modMult(V, V).equals(fourQ))
- {
-
- if (V.testBit(0))
- {
- V = V.add(q);
- }
- V = V.shiftRight(1);
- return new ECFieldElementFp(q,V);
- }
- }
- while (U.equals(BigInteger.ONE) || U.equals(qMinusOne));
- return null;
- }
- ECFieldElementFp.prototype.lucasSequence = function(P,Q,k)
- {
- var n = k.bitLength();
- var s = k.getLowestSetBit();
- var Uh = BigInteger.ONE;
- var Vl = BigInteger.TWO;
- var Vh = P;
- var Ql = BigInteger.ONE;
- var Qh = BigInteger.ONE;
- for (var j = n - 1; j >= s + 1; --j)
- {
- Ql = this.modMult(Ql, Qh);
- if (k.testBit(j))
- {
- Qh = this.modMult(Ql, Q);
- Uh = this.modMult(Uh, Vh);
- Vl = this.modReduce(Vh.multiply(Vl).subtract(P.multiply(Ql)));
- Vh = this.modReduce(Vh.multiply(Vh).subtract(Qh.shiftLeft(1)));
- }
- else
- {
- Qh = Ql;
- Uh = this.modReduce(Uh.multiply(Vl).subtract(Ql));
- Vh = this.modReduce(Vh.multiply(Vl).subtract(P.multiply(Ql)));
- Vl = this.modReduce(Vl.multiply(Vl).subtract(Ql.shiftLeft(1)));
- }
- }
- Ql = this.modMult(Ql, Qh);
- Qh = this.modMult(Ql, Q);
- Uh = this.modReduce(Uh.multiply(Vl).subtract(Ql));
- Vl = this.modReduce(Vh.multiply(Vl).subtract(P.multiply(Ql)));
- Ql = this.modMult(Ql, Qh);
- for (var j = 1; j <= s; ++j)
- {
- Uh = this.modMult(Uh, Vl);
- Vl = this.modReduce(Vl.multiply(Vl).subtract(Ql.shiftLeft(1)));
- Ql = this.modMult(Ql, Ql);
- }
- return [ Uh, Vl ];
- }
- var exports = {
- ECCurveFp: ECCurveFp,
- ECPointFp: ECPointFp,
- ECFieldElementFp: ECFieldElementFp
- }
- module.exports = exports
|