Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /**
- * base class for all ecc operations.
- */
- sjcl.ecc = {};
- /**
- * Represents a point on a curve in affine coordinates.
- * @constructor
- * @param {sjcl.ecc.curve} curve The curve that this point lies on.
- * @param {bigInt} x The x coordinate.
- * @param {bigInt} y The y coordinate.
- */
- sjcl.ecc.point = function(curve,x,y) {
- if (x === undefined) {
- this.isIdentity = true;
- } else {
- if (x instanceof sjcl.bn) {
- x = new curve.field(x);
- }
- if (y instanceof sjcl.bn) {
- y = new curve.field(y);
- }
- this.x = x;
- this.y = y;
- this.isIdentity = false;
- }
- this.curve = curve;
- };
- sjcl.ecc.point.prototype = {
- toJac: function() {
- return new sjcl.ecc.pointJac(this.curve, this.x, this.y, new this.curve.field(1));
- },
- mult: function(k) {
- return this.toJac().mult(k, this).toAffine();
- },
- /**
- * Multiply this point by k, added to affine2*k2, and return the answer in Jacobian coordinates.
- * @param {bigInt} k The coefficient to multiply this by.
- * @param {bigInt} k2 The coefficient to multiply affine2 this by.
- * @param {sjcl.ecc.point} affine The other point in affine coordinates.
- * @return {sjcl.ecc.pointJac} The result of the multiplication and addition, in Jacobian coordinates.
- */
- mult2: function(k, k2, affine2) {
- return this.toJac().mult2(k, this, k2, affine2).toAffine();
- },
- multiples: function() {
- var m, i, j;
- if (this._multiples === undefined) {
- j = this.toJac().doubl();
- m = this._multiples = [new sjcl.ecc.point(this.curve), this, j.toAffine()];
- for (i=3; i<16; i++) {
- j = j.add(this);
- m.push(j.toAffine());
- }
- }
- return this._multiples;
- },
- negate: function() {
- var newY = new this.curve.field(0).sub(this.y).normalize().reduce();
- return new sjcl.ecc.point(this.curve, this.x, newY);
- },
- isValid: function() {
- return this.y.square().equals(this.curve.b.add(this.x.mul(this.curve.a.add(this.x.square()))));
- },
- toBits: function(compress, littleEndian) {
- var out, x, y;
- if (!compress) {
- x = this.x.toBits();
- y = this.y.toBits();
- if (!!littleEndian) {
- x = sjcl.bitArray.swapEndian(x);
- y = sjcl.bitArray.swapEndian(y);
- }
- out = sjcl.bitArray.concat(x, y);
- } else {
- out = new sjcl.bn(this.x.fullReduce());
- if (this.y.fullReduce().mod(2).equals(1)) {
- out.addM(new sjcl.bn(Math.pow(2, this.x.exponent)));
- }
- out = out.toBits(this.x.exponent + 1);
- if (!!littleEndian) {
- out = sjcl.bitArray.swapEndian(out);
- }
- }
- return out;
- }
- };
- /**
- * Represents a point on a curve in Jacobian coordinates. Coordinates can be specified as bigInts or strings (which
- * will be converted to bigInts).
- *
- * @constructor
- * @param {bigInt/string} x The x coordinate.
- * @param {bigInt/string} y The y coordinate.
- * @param {bigInt/string} z The z coordinate.
- * @param {sjcl.ecc.curve} curve The curve that this point lies on.
- */
- sjcl.ecc.pointJac = function(curve, x, y, z) {
- if (x === undefined) {
- this.isIdentity = true;
- } else {
- this.x = x;
- this.y = y;
- this.z = z;
- this.isIdentity = false;
- }
- this.curve = curve;
- };
- sjcl.ecc.pointJac.prototype = {
- /**
- * Adds S and T and returns the result in Jacobian coordinates. Note that S must be in Jacobian coordinates and T must be in affine coordinates.
- * @param {sjcl.ecc.pointJac} S One of the points to add, in Jacobian coordinates.
- * @param {sjcl.ecc.point} T The other point to add, in affine coordinates.
- * @return {sjcl.ecc.pointJac} The sum of the two points, in Jacobian coordinates.
- */
- add: function(T) {
- var S = this, sz2, c, d, c2, x1, x2, x, y1, y2, y, z;
- if (S.curve !== T.curve) {
- throw("sjcl.ecc.add(): Points must be on the same curve to add them!");
- }
- if (S.isIdentity) {
- return T.toJac();
- } else if (T.isIdentity) {
- return S;
- }
- sz2 = S.z.square();
- c = T.x.mul(sz2).subM(S.x);
- if (c.equals(0)) {
- if (S.y.equals(T.y.mul(sz2.mul(S.z)))) {
- // same point
- return S.doubl();
- } else {
- // inverses
- return new sjcl.ecc.pointJac(S.curve);
- }
- }
- d = T.y.mul(sz2.mul(S.z)).subM(S.y);
- c2 = c.square();
- x1 = d.square();
- x2 = c.square().mul(c).addM( S.x.add(S.x).mul(c2) );
- x = x1.subM(x2);
- y1 = S.x.mul(c2).subM(x).mul(d);
- y2 = S.y.mul(c.square().mul(c));
- y = y1.subM(y2);
- z = S.z.mul(c);
- return new sjcl.ecc.pointJac(this.curve,x,y,z);
- },
- /**
- * doubles this point.
- * @return {sjcl.ecc.pointJac} The doubled point.
- */
- doubl: function() {
- if (this.isIdentity) { return this; }
- var
- y2 = this.y.square(),
- a = y2.mul(this.x.mul(4)),
- b = y2.square().mul(8),
- z2 = this.z.square(),
- c = this.curve.a.toString() == (new sjcl.bn(-3)).toString() ?
- this.x.sub(z2).mul(3).mul(this.x.add(z2)) :
- this.x.square().mul(3).add(z2.square().mul(this.curve.a)),
- x = c.square().subM(a).subM(a),
- y = a.sub(x).mul(c).subM(b),
- z = this.y.add(this.y).mul(this.z);
- return new sjcl.ecc.pointJac(this.curve, x, y, z);
- },
- /**
- * Returns a copy of this point converted to affine coordinates.
- * @return {sjcl.ecc.point} The converted point.
- */
- toAffine: function() {
- if (this.isIdentity || this.z.equals(0)) {
- return new sjcl.ecc.point(this.curve);
- }
- var zi = this.z.inverse(), zi2 = zi.square();
- return new sjcl.ecc.point(this.curve, this.x.mul(zi2).fullReduce(), this.y.mul(zi2.mul(zi)).fullReduce());
- },
- /**
- * Multiply this point by k and return the answer in Jacobian coordinates.
- * @param {bigInt} k The coefficient to multiply by.
- * @param {sjcl.ecc.point} affine This point in affine coordinates.
- * @return {sjcl.ecc.pointJac} The result of the multiplication, in Jacobian coordinates.
- */
- mult: function(k, affine) {
- if (typeof(k) === "number") {
- k = [k];
- } else if (k.limbs !== undefined) {
- k = k.normalize().limbs;
- }
- var i, j, out = new sjcl.ecc.point(this.curve).toJac(), multiples = affine.multiples();
- for (i=k.length-1; i>=0; i--) {
- for (j=sjcl.bn.prototype.radix-4; j>=0; j-=4) {
- out = out.doubl().doubl().doubl().doubl().add(multiples[k[i]>>j & 0xF]);
- }
- }
- return out;
- },
- /**
- * Multiply this point by k, added to affine2*k2, and return the answer in Jacobian coordinates.
- * @param {bigInt} k The coefficient to multiply this by.
- * @param {sjcl.ecc.point} affine This point in affine coordinates.
- * @param {bigInt} k2 The coefficient to multiply affine2 this by.
- * @param {sjcl.ecc.point} affine The other point in affine coordinates.
- * @return {sjcl.ecc.pointJac} The result of the multiplication and addition, in Jacobian coordinates.
- */
- mult2: function(k1, affine, k2, affine2) {
- if (typeof(k1) === "number") {
- k1 = [k1];
- } else if (k1.limbs !== undefined) {
- k1 = k1.normalize().limbs;
- }
- if (typeof(k2) === "number") {
- k2 = [k2];
- } else if (k2.limbs !== undefined) {
- k2 = k2.normalize().limbs;
- }
- var i, j, out = new sjcl.ecc.point(this.curve).toJac(), m1 = affine.multiples(),
- m2 = affine2.multiples(), l1, l2;
- for (i=Math.max(k1.length,k2.length)-1; i>=0; i--) {
- l1 = k1[i] | 0;
- l2 = k2[i] | 0;
- for (j=sjcl.bn.prototype.radix-4; j>=0; j-=4) {
- out = out.doubl().doubl().doubl().doubl().add(m1[l1>>j & 0xF]).add(m2[l2>>j & 0xF]);
- }
- }
- return out;
- },
- negate: function() {
- return this.toAffine().negate().toJac();
- },
- isValid: function() {
- var z2 = this.z.square(), z4 = z2.square(), z6 = z4.mul(z2);
- return this.y.square().equals(
- this.curve.b.mul(z6).add(this.x.mul(
- this.curve.a.mul(z4).add(this.x.square()))));
- }
- };
- /**
- * Construct an elliptic curve. Most users will not use this and instead start with one of the NIST curves defined below.
- *
- * @constructor
- * @param {bigInt} p The prime modulus.
- * @param {bigInt} r The prime order of the curve.
- * @param {bigInt} a The constant a in the equation of the curve y^2 = x^3 + ax + b (for NIST curves, a is always -3).
- * @param {bigInt} b The constant b in the equation of the curve y^2 = x^3 + ax + b.
- * @param {bigInt} x The x coordinate of a base point of the curve.
- * @param {bigInt} y The y coordinate of a base point of the curve.
- * @param {bigInt} mx The x coordinate of the M point of the curve for SPAKE2/PAKE2+.
- * @param {bigInt} my The y coordinate of the M point of the curve for SPAKE2/PAKE2+.
- * @param {bigInt} nx The x coordinate of the N point of the curve for SPAKE2/PAKE2+.
- * @param {bigInt} ny The y coordinate of the N point of the curve for SPAKE2/PAKE2+.
- */
- sjcl.ecc.curve = function(Field, r, a, b, x, y, mx, my, nx, ny) {
- this.field = Field;
- this.r = new sjcl.bn(r);
- this.a = new Field(a);
- this.b = new Field(b);
- this.G = new sjcl.ecc.point(this, new Field(x), new Field(y));
- if (mx && my && nx && ny) {
- this.M = new sjcl.ecc.point(this, new Field(mx), new Field(my));
- this.N = new sjcl.ecc.point(this, new Field(nx), new Field(ny));
- }
- };
- sjcl.ecc.curve.prototype = {
- fromBits: function(bits, littleEndian) {
- var w = sjcl.bitArray, n = this.field.prototype.exponent, l = n + 7 & -8, p, x, y;
- if (w.bitLength(bits) == 2*l) {
- x = w.bitSlice(bits, 0, l);
- y = w.bitSlice(bits, l, 2*l);
- if (littleEndian) {
- x = sjcl.bitArray.swapEndian(x);
- y = sjcl.bitArray.swapEndian(y);
- }
- p = new sjcl.ecc.point(this, this.field.fromBits(x), this.field.fromBits(y));
- } else if (w.bitLength(bits) == (n + 8 & -8)) {
- if (littleEndian) {
- bits = sjcl.bitArray.swapEndian(bits);
- }
- var bit = new sjcl.bn(Math.pow(2, this.field.prototype.exponent)),
- x = sjcl.bn.fromBits(bits);
- if (x.greaterEquals(bit)) {
- x.subM(bit);
- bit = 1;
- } else {
- bit = 0;
- }
- p = this.recoverPt(x);
- if (!p.y.fullReduce().mod(2).equals(bit)) {
- p = p.negate();
- }
- } else {
- throw new sjcl.exception.corrupt("not on the curve!");
- }
- if (!p.isValid()) {
- throw new sjcl.exception.corrupt("not on the curve!");
- }
- return p;
- },
- /**
- * Recovers the y value from x.
- *
- * @param {bigInt} x The x value.
- * @return {sjcl.ecc.point}
- */
- recoverPt: function(x) {
- // y = sqrt(x^3 + ax + b)
- x = new this.field(x);
- return new sjcl.ecc.point(this, x, x.mul(x.square()).add(x.mul(this.a)).add(this.b).sqrtMod().fullReduce());
- },
- /**
- * Creates a deterministic random point in constant time.
- * Uses the simplified Shallue-Woestijne-Ulas algorithm (https://eprint.iacr.org/2009/340.pdf, page 16)
- *
- * Yes: c192, c256, c384, c521, k192, k256
- * No: c224, k224
- *
- * @param {bigInt} num A number 0 <= x < sjcl.ecc.curve.field.modulus.
- * @return {sjcl.ecc.point} A deterministic random point.
- */
- deterministicRandomPoint: function (num) {
- var u, c, x2, x3, h2, h3, p, y2, y3, pow, zero = new this.field(0), one = new this.field(1);
- if (!this.canDeterministicRandomPoint()) {
- throw("sjcl.ecc.curve.deterministicRandomPoint(): Curve can't create a deterministic random point in constant time");
- }
- u = new this.field(num);
- // c = -u^2
- c = zero.sub(u.square());
- // X2 = -b / a * (1 + 1 / (c^2 + c))
- x2 = zero.sub(this.b.mul(this.a.inverse())).mul(one.add(c.square().add(c).inverse()));
- // X3 = c * X2
- x3 = c.mul(x2);
- // h2 = X2^3 + a * X2 + b
- h2 = x2.square().mul(x2).add(this.a.mul(x2)).add(this.b);
- // h3 = X3^3 + a * X3 + b
- h3 = x3.square().mul(x3).add(this.a.mul(x3)).add(this.b);
- // if (h2 is square)
- pow = this.field.modulus.add(one).normalize().halveM().halveM();
- y2 = h2.power(pow);
- y3 = zero.sub(h3.power(pow));
- if (h2.equals(y2.square())) {
- // (X2, h2 ^ ((q + 1) / 4))
- p = new sjcl.ecc.point(this, x2, y2);
- } else {
- // (X3, -h3 ^ ((q + 1) / 4))
- p = new sjcl.ecc.point(this, x3, y3);
- }
- return p;
- },
- /**
- * Determines if the curve can create a deterministic random point in constant time.
- * Yes: c192, c256, c384, c521, k192, k256
- * No: c224, k224
- *
- * @return {Bool} True if this curve can.
- */
- canDeterministicRandomPoint: function () {
- return this.field.modulus.mod(4).equals(3);
- }
- };
- /**
- * Represents a point on a twisted Edwards curve in affine coordinates.
- * @constructor
- * @param {sjcl.ecc.tEdCurve} curve The curve that this point lies on.
- * @param {bigInt} x The x coordinate.
- * @param {bigInt} y The y coordinate.
- */
- sjcl.ecc.tEdPoint = function(curve,x,y) {
- this.isIdentity = true;
- if (x !== undefined) {
- if (x instanceof sjcl.bn) {
- x = new curve.field(x);
- }
- if (y instanceof sjcl.bn) {
- y = new curve.field(y);
- }
- if (!x.equals(0) || !y.equals(1)) {
- this.x = x;
- this.y = y;
- this.isIdentity = false;
- }
- }
- this.curve = curve;
- };
- sjcl.ecc.tEdPoint.prototype = {
- toJac: function() {
- if (this.isIdentity) {
- return new sjcl.ecc.tEdPointJac(this.curve);
- }
- return new sjcl.ecc.tEdPointJac(this.curve, this.x, this.y, new this.curve.field(1), this.x.mul(this.y));
- },
- mult: function(k) {
- return this.toJac().mult(k, this).toAffine();
- },
- /**
- * Multiply this point by k, added to affine2*k2, and return the answer in Jacobian coordinates.
- * @param {bigInt} k The coefficient to multiply this by.
- * @param {bigInt} k2 The coefficient to multiply affine2 this by.
- * @param {sjcl.ecc.tEdPoint} affine The other point in affine coordinates.
- * @return {sjcl.ecc.tEdPointJac} The result of the multiplication and addition, in Jacobian coordinates.
- */
- mult2: function(k, k2, affine2) {
- return this.toJac().mult2(k, this, k2, affine2).toAffine();
- },
- multiples: function() {
- var m, i, j;
- if (this._multiples === undefined) {
- j = this.toJac().doubl();
- m = this._multiples = [new sjcl.ecc.tEdPoint(this.curve), this, j.toAffine()];
- for (i=3; i<16; i++) {
- j = j.add(this);
- m.push(j.toAffine());
- }
- }
- return this._multiples;
- },
- negate: function() {
- var newX = new this.curve.field(0).sub(this.x).normalize().reduce();
- return new sjcl.ecc.tEdPoint(this.curve, newX, this.y);
- },
- isValid: function() {
- // a = -1
- // a * x^2 + y^2 = 1 + d * x^2 * y^2
- var xx, yy;
- xx = this.x.square();
- yy = this.y.square();
- return yy.sub(xx).equals(this.curve.d.mul(xx).mul(yy).add(1));
- },
- toBits: function(compress, littleEndian) {
- var out, x, y;
- if (!compress) {
- x = this.x.toBits();
- y = this.y.toBits();
- if (!!littleEndian) {
- x = sjcl.bitArray.swapEndian(x);
- y = sjcl.bitArray.swapEndian(y);
- }
- out = sjcl.bitArray.concat(x, y);
- } else {
- out = new sjcl.bn(this.y.fullReduce());
- if (this.x.fullReduce().mod(2).equals(1)) {
- out.addM(new sjcl.bn(Math.pow(2, this.x.exponent)));
- }
- out = out.toBits(this.x.exponent + 1);
- if (!!littleEndian) {
- out = sjcl.bitArray.swapEndian(out);
- }
- }
- return out;
- }
- };
- /**
- * Represents a point on a twisted Edwards curve in Jacobian coordinates. Coordinates can be specified as bigInts or strings (which
- * will be converted to bigInts).
- *
- * @constructor
- * @param {bigInt/string} x The x coordinate.
- * @param {bigInt/string} y The y coordinate.
- * @param {bigInt/string} z The z coordinate.
- * @param {bigInt/string} t The t coordinate.
- * @param {sjcl.ecc.curve} curve The curve that this point lies on.
- */
- sjcl.ecc.tEdPointJac = function(curve, x, y, z, t) {
- if (x === undefined) {
- this.isIdentity = true;
- } else {
- this.x = x;
- this.y = y;
- this.z = z;
- this.t = t;
- this.isIdentity = false;
- }
- this.curve = curve;
- };
- sjcl.ecc.tEdPointJac.prototype = {
- /**
- * Adds S and T and returns the result in Jacobian coordinates. Note that S must be in Jacobian coordinates and T must be in affine coordinates.
- * @param {sjcl.ecc.tEdPointJac} S One of the points to add, in Jacobian coordinates.
- * @param {sjcl.ecc.tEdPoint} T The other point to add, in affine coordinates.
- * @return {sjcl.ecc.tEdPointJac} The sum of the two points, in Jacobian coordinates.
- */
- add: function(T) {
- var S = this, a, b, c, d, e, f, g, h, x, y, z, t;
- if (S.curve !== T.curve) {
- throw("sjcl.ecc.add(): Points must be on the same curve to add them!");
- }
- if (S.isIdentity) {
- return T.toJac();
- } else if (T.isIdentity) {
- return S;
- }
- // A = (Y1-X1)*(Y2-X2)
- a = S.y.sub(S.x).mul(T.y.sub(T.x));
- // B = (Y1+X1)*(Y2+X2)
- b = S.y.add(S.x).mul(T.y.add(T.x));
- // C = T1*k*T2
- c = S.t.mul(S.curve.k).mul(T.x.mul(T.y));
- d = S.z.add(S.z); // D = 2*Z1
- e = b.sub(a); // E = B-A
- f = d.sub(c); // F = D-C
- g = d.add(c); // G = D+C
- h = b.add(a); // H = B+A
- x = e.mul(f); // X3 = E*F
- y = g.mul(h); // Y3 = G*H
- t = e.mul(h); // T3 = E*H
- z = f.mul(g); // Z3 = F*G
- return new sjcl.ecc.tEdPointJac(this.curve,x,y,z,t);
- },
- /**
- * doubles this point.
- * @return {sjcl.ecc.tEdPointJac} The doubled point.
- */
- doubl: function() {
- var a, b, c, d, e, f, g, h, x, y, z, t;
- if (this.isIdentity) { return this; }
- a = this.x.square(); // A = X1^2
- b = this.y.square(); // B = Y1^2
- c = this.z.square(); // C = 2*Z1^2
- c = c.add(c);
- // D = -A
- d = new this.curve.field(0).sub(a);
- // E = (X1+Y1)^2-A-B
- e = this.x.add(this.y).square().sub(a).sub(b);
- g = d.add(b); // G = D+B
- f = g.sub(c); // F = G-C
- h = d.sub(b); // H = D-B
- x = e.mul(f); // X3 = E*F
- y = g.mul(h); // Y3 = G*H
- t = e.mul(h); // T3 = E*H
- z = f.mul(g); // Z3 = F*G
- return new sjcl.ecc.tEdPointJac(this.curve, x, y, z, t);
- },
- /**
- * Returns a copy of this point converted to affine coordinates.
- * @return {sjcl.ecc.tEdPoint} The converted point.
- */
- toAffine: function() {
- if (this.isIdentity || this.z.equals(0)) {
- return new sjcl.ecc.tEdPoint(this.curve);
- }
- var zi = this.z.inverse();
- return new sjcl.ecc.tEdPoint(this.curve, this.x.mul(zi).fullReduce(), this.y.mul(zi).fullReduce());
- },
- /**
- * Multiply this point by k and return the answer in Jacobian coordinates.
- * @param {bigInt} k The coefficient to multiply by.
- * @param {sjcl.ecc.tEdPoint} affine This point in affine coordinates.
- * @return {sjcl.ecc.tEdPointJac} The result of the multiplication, in Jacobian coordinates.
- */
- mult: function(k, affine) {
- if (typeof(k) === "number") {
- k = [k];
- } else if (k.limbs !== undefined) {
- k = k.normalize().limbs;
- }
- var i, j, out = new sjcl.ecc.tEdPoint(this.curve).toJac(), multiples = affine.multiples();
- for (i=k.length-1; i>=0; i--) {
- for (j=sjcl.bn.prototype.radix-4; j>=0; j-=4) {
- out = out.doubl().doubl().doubl().doubl().add(multiples[k[i]>>j & 0xF]);
- }
- }
- return out;
- },
- /**
- * Multiply this point by k, added to affine2*k2, and return the answer in Jacobian coordinates.
- * @param {bigInt} k The coefficient to multiply this by.
- * @param {sjcl.ecc.tEdPoint} affine This point in affine coordinates.
- * @param {bigInt} k2 The coefficient to multiply affine2 this by.
- * @param {sjcl.ecc.tEdPoint} affine The other point in affine coordinates.
- * @return {sjcl.ecc.tEdPointJac} The result of the multiplication and addition, in Jacobian coordinates.
- */
- mult2: function(k1, affine, k2, affine2) {
- if (typeof(k1) === "number") {
- k1 = [k1];
- } else if (k1.limbs !== undefined) {
- k1 = k1.normalize().limbs;
- }
- if (typeof(k2) === "number") {
- k2 = [k2];
- } else if (k2.limbs !== undefined) {
- k2 = k2.normalize().limbs;
- }
- var i, j, out = new sjcl.ecc.tEdPoint(this.curve).toJac(), m1 = affine.multiples(),
- m2 = affine2.multiples(), l1, l2;
- for (i=Math.max(k1.length,k2.length)-1; i>=0; i--) {
- l1 = k1[i] | 0;
- l2 = k2[i] | 0;
- for (j=sjcl.bn.prototype.radix-4; j>=0; j-=4) {
- out = out.doubl().doubl().doubl().doubl().add(m1[l1>>j & 0xF]).add(m2[l2>>j & 0xF]);
- }
- }
- return out;
- },
- negate: function() {
- return this.toAffine().negate().toJac();
- },
- isValid: function() {
- // a = -1
- // a * x^2 + y^2 = 1 + d * x^2 * y^2
- // a * X^2 / Z^2 + Y^2 / Z^2 = Z^2 / Z^2 + d * X^2 * Y^2 / Z^2
- // (a * X^2 + Y^2) / Z^2 = (Z^2 + d * X^2 * Y^2) / Z^2
- // a * X^2 + Y^2 = Z^2 + d * X^2 * Y^2
- // T/Z = x*y
- // T/Z = X/Z*Y/Z
- // T*Z = X*Y
- var xx, yy;
- xx = this.x.square();
- yy = this.y.square();
- return
- yy.sub(xx).equals(this.z.square().add(this.curve.d.mul(xx).mul(yy))) &&
- this.t.mul(this.z).equals(this.x.mul(this.y));
- }
- };
- /**
- * Construct a twisted Edwards elliptic curve. Most users will not use this and instead start with Ed25519 defined below.
- *
- * @constructor
- * @param {bigInt} p The prime modulus.
- * @param {bigInt} r The prime order of the curve.
- * @param {bigInt} d The constant d in the equation of the curve a * x^2 + y^2 = 1 + d * x^2 * y^2 (a = -1).
- * @param {bigInt} x The x coordinate of a base point of the curve.
- * @param {bigInt} y The y coordinate of a base point of the curve.
- * @param {bigInt} mx The x coordinate of the M point of the curve for SPAKE2/PAKE2+.
- * @param {bigInt} my The y coordinate of the M point of the curve for SPAKE2/PAKE2+.
- * @param {bigInt} nx The x coordinate of the N point of the curve for SPAKE2/PAKE2+.
- * @param {bigInt} ny The y coordinate of the N point of the curve for SPAKE2/PAKE2+.
- * @param {bigInt} ex The x coordinate of a point of order 2.
- * @param {bigInt} ey The y coordinate of a point of order 2.
- */
- sjcl.ecc.tEdCurve = function(Field, r, d, x, y, mx, my, nx, ny, ex, ey) {
- this.field = Field;
- this.r = new sjcl.bn(r);
- this.d = new Field(d);
- this.k = this.d.add(this.d);
- this.G = new sjcl.ecc.tEdPoint(this, new Field(x), new Field(y));
- if (mx && my && nx && ny) {
- this.M = new sjcl.ecc.tEdPoint(this, new Field(mx), new Field(my));
- this.N = new sjcl.ecc.tEdPoint(this, new Field(nx), new Field(ny));
- }
- if (ex && ey) {
- this.order2P = new sjcl.ecc.tEdPoint(this, new Field(ex), new Field(ey));
- }
- };
- sjcl.ecc.tEdCurve.prototype = {
- fromBits: function(bits, littleEndian) {
- var w = sjcl.bitArray, n = this.field.prototype.exponent, l = n + 7 & -8, p, x, y;
- if (w.bitLength(bits) == 2*l) {
- x = w.bitSlice(bits, 0, l);
- y = w.bitSlice(bits, l, 2*l);
- if (littleEndian) {
- x = sjcl.bitArray.swapEndian(x);
- y = sjcl.bitArray.swapEndian(y);
- }
- p = new sjcl.ecc.tEdPoint(this, this.field.fromBits(x), this.field.fromBits(y));
- } else if (w.bitLength(bits) == (n + 8 & -8)) {
- if (littleEndian) {
- bits = sjcl.bitArray.swapEndian(bits);
- }
- var bit = new sjcl.bn(Math.pow(2, this.field.prototype.exponent)),
- y = sjcl.bn.fromBits(bits);
- if (y.greaterEquals(bit)) {
- y.subM(bit);
- bit = 1;
- } else {
- bit = 0;
- }
- p = this.recoverPt(y);
- if (!p.x.fullReduce().mod(2).equals(bit)) {
- p = p.negate();
- }
- } else {
- throw new sjcl.exception.corrupt("not on the curve!");
- }
- if (!p.isValid()) {
- throw new sjcl.exception.corrupt("not on the curve!");
- }
- return p;
- },
- /**
- * Recovers the x value from y.
- *
- * @param {bigInt} y The y value.
- * @return {sjcl.ecc.point}
- */
- recoverPt: function(y) {
- // a = -1
- // x = sqrt((y^2 - 1) * inv(d * y^2 - a))
- y = new this.field(y);
- yy = y.square();
- return new sjcl.ecc.tEdPoint(this, yy.sub(1).mul(this.d.mul(yy).add(1).inverse()).sqrtMod().fullReduce(), y);
- },
- /**
- * Creates a deterministic random point in constant time.
- * Uses elligator
- *
- * @param {bigInt} num A number 0 <= x < sjcl.ecc.tEdCurve.field.modulus.
- * @return {sjcl.ecc.tEdPoint} A deterministic random point.
- */
- deterministicRandomPoint: function (data) {
- var p;
- if (!this.canDeterministicRandomPoint()) {
- throw("sjcl.ecc.tEdCurve.deterministicRandomPoint(): Curve can't create a deterministic random point in constant time");
- }
- return p;
- },
- /**
- * Determines if the curve can use elligator.
- *
- * @return {Bool} True if curve can use elligator.
- */
- canDeterministicRandomPoint: function () {
- return false;
- // return this.order2P !== undefined;
- }
- };
- sjcl.ecc.curves = {
- c192: new sjcl.ecc.curve(
- sjcl.bn.prime.p192,
- "0xffffffffffffffffffffffff99def836146bc9b1b4d22831",
- -3,
- "0x64210519e59c80e70fa7e9ab72243049feb8deecc146b9b1",
- "0x188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012",
- "0x07192b95ffc8da78631011ed6b24cdd573f977a11e794811",
- "0x2","0x2df5fa08ab474e8f8f2ad5caca8264347d1fb30043214687",
- "0x3","0x64fc66b7c0f932d5564fa514b3ba7858c8ee083f8c728022"),
- c224: new sjcl.ecc.curve(
- sjcl.bn.prime.p224,
- "0xffffffffffffffffffffffffffff16a2e0b8f03e13dd29455c5c2a3d",
- -3,
- "0xb4050a850c04b3abf54132565044b0b7d7bfd8ba270b39432355ffb4",
- "0xb70e0cbd6bb4bf7f321390b94a03c1d356c21122343280d6115c1d21",
- "0xbd376388b5f723fb4c22dfe6cd4375a05a07476444d5819985007e34",
- "0x3","0x7cac269c67bd55ea14efff4eadefe5e74978514af14c88fab46ec046",
- "0x5","0x725c51c9ec2d0e1eb2dbc219f8d67054e02eda5b8431629fe0c0ec8b"),
- c256: new sjcl.ecc.curve(
- sjcl.bn.prime.p256,
- "0xffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551",
- -3,
- "0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b",
- "0x6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296",
- "0x4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5",
- "0x5","0x459243b9aa581806fe913bce99817ade11ca503c64d9a3c533415c083248fbcc",
- "0x6","0x36b24c2c54250ac2466985e533720047dcd102b80fe7c0e9220d5128828223cb"),
- c384: new sjcl.ecc.curve(
- sjcl.bn.prime.p384,
- "0xffffffffffffffffffffffffffffffffffffffffffffffffc7634d81f4372ddf581a0db248b0a77aecec196accc52973",
- -3,
- "0xb3312fa7e23ee7e4988e056be3f82d19181d9c6efe8141120314088f5013875ac656398d8a2ed19d2a85c8edd3ec2aef",
- "0xaa87ca22be8b05378eb1c71ef320ad746e1d3b628ba79b9859f741e082542a385502f25dbf55296c3a545e3872760ab7",
- "0x3617de4a96262c6f5d9e98bf9292dc29f8f41dbd289a147ce9da3113b5f0b8c00a60b1ce1d7e819d7a431d7c90ea0e5f",
- "0x2","0x732152442fb6ee5c3e6ce1d920c059bc623563814d79042b903ce60f1d4487fccd450a86da03f3e6ed525d02017bfdb3",
- "0x3","0x6660041b1c7984620e8d7fd7ccdb50cc3ba816da14d41a4d8affaba8488867f0ca5a24f8d42dd7e44b530a27dc5b58da"),
- c521: new sjcl.ecc.curve(
- sjcl.bn.prime.p521,
- "0x1FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFA51868783BF2F966B7FCC0148F709A5D03BB5C9B8899C47AEBB6FB71E91386409",
- -3,
- "0x051953EB9618E1C9A1F929A21A0B68540EEA2DA725B99B315F3B8B489918EF109E156193951EC7E937B1652C0BD3BB1BF073573DF883D2C34F1EF451FD46B503F00",
- "0xC6858E06B70404E9CD9E3ECB662395B4429C648139053FB521F828AF606B4D3DBAA14B5E77EFE75928FE1DC127A2FFA8DE3348B3C1856A429BF97E7E31C2E5BD66",
- "0x11839296A789A3BC0045C8A5FB42C7D1BD998F54449579B446817AFBD17273E662C97EE72995EF42640C550B9013FAD0761353C7086A272C24088BE94769FD16650",
- "0x2","0xd9254fdf800496acb33790b103c5ee9fac12832fe546c632225b0f7fce3da4574b1a879b623d722fa8fc34d5fc2a8731aad691a9a8bb8b554c95a051d6aa505acf",
- "0x4","0x3eae97c9f1965bfeb023757973f48b400405b8b2741c47a8839cb83cfdee4aea8b729ca7a63034b4055e124dfb8bb8058b74b4aee5d42e5741ec130466549d7e27"),
- k192: new sjcl.ecc.curve(
- sjcl.bn.prime.p192k,
- "0xfffffffffffffffffffffffe26f2fc170f69466a74defd8d",
- 0,
- 3,
- "0xdb4ff10ec057e9ae26b07d0280b7f4341da5d1b1eae06c7d",
- "0x9b2f2f6d9c5628a7844163d015be86344082aa88d95e2f9d",
- "0x3","0xc13d09285ad3c2891f1318edf676acb26d65aaecc45fdbf",
- "0x5","0x231585f0375e78018e41d7a0a1c1ab087a0851ebd58dc1f0"),
- k224: new sjcl.ecc.curve(
- sjcl.bn.prime.p224k,
- "0x010000000000000000000000000001dce8d2ec6184caf0a971769fb1f7",
- 0,
- 5,
- "0xa1455b334df099df30fc28a169a467e9e47075a90f7e650eb6b7a45c",
- "0x7e089fed7fba344282cafbd6f7e319f7c0b0bd59e2ca4bdb556d61a5",
- "0x2","0x16c4805dc7abc9a9c59dd8fb4d9d379d3bd4f4a2e9beb766d4d999ab",
- "0x4","0x7f7a7ae1abee58fb26ffec3765dd846b9fec0bd24fdeb8383ff49c9"),
- k256: new sjcl.ecc.curve(
- sjcl.bn.prime.p256k,
- "0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141",
- 0,
- 7,
- "0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798",
- "0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8",
- "0x2","0x66fbe727b2ba09e09f5a98d70a5efce8424c5fa425bbda1c511f860657b8535e",
- "0x3","0x2f233395c8b07a3834a0e59bda43944b5df378852e560ebc0f22877e9f49bb4b"),
- ed25519: new sjcl.ecc.tEdCurve(
- sjcl.bn.prime.p25519,
- "0x1000000000000000000000000000000014def9dea2f79cd65812631a5cf5d3ed",
- "0x52036cee2b6ffe738cc740797779e89800700a4d4141d8ab75eb4dca135978a3",
- "0x216936d3cd6e53fec0a4e231fdd6dc5c692cc7609525a7b2c9562d608f25d51a",
- "0x6666666666666666666666666666666666666666666666666666666666666658",
- "0x6fe31a937f53b0714daaa6d39e2975afa4564f8c5508aa235bf5acbd527f9b28","0x1a",
- "0x6b1b681577e2349d5ea02296162c66ef40b529560c69a20cd52c69e793baba86","0x25",
- 0,"0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffec")
- };
- sjcl.ecc.curveName = function (curve) {
- var curcurve;
- for (curcurve in sjcl.ecc.curves) {
- if (sjcl.ecc.curves.hasOwnProperty(curcurve)) {
- if (sjcl.ecc.curves[curcurve] === curve) {
- return curcurve;
- }
- }
- }
- throw new sjcl.exception.invalid("no such curve");
- };
- sjcl.ecc.deserialize = function (key) {
- var types = ["elGamal", "ecdsa"];
- if (!key || !key.curve || !sjcl.ecc.curves[key.curve]) { throw new sjcl.exception.invalid("invalid serialization"); }
- if (types.indexOf(key.type) === -1) { throw new sjcl.exception.invalid("invalid type"); }
- var curve = sjcl.ecc.curves[key.curve];
- if (key.secretKey) {
- if (!key.exponent) { throw new sjcl.exception.invalid("invalid exponent"); }
- var exponent = new sjcl.bn(key.exponent);
- return new sjcl.ecc[key.type].secretKey(curve, exponent);
- } else {
- if (!key.point) { throw new sjcl.exception.invalid("invalid point"); }
- var point = curve.fromBits(sjcl.codec.hex.toBits(key.point));
- return new sjcl.ecc[key.type].publicKey(curve, point);
- }
- };
- /** our basicKey classes
- */
- sjcl.ecc.basicKey = {
- /** ecc publicKey.
- * @constructor
- * @param {curve} curve the elliptic curve
- * @param {point} point the point on the curve
- */
- publicKey: function(curve, point) {
- this._curve = curve;
- this._curveBitLength = curve.r.bitLength();
- if (point instanceof Array) {
- this._point = curve.fromBits(point);
- } else {
- this._point = point;
- }
- this.serialize = function () {
- var curveName = sjcl.ecc.curveName(curve);
- return {
- type: this.getType(),
- secretKey: false,
- point: sjcl.codec.hex.fromBits(this._point.toBits()),
- curve: curveName
- };
- };
- /** get this keys point data
- * @return x and y as bitArrays
- */
- this.get = function() {
- var pointbits = this._point.toBits();
- var len = sjcl.bitArray.bitLength(pointbits);
- var x = sjcl.bitArray.bitSlice(pointbits, 0, len/2);
- var y = sjcl.bitArray.bitSlice(pointbits, len/2);
- return { x: x, y: y };
- };
- },
- /** ecc secretKey
- * @constructor
- * @param {curve} curve the elliptic curve
- * @param exponent
- */
- secretKey: function(curve, exponent) {
- this._curve = curve;
- this._curveBitLength = curve.r.bitLength();
- this._exponent = exponent;
- this.serialize = function () {
- var exponent = this.get();
- var curveName = sjcl.ecc.curveName(curve);
- return {
- type: this.getType(),
- secretKey: true,
- exponent: sjcl.codec.hex.fromBits(exponent),
- curve: curveName
- };
- };
- /** get this keys exponent data
- * @return {bitArray} exponent
- */
- this.get = function () {
- return this._exponent.toBits();
- };
- }
- };
- /** @private */
- sjcl.ecc.basicKey.generateKeys = function(cn) {
- return function generateKeys(curve, paranoia, sec) {
- curve = curve || 256;
- if (typeof curve === "number") {
- curve = sjcl.ecc.curves['c'+curve];
- if (curve === undefined) {
- throw new sjcl.exception.invalid("no such curve");
- }
- }
- sec = sec || sjcl.bn.random(curve.r, paranoia);
- var pub = curve.G.mult(sec);
- return { pub: new sjcl.ecc[cn].publicKey(curve, pub),
- sec: new sjcl.ecc[cn].secretKey(curve, sec) };
- };
- };
- /** elGamal keys */
- sjcl.ecc.elGamal = {
- /** generate keys
- * @function
- * @param curve
- * @param {int} paranoia Paranoia for generation (default 6)
- * @param {secretKey} sec secret Key to use. used to get the publicKey for ones secretKey
- */
- generateKeys: sjcl.ecc.basicKey.generateKeys("elGamal"),
- /** elGamal publicKey.
- * @constructor
- * @augments sjcl.ecc.basicKey.publicKey
- */
- publicKey: function (curve, point) {
- sjcl.ecc.basicKey.publicKey.apply(this, arguments);
- },
- /** elGamal secretKey
- * @constructor
- * @augments sjcl.ecc.basicKey.secretKey
- */
- secretKey: function (curve, exponent) {
- sjcl.ecc.basicKey.secretKey.apply(this, arguments);
- }
- };
- sjcl.ecc.elGamal.publicKey.prototype = {
- /** Kem function of elGamal Public Key
- * @param paranoia paranoia to use for randomization.
- * @return {object} key and tag. unkem(tag) with the corresponding secret key results in the key returned.
- */
- kem: function(paranoia) {
- var sec = sjcl.bn.random(this._curve.r, paranoia),
- tag = this._curve.G.mult(sec).toBits(),
- key = sjcl.hash.sha256.hash(this._point.mult(sec).toBits());
- return { key: key, tag: tag };
- },
- getType: function() {
- return "elGamal";
- }
- };
- sjcl.ecc.elGamal.secretKey.prototype = {
- /** UnKem function of elGamal Secret Key
- * @param {bitArray} tag The Tag to decrypt.
- * @return {bitArray} decrypted key.
- */
- unkem: function(tag) {
- return sjcl.hash.sha256.hash(this._curve.fromBits(tag).mult(this._exponent).toBits());
- },
- /** Diffie-Hellmann function
- * @param {elGamal.publicKey} pk The Public Key to do Diffie-Hellmann with
- * @return {bitArray} diffie-hellmann result for this key combination.
- */
- dh: function(pk) {
- return sjcl.hash.sha256.hash(pk._point.mult(this._exponent).toBits());
- },
- /** Diffie-Hellmann function, compatible with Java generateSecret
- * @param {elGamal.publicKey} pk The Public Key to do Diffie-Hellmann with
- * @return {bitArray} undigested X value, diffie-hellmann result for this key combination,
- * compatible with Java generateSecret().
- */
- dhJavaEc: function(pk) {
- return pk._point.mult(this._exponent).x.toBits();
- },
- getType: function() {
- return "elGamal";
- }
- };
- /** ecdsa keys */
- sjcl.ecc.ecdsa = {
- /** generate keys
- * @function
- * @param curve
- * @param {int} paranoia Paranoia for generation (default 6)
- * @param {secretKey} sec secret Key to use. used to get the publicKey for ones secretKey
- */
- generateKeys: sjcl.ecc.basicKey.generateKeys("ecdsa")
- };
- /** ecdsa publicKey.
- * @constructor
- * @augments sjcl.ecc.basicKey.publicKey
- */
- sjcl.ecc.ecdsa.publicKey = function (curve, point) {
- sjcl.ecc.basicKey.publicKey.apply(this, arguments);
- };
- /** specific functions for ecdsa publicKey. */
- sjcl.ecc.ecdsa.publicKey.prototype = {
- /** Diffie-Hellmann function
- * @param {bitArray} hash hash to verify.
- * @param {bitArray} rs signature bitArray.
- * @param {boolean} fakeLegacyVersion use old legacy version
- */
- verify: function(hash, rs, fakeLegacyVersion) {
- if (sjcl.bitArray.bitLength(hash) > this._curveBitLength) {
- hash = sjcl.bitArray.clamp(hash, this._curveBitLength);
- }
- var w = sjcl.bitArray,
- R = this._curve.r,
- l = this._curveBitLength,
- r = sjcl.bn.fromBits(w.bitSlice(rs,0,l)),
- ss = sjcl.bn.fromBits(w.bitSlice(rs,l,2*l)),
- s = fakeLegacyVersion ? ss : ss.inverseMod(R),
- hG = sjcl.bn.fromBits(hash).mul(s).mod(R),
- hA = r.mul(s).mod(R),
- r2 = this._curve.G.mult2(hG, hA, this._point).x;
- if (r.equals(0) || ss.equals(0) || r.greaterEquals(R) || ss.greaterEquals(R) || !r2.equals(r)) {
- if (fakeLegacyVersion === undefined) {
- return this.verify(hash, rs, true);
- } else {
- throw (new sjcl.exception.corrupt("signature didn't check out"));
- }
- }
- return true;
- },
- getType: function() {
- return "ecdsa";
- }
- };
- /** ecdsa secretKey
- * @constructor
- * @augments sjcl.ecc.basicKey.publicKey
- */
- sjcl.ecc.ecdsa.secretKey = function (curve, exponent) {
- sjcl.ecc.basicKey.secretKey.apply(this, arguments);
- };
- /** specific functions for ecdsa secretKey. */
- sjcl.ecc.ecdsa.secretKey.prototype = {
- /** Diffie-Hellmann function
- * @param {bitArray} hash hash to sign.
- * @param {int} paranoia paranoia for random number generation
- * @param {boolean} fakeLegacyVersion use old legacy version
- */
- sign: function(hash, paranoia, fakeLegacyVersion, fixedKForTesting) {
- if (sjcl.bitArray.bitLength(hash) > this._curveBitLength) {
- hash = sjcl.bitArray.clamp(hash, this._curveBitLength);
- }
- var R = this._curve.r,
- l = R.bitLength(),
- k = fixedKForTesting || sjcl.bn.random(R.sub(1), paranoia).add(1),
- r = this._curve.G.mult(k).x.mod(R),
- ss = sjcl.bn.fromBits(hash).add(r.mul(this._exponent)),
- s = fakeLegacyVersion ? ss.inverseMod(R).mul(k).mod(R)
- : ss.mul(k.inverseMod(R)).mod(R);
- return sjcl.bitArray.concat(r.toBits(l), s.toBits(l));
- },
- getType: function() {
- return "ecdsa";
- }
- };
- // fully compatible with https://github.com/warner/python-spake2
- sjcl.ecc.curves.ed25519.M = sjcl.ecc.curves.ed25519.fromBits(sjcl.codec.hex.toBits("d6305877e6a4e08cbaff4e57326d5a9575c20a4e304b58b7cd30526edf2f0ea4"));
- sjcl.ecc.curves.ed25519.N = sjcl.ecc.curves.ed25519.fromBits(sjcl.codec.hex.toBits("5b4393b59342dc791867774ceeb92152ac7240044410c0c97334f22302025402"));
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement