'use strict';
|
|
var BN = require('bn.js');
|
var utils = require('../utils');
|
var getNAF = utils.getNAF;
|
var getJSF = utils.getJSF;
|
var assert = utils.assert;
|
|
function BaseCurve(type, conf) {
|
this.type = type;
|
this.p = new BN(conf.p, 16);
|
|
// Use Montgomery, when there is no fast reduction for the prime
|
this.red = conf.prime ? BN.red(conf.prime) : BN.mont(this.p);
|
|
// Useful for many curves
|
this.zero = new BN(0).toRed(this.red);
|
this.one = new BN(1).toRed(this.red);
|
this.two = new BN(2).toRed(this.red);
|
|
// Curve configuration, optional
|
this.n = conf.n && new BN(conf.n, 16);
|
this.g = conf.g && this.pointFromJSON(conf.g, conf.gRed);
|
|
// Temporary arrays
|
this._wnafT1 = new Array(4);
|
this._wnafT2 = new Array(4);
|
this._wnafT3 = new Array(4);
|
this._wnafT4 = new Array(4);
|
|
this._bitLength = this.n ? this.n.bitLength() : 0;
|
|
// Generalized Greg Maxwell's trick
|
var adjustCount = this.n && this.p.div(this.n);
|
if (!adjustCount || adjustCount.cmpn(100) > 0) {
|
this.redN = null;
|
} else {
|
this._maxwellTrick = true;
|
this.redN = this.n.toRed(this.red);
|
}
|
}
|
module.exports = BaseCurve;
|
|
BaseCurve.prototype.point = function point() {
|
throw new Error('Not implemented');
|
};
|
|
BaseCurve.prototype.validate = function validate() {
|
throw new Error('Not implemented');
|
};
|
|
BaseCurve.prototype._fixedNafMul = function _fixedNafMul(p, k) {
|
assert(p.precomputed);
|
var doubles = p._getDoubles();
|
|
var naf = getNAF(k, 1, this._bitLength);
|
var I = (1 << (doubles.step + 1)) - (doubles.step % 2 === 0 ? 2 : 1);
|
I /= 3;
|
|
// Translate into more windowed form
|
var repr = [];
|
var j;
|
var nafW;
|
for (j = 0; j < naf.length; j += doubles.step) {
|
nafW = 0;
|
for (var l = j + doubles.step - 1; l >= j; l--)
|
nafW = (nafW << 1) + naf[l];
|
repr.push(nafW);
|
}
|
|
var a = this.jpoint(null, null, null);
|
var b = this.jpoint(null, null, null);
|
for (var i = I; i > 0; i--) {
|
for (j = 0; j < repr.length; j++) {
|
nafW = repr[j];
|
if (nafW === i)
|
b = b.mixedAdd(doubles.points[j]);
|
else if (nafW === -i)
|
b = b.mixedAdd(doubles.points[j].neg());
|
}
|
a = a.add(b);
|
}
|
return a.toP();
|
};
|
|
BaseCurve.prototype._wnafMul = function _wnafMul(p, k) {
|
var w = 4;
|
|
// Precompute window
|
var nafPoints = p._getNAFPoints(w);
|
w = nafPoints.wnd;
|
var wnd = nafPoints.points;
|
|
// Get NAF form
|
var naf = getNAF(k, w, this._bitLength);
|
|
// Add `this`*(N+1) for every w-NAF index
|
var acc = this.jpoint(null, null, null);
|
for (var i = naf.length - 1; i >= 0; i--) {
|
// Count zeroes
|
for (var l = 0; i >= 0 && naf[i] === 0; i--)
|
l++;
|
if (i >= 0)
|
l++;
|
acc = acc.dblp(l);
|
|
if (i < 0)
|
break;
|
var z = naf[i];
|
assert(z !== 0);
|
if (p.type === 'affine') {
|
// J +- P
|
if (z > 0)
|
acc = acc.mixedAdd(wnd[(z - 1) >> 1]);
|
else
|
acc = acc.mixedAdd(wnd[(-z - 1) >> 1].neg());
|
} else {
|
// J +- J
|
if (z > 0)
|
acc = acc.add(wnd[(z - 1) >> 1]);
|
else
|
acc = acc.add(wnd[(-z - 1) >> 1].neg());
|
}
|
}
|
return p.type === 'affine' ? acc.toP() : acc;
|
};
|
|
BaseCurve.prototype._wnafMulAdd = function _wnafMulAdd(defW,
|
points,
|
coeffs,
|
len,
|
jacobianResult) {
|
var wndWidth = this._wnafT1;
|
var wnd = this._wnafT2;
|
var naf = this._wnafT3;
|
|
// Fill all arrays
|
var max = 0;
|
var i;
|
var j;
|
var p;
|
for (i = 0; i < len; i++) {
|
p = points[i];
|
var nafPoints = p._getNAFPoints(defW);
|
wndWidth[i] = nafPoints.wnd;
|
wnd[i] = nafPoints.points;
|
}
|
|
// Comb small window NAFs
|
for (i = len - 1; i >= 1; i -= 2) {
|
var a = i - 1;
|
var b = i;
|
if (wndWidth[a] !== 1 || wndWidth[b] !== 1) {
|
naf[a] = getNAF(coeffs[a], wndWidth[a], this._bitLength);
|
naf[b] = getNAF(coeffs[b], wndWidth[b], this._bitLength);
|
max = Math.max(naf[a].length, max);
|
max = Math.max(naf[b].length, max);
|
continue;
|
}
|
|
var comb = [
|
points[a], /* 1 */
|
null, /* 3 */
|
null, /* 5 */
|
points[b], /* 7 */
|
];
|
|
// Try to avoid Projective points, if possible
|
if (points[a].y.cmp(points[b].y) === 0) {
|
comb[1] = points[a].add(points[b]);
|
comb[2] = points[a].toJ().mixedAdd(points[b].neg());
|
} else if (points[a].y.cmp(points[b].y.redNeg()) === 0) {
|
comb[1] = points[a].toJ().mixedAdd(points[b]);
|
comb[2] = points[a].add(points[b].neg());
|
} else {
|
comb[1] = points[a].toJ().mixedAdd(points[b]);
|
comb[2] = points[a].toJ().mixedAdd(points[b].neg());
|
}
|
|
var index = [
|
-3, /* -1 -1 */
|
-1, /* -1 0 */
|
-5, /* -1 1 */
|
-7, /* 0 -1 */
|
0, /* 0 0 */
|
7, /* 0 1 */
|
5, /* 1 -1 */
|
1, /* 1 0 */
|
3, /* 1 1 */
|
];
|
|
var jsf = getJSF(coeffs[a], coeffs[b]);
|
max = Math.max(jsf[0].length, max);
|
naf[a] = new Array(max);
|
naf[b] = new Array(max);
|
for (j = 0; j < max; j++) {
|
var ja = jsf[0][j] | 0;
|
var jb = jsf[1][j] | 0;
|
|
naf[a][j] = index[(ja + 1) * 3 + (jb + 1)];
|
naf[b][j] = 0;
|
wnd[a] = comb;
|
}
|
}
|
|
var acc = this.jpoint(null, null, null);
|
var tmp = this._wnafT4;
|
for (i = max; i >= 0; i--) {
|
var k = 0;
|
|
while (i >= 0) {
|
var zero = true;
|
for (j = 0; j < len; j++) {
|
tmp[j] = naf[j][i] | 0;
|
if (tmp[j] !== 0)
|
zero = false;
|
}
|
if (!zero)
|
break;
|
k++;
|
i--;
|
}
|
if (i >= 0)
|
k++;
|
acc = acc.dblp(k);
|
if (i < 0)
|
break;
|
|
for (j = 0; j < len; j++) {
|
var z = tmp[j];
|
p;
|
if (z === 0)
|
continue;
|
else if (z > 0)
|
p = wnd[j][(z - 1) >> 1];
|
else if (z < 0)
|
p = wnd[j][(-z - 1) >> 1].neg();
|
|
if (p.type === 'affine')
|
acc = acc.mixedAdd(p);
|
else
|
acc = acc.add(p);
|
}
|
}
|
// Zeroify references
|
for (i = 0; i < len; i++)
|
wnd[i] = null;
|
|
if (jacobianResult)
|
return acc;
|
else
|
return acc.toP();
|
};
|
|
function BasePoint(curve, type) {
|
this.curve = curve;
|
this.type = type;
|
this.precomputed = null;
|
}
|
BaseCurve.BasePoint = BasePoint;
|
|
BasePoint.prototype.eq = function eq(/*other*/) {
|
throw new Error('Not implemented');
|
};
|
|
BasePoint.prototype.validate = function validate() {
|
return this.curve.validate(this);
|
};
|
|
BaseCurve.prototype.decodePoint = function decodePoint(bytes, enc) {
|
bytes = utils.toArray(bytes, enc);
|
|
var len = this.p.byteLength();
|
|
// uncompressed, hybrid-odd, hybrid-even
|
if ((bytes[0] === 0x04 || bytes[0] === 0x06 || bytes[0] === 0x07) &&
|
bytes.length - 1 === 2 * len) {
|
if (bytes[0] === 0x06)
|
assert(bytes[bytes.length - 1] % 2 === 0);
|
else if (bytes[0] === 0x07)
|
assert(bytes[bytes.length - 1] % 2 === 1);
|
|
var res = this.point(bytes.slice(1, 1 + len),
|
bytes.slice(1 + len, 1 + 2 * len));
|
|
return res;
|
} else if ((bytes[0] === 0x02 || bytes[0] === 0x03) &&
|
bytes.length - 1 === len) {
|
return this.pointFromX(bytes.slice(1, 1 + len), bytes[0] === 0x03);
|
}
|
throw new Error('Unknown point format');
|
};
|
|
BasePoint.prototype.encodeCompressed = function encodeCompressed(enc) {
|
return this.encode(enc, true);
|
};
|
|
BasePoint.prototype._encode = function _encode(compact) {
|
var len = this.curve.p.byteLength();
|
var x = this.getX().toArray('be', len);
|
|
if (compact)
|
return [ this.getY().isEven() ? 0x02 : 0x03 ].concat(x);
|
|
return [ 0x04 ].concat(x, this.getY().toArray('be', len));
|
};
|
|
BasePoint.prototype.encode = function encode(enc, compact) {
|
return utils.encode(this._encode(compact), enc);
|
};
|
|
BasePoint.prototype.precompute = function precompute(power) {
|
if (this.precomputed)
|
return this;
|
|
var precomputed = {
|
doubles: null,
|
naf: null,
|
beta: null,
|
};
|
precomputed.naf = this._getNAFPoints(8);
|
precomputed.doubles = this._getDoubles(4, power);
|
precomputed.beta = this._getBeta();
|
this.precomputed = precomputed;
|
|
return this;
|
};
|
|
BasePoint.prototype._hasDoubles = function _hasDoubles(k) {
|
if (!this.precomputed)
|
return false;
|
|
var doubles = this.precomputed.doubles;
|
if (!doubles)
|
return false;
|
|
return doubles.points.length >= Math.ceil((k.bitLength() + 1) / doubles.step);
|
};
|
|
BasePoint.prototype._getDoubles = function _getDoubles(step, power) {
|
if (this.precomputed && this.precomputed.doubles)
|
return this.precomputed.doubles;
|
|
var doubles = [ this ];
|
var acc = this;
|
for (var i = 0; i < power; i += step) {
|
for (var j = 0; j < step; j++)
|
acc = acc.dbl();
|
doubles.push(acc);
|
}
|
return {
|
step: step,
|
points: doubles,
|
};
|
};
|
|
BasePoint.prototype._getNAFPoints = function _getNAFPoints(wnd) {
|
if (this.precomputed && this.precomputed.naf)
|
return this.precomputed.naf;
|
|
var res = [ this ];
|
var max = (1 << wnd) - 1;
|
var dbl = max === 1 ? null : this.dbl();
|
for (var i = 1; i < max; i++)
|
res[i] = res[i - 1].add(dbl);
|
return {
|
wnd: wnd,
|
points: res,
|
};
|
};
|
|
BasePoint.prototype._getBeta = function _getBeta() {
|
return null;
|
};
|
|
BasePoint.prototype.dblp = function dblp(k) {
|
var r = this;
|
for (var i = 0; i < k; i++)
|
r = r.dbl();
|
return r;
|
};
|
