diff options
Diffstat (limited to 'node_modules/public-encrypt')
36 files changed, 4599 insertions, 0 deletions
diff --git a/node_modules/public-encrypt/.travis.yml b/node_modules/public-encrypt/.travis.yml new file mode 100644 index 0000000..1b72666 --- /dev/null +++ b/node_modules/public-encrypt/.travis.yml @@ -0,0 +1,6 @@ +language: node_js +node_js: + - "0.10" + - "0.11" + - "0.12" + - iojs
\ No newline at end of file diff --git a/node_modules/public-encrypt/LICENSE b/node_modules/public-encrypt/LICENSE new file mode 100644 index 0000000..c9ddc0f --- /dev/null +++ b/node_modules/public-encrypt/LICENSE @@ -0,0 +1,19 @@ +Copyright (c) 2017 Calvin Metcalf + +Permission is hereby granted, free of charge, to any person obtaining a copy +of this software and associated documentation files (the "Software"), to deal +in the Software without restriction, including without limitation the rights +to use, copy, modify, merge, publish, distribute, sublicense, and/or sell +copies of the Software, and to permit persons to whom the Software is +furnished to do so, subject to the following conditions: + +The above copyright notice and this permission notice shall be included in all +copies or substantial portions of the Software. + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, +OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE +SOFTWARE. diff --git a/node_modules/public-encrypt/browser.js b/node_modules/public-encrypt/browser.js new file mode 100644 index 0000000..4032f68 --- /dev/null +++ b/node_modules/public-encrypt/browser.js @@ -0,0 +1,10 @@ +exports.publicEncrypt = require('./publicEncrypt') +exports.privateDecrypt = require('./privateDecrypt') + +exports.privateEncrypt = function privateEncrypt (key, buf) { + return exports.publicEncrypt(key, buf, true) +} + +exports.publicDecrypt = function publicDecrypt (key, buf) { + return exports.privateDecrypt(key, buf, true) +} diff --git a/node_modules/public-encrypt/index.js b/node_modules/public-encrypt/index.js new file mode 100644 index 0000000..6ff4014 --- /dev/null +++ b/node_modules/public-encrypt/index.js @@ -0,0 +1,18 @@ +var crypto = require('crypto') +if (typeof crypto.publicEncrypt !== 'function') { + crypto = require('./browser') +} +exports.publicEncrypt = crypto.publicEncrypt +exports.privateDecrypt = crypto.privateDecrypt + +if (typeof crypto.privateEncrypt !== 'function') { + exports.privateEncrypt = require('./browser').privateEncrypt +} else { + exports.privateEncrypt = crypto.privateEncrypt +} + +if (typeof crypto.publicDecrypt !== 'function') { + exports.publicDecrypt = require('./browser').publicDecrypt +} else { + exports.publicDecrypt = crypto.publicDecrypt +} diff --git a/node_modules/public-encrypt/mgf.js b/node_modules/public-encrypt/mgf.js new file mode 100644 index 0000000..b966f31 --- /dev/null +++ b/node_modules/public-encrypt/mgf.js @@ -0,0 +1,19 @@ +var createHash = require('create-hash') +var Buffer = require('safe-buffer').Buffer + +module.exports = function (seed, len) { + var t = Buffer.alloc(0) + var i = 0 + var c + while (t.length < len) { + c = i2ops(i++) + t = Buffer.concat([t, createHash('sha1').update(seed).update(c).digest()]) + } + return t.slice(0, len) +} + +function i2ops (c) { + var out = Buffer.allocUnsafe(4) + out.writeUInt32BE(c, 0) + return out +} diff --git a/node_modules/public-encrypt/node_modules/bn.js/README.md b/node_modules/public-encrypt/node_modules/bn.js/README.md new file mode 100644 index 0000000..370f06d --- /dev/null +++ b/node_modules/public-encrypt/node_modules/bn.js/README.md @@ -0,0 +1,221 @@ +# <img src="./logo.png" alt="bn.js" width="160" height="160" /> + +> BigNum in pure javascript + +[](http://travis-ci.org/indutny/bn.js) + +## Install +`npm install --save bn.js` + +## Usage + +```js +const BN = require('bn.js'); + +var a = new BN('dead', 16); +var b = new BN('101010', 2); + +var res = a.add(b); +console.log(res.toString(10)); // 57047 +``` + +**Note**: decimals are not supported in this library. + +## Notation + +### Prefixes + +There are several prefixes to instructions that affect the way the work. Here +is the list of them in the order of appearance in the function name: + +* `i` - perform operation in-place, storing the result in the host object (on + which the method was invoked). Might be used to avoid number allocation costs +* `u` - unsigned, ignore the sign of operands when performing operation, or + always return positive value. Second case applies to reduction operations + like `mod()`. In such cases if the result will be negative - modulo will be + added to the result to make it positive + +### Postfixes + +The only available postfix at the moment is: + +* `n` - which means that the argument of the function must be a plain JavaScript + Number. Decimals are not supported. + +### Examples + +* `a.iadd(b)` - perform addition on `a` and `b`, storing the result in `a` +* `a.umod(b)` - reduce `a` modulo `b`, returning positive value +* `a.iushln(13)` - shift bits of `a` left by 13 + +## Instructions + +Prefixes/postfixes are put in parens at the of the line. `endian` - could be +either `le` (little-endian) or `be` (big-endian). + +### Utilities + +* `a.clone()` - clone number +* `a.toString(base, length)` - convert to base-string and pad with zeroes +* `a.toNumber()` - convert to Javascript Number (limited to 53 bits) +* `a.toJSON()` - convert to JSON compatible hex string (alias of `toString(16)`) +* `a.toArray(endian, length)` - convert to byte `Array`, and optionally zero + pad to length, throwing if already exceeding +* `a.toArrayLike(type, endian, length)` - convert to an instance of `type`, + which must behave like an `Array` +* `a.toBuffer(endian, length)` - convert to Node.js Buffer (if available). For + compatibility with browserify and similar tools, use this instead: + `a.toArrayLike(Buffer, endian, length)` +* `a.bitLength()` - get number of bits occupied +* `a.zeroBits()` - return number of less-significant consequent zero bits + (example: `1010000` has 4 zero bits) +* `a.byteLength()` - return number of bytes occupied +* `a.isNeg()` - true if the number is negative +* `a.isEven()` - no comments +* `a.isOdd()` - no comments +* `a.isZero()` - no comments +* `a.cmp(b)` - compare numbers and return `-1` (a `<` b), `0` (a `==` b), or `1` (a `>` b) + depending on the comparison result (`ucmp`, `cmpn`) +* `a.lt(b)` - `a` less than `b` (`n`) +* `a.lte(b)` - `a` less than or equals `b` (`n`) +* `a.gt(b)` - `a` greater than `b` (`n`) +* `a.gte(b)` - `a` greater than or equals `b` (`n`) +* `a.eq(b)` - `a` equals `b` (`n`) +* `a.toTwos(width)` - convert to two's complement representation, where `width` is bit width +* `a.fromTwos(width)` - convert from two's complement representation, where `width` is the bit width +* `BN.isBN(object)` - returns true if the supplied `object` is a BN.js instance + +### Arithmetics + +* `a.neg()` - negate sign (`i`) +* `a.abs()` - absolute value (`i`) +* `a.add(b)` - addition (`i`, `n`, `in`) +* `a.sub(b)` - subtraction (`i`, `n`, `in`) +* `a.mul(b)` - multiply (`i`, `n`, `in`) +* `a.sqr()` - square (`i`) +* `a.pow(b)` - raise `a` to the power of `b` +* `a.div(b)` - divide (`divn`, `idivn`) +* `a.mod(b)` - reduct (`u`, `n`) (but no `umodn`) +* `a.divRound(b)` - rounded division + +### Bit operations + +* `a.or(b)` - or (`i`, `u`, `iu`) +* `a.and(b)` - and (`i`, `u`, `iu`, `andln`) (NOTE: `andln` is going to be replaced + with `andn` in future) +* `a.xor(b)` - xor (`i`, `u`, `iu`) +* `a.setn(b)` - set specified bit to `1` +* `a.shln(b)` - shift left (`i`, `u`, `iu`) +* `a.shrn(b)` - shift right (`i`, `u`, `iu`) +* `a.testn(b)` - test if specified bit is set +* `a.maskn(b)` - clear bits with indexes higher or equal to `b` (`i`) +* `a.bincn(b)` - add `1 << b` to the number +* `a.notn(w)` - not (for the width specified by `w`) (`i`) + +### Reduction + +* `a.gcd(b)` - GCD +* `a.egcd(b)` - Extended GCD results (`{ a: ..., b: ..., gcd: ... }`) +* `a.invm(b)` - inverse `a` modulo `b` + +## Fast reduction + +When doing lots of reductions using the same modulo, it might be beneficial to +use some tricks: like [Montgomery multiplication][0], or using special algorithm +for [Mersenne Prime][1]. + +### Reduction context + +To enable this tricks one should create a reduction context: + +```js +var red = BN.red(num); +``` +where `num` is just a BN instance. + +Or: + +```js +var red = BN.red(primeName); +``` + +Where `primeName` is either of these [Mersenne Primes][1]: + +* `'k256'` +* `'p224'` +* `'p192'` +* `'p25519'` + +Or: + +```js +var red = BN.mont(num); +``` + +To reduce numbers with [Montgomery trick][0]. `.mont()` is generally faster than +`.red(num)`, but slower than `BN.red(primeName)`. + +### Converting numbers + +Before performing anything in reduction context - numbers should be converted +to it. Usually, this means that one should: + +* Convert inputs to reducted ones +* Operate on them in reduction context +* Convert outputs back from the reduction context + +Here is how one may convert numbers to `red`: + +```js +var redA = a.toRed(red); +``` +Where `red` is a reduction context created using instructions above + +Here is how to convert them back: + +```js +var a = redA.fromRed(); +``` + +### Red instructions + +Most of the instructions from the very start of this readme have their +counterparts in red context: + +* `a.redAdd(b)`, `a.redIAdd(b)` +* `a.redSub(b)`, `a.redISub(b)` +* `a.redShl(num)` +* `a.redMul(b)`, `a.redIMul(b)` +* `a.redSqr()`, `a.redISqr()` +* `a.redSqrt()` - square root modulo reduction context's prime +* `a.redInvm()` - modular inverse of the number +* `a.redNeg()` +* `a.redPow(b)` - modular exponentiation + +## LICENSE + +This software is licensed under the MIT License. + +Copyright Fedor Indutny, 2015. + +Permission is hereby granted, free of charge, to any person obtaining a +copy of this software and associated documentation files (the +"Software"), to deal in the Software without restriction, including +without limitation the rights to use, copy, modify, merge, publish, +distribute, sublicense, and/or sell copies of the Software, and to permit +persons to whom the Software is furnished to do so, subject to the +following conditions: + +The above copyright notice and this permission notice shall be included +in all copies or substantial portions of the Software. + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS +OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF +MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN +NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, +DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR +OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE +USE OR OTHER DEALINGS IN THE SOFTWARE. + +[0]: https://en.wikipedia.org/wiki/Montgomery_modular_multiplication +[1]: https://en.wikipedia.org/wiki/Mersenne_prime diff --git a/node_modules/public-encrypt/node_modules/bn.js/lib/bn.js b/node_modules/public-encrypt/node_modules/bn.js/lib/bn.js new file mode 100644 index 0000000..855dfa6 --- /dev/null +++ b/node_modules/public-encrypt/node_modules/bn.js/lib/bn.js @@ -0,0 +1,3433 @@ +(function (module, exports) { + 'use strict'; + + // Utils + function assert (val, msg) { + if (!val) throw new Error(msg || 'Assertion failed'); + } + + // Could use `inherits` module, but don't want to move from single file + // architecture yet. + function inherits (ctor, superCtor) { + ctor.super_ = superCtor; + var TempCtor = function () {}; + TempCtor.prototype = superCtor.prototype; + ctor.prototype = new TempCtor(); + ctor.prototype.constructor = ctor; + } + + // BN + + function BN (number, base, endian) { + if (BN.isBN(number)) { + return number; + } + + this.negative = 0; + this.words = null; + this.length = 0; + + // Reduction context + this.red = null; + + if (number !== null) { + if (base === 'le' || base === 'be') { + endian = base; + base = 10; + } + + this._init(number || 0, base || 10, endian || 'be'); + } + } + if (typeof module === 'object') { + module.exports = BN; + } else { + exports.BN = BN; + } + + BN.BN = BN; + BN.wordSize = 26; + + var Buffer; + try { + Buffer = require('buffer').Buffer; + } catch (e) { + } + + BN.isBN = function isBN (num) { + if (num instanceof BN) { + return true; + } + + return num !== null && typeof num === 'object' && + num.constructor.wordSize === BN.wordSize && Array.isArray(num.words); + }; + + BN.max = function max (left, right) { + if (left.cmp(right) > 0) return left; + return right; + }; + + BN.min = function min (left, right) { + if (left.cmp(right) < 0) return left; + return right; + }; + + BN.prototype._init = function init (number, base, endian) { + if (typeof number === 'number') { + return this._initNumber(number, base, endian); + } + + if (typeof number === 'object') { + return this._initArray(number, base, endian); + } + + if (base === 'hex') { + base = 16; + } + assert(base === (base | 0) && base >= 2 && base <= 36); + + number = number.toString().replace(/\s+/g, ''); + var start = 0; + if (number[0] === '-') { + start++; + } + + if (base === 16) { + this._parseHex(number, start); + } else { + this._parseBase(number, base, start); + } + + if (number[0] === '-') { + this.negative = 1; + } + + this.strip(); + + if (endian !== 'le') return; + + this._initArray(this.toArray(), base, endian); + }; + + BN.prototype._initNumber = function _initNumber (number, base, endian) { + if (number < 0) { + this.negative = 1; + number = -number; + } + if (number < 0x4000000) { + this.words = [ number & 0x3ffffff ]; + this.length = 1; + } else if (number < 0x10000000000000) { + this.words = [ + number & 0x3ffffff, + (number / 0x4000000) & 0x3ffffff + ]; + this.length = 2; + } else { + assert(number < 0x20000000000000); // 2 ^ 53 (unsafe) + this.words = [ + number & 0x3ffffff, + (number / 0x4000000) & 0x3ffffff, + 1 + ]; + this.length = 3; + } + + if (endian !== 'le') return; + + // Reverse the bytes + this._initArray(this.toArray(), base, endian); + }; + + BN.prototype._initArray = function _initArray (number, base, endian) { + // Perhaps a Uint8Array + assert(typeof number.length === 'number'); + if (number.length <= 0) { + this.words = [ 0 ]; + this.length = 1; + return this; + } + + this.length = Math.ceil(number.length / 3); + this.words = new Array(this.length); + for (var i = 0; i < this.length; i++) { + this.words[i] = 0; + } + + var j, w; + var off = 0; + if (endian === 'be') { + for (i = number.length - 1, j = 0; i >= 0; i -= 3) { + w = number[i] | (number[i - 1] << 8) | (number[i - 2] << 16); + this.words[j] |= (w << off) & 0x3ffffff; + this.words[j + 1] = (w >>> (26 - off)) & 0x3ffffff; + off += 24; + if (off >= 26) { + off -= 26; + j++; + } + } + } else if (endian === 'le') { + for (i = 0, j = 0; i < number.length; i += 3) { + w = number[i] | (number[i + 1] << 8) | (number[i + 2] << 16); + this.words[j] |= (w << off) & 0x3ffffff; + this.words[j + 1] = (w >>> (26 - off)) & 0x3ffffff; + off += 24; + if (off >= 26) { + off -= 26; + j++; + } + } + } + return this.strip(); + }; + + function parseHex (str, start, end) { + var r = 0; + var len = Math.min(str.length, end); + for (var i = start; i < len; i++) { + var c = str.charCodeAt(i) - 48; + + r <<= 4; + + // 'a' - 'f' + if (c >= 49 && c <= 54) { + r |= c - 49 + 0xa; + + // 'A' - 'F' + } else if (c >= 17 && c <= 22) { + r |= c - 17 + 0xa; + + // '0' - '9' + } else { + r |= c & 0xf; + } + } + return r; + } + + BN.prototype._parseHex = function _parseHex (number, start) { + // Create possibly bigger array to ensure that it fits the number + this.length = Math.ceil((number.length - start) / 6); + this.words = new Array(this.length); + for (var i = 0; i < this.length; i++) { + this.words[i] = 0; + } + + var j, w; + // Scan 24-bit chunks and add them to the number + var off = 0; + for (i = number.length - 6, j = 0; i >= start; i -= 6) { + w = parseHex(number, i, i + 6); + this.words[j] |= (w << off) & 0x3ffffff; + // NOTE: `0x3fffff` is intentional here, 26bits max shift + 24bit hex limb + this.words[j + 1] |= w >>> (26 - off) & 0x3fffff; + off += 24; + if (off >= 26) { + off -= 26; + j++; + } + } + if (i + 6 !== start) { + w = parseHex(number, start, i + 6); + this.words[j] |= (w << off) & 0x3ffffff; + this.words[j + 1] |= w >>> (26 - off) & 0x3fffff; + } + this.strip(); + }; + + function parseBase (str, start, end, mul) { + var r = 0; + var len = Math.min(str.length, end); + for (var i = start; i < len; i++) { + var c = str.charCodeAt(i) - 48; + + r *= mul; + + // 'a' + if (c >= 49) { + r += c - 49 + 0xa; + + // 'A' + } else if (c >= 17) { + r += c - 17 + 0xa; + + // '0' - '9' + } else { + r += c; + } + } + return r; + } + + BN.prototype._parseBase = function _parseBase (number, base, start) { + // Initialize as zero + this.words = [ 0 ]; + this.length = 1; + + // Find length of limb in base + for (var limbLen = 0, limbPow = 1; limbPow <= 0x3ffffff; limbPow *= base) { + limbLen++; + } + limbLen--; + limbPow = (limbPow / base) | 0; + + var total = number.length - start; + var mod = total % limbLen; + var end = Math.min(total, total - mod) + start; + + var word = 0; + for (var i = start; i < end; i += limbLen) { + word = parseBase(number, i, i + limbLen, base); + + this.imuln(limbPow); + if (this.words[0] + word < 0x4000000) { + this.words[0] += word; + } else { + this._iaddn(word); + } + } + + if (mod !== 0) { + var pow = 1; + word = parseBase(number, i, number.length, base); + + for (i = 0; i < mod; i++) { + pow *= base; + } + + this.imuln(pow); + if (this.words[0] + word < 0x4000000) { + this.words[0] += word; + } else { + this._iaddn(word); + } + } + }; + + BN.prototype.copy = function copy (dest) { + dest.words = new Array(this.length); + for (var i = 0; i < this.length; i++) { + dest.words[i] = this.words[i]; + } + dest.length = this.length; + dest.negative = this.negative; + dest.red = this.red; + }; + + BN.prototype.clone = function clone () { + var r = new BN(null); + this.copy(r); + return r; + }; + + BN.prototype._expand = function _expand (size) { + while (this.length < size) { + this.words[this.length++] = 0; + } + return this; + }; + + // Remove leading `0` from `this` + BN.prototype.strip = function strip () { + while (this.length > 1 && this.words[this.length - 1] === 0) { + this.length--; + } + return this._normSign(); + }; + + BN.prototype._normSign = function _normSign () { + // -0 = 0 + if (this.length === 1 && this.words[0] === 0) { + this.negative = 0; + } + return this; + }; + + BN.prototype.inspect = function inspect () { + return (this.red ? '<BN-R: ' : '<BN: ') + this.toString(16) + '>'; + }; + + /* + + var zeros = []; + var groupSizes = []; + var groupBases = []; + + var s = ''; + var i = -1; + while (++i < BN.wordSize) { + zeros[i] = s; + s += '0'; + } + groupSizes[0] = 0; + groupSizes[1] = 0; + groupBases[0] = 0; + groupBases[1] = 0; + var base = 2 - 1; + while (++base < 36 + 1) { + var groupSize = 0; + var groupBase = 1; + while (groupBase < (1 << BN.wordSize) / base) { + groupBase *= base; + groupSize += 1; + } + groupSizes[base] = groupSize; + groupBases[base] = groupBase; + } + + */ + + var zeros = [ + '', + '0', + '00', + '000', + '0000', + '00000', + '000000', + '0000000', + '00000000', + '000000000', + '0000000000', + '00000000000', + '000000000000', + '0000000000000', + '00000000000000', + '000000000000000', + '0000000000000000', + '00000000000000000', + '000000000000000000', + '0000000000000000000', + '00000000000000000000', + '000000000000000000000', + '0000000000000000000000', + '00000000000000000000000', + '000000000000000000000000', + '0000000000000000000000000' + ]; + + var groupSizes = [ + 0, 0, + 25, 16, 12, 11, 10, 9, 8, + 8, 7, 7, 7, 7, 6, 6, + 6, 6, 6, 6, 6, 5, 5, + 5, 5, 5, 5, 5, 5, 5, + 5, 5, 5, 5, 5, 5, 5 + ]; + + var groupBases = [ + 0, 0, + 33554432, 43046721, 16777216, 48828125, 60466176, 40353607, 16777216, + 43046721, 10000000, 19487171, 35831808, 62748517, 7529536, 11390625, + 16777216, 24137569, 34012224, 47045881, 64000000, 4084101, 5153632, + 6436343, 7962624, 9765625, 11881376, 14348907, 17210368, 20511149, + 24300000, 28629151, 33554432, 39135393, 45435424, 52521875, 60466176 + ]; + + BN.prototype.toString = function toString (base, padding) { + base = base || 10; + padding = padding | 0 || 1; + + var out; + if (base === 16 || base === 'hex') { + out = ''; + var off = 0; + var carry = 0; + for (var i = 0; i < this.length; i++) { + var w = this.words[i]; + var word = (((w << off) | carry) & 0xffffff).toString(16); + carry = (w >>> (24 - off)) & 0xffffff; + if (carry !== 0 || i !== this.length - 1) { + out = zeros[6 - word.length] + word + out; + } else { + out = word + out; + } + off += 2; + if (off >= 26) { + off -= 26; + i--; + } + } + if (carry !== 0) { + out = carry.toString(16) + out; + } + while (out.length % padding !== 0) { + out = '0' + out; + } + if (this.negative !== 0) { + out = '-' + out; + } + return out; + } + + if (base === (base | 0) && base >= 2 && base <= 36) { + // var groupSize = Math.floor(BN.wordSize * Math.LN2 / Math.log(base)); + var groupSize = groupSizes[base]; + // var groupBase = Math.pow(base, groupSize); + var groupBase = groupBases[base]; + out = ''; + var c = this.clone(); + c.negative = 0; + while (!c.isZero()) { + var r = c.modn(groupBase).toString(base); + c = c.idivn(groupBase); + + if (!c.isZero()) { + out = zeros[groupSize - r.length] + r + out; + } else { + out = r + out; + } + } + if (this.isZero()) { + out = '0' + out; + } + while (out.length % padding !== 0) { + out = '0' + out; + } + if (this.negative !== 0) { + out = '-' + out; + } + return out; + } + + assert(false, 'Base should be between 2 and 36'); + }; + + BN.prototype.toNumber = function toNumber () { + var ret = this.words[0]; + if (this.length === 2) { + ret += this.words[1] * 0x4000000; + } else if (this.length === 3 && this.words[2] === 0x01) { + // NOTE: at this stage it is known that the top bit is set + ret += 0x10000000000000 + (this.words[1] * 0x4000000); + } else if (this.length > 2) { + assert(false, 'Number can only safely store up to 53 bits'); + } + return (this.negative !== 0) ? -ret : ret; + }; + + BN.prototype.toJSON = function toJSON () { + return this.toString(16); + }; + + BN.prototype.toBuffer = function toBuffer (endian, length) { + assert(typeof Buffer !== 'undefined'); + return this.toArrayLike(Buffer, endian, length); + }; + + BN.prototype.toArray = function toArray (endian, length) { + return this.toArrayLike(Array, endian, length); + }; + + BN.prototype.toArrayLike = function toArrayLike (ArrayType, endian, length) { + var byteLength = this.byteLength(); + var reqLength = length || Math.max(1, byteLength); + assert(byteLength <= reqLength, 'byte array longer than desired length'); + assert(reqLength > 0, 'Requested array length <= 0'); + + this.strip(); + var littleEndian = endian === 'le'; + var res = new ArrayType(reqLength); + + var b, i; + var q = this.clone(); + if (!littleEndian) { + // Assume big-endian + for (i = 0; i < reqLength - byteLength; i++) { + res[i] = 0; + } + + for (i = 0; !q.isZero(); i++) { + b = q.andln(0xff); + q.iushrn(8); + + res[reqLength - i - 1] = b; + } + } else { + for (i = 0; !q.isZero(); i++) { + b = q.andln(0xff); + q.iushrn(8); + + res[i] = b; + } + + for (; i < reqLength; i++) { + res[i] = 0; + } + } + + return res; + }; + + if (Math.clz32) { + BN.prototype._countBits = function _countBits (w) { + return 32 - Math.clz32(w); + }; + } else { + BN.prototype._countBits = function _countBits (w) { + var t = w; + var r = 0; + if (t >= 0x1000) { + r += 13; + t >>>= 13; + } + if (t >= 0x40) { + r += 7; + t >>>= 7; + } + if (t >= 0x8) { + r += 4; + t >>>= 4; + } + if (t >= 0x02) { + r += 2; + t >>>= 2; + } + return r + t; + }; + } + + BN.prototype._zeroBits = function _zeroBits (w) { + // Short-cut + if (w === 0) return 26; + + var t = w; + var r = 0; + if ((t & 0x1fff) === 0) { + r += 13; + t >>>= 13; + } + if ((t & 0x7f) === 0) { + r += 7; + t >>>= 7; + } + if ((t & 0xf) === 0) { + r += 4; + t >>>= 4; + } + if ((t & 0x3) === 0) { + r += 2; + t >>>= 2; + } + if ((t & 0x1) === 0) { + r++; + } + return r; + }; + + // Return number of used bits in a BN + BN.prototype.bitLength = function bitLength () { + var w = this.words[this.length - 1]; + var hi = this._countBits(w); + return (this.length - 1) * 26 + hi; + }; + + function toBitArray (num) { + var w = new Array(num.bitLength()); + + for (var bit = 0; bit < w.length; bit++) { + var off = (bit / 26) | 0; + var wbit = bit % 26; + + w[bit] = (num.words[off] & (1 << wbit)) >>> wbit; + } + + return w; + } + + // Number of trailing zero bits + BN.prototype.zeroBits = function zeroBits () { + if (this.isZero()) return 0; + + var r = 0; + for (var i = 0; i < this.length; i++) { + var b = this._zeroBits(this.words[i]); + r += b; + if (b !== 26) break; + } + return r; + }; + + BN.prototype.byteLength = function byteLength () { + return Math.ceil(this.bitLength() / 8); + }; + + BN.prototype.toTwos = function toTwos (width) { + if (this.negative !== 0) { + return this.abs().inotn(width).iaddn(1); + } + return this.clone(); + }; + + BN.prototype.fromTwos = function fromTwos (width) { + if (this.testn(width - 1)) { + return this.notn(width).iaddn(1).ineg(); + } + return this.clone(); + }; + + BN.prototype.isNeg = function isNeg () { + return this.negative !== 0; + }; + + // Return negative clone of `this` + BN.prototype.neg = function neg () { + return this.clone().ineg(); + }; + + BN.prototype.ineg = function ineg () { + if (!this.isZero()) { + this.negative ^= 1; + } + + return this; + }; + + // Or `num` with `this` in-place + BN.prototype.iuor = function iuor (num) { + while (this.length < num.length) { + this.words[this.length++] = 0; + } + + for (var i = 0; i < num.length; i++) { + this.words[i] = this.words[i] | num.words[i]; + } + + return this.strip(); + }; + + BN.prototype.ior = function ior (num) { + assert((this.negative | num.negative) === 0); + return this.iuor(num); + }; + + // Or `num` with `this` + BN.prototype.or = function or (num) { + if (this.length > num.length) return this.clone().ior(num); + return num.clone().ior(this); + }; + + BN.prototype.uor = function uor (num) { + if (this.length > num.length) return this.clone().iuor(num); + return num.clone().iuor(this); + }; + + // And `num` with `this` in-place + BN.prototype.iuand = function iuand (num) { + // b = min-length(num, this) + var b; + if (this.length > num.length) { + b = num; + } else { + b = this; + } + + for (var i = 0; i < b.length; i++) { + this.words[i] = this.words[i] & num.words[i]; + } + + this.length = b.length; + + return this.strip(); + }; + + BN.prototype.iand = function iand (num) { + assert((this.negative | num.negative) === 0); + return this.iuand(num); + }; + + // And `num` with `this` + BN.prototype.and = function and (num) { + if (this.length > num.length) return this.clone().iand(num); + return num.clone().iand(this); + }; + + BN.prototype.uand = function uand (num) { + if (this.length > num.length) return this.clone().iuand(num); + return num.clone().iuand(this); + }; + + // Xor `num` with `this` in-place + BN.prototype.iuxor = function iuxor (num) { + // a.length > b.length + var a; + var b; + if (this.length > num.length) { + a = this; + b = num; + } else { + a = num; + b = this; + } + + for (var i = 0; i < b.length; i++) { + this.words[i] = a.words[i] ^ b.words[i]; + } + + if (this !== a) { + for (; i < a.length; i++) { + this.words[i] = a.words[i]; + } + } + + this.length = a.length; + + return this.strip(); + }; + + BN.prototype.ixor = function ixor (num) { + assert((this.negative | num.negative) === 0); + return this.iuxor(num); + }; + + // Xor `num` with `this` + BN.prototype.xor = function xor (num) { + if (this.length > num.length) return this.clone().ixor(num); + return num.clone().ixor(this); + }; + + BN.prototype.uxor = function uxor (num) { + if (this.length > num.length) return this.clone().iuxor(num); + return num.clone().iuxor(this); + }; + + // Not ``this`` with ``width`` bitwidth + BN.prototype.inotn = function inotn (width) { + assert(typeof width === 'number' && width >= 0); + + var bytesNeeded = Math.ceil(width / 26) | 0; + var bitsLeft = width % 26; + + // Extend the buffer with leading zeroes + this._expand(bytesNeeded); + + if (bitsLeft > 0) { + bytesNeeded--; + } + + // Handle complete words + for (var i = 0; i < bytesNeeded; i++) { + this.words[i] = ~this.words[i] & 0x3ffffff; + } + + // Handle the residue + if (bitsLeft > 0) { + this.words[i] = ~this.words[i] & (0x3ffffff >> (26 - bitsLeft)); + } + + // And remove leading zeroes + return this.strip(); + }; + + BN.prototype.notn = function notn (width) { + return this.clone().inotn(width); + }; + + // Set `bit` of `this` + BN.prototype.setn = function setn (bit, val) { + assert(typeof bit === 'number' && bit >= 0); + + var off = (bit / 26) | 0; + var wbit = bit % 26; + + this._expand(off + 1); + + if (val) { + this.words[off] = this.words[off] | (1 << wbit); + } else { + this.words[off] = this.words[off] & ~(1 << wbit); + } + + return this.strip(); + }; + + // Add `num` to `this` in-place + BN.prototype.iadd = function iadd (num) { + var r; + + // negative + positive + if (this.negative !== 0 && num.negative === 0) { + this.negative = 0; + r = this.isub(num); + this.negative ^= 1; + return this._normSign(); + + // positive + negative + } else if (this.negative === 0 && num.negative !== 0) { + num.negative = 0; + r = this.isub(num); + num.negative = 1; + return r._normSign(); + } + + // a.length > b.length + var a, b; + if (this.length > num.length) { + a = this; + b = num; + } else { + a = num; + b = this; + } + + var carry = 0; + for (var i = 0; i < b.length; i++) { + r = (a.words[i] | 0) + (b.words[i] | 0) + carry; + this.words[i] = r & 0x3ffffff; + carry = r >>> 26; + } + for (; carry !== 0 && i < a.length; i++) { + r = (a.words[i] | 0) + carry; + this.words[i] = r & 0x3ffffff; + carry = r >>> 26; + } + + this.length = a.length; + if (carry !== 0) { + this.words[this.length] = carry; + this.length++; + // Copy the rest of the words + } else if (a !== this) { + for (; i < a.length; i++) { + this.words[i] = a.words[i]; + } + } + + return this; + }; + + // Add `num` to `this` + BN.prototype.add = function add (num) { + var res; + if (num.negative !== 0 && this.negative === 0) { + num.negative = 0; + res = this.sub(num); + num.negative ^= 1; + return res; + } else if (num.negative === 0 && this.negative !== 0) { + this.negative = 0; + res = num.sub(this); + this.negative = 1; + return res; + } + + if (this.length > num.length) return this.clone().iadd(num); + + return num.clone().iadd(this); + }; + + // Subtract `num` from `this` in-place + BN.prototype.isub = function isub (num) { + // this - (-num) = this + num + if (num.negative !== 0) { + num.negative = 0; + var r = this.iadd(num); + num.negative = 1; + return r._normSign(); + + // -this - num = -(this + num) + } else if (this.negative !== 0) { + this.negative = 0; + this.iadd(num); + this.negative = 1; + return this._normSign(); + } + + // At this point both numbers are positive + var cmp = this.cmp(num); + + // Optimization - zeroify + if (cmp === 0) { + this.negative = 0; + this.length = 1; + this.words[0] = 0; + return this; + } + + // a > b + var a, b; + if (cmp > 0) { + a = this; + b = num; + } else { + a = num; + b = this; + } + + var carry = 0; + for (var i = 0; i < b.length; i++) { + r = (a.words[i] | 0) - (b.words[i] | 0) + carry; + carry = r >> 26; + this.words[i] = r & 0x3ffffff; + } + for (; carry !== 0 && i < a.length; i++) { + r = (a.words[i] | 0) + carry; + carry = r >> 26; + this.words[i] = r & 0x3ffffff; + } + + // Copy rest of the words + if (carry === 0 && i < a.length && a !== this) { + for (; i < a.length; i++) { + this.words[i] = a.words[i]; + } + } + + this.length = Math.max(this.length, i); + + if (a !== this) { + this.negative = 1; + } + + return this.strip(); + }; + + // Subtract `num` from `this` + BN.prototype.sub = function sub (num) { + return this.clone().isub(num); + }; + + function smallMulTo (self, num, out) { + out.negative = num.negative ^ self.negative; + var len = (self.length + num.length) | 0; + out.length = len; + len = (len - 1) | 0; + + // Peel one iteration (compiler can't do it, because of code complexity) + var a = self.words[0] | 0; + var b = num.words[0] | 0; + var r = a * b; + + var lo = r & 0x3ffffff; + var carry = (r / 0x4000000) | 0; + out.words[0] = lo; + + for (var k = 1; k < len; k++) { + // Sum all words with the same `i + j = k` and accumulate `ncarry`, + // note that ncarry could be >= 0x3ffffff + var ncarry = carry >>> 26; + var rword = carry & 0x3ffffff; + var maxJ = Math.min(k, num.length - 1); + for (var j = Math.max(0, k - self.length + 1); j <= maxJ; j++) { + var i = (k - j) | 0; + a = self.words[i] | 0; + b = num.words[j] | 0; + r = a * b + rword; + ncarry += (r / 0x4000000) | 0; + rword = r & 0x3ffffff; + } + out.words[k] = rword | 0; + carry = ncarry | 0; + } + if (carry !== 0) { + out.words[k] = carry | 0; + } else { + out.length--; + } + + return out.strip(); + } + + // TODO(indutny): it may be reasonable to omit it for users who don't need + // to work with 256-bit numbers, otherwise it gives 20% improvement for 256-bit + // multiplication (like elliptic secp256k1). + var comb10MulTo = function comb10MulTo (self, num, out) { + var a = self.words; + var b = num.words; + var o = out.words; + var c = 0; + var lo; + var mid; + var hi; + var a0 = a[0] | 0; + var al0 = a0 & 0x1fff; + var ah0 = a0 >>> 13; + var a1 = a[1] | 0; + var al1 = a1 & 0x1fff; + var ah1 = a1 >>> 13; + var a2 = a[2] | 0; + var al2 = a2 & 0x1fff; + var ah2 = a2 >>> 13; + var a3 = a[3] | 0; + var al3 = a3 & 0x1fff; + var ah3 = a3 >>> 13; + var a4 = a[4] | 0; + var al4 = a4 & 0x1fff; + var ah4 = a4 >>> 13; + var a5 = a[5] | 0; + var al5 = a5 & 0x1fff; + var ah5 = a5 >>> 13; + var a6 = a[6] | 0; + var al6 = a6 & 0x1fff; + var ah6 = a6 >>> 13; + var a7 = a[7] | 0; + var al7 = a7 & 0x1fff; + var ah7 = a7 >>> 13; + var a8 = a[8] | 0; + var al8 = a8 & 0x1fff; + var ah8 = a8 >>> 13; + var a9 = a[9] | 0; + var al9 = a9 & 0x1fff; + var ah9 = a9 >>> 13; + var b0 = b[0] | 0; + var bl0 = b0 & 0x1fff; + var bh0 = b0 >>> 13; + var b1 = b[1] | 0; + var bl1 = b1 & 0x1fff; + var bh1 = b1 >>> 13; + var b2 = b[2] | 0; + var bl2 = b2 & 0x1fff; + var bh2 = b2 >>> 13; + var b3 = b[3] | 0; + var bl3 = b3 & 0x1fff; + var bh3 = b3 >>> 13; + var b4 = b[4] | 0; + var bl4 = b4 & 0x1fff; + var bh4 = b4 >>> 13; + var b5 = b[5] | 0; + var bl5 = b5 & 0x1fff; + var bh5 = b5 >>> 13; + var b6 = b[6] | 0; + var bl6 = b6 & 0x1fff; + var bh6 = b6 >>> 13; + var b7 = b[7] | 0; + var bl7 = b7 & 0x1fff; + var bh7 = b7 >>> 13; + var b8 = b[8] | 0; + var bl8 = b8 & 0x1fff; + var bh8 = b8 >>> 13; + var b9 = b[9] | 0; + var bl9 = b9 & 0x1fff; + var bh9 = b9 >>> 13; + + out.negative = self.negative ^ num.negative; + out.length = 19; + /* k = 0 */ + lo = Math.imul(al0, bl0); + mid = Math.imul(al0, bh0); + mid = (mid + Math.imul(ah0, bl0)) | 0; + hi = Math.imul(ah0, bh0); + var w0 = (((c + lo) | 0) + ((mid & 0x1fff) << 13)) | 0; + c = (((hi + (mid >>> 13)) | 0) + (w0 >>> 26)) | 0; + w0 &= 0x3ffffff; + /* k = 1 */ + lo = Math.imul(al1, bl0); + mid = Math.imul(al1, bh0); + mid = (mid + Math.imul(ah1, bl0)) | 0; + hi = Math.imul(ah1, bh0); + lo = (lo + Math.imul(al0, bl1)) | 0; + mid = (mid + Math.imul(al0, bh1)) | 0; + mid = (mid + Math.imul(ah0, bl1)) | 0; + hi = (hi + Math.imul(ah0, bh1)) | 0; + var w1 = (((c + lo) | 0) + ((mid & 0x1fff) << 13)) | 0; + c = (((hi + (mid >>> 13)) | 0) + (w1 >>> 26)) | 0; + w1 &= 0x3ffffff; + /* k = 2 */ + lo = Math.imul(al2, bl0); + mid = Math.imul(al2, bh0); + mid = (mid + Math.imul(ah2, bl0)) | 0; + hi = Math.imul(ah2, bh0); + lo = (lo + Math.imul(al1, bl1)) | 0; + mid = (mid + Math.imul(al1, bh1)) | 0; + mid = (mid + Math.imul(ah1, bl1)) | 0; + hi = (hi + Math.imul(ah1, bh1)) | 0; + lo = (lo + Math.imul(al0, bl2)) | 0; + mid = (mid + Math.imul(al0, bh2)) | 0; + mid = (mid + Math.imul(ah0, bl2)) | 0; + hi = (hi + Math.imul(ah0, bh2)) | 0; + var w2 = (((c + lo) | 0) + ((mid & 0x1fff) << 13)) | 0; + c = (((hi + (mid >>> 13)) | 0) + (w2 >>> 26)) | 0; + w2 &= 0x3ffffff; + /* k = 3 */ + lo = Math.imul(al3, bl0); + mid = Math.imul(al3, bh0); + mid = (mid + Math.imul(ah3, bl0)) | 0; + hi = Math.imul(ah3, bh0); + lo = (lo + Math.imul(al2, bl1)) | 0; + mid = (mid + Math.imul(al2, bh1)) | 0; + mid = (mid + Math.imul(ah2, bl1)) | 0; + hi = (hi + Math.imul(ah2, bh1)) | 0; + lo = (lo + Math.imul(al1, bl2)) | 0; + mid = (mid + Math.imul(al1, bh2)) | 0; + mid = (mid + Math.imul(ah1, bl2)) | 0; + hi = (hi + Math.imul(ah1, bh2)) | 0; + lo = (lo + Math.imul(al0, bl3)) | 0; + mid = (mid + Math.imul(al0, bh3)) | 0; + mid = (mid + Math.imul(ah0, bl3)) | 0; + hi = (hi + Math.imul(ah0, bh3)) | 0; + var w3 = (((c + lo) | 0) + ((mid & 0x1fff) << 13)) | 0; + c = (((hi + (mid >>> 13)) | 0) + (w3 >>> 26)) | 0; + w3 &= 0x3ffffff; + /* k = 4 */ + lo = Math.imul(al4, bl0); + mid = Math.imul(al4, bh0); + mid = (mid + Math.imul(ah4, bl0)) | 0; + hi = Math.imul(ah4, bh0); + lo = (lo + Math.imul(al3, bl1)) | 0; + mid = (mid + Math.imul(al3, bh1)) | 0; + mid = (mid + Math.imul(ah3, bl1)) | 0; + hi = (hi + Math.imul(ah3, bh1)) | 0; + lo = (lo + Math.imul(al2, bl2)) | 0; + mid = (mid + Math.imul(al2, bh2)) | 0; + mid = (mid + Math.imul(ah2, bl2)) | 0; + hi = (hi + Math.imul(ah2, bh2)) | 0; + lo = (lo + Math.imul(al1, bl3)) | 0; + mid = (mid + Math.imul(al1, bh3)) | 0; + mid = (mid + Math.imul(ah1, bl3)) | 0; + hi = (hi + Math.imul(ah1, bh3)) | 0; + lo = (lo + Math.imul(al0, bl4)) | 0; + mid = (mid + Math.imul(al0, bh4)) | 0; + mid = (mid + Math.imul(ah0, bl4)) | 0; + hi = (hi + Math.imul(ah0, bh4)) | 0; + var w4 = (((c + lo) | 0) + ((mid & 0x1fff) << 13)) | 0; + c = (((hi + (mid >>> 13)) | 0) + (w4 >>> 26)) | 0; + w4 &= 0x3ffffff; + /* k = 5 */ + lo = Math.imul(al5, bl0); + mid = Math.imul(al5, bh0); + mid = (mid + Math.imul(ah5, bl0)) | 0; + hi = Math.imul(ah5, bh0); + lo = (lo + Math.imul(al4, bl1)) | 0; + mid = (mid + Math.imul(al4, bh1)) | 0; + mid = (mid + Math.imul(ah4, bl1)) | 0; + hi = (hi + Math.imul(ah4, bh1)) | 0; + lo = (lo + Math.imul(al3, bl2)) | 0; + mid = (mid + Math.imul(al3, bh2)) | 0; + mid = (mid + Math.imul(ah3, bl2)) | 0; + hi = (hi + Math.imul(ah3, bh2)) | 0; + lo = (lo + Math.imul(al2, bl3)) | 0; + mid = (mid + Math.imul(al2, bh3)) | 0; + mid = (mid + Math.imul(ah2, bl3)) | 0; + hi = (hi + Math.imul(ah2, bh3)) | 0; + lo = (lo + Math.imul(al1, bl4)) | 0; + mid = (mid + Math.imul(al1, bh4)) | 0; + mid = (mid + Math.imul(ah1, bl4)) | 0; + hi = (hi + Math.imul(ah1, bh4)) | 0; + lo = (lo + Math.imul(al0, bl5)) | 0; + mid = (mid + Math.imul(al0, bh5)) | 0; + mid = (mid + Math.imul(ah0, bl5)) | 0; + hi = (hi + Math.imul(ah0, bh5)) | 0; + var w5 = (((c + lo) | 0) + ((mid & 0x1fff) << 13)) | 0; + c = (((hi + (mid >>> 13)) | 0) + (w5 >>> 26)) | 0; + w5 &= 0x3ffffff; + /* k = 6 */ + lo = Math.imul(al6, bl0); + mid = Math.imul(al6, bh0); + mid = (mid + Math.imul(ah6, bl0)) | 0; + hi = Math.imul(ah6, bh0); + lo = (lo + Math.imul(al5, bl1)) | 0; + mid = (mid + Math.imul(al5, bh1)) | 0; + mid = (mid + Math.imul(ah5, bl1)) | 0; + hi = (hi + Math.imul(ah5, bh1)) | 0; + lo = (lo + Math.imul(al4, bl2)) | 0; + mid = (mid + Math.imul(al4, bh2)) | 0; + mid = (mid + Math.imul(ah4, bl2)) | 0; + hi = (hi + Math.imul(ah4, bh2)) | 0; + lo = (lo + Math.imul(al3, bl3)) | 0; + mid = (mid + Math.imul(al3, bh3)) | 0; + mid = (mid + Math.imul(ah3, bl3)) | 0; + hi = (hi + Math.imul(ah3, bh3)) | 0; + lo = (lo + Math.imul(al2, bl4)) | 0; + mid = (mid + Math.imul(al2, bh4)) | 0; + mid = (mid + Math.imul(ah2, bl4)) | 0; + hi = (hi + Math.imul(ah2, bh4)) | 0; + lo = (lo + Math.imul(al1, bl5)) | 0; + mid = (mid + Math.imul(al1, bh5)) | 0; + mid = (mid + Math.imul(ah1, bl5)) | 0; + hi = (hi + Math.imul(ah1, bh5)) | 0; + lo = (lo + Math.imul(al0, bl6)) | 0; + mid = (mid + Math.imul(al0, bh6)) | 0; + mid = (mid + Math.imul(ah0, bl6)) | 0; + hi = (hi + Math.imul(ah0, bh6)) | 0; + var w6 = (((c + lo) | 0) + ((mid & 0x1fff) << 13)) | 0; + c = (((hi + (mid >>> 13)) | 0) + (w6 >>> 26)) | 0; + w6 &= 0x3ffffff; + /* k = 7 */ + lo = Math.imul(al7, bl0); + mid = Math.imul(al7, bh0); + mid = (mid + Math.imul(ah7, bl0)) | 0; + hi = Math.imul(ah7, bh0); + lo = (lo + Math.imul(al6, bl1)) | 0; + mid = (mid + Math.imul(al6, bh1)) | 0; + mid = (mid + Math.imul(ah6, bl1)) | 0; + hi = (hi + Math.imul(ah6, bh1)) | 0; + lo = (lo + Math.imul(al5, bl2)) | 0; + mid = (mid + Math.imul(al5, bh2)) | 0; + mid = (mid + Math.imul(ah5, bl2)) | 0; + hi = (hi + Math.imul(ah5, bh2)) | 0; + lo = (lo + Math.imul(al4, bl3)) | 0; + mid = (mid + Math.imul(al4, bh3)) | 0; + mid = (mid + Math.imul(ah4, bl3)) | 0; + hi = (hi + Math.imul(ah4, bh3)) | 0; + lo = (lo + Math.imul(al3, bl4)) | 0; + mid = (mid + Math.imul(al3, bh4)) | 0; + mid = (mid + Math.imul(ah3, bl4)) | 0; + hi = (hi + Math.imul(ah3, bh4)) | 0; + lo = (lo + Math.imul(al2, bl5)) | 0; + mid = (mid + Math.imul(al2, bh5)) | 0; + mid = (mid + Math.imul(ah2, bl5)) | 0; + hi = (hi + Math.imul(ah2, bh5)) | 0; + lo = (lo + Math.imul(al1, bl6)) | 0; + mid = (mid + Math.imul(al1, bh6)) | 0; + mid = (mid + Math.imul(ah1, bl6)) | 0; + hi = (hi + Math.imul(ah1, bh6)) | 0; + lo = (lo + Math.imul(al0, bl7)) | 0; + mid = (mid + Math.imul(al0, bh7)) | 0; + mid = (mid + Math.imul(ah0, bl7)) | 0; + hi = (hi + Math.imul(ah0, bh7)) | 0; + var w7 = (((c + lo) | 0) + ((mid & 0x1fff) << 13)) | 0; + c = (((hi + (mid >>> 13)) | 0) + (w7 >>> 26)) | 0; + w7 &= 0x3ffffff; + /* k = 8 */ + lo = Math.imul(al8, bl0); + mid = Math.imul(al8, bh0); + mid = (mid + Math.imul(ah8, bl0)) | 0; + hi = Math.imul(ah8, bh0); + lo = (lo + Math.imul(al7, bl1)) | 0; + mid = (mid + Math.imul(al7, bh1)) | 0; + mid = (mid + Math.imul(ah7, bl1)) | 0; + hi = (hi + Math.imul(ah7, bh1)) | 0; + lo = (lo + Math.imul(al6, bl2)) | 0; + mid = (mid + Math.imul(al6, bh2)) | 0; + mid = (mid + Math.imul(ah6, bl2)) | 0; + hi = (hi + Math.imul(ah6, bh2)) | 0; + lo = (lo + Math.imul(al5, bl3)) | 0; + mid = (mid + Math.imul(al5, bh3)) | 0; + mid = (mid + Math.imul(ah5, bl3)) | 0; + hi = (hi + Math.imul(ah5, bh3)) | 0; + lo = (lo + Math.imul(al4, bl4)) | 0; + mid = (mid + Math.imul(al4, bh4)) | 0; + mid = (mid + Math.imul(ah4, bl4)) | 0; + hi = (hi + Math.imul(ah4, bh4)) | 0; + lo = (lo + Math.imul(al3, bl5)) | 0; + mid = (mid + Math.imul(al3, bh5)) | 0; + mid = (mid + Math.imul(ah3, bl5)) | 0; + hi = (hi + Math.imul(ah3, bh5)) | 0; + lo = (lo + Math.imul(al2, bl6)) | 0; + mid = (mid + Math.imul(al2, bh6)) | 0; + mid = (mid + Math.imul(ah2, bl6)) | 0; + hi = (hi + Math.imul(ah2, bh6)) | 0; + lo = (lo + Math.imul(al1, bl7)) | 0; + mid = (mid + Math.imul(al1, bh7)) | 0; + mid = (mid + Math.imul(ah1, bl7)) | 0; + hi = (hi + Math.imul(ah1, bh7)) | 0; + lo = (lo + Math.imul(al0, bl8)) | 0; + mid = (mid + Math.imul(al0, bh8)) | 0; + mid = (mid + Math.imul(ah0, bl8)) | 0; + hi = (hi + Math.imul(ah0, bh8)) | 0; + var w8 = (((c + lo) | 0) + ((mid & 0x1fff) << 13)) | 0; + c = (((hi + (mid >>> 13)) | 0) + (w8 >>> 26)) | 0; + w8 &= 0x3ffffff; + /* k = 9 */ + lo = Math.imul(al9, bl0); + mid = Math.imul(al9, bh0); + mid = (mid + Math.imul(ah9, bl0)) | 0; + hi = Math.imul(ah9, bh0); + lo = (lo + Math.imul(al8, bl1)) | 0; + mid = (mid + Math.imul(al8, bh1)) | 0; + mid = (mid + Math.imul(ah8, bl1)) | 0; + hi = (hi + Math.imul(ah8, bh1)) | 0; + lo = (lo + Math.imul(al7, bl2)) | 0; + mid = (mid + Math.imul(al7, bh2)) | 0; + mid = (mid + Math.imul(ah7, bl2)) | 0; + hi = (hi + Math.imul(ah7, bh2)) | 0; + lo = (lo + Math.imul(al6, bl3)) | 0; + mid = (mid + Math.imul(al6, bh3)) | 0; + mid = (mid + Math.imul(ah6, bl3)) | 0; + hi = (hi + Math.imul(ah6, bh3)) | 0; + lo = (lo + Math.imul(al5, bl4)) | 0; + mid = (mid + Math.imul(al5, bh4)) | 0; + mid = (mid + Math.imul(ah5, bl4)) | 0; + hi = (hi + Math.imul(ah5, bh4)) | 0; + lo = (lo + Math.imul(al4, bl5)) | 0; + mid = (mid + Math.imul(al4, bh5)) | 0; + mid = (mid + Math.imul(ah4, bl5)) | 0; + hi = (hi + Math.imul(ah4, bh5)) | 0; + lo = (lo + Math.imul(al3, bl6)) | 0; + mid = (mid + Math.imul(al3, bh6)) | 0; + mid = (mid + Math.imul(ah3, bl6)) | 0; + hi = (hi + Math.imul(ah3, bh6)) | 0; + lo = (lo + Math.imul(al2, bl7)) | 0; + mid = (mid + Math.imul(al2, bh7)) | 0; + mid = (mid + Math.imul(ah2, bl7)) | 0; + hi = (hi + Math.imul(ah2, bh7)) | 0; + lo = (lo + Math.imul(al1, bl8)) | 0; + mid = (mid + Math.imul(al1, bh8)) | 0; + mid = (mid + Math.imul(ah1, bl8)) | 0; + hi = (hi + Math.imul(ah1, bh8)) | 0; + lo = (lo + Math.imul(al0, bl9)) | 0; + mid = (mid + Math.imul(al0, bh9)) | 0; + mid = (mid + Math.imul(ah0, bl9)) | 0; + hi = (hi + Math.imul(ah0, bh9)) | 0; + var w9 = (((c + lo) | 0) + ((mid & 0x1fff) << 13)) | 0; + c = (((hi + (mid >>> 13)) | 0) + (w9 >>> 26)) | 0; + w9 &= 0x3ffffff; + /* k = 10 */ + lo = Math.imul(al9, bl1); + mid = Math.imul(al9, bh1); + mid = (mid + Math.imul(ah9, bl1)) | 0; + hi = Math.imul(ah9, bh1); + lo = (lo + Math.imul(al8, bl2)) | 0; + mid = (mid + Math.imul(al8, bh2)) | 0; + mid = (mid + Math.imul(ah8, bl2)) | 0; + hi = (hi + Math.imul(ah8, bh2)) | 0; + lo = (lo + Math.imul(al7, bl3)) | 0; + mid = (mid + Math.imul(al7, bh3)) | 0; + mid = (mid + Math.imul(ah7, bl3)) | 0; + hi = (hi + Math.imul(ah7, bh3)) | 0; + lo = (lo + Math.imul(al6, bl4)) | 0; + mid = (mid + Math.imul(al6, bh4)) | 0; + mid = (mid + Math.imul(ah6, bl4)) | 0; + hi = (hi + Math.imul(ah6, bh4)) | 0; + lo = (lo + Math.imul(al5, bl5)) | 0; + mid = (mid + Math.imul(al5, bh5)) | 0; + mid = (mid + Math.imul(ah5, bl5)) | 0; + hi = (hi + Math.imul(ah5, bh5)) | 0; + lo = (lo + Math.imul(al4, bl6)) | 0; + mid = (mid + Math.imul(al4, bh6)) | 0; + mid = (mid + Math.imul(ah4, bl6)) | 0; + hi = (hi + Math.imul(ah4, bh6)) | 0; + lo = (lo + Math.imul(al3, bl7)) | 0; + mid = (mid + Math.imul(al3, bh7)) | 0; + mid = (mid + Math.imul(ah3, bl7)) | 0; + hi = (hi + Math.imul(ah3, bh7)) | 0; + lo = (lo + Math.imul(al2, bl8)) | 0; + mid = (mid + Math.imul(al2, bh8)) | 0; + mid = (mid + Math.imul(ah2, bl8)) | 0; + hi = (hi + Math.imul(ah2, bh8)) | 0; + lo = (lo + Math.imul(al1, bl9)) | 0; + mid = (mid + Math.imul(al1, bh9)) | 0; + mid = (mid + Math.imul(ah1, bl9)) | 0; + hi = (hi + Math.imul(ah1, bh9)) | 0; + var w10 = (((c + lo) | 0) + ((mid & 0x1fff) << 13)) | 0; + c = (((hi + (mid >>> 13)) | 0) + (w10 >>> 26)) | 0; + w10 &= 0x3ffffff; + /* k = 11 */ + lo = Math.imul(al9, bl2); + mid = Math.imul(al9, bh2); + mid = (mid + Math.imul(ah9, bl2)) | 0; + hi = Math.imul(ah9, bh2); + lo = (lo + Math.imul(al8, bl3)) | 0; + mid = (mid + Math.imul(al8, bh3)) | 0; + mid = (mid + Math.imul(ah8, bl3)) | 0; + hi = (hi + Math.imul(ah8, bh3)) | 0; + lo = (lo + Math.imul(al7, bl4)) | 0; + mid = (mid + Math.imul(al7, bh4)) | 0; + mid = (mid + Math.imul(ah7, bl4)) | 0; + hi = (hi + Math.imul(ah7, bh4)) | 0; + lo = (lo + Math.imul(al6, bl5)) | 0; + mid = (mid + Math.imul(al6, bh5)) | 0; + mid = (mid + Math.imul(ah6, bl5)) | 0; + hi = (hi + Math.imul(ah6, bh5)) | 0; + lo = (lo + Math.imul(al5, bl6)) | 0; + mid = (mid + Math.imul(al5, bh6)) | 0; + mid = (mid + Math.imul(ah5, bl6)) | 0; + hi = (hi + Math.imul(ah5, bh6)) | 0; + lo = (lo + Math.imul(al4, bl7)) | 0; + mid = (mid + Math.imul(al4, bh7)) | 0; + mid = (mid + Math.imul(ah4, bl7)) | 0; + hi = (hi + Math.imul(ah4, bh7)) | 0; + lo = (lo + Math.imul(al3, bl8)) | 0; + mid = (mid + Math.imul(al3, bh8)) | 0; + mid = (mid + Math.imul(ah3, bl8)) | 0; + hi = (hi + Math.imul(ah3, bh8)) | 0; + lo = (lo + Math.imul(al2, bl9)) | 0; + mid = (mid + Math.imul(al2, bh9)) | 0; + mid = (mid + Math.imul(ah2, bl9)) | 0; + hi = (hi + Math.imul(ah2, bh9)) | 0; + var w11 = (((c + lo) | 0) + ((mid & 0x1fff) << 13)) | 0; + c = (((hi + (mid >>> 13)) | 0) + (w11 >>> 26)) | 0; + w11 &= 0x3ffffff; + /* k = 12 */ + lo = Math.imul(al9, bl3); + mid = Math.imul(al9, bh3); + mid = (mid + Math.imul(ah9, bl3)) | 0; + hi = Math.imul(ah9, bh3); + lo = (lo + Math.imul(al8, bl4)) | 0; + mid = (mid + Math.imul(al8, bh4)) | 0; + mid = (mid + Math.imul(ah8, bl4)) | 0; + hi = (hi + Math.imul(ah8, bh4)) | 0; + lo = (lo + Math.imul(al7, bl5)) | 0; + mid = (mid + Math.imul(al7, bh5)) | 0; + mid = (mid + Math.imul(ah7, bl5)) | 0; + hi = (hi + Math.imul(ah7, bh5)) | 0; + lo = (lo + Math.imul(al6, bl6)) | 0; + mid = (mid + Math.imul(al6, bh6)) | 0; + mid = (mid + Math.imul(ah6, bl6)) | 0; + hi = (hi + Math.imul(ah6, bh6)) | 0; + lo = (lo + Math.imul(al5, bl7)) | 0; + mid = (mid + Math.imul(al5, bh7)) | 0; + mid = (mid + Math.imul(ah5, bl7)) | 0; + hi = (hi + Math.imul(ah5, bh7)) | 0; + lo = (lo + Math.imul(al4, bl8)) | 0; + mid = (mid + Math.imul(al4, bh8)) | 0; + mid = (mid + Math.imul(ah4, bl8)) | 0; + hi = (hi + Math.imul(ah4, bh8)) | 0; + lo = (lo + Math.imul(al3, bl9)) | 0; + mid = (mid + Math.imul(al3, bh9)) | 0; + mid = (mid + Math.imul(ah3, bl9)) | 0; + hi = (hi + Math.imul(ah3, bh9)) | 0; + var w12 = (((c + lo) | 0) + ((mid & 0x1fff) << 13)) | 0; + c = (((hi + (mid >>> 13)) | 0) + (w12 >>> 26)) | 0; + w12 &= 0x3ffffff; + /* k = 13 */ + lo = Math.imul(al9, bl4); + mid = Math.imul(al9, bh4); + mid = (mid + Math.imul(ah9, bl4)) | 0; + hi = Math.imul(ah9, bh4); + lo = (lo + Math.imul(al8, bl5)) | 0; + mid = (mid + Math.imul(al8, bh5)) | 0; + mid = (mid + Math.imul(ah8, bl5)) | 0; + hi = (hi + Math.imul(ah8, bh5)) | 0; + lo = (lo + Math.imul(al7, bl6)) | 0; + mid = (mid + Math.imul(al7, bh6)) | 0; + mid = (mid + Math.imul(ah7, bl6)) | 0; + hi = (hi + Math.imul(ah7, bh6)) | 0; + lo = (lo + Math.imul(al6, bl7)) | 0; + mid = (mid + Math.imul(al6, bh7)) | 0; + mid = (mid + Math.imul(ah6, bl7)) | 0; + hi = (hi + Math.imul(ah6, bh7)) | 0; + lo = (lo + Math.imul(al5, bl8)) | 0; + mid = (mid + Math.imul(al5, bh8)) | 0; + mid = (mid + Math.imul(ah5, bl8)) | 0; + hi = (hi + Math.imul(ah5, bh8)) | 0; + lo = (lo + Math.imul(al4, bl9)) | 0; + mid = (mid + Math.imul(al4, bh9)) | 0; + mid = (mid + Math.imul(ah4, bl9)) | 0; + hi = (hi + Math.imul(ah4, bh9)) | 0; + var w13 = (((c + lo) | 0) + ((mid & 0x1fff) << 13)) | 0; + c = (((hi + (mid >>> 13)) | 0) + (w13 >>> 26)) | 0; + w13 &= 0x3ffffff; + /* k = 14 */ + lo = Math.imul(al9, bl5); + mid = Math.imul(al9, bh5); + mid = (mid + Math.imul(ah9, bl5)) | 0; + hi = Math.imul(ah9, bh5); + lo = (lo + Math.imul(al8, bl6)) | 0; + mid = (mid + Math.imul(al8, bh6)) | 0; + mid = (mid + Math.imul(ah8, bl6)) | 0; + hi = (hi + Math.imul(ah8, bh6)) | 0; + lo = (lo + Math.imul(al7, bl7)) | 0; + mid = (mid + Math.imul(al7, bh7)) | 0; + mid = (mid + Math.imul(ah7, bl7)) | 0; + hi = (hi + Math.imul(ah7, bh7)) | 0; + lo = (lo + Math.imul(al6, bl8)) | 0; + mid = (mid + Math.imul(al6, bh8)) | 0; + mid = (mid + Math.imul(ah6, bl8)) | 0; + hi = (hi + Math.imul(ah6, bh8)) | 0; + lo = (lo + Math.imul(al5, bl9)) | 0; + mid = (mid + Math.imul(al5, bh9)) | 0; + mid = (mid + Math.imul(ah5, bl9)) | 0; + hi = (hi + Math.imul(ah5, bh9)) | 0; + var w14 = (((c + lo) | 0) + ((mid & 0x1fff) << 13)) | 0; + c = (((hi + (mid >>> 13)) | 0) + (w14 >>> 26)) | 0; + w14 &= 0x3ffffff; + /* k = 15 */ + lo = Math.imul(al9, bl6); + mid = Math.imul(al9, bh6); + mid = (mid + Math.imul(ah9, bl6)) | 0; + hi = Math.imul(ah9, bh6); + lo = (lo + Math.imul(al8, bl7)) | 0; + mid = (mid + Math.imul(al8, bh7)) | 0; + mid = (mid + Math.imul(ah8, bl7)) | 0; + hi = (hi + Math.imul(ah8, bh7)) | 0; + lo = (lo + Math.imul(al7, bl8)) | 0; + mid = (mid + Math.imul(al7, bh8)) | 0; + mid = (mid + Math.imul(ah7, bl8)) | 0; + hi = (hi + Math.imul(ah7, bh8)) | 0; + lo = (lo + Math.imul(al6, bl9)) | 0; + mid = (mid + Math.imul(al6, bh9)) | 0; + mid = (mid + Math.imul(ah6, bl9)) | 0; + hi = (hi + Math.imul(ah6, bh9)) | 0; + var w15 = (((c + lo) | 0) + ((mid & 0x1fff) << 13)) | 0; + c = (((hi + (mid >>> 13)) | 0) + (w15 >>> 26)) | 0; + w15 &= 0x3ffffff; + /* k = 16 */ + lo = Math.imul(al9, bl7); + mid = Math.imul(al9, bh7); + mid = (mid + Math.imul(ah9, bl7)) | 0; + hi = Math.imul(ah9, bh7); + lo = (lo + Math.imul(al8, bl8)) | 0; + mid = (mid + Math.imul(al8, bh8)) | 0; + mid = (mid + Math.imul(ah8, bl8)) | 0; + hi = (hi + Math.imul(ah8, bh8)) | 0; + lo = (lo + Math.imul(al7, bl9)) | 0; + mid = (mid + Math.imul(al7, bh9)) | 0; + mid = (mid + Math.imul(ah7, bl9)) | 0; + hi = (hi + Math.imul(ah7, bh9)) | 0; + var w16 = (((c + lo) | 0) + ((mid & 0x1fff) << 13)) | 0; + c = (((hi + (mid >>> 13)) | 0) + (w16 >>> 26)) | 0; + w16 &= 0x3ffffff; + /* k = 17 */ + lo = Math.imul(al9, bl8); + mid = Math.imul(al9, bh8); + mid = (mid + Math.imul(ah9, bl8)) | 0; + hi = Math.imul(ah9, bh8); + lo = (lo + Math.imul(al8, bl9)) | 0; + mid = (mid + Math.imul(al8, bh9)) | 0; + mid = (mid + Math.imul(ah8, bl9)) | 0; + hi = (hi + Math.imul(ah8, bh9)) | 0; + var w17 = (((c + lo) | 0) + ((mid & 0x1fff) << 13)) | 0; + c = (((hi + (mid >>> 13)) | 0) + (w17 >>> 26)) | 0; + w17 &= 0x3ffffff; + /* k = 18 */ + lo = Math.imul(al9, bl9); + mid = Math.imul(al9, bh9); + mid = (mid + Math.imul(ah9, bl9)) | 0; + hi = Math.imul(ah9, bh9); + var w18 = (((c + lo) | 0) + ((mid & 0x1fff) << 13)) | 0; + c = (((hi + (mid >>> 13)) | 0) + (w18 >>> 26)) | 0; + w18 &= 0x3ffffff; + o[0] = w0; + o[1] = w1; + o[2] = w2; + o[3] = w3; + o[4] = w4; + o[5] = w5; + o[6] = w6; + o[7] = w7; + o[8] = w8; + o[9] = w9; + o[10] = w10; + o[11] = w11; + o[12] = w12; + o[13] = w13; + o[14] = w14; + o[15] = w15; + o[16] = w16; + o[17] = w17; + o[18] = w18; + if (c !== 0) { + o[19] = c; + out.length++; + } + return out; + }; + + // Polyfill comb + if (!Math.imul) { + comb10MulTo = smallMulTo; + } + + function bigMulTo (self, num, out) { + out.negative = num.negative ^ self.negative; + out.length = self.length + num.length; + + var carry = 0; + var hncarry = 0; + for (var k = 0; k < out.length - 1; k++) { + // Sum all words with the same `i + j = k` and accumulate `ncarry`, + // note that ncarry could be >= 0x3ffffff + var ncarry = hncarry; + hncarry = 0; + var rword = carry & 0x3ffffff; + var maxJ = Math.min(k, num.length - 1); + for (var j = Math.max(0, k - self.length + 1); j <= maxJ; j++) { + var i = k - j; + var a = self.words[i] | 0; + var b = num.words[j] | 0; + var r = a * b; + + var lo = r & 0x3ffffff; + ncarry = (ncarry + ((r / 0x4000000) | 0)) | 0; + lo = (lo + rword) | 0; + rword = lo & 0x3ffffff; + ncarry = (ncarry + (lo >>> 26)) | 0; + + hncarry += ncarry >>> 26; + ncarry &= 0x3ffffff; + } + out.words[k] = rword; + carry = ncarry; + ncarry = hncarry; + } + if (carry !== 0) { + out.words[k] = carry; + } else { + out.length--; + } + + return out.strip(); + } + + function jumboMulTo (self, num, out) { + var fftm = new FFTM(); + return fftm.mulp(self, num, out); + } + + BN.prototype.mulTo = function mulTo (num, out) { + var res; + var len = this.length + num.length; + if (this.length === 10 && num.length === 10) { + res = comb10MulTo(this, num, out); + } else if (len < 63) { + res = smallMulTo(this, num, out); + } else if (len < 1024) { + res = bigMulTo(this, num, out); + } else { + res = jumboMulTo(this, num, out); + } + + return res; + }; + + // Cooley-Tukey algorithm for FFT + // slightly revisited to rely on looping instead of recursion + + function FFTM (x, y) { + this.x = x; + this.y = y; + } + + FFTM.prototype.makeRBT = function makeRBT (N) { + var t = new Array(N); + var l = BN.prototype._countBits(N) - 1; + for (var i = 0; i < N; i++) { + t[i] = this.revBin(i, l, N); + } + + return t; + }; + + // Returns binary-reversed representation of `x` + FFTM.prototype.revBin = function revBin (x, l, N) { + if (x === 0 || x === N - 1) return x; + + var rb = 0; + for (var i = 0; i < l; i++) { + rb |= (x & 1) << (l - i - 1); + x >>= 1; + } + + return rb; + }; + + // Performs "tweedling" phase, therefore 'emulating' + // behaviour of the recursive algorithm + FFTM.prototype.permute = function permute (rbt, rws, iws, rtws, itws, N) { + for (var i = 0; i < N; i++) { + rtws[i] = rws[rbt[i]]; + itws[i] = iws[rbt[i]]; + } + }; + + FFTM.prototype.transform = function transform (rws, iws, rtws, itws, N, rbt) { + this.permute(rbt, rws, iws, rtws, itws, N); + + for (var s = 1; s < N; s <<= 1) { + var l = s << 1; + + var rtwdf = Math.cos(2 * Math.PI / l); + var itwdf = Math.sin(2 * Math.PI / l); + + for (var p = 0; p < N; p += l) { + var rtwdf_ = rtwdf; + var itwdf_ = itwdf; + + for (var j = 0; j < s; j++) { + var re = rtws[p + j]; + var ie = itws[p + j]; + + var ro = rtws[p + j + s]; + var io = itws[p + j + s]; + + var rx = rtwdf_ * ro - itwdf_ * io; + + io = rtwdf_ * io + itwdf_ * ro; + ro = rx; + + rtws[p + j] = re + ro; + itws[p + j] = ie + io; + + rtws[p + j + s] = re - ro; + itws[p + j + s] = ie - io; + + /* jshint maxdepth : false */ + if (j !== l) { + rx = rtwdf * rtwdf_ - itwdf * itwdf_; + + itwdf_ = rtwdf * itwdf_ + itwdf * rtwdf_; + rtwdf_ = rx; + } + } + } + } + }; + + FFTM.prototype.guessLen13b = function guessLen13b (n, m) { + var N = Math.max(m, n) | 1; + var odd = N & 1; + var i = 0; + for (N = N / 2 | 0; N; N = N >>> 1) { + i++; + } + + return 1 << i + 1 + odd; + }; + + FFTM.prototype.conjugate = function conjugate (rws, iws, N) { + if (N <= 1) return; + + for (var i = 0; i < N / 2; i++) { + var t = rws[i]; + + rws[i] = rws[N - i - 1]; + rws[N - i - 1] = t; + + t = iws[i]; + + iws[i] = -iws[N - i - 1]; + iws[N - i - 1] = -t; + } + }; + + FFTM.prototype.normalize13b = function normalize13b (ws, N) { + var carry = 0; + for (var i = 0; i < N / 2; i++) { + var w = Math.round(ws[2 * i + 1] / N) * 0x2000 + + Math.round(ws[2 * i] / N) + + carry; + + ws[i] = w & 0x3ffffff; + + if (w < 0x4000000) { + carry = 0; + } else { + carry = w / 0x4000000 | 0; + } + } + + return ws; + }; + + FFTM.prototype.convert13b = function convert13b (ws, len, rws, N) { + var carry = 0; + for (var i = 0; i < len; i++) { + carry = carry + (ws[i] | 0); + + rws[2 * i] = carry & 0x1fff; carry = carry >>> 13; + rws[2 * i + 1] = carry & 0x1fff; carry = carry >>> 13; + } + + // Pad with zeroes + for (i = 2 * len; i < N; ++i) { + rws[i] = 0; + } + + assert(carry === 0); + assert((carry & ~0x1fff) === 0); + }; + + FFTM.prototype.stub = function stub (N) { + var ph = new Array(N); + for (var i = 0; i < N; i++) { + ph[i] = 0; + } + + return ph; + }; + + FFTM.prototype.mulp = function mulp (x, y, out) { + var N = 2 * this.guessLen13b(x.length, y.length); + + var rbt = this.makeRBT(N); + + var _ = this.stub(N); + + var rws = new Array(N); + var rwst = new Array(N); + var iwst = new Array(N); + + var nrws = new Array(N); + var nrwst = new Array(N); + var niwst = new Array(N); + + var rmws = out.words; + rmws.length = N; + + this.convert13b(x.words, x.length, rws, N); + this.convert13b(y.words, y.length, nrws, N); + + this.transform(rws, _, rwst, iwst, N, rbt); + this.transform(nrws, _, nrwst, niwst, N, rbt); + + for (var i = 0; i < N; i++) { + var rx = rwst[i] * nrwst[i] - iwst[i] * niwst[i]; + iwst[i] = rwst[i] * niwst[i] + iwst[i] * nrwst[i]; + rwst[i] = rx; + } + + this.conjugate(rwst, iwst, N); + this.transform(rwst, iwst, rmws, _, N, rbt); + this.conjugate(rmws, _, N); + this.normalize13b(rmws, N); + + out.negative = x.negative ^ y.negative; + out.length = x.length + y.length; + return out.strip(); + }; + + // Multiply `this` by `num` + BN.prototype.mul = function mul (num) { + var out = new BN(null); + out.words = new Array(this.length + num.length); + return this.mulTo(num, out); + }; + + // Multiply employing FFT + BN.prototype.mulf = function mulf (num) { + var out = new BN(null); + out.words = new Array(this.length + num.length); + return jumboMulTo(this, num, out); + }; + + // In-place Multiplication + BN.prototype.imul = function imul (num) { + return this.clone().mulTo(num, this); + }; + + BN.prototype.imuln = function imuln (num) { + assert(typeof num === 'number'); + assert(num < 0x4000000); + + // Carry + var carry = 0; + for (var i = 0; i < this.length; i++) { + var w = (this.words[i] | 0) * num; + var lo = (w & 0x3ffffff) + (carry & 0x3ffffff); + carry >>= 26; + carry += (w / 0x4000000) | 0; + // NOTE: lo is 27bit maximum + carry += lo >>> 26; + this.words[i] = lo & 0x3ffffff; + } + + if (carry !== 0) { + this.words[i] = carry; + this.length++; + } + + return this; + }; + + BN.prototype.muln = function muln (num) { + return this.clone().imuln(num); + }; + + // `this` * `this` + BN.prototype.sqr = function sqr () { + return this.mul(this); + }; + + // `this` * `this` in-place + BN.prototype.isqr = function isqr () { + return this.imul(this.clone()); + }; + + // Math.pow(`this`, `num`) + BN.prototype.pow = function pow (num) { + var w = toBitArray(num); + if (w.length === 0) return new BN(1); + + // Skip leading zeroes + var res = this; + for (var i = 0; i < w.length; i++, res = res.sqr()) { + if (w[i] !== 0) break; + } + + if (++i < w.length) { + for (var q = res.sqr(); i < w.length; i++, q = q.sqr()) { + if (w[i] === 0) continue; + + res = res.mul(q); + } + } + + return res; + }; + + // Shift-left in-place + BN.prototype.iushln = function iushln (bits) { + assert(typeof bits === 'number' && bits >= 0); + var r = bits % 26; + var s = (bits - r) / 26; + var carryMask = (0x3ffffff >>> (26 - r)) << (26 - r); + var i; + + if (r !== 0) { + var carry = 0; + + for (i = 0; i < this.length; i++) { + var newCarry = this.words[i] & carryMask; + var c = ((this.words[i] | 0) - newCarry) << r; + this.words[i] = c | carry; + carry = newCarry >>> (26 - r); + } + + if (carry) { + this.words[i] = carry; + this.length++; + } + } + + if (s !== 0) { + for (i = this.length - 1; i >= 0; i--) { + this.words[i + s] = this.words[i]; + } + + for (i = 0; i < s; i++) { + this.words[i] = 0; + } + + this.length += s; + } + + return this.strip(); + }; + + BN.prototype.ishln = function ishln (bits) { + // TODO(indutny): implement me + assert(this.negative === 0); + return this.iushln(bits); + }; + + // Shift-right in-place + // NOTE: `hint` is a lowest bit before trailing zeroes + // NOTE: if `extended` is present - it will be filled with destroyed bits + BN.prototype.iushrn = function iushrn (bits, hint, extended) { + assert(typeof bits === 'number' && bits >= 0); + var h; + if (hint) { + h = (hint - (hint % 26)) / 26; + } else { + h = 0; + } + + var r = bits % 26; + var s = Math.min((bits - r) / 26, this.length); + var mask = 0x3ffffff ^ ((0x3ffffff >>> r) << r); + var maskedWords = extended; + + h -= s; + h = Math.max(0, h); + + // Extended mode, copy masked part + if (maskedWords) { + for (var i = 0; i < s; i++) { + maskedWords.words[i] = this.words[i]; + } + maskedWords.length = s; + } + + if (s === 0) { + // No-op, we should not move anything at all + } else if (this.length > s) { + this.length -= s; + for (i = 0; i < this.length; i++) { + this.words[i] = this.words[i + s]; + } + } else { + this.words[0] = 0; + this.length = 1; + } + + var carry = 0; + for (i = this.length - 1; i >= 0 && (carry !== 0 || i >= h); i--) { + var word = this.words[i] | 0; + this.words[i] = (carry << (26 - r)) | (word >>> r); + carry = word & mask; + } + + // Push carried bits as a mask + if (maskedWords && carry !== 0) { + maskedWords.words[maskedWords.length++] = carry; + } + + if (this.length === 0) { + this.words[0] = 0; + this.length = 1; + } + + return this.strip(); + }; + + BN.prototype.ishrn = function ishrn (bits, hint, extended) { + // TODO(indutny): implement me + assert(this.negative === 0); + return this.iushrn(bits, hint, extended); + }; + + // Shift-left + BN.prototype.shln = function shln (bits) { + return this.clone().ishln(bits); + }; + + BN.prototype.ushln = function ushln (bits) { + return this.clone().iushln(bits); + }; + + // Shift-right + BN.prototype.shrn = function shrn (bits) { + return this.clone().ishrn(bits); + }; + + BN.prototype.ushrn = function ushrn (bits) { + return this.clone().iushrn(bits); + }; + + // Test if n bit is set + BN.prototype.testn = function testn (bit) { + assert(typeof bit === 'number' && bit >= 0); + var r = bit % 26; + var s = (bit - r) / 26; + var q = 1 << r; + + // Fast case: bit is much higher than all existing words + if (this.length <= s) return false; + + // Check bit and return + var w = this.words[s]; + + return !!(w & q); + }; + + // Return only lowers bits of number (in-place) + BN.prototype.imaskn = function imaskn (bits) { + assert(typeof bits === 'number' && bits >= 0); + var r = bits % 26; + var s = (bits - r) / 26; + + assert(this.negative === 0, 'imaskn works only with positive numbers'); + + if (this.length <= s) { + return this; + } + + if (r !== 0) { + s++; + } + this.length = Math.min(s, this.length); + + if (r !== 0) { + var mask = 0x3ffffff ^ ((0x3ffffff >>> r) << r); + this.words[this.length - 1] &= mask; + } + + return this.strip(); + }; + + // Return only lowers bits of number + BN.prototype.maskn = function maskn (bits) { + return this.clone().imaskn(bits); + }; + + // Add plain number `num` to `this` + BN.prototype.iaddn = function iaddn (num) { + assert(typeof num === 'number'); + assert(num < 0x4000000); + if (num < 0) return this.isubn(-num); + + // Possible sign change + if (this.negative !== 0) { + if (this.length === 1 && (this.words[0] | 0) < num) { + this.words[0] = num - (this.words[0] | 0); + this.negative = 0; + return this; + } + + this.negative = 0; + this.isubn(num); + this.negative = 1; + return this; + } + + // Add without checks + return this._iaddn(num); + }; + + BN.prototype._iaddn = function _iaddn (num) { + this.words[0] += num; + + // Carry + for (var i = 0; i < this.length && this.words[i] >= 0x4000000; i++) { + this.words[i] -= 0x4000000; + if (i === this.length - 1) { + this.words[i + 1] = 1; + } else { + this.words[i + 1]++; + } + } + this.length = Math.max(this.length, i + 1); + + return this; + }; + + // Subtract plain number `num` from `this` + BN.prototype.isubn = function isubn (num) { + assert(typeof num === 'number'); + assert(num < 0x4000000); + if (num < 0) return this.iaddn(-num); + + if (this.negative !== 0) { + this.negative = 0; + this.iaddn(num); + this.negative = 1; + return this; + } + + this.words[0] -= num; + + if (this.length === 1 && this.words[0] < 0) { + this.words[0] = -this.words[0]; + this.negative = 1; + } else { + // Carry + for (var i = 0; i < this.length && this.words[i] < 0; i++) { + this.words[i] += 0x4000000; + this.words[i + 1] -= 1; + } + } + + return this.strip(); + }; + + BN.prototype.addn = function addn (num) { + return this.clone().iaddn(num); + }; + + BN.prototype.subn = function subn (num) { + return this.clone().isubn(num); + }; + + BN.prototype.iabs = function iabs () { + this.negative = 0; + + return this; + }; + + BN.prototype.abs = function abs () { + return this.clone().iabs(); + }; + + BN.prototype._ishlnsubmul = function _ishlnsubmul (num, mul, shift) { + var len = num.length + shift; + var i; + + this._expand(len); + + var w; + var carry = 0; + for (i = 0; i < num.length; i++) { + w = (this.words[i + shift] | 0) + carry; + var right = (num.words[i] | 0) * mul; + w -= right & 0x3ffffff; + carry = (w >> 26) - ((right / 0x4000000) | 0); + this.words[i + shift] = w & 0x3ffffff; + } + for (; i < this.length - shift; i++) { + w = (this.words[i + shift] | 0) + carry; + carry = w >> 26; + this.words[i + shift] = w & 0x3ffffff; + } + + if (carry === 0) return this.strip(); + + // Subtraction overflow + assert(carry === -1); + carry = 0; + for (i = 0; i < this.length; i++) { + w = -(this.words[i] | 0) + carry; + carry = w >> 26; + this.words[i] = w & 0x3ffffff; + } + this.negative = 1; + + return this.strip(); + }; + + BN.prototype._wordDiv = function _wordDiv (num, mode) { + var shift = this.length - num.length; + + var a = this.clone(); + var b = num; + + // Normalize + var bhi = b.words[b.length - 1] | 0; + var bhiBits = this._countBits(bhi); + shift = 26 - bhiBits; + if (shift !== 0) { + b = b.ushln(shift); + a.iushln(shift); + bhi = b.words[b.length - 1] | 0; + } + + // Initialize quotient + var m = a.length - b.length; + var q; + + if (mode !== 'mod') { + q = new BN(null); + q.length = m + 1; + q.words = new Array(q.length); + for (var i = 0; i < q.length; i++) { + q.words[i] = 0; + } + } + + var diff = a.clone()._ishlnsubmul(b, 1, m); + if (diff.negative === 0) { + a = diff; + if (q) { + q.words[m] = 1; + } + } + + for (var j = m - 1; j >= 0; j--) { + var qj = (a.words[b.length + j] | 0) * 0x4000000 + + (a.words[b.length + j - 1] | 0); + + // NOTE: (qj / bhi) is (0x3ffffff * 0x4000000 + 0x3ffffff) / 0x2000000 max + // (0x7ffffff) + qj = Math.min((qj / bhi) | 0, 0x3ffffff); + + a._ishlnsubmul(b, qj, j); + while (a.negative !== 0) { + qj--; + a.negative = 0; + a._ishlnsubmul(b, 1, j); + if (!a.isZero()) { + a.negative ^= 1; + } + } + if (q) { + q.words[j] = qj; + } + } + if (q) { + q.strip(); + } + a.strip(); + + // Denormalize + if (mode !== 'div' && shift !== 0) { + a.iushrn(shift); + } + + return { + div: q || null, + mod: a + }; + }; + + // NOTE: 1) `mode` can be set to `mod` to request mod only, + // to `div` to request div only, or be absent to + // request both div & mod + // 2) `positive` is true if unsigned mod is requested + BN.prototype.divmod = function divmod (num, mode, positive) { + assert(!num.isZero()); + + if (this.isZero()) { + return { + div: new BN(0), + mod: new BN(0) + }; + } + + var div, mod, res; + if (this.negative !== 0 && num.negative === 0) { + res = this.neg().divmod(num, mode); + + if (mode !== 'mod') { + div = res.div.neg(); + } + + if (mode !== 'div') { + mod = res.mod.neg(); + if (positive && mod.negative !== 0) { + mod.iadd(num); + } + } + + return { + div: div, + mod: mod + }; + } + + if (this.negative === 0 && num.negative !== 0) { + res = this.divmod(num.neg(), mode); + + if (mode !== 'mod') { + div = res.div.neg(); + } + + return { + div: div, + mod: res.mod + }; + } + + if ((this.negative & num.negative) !== 0) { + res = this.neg().divmod(num.neg(), mode); + + if (mode !== 'div') { + mod = res.mod.neg(); + if (positive && mod.negative !== 0) { + mod.isub(num); + } + } + + return { + div: res.div, + mod: mod + }; + } + + // Both numbers are positive at this point + + // Strip both numbers to approximate shift value + if (num.length > this.length || this.cmp(num) < 0) { + return { + div: new BN(0), + mod: this + }; + } + + // Very short reduction + if (num.length === 1) { + if (mode === 'div') { + return { + div: this.divn(num.words[0]), + mod: null + }; + } + + if (mode === 'mod') { + return { + div: null, + mod: new BN(this.modn(num.words[0])) + }; + } + + return { + div: this.divn(num.words[0]), + mod: new BN(this.modn(num.words[0])) + }; + } + + return this._wordDiv(num, mode); + }; + + // Find `this` / `num` + BN.prototype.div = function div (num) { + return this.divmod(num, 'div', false).div; + }; + + // Find `this` % `num` + BN.prototype.mod = function mod (num) { + return this.divmod(num, 'mod', false).mod; + }; + + BN.prototype.umod = function umod (num) { + return this.divmod(num, 'mod', true).mod; + }; + + // Find Round(`this` / `num`) + BN.prototype.divRound = function divRound (num) { + var dm = this.divmod(num); + + // Fast case - exact division + if (dm.mod.isZero()) return dm.div; + + var mod = dm.div.negative !== 0 ? dm.mod.isub(num) : dm.mod; + + var half = num.ushrn(1); + var r2 = num.andln(1); + var cmp = mod.cmp(half); + + // Round down + if (cmp < 0 || r2 === 1 && cmp === 0) return dm.div; + + // Round up + return dm.div.negative !== 0 ? dm.div.isubn(1) : dm.div.iaddn(1); + }; + + BN.prototype.modn = function modn (num) { + assert(num <= 0x3ffffff); + var p = (1 << 26) % num; + + var acc = 0; + for (var i = this.length - 1; i >= 0; i--) { + acc = (p * acc + (this.words[i] | 0)) % num; + } + + return acc; + }; + + // In-place division by number + BN.prototype.idivn = function idivn (num) { + assert(num <= 0x3ffffff); + + var carry = 0; + for (var i = this.length - 1; i >= 0; i--) { + var w = (this.words[i] | 0) + carry * 0x4000000; + this.words[i] = (w / num) | 0; + carry = w % num; + } + + return this.strip(); + }; + + BN.prototype.divn = function divn (num) { + return this.clone().idivn(num); + }; + + BN.prototype.egcd = function egcd (p) { + assert(p.negative === 0); + assert(!p.isZero()); + + var x = this; + var y = p.clone(); + + if (x.negative !== 0) { + x = x.umod(p); + } else { + x = x.clone(); + } + + // A * x + B * y = x + var A = new BN(1); + var B = new BN(0); + + // C * x + D * y = y + var C = new BN(0); + var D = new BN(1); + + var g = 0; + + while (x.isEven() && y.isEven()) { + x.iushrn(1); + y.iushrn(1); + ++g; + } + + var yp = y.clone(); + var xp = x.clone(); + + while (!x.isZero()) { + for (var i = 0, im = 1; (x.words[0] & im) === 0 && i < 26; ++i, im <<= 1); + if (i > 0) { + x.iushrn(i); + while (i-- > 0) { + if (A.isOdd() || B.isOdd()) { + A.iadd(yp); + B.isub(xp); + } + + A.iushrn(1); + B.iushrn(1); + } + } + + for (var j = 0, jm = 1; (y.words[0] & jm) === 0 && j < 26; ++j, jm <<= 1); + if (j > 0) { + y.iushrn(j); + while (j-- > 0) { + if (C.isOdd() || D.isOdd()) { + C.iadd(yp); + D.isub(xp); + } + + C.iushrn(1); + D.iushrn(1); + } + } + + if (x.cmp(y) >= 0) { + x.isub(y); + A.isub(C); + B.isub(D); + } else { + y.isub(x); + C.isub(A); + D.isub(B); + } + } + + return { + a: C, + b: D, + gcd: y.iushln(g) + }; + }; + + // This is reduced incarnation of the binary EEA + // above, designated to invert members of the + // _prime_ fields F(p) at a maximal speed + BN.prototype._invmp = function _invmp (p) { + assert(p.negative === 0); + assert(!p.isZero()); + + var a = this; + var b = p.clone(); + + if (a.negative !== 0) { + a = a.umod(p); + } else { + a = a.clone(); + } + + var x1 = new BN(1); + var x2 = new BN(0); + + var delta = b.clone(); + + while (a.cmpn(1) > 0 && b.cmpn(1) > 0) { + for (var i = 0, im = 1; (a.words[0] & im) === 0 && i < 26; ++i, im <<= 1); + if (i > 0) { + a.iushrn(i); + while (i-- > 0) { + if (x1.isOdd()) { + x1.iadd(delta); + } + + x1.iushrn(1); + } + } + + for (var j = 0, jm = 1; (b.words[0] & jm) === 0 && j < 26; ++j, jm <<= 1); + if (j > 0) { + b.iushrn(j); + while (j-- > 0) { + if (x2.isOdd()) { + x2.iadd(delta); + } + + x2.iushrn(1); + } + } + + if (a.cmp(b) >= 0) { + a.isub(b); + x1.isub(x2); + } else { + b.isub(a); + x2.isub(x1); + } + } + + var res; + if (a.cmpn(1) === 0) { + res = x1; + } else { + res = x2; + } + + if (res.cmpn(0) < 0) { + res.iadd(p); + } + + return res; + }; + + BN.prototype.gcd = function gcd (num) { + if (this.isZero()) return num.abs(); + if (num.isZero()) return this.abs(); + + var a = this.clone(); + var b = num.clone(); + a.negative = 0; + b.negative = 0; + + // Remove common factor of two + for (var shift = 0; a.isEven() && b.isEven(); shift++) { + a.iushrn(1); + b.iushrn(1); + } + + do { + while (a.isEven()) { + a.iushrn(1); + } + while (b.isEven()) { + b.iushrn(1); + } + + var r = a.cmp(b); + if (r < 0) { + // Swap `a` and `b` to make `a` always bigger than `b` + var t = a; + a = b; + b = t; + } else if (r === 0 || b.cmpn(1) === 0) { + break; + } + + a.isub(b); + } while (true); + + return b.iushln(shift); + }; + + // Invert number in the field F(num) + BN.prototype.invm = function invm (num) { + return this.egcd(num).a.umod(num); + }; + + BN.prototype.isEven = function isEven () { + return (this.words[0] & 1) === 0; + }; + + BN.prototype.isOdd = function isOdd () { + return (this.words[0] & 1) === 1; + }; + + // And first word and num + BN.prototype.andln = function andln (num) { + return this.words[0] & num; + }; + + // Increment at the bit position in-line + BN.prototype.bincn = function bincn (bit) { + assert(typeof bit === 'number'); + var r = bit % 26; + var s = (bit - r) / 26; + var q = 1 << r; + + // Fast case: bit is much higher than all existing words + if (this.length <= s) { + this._expand(s + 1); + this.words[s] |= q; + return this; + } + + // Add bit and propagate, if needed + var carry = q; + for (var i = s; carry !== 0 && i < this.length; i++) { + var w = this.words[i] | 0; + w += carry; + carry = w >>> 26; + w &= 0x3ffffff; + this.words[i] = w; + } + if (carry !== 0) { + this.words[i] = carry; + this.length++; + } + return this; + }; + + BN.prototype.isZero = function isZero () { + return this.length === 1 && this.words[0] === 0; + }; + + BN.prototype.cmpn = function cmpn (num) { + var negative = num < 0; + + if (this.negative !== 0 && !negative) return -1; + if (this.negative === 0 && negative) return 1; + + this.strip(); + + var res; + if (this.length > 1) { + res = 1; + } else { + if (negative) { + num = -num; + } + + assert(num <= 0x3ffffff, 'Number is too big'); + + var w = this.words[0] | 0; + res = w === num ? 0 : w < num ? -1 : 1; + } + if (this.negative !== 0) return -res | 0; + return res; + }; + + // Compare two numbers and return: + // 1 - if `this` > `num` + // 0 - if `this` == `num` + // -1 - if `this` < `num` + BN.prototype.cmp = function cmp (num) { + if (this.negative !== 0 && num.negative === 0) return -1; + if (this.negative === 0 && num.negative !== 0) return 1; + + var res = this.ucmp(num); + if (this.negative !== 0) return -res | 0; + return res; + }; + + // Unsigned comparison + BN.prototype.ucmp = function ucmp (num) { + // At this point both numbers have the same sign + if (this.length > num.length) return 1; + if (this.length < num.length) return -1; + + var res = 0; + for (var i = this.length - 1; i >= 0; i--) { + var a = this.words[i] | 0; + var b = num.words[i] | 0; + + if (a === b) continue; + if (a < b) { + res = -1; + } else if (a > b) { + res = 1; + } + break; + } + return res; + }; + + BN.prototype.gtn = function gtn (num) { + return this.cmpn(num) === 1; + }; + + BN.prototype.gt = function gt (num) { + return this.cmp(num) === 1; + }; + + BN.prototype.gten = function gten (num) { + return this.cmpn(num) >= 0; + }; + + BN.prototype.gte = function gte (num) { + return this.cmp(num) >= 0; + }; + + BN.prototype.ltn = function ltn (num) { + return this.cmpn(num) === -1; + }; + + BN.prototype.lt = function lt (num) { + return this.cmp(num) === -1; + }; + + BN.prototype.lten = function lten (num) { + return this.cmpn(num) <= 0; + }; + + BN.prototype.lte = function lte (num) { + return this.cmp(num) <= 0; + }; + + BN.prototype.eqn = function eqn (num) { + return this.cmpn(num) === 0; + }; + + BN.prototype.eq = function eq (num) { + return this.cmp(num) === 0; + }; + + // + // A reduce context, could be using montgomery or something better, depending + // on the `m` itself. + // + BN.red = function red (num) { + return new Red(num); + }; + + BN.prototype.toRed = function toRed (ctx) { + assert(!this.red, 'Already a number in reduction context'); + assert(this.negative === 0, 'red works only with positives'); + return ctx.convertTo(this)._forceRed(ctx); + }; + + BN.prototype.fromRed = function fromRed () { + assert(this.red, 'fromRed works only with numbers in reduction context'); + return this.red.convertFrom(this); + }; + + BN.prototype._forceRed = function _forceRed (ctx) { + this.red = ctx; + return this; + }; + + BN.prototype.forceRed = function forceRed (ctx) { + assert(!this.red, 'Already a number in reduction context'); + return this._forceRed(ctx); + }; + + BN.prototype.redAdd = function redAdd (num) { + assert(this.red, 'redAdd works only with red numbers'); + return this.red.add(this, num); + }; + + BN.prototype.redIAdd = function redIAdd (num) { + assert(this.red, 'redIAdd works only with red numbers'); + return this.red.iadd(this, num); + }; + + BN.prototype.redSub = function redSub (num) { + assert(this.red, 'redSub works only with red numbers'); + return this.red.sub(this, num); + }; + + BN.prototype.redISub = function redISub (num) { + assert(this.red, 'redISub works only with red numbers'); + return this.red.isub(this, num); + }; + + BN.prototype.redShl = function redShl (num) { + assert(this.red, 'redShl works only with red numbers'); + return this.red.shl(this, num); + }; + + BN.prototype.redMul = function redMul (num) { + assert(this.red, 'redMul works only with red numbers'); + this.red._verify2(this, num); + return this.red.mul(this, num); + }; + + BN.prototype.redIMul = function redIMul (num) { + assert(this.red, 'redMul works only with red numbers'); + this.red._verify2(this, num); + return this.red.imul(this, num); + }; + + BN.prototype.redSqr = function redSqr () { + assert(this.red, 'redSqr works only with red numbers'); + this.red._verify1(this); + return this.red.sqr(this); + }; + + BN.prototype.redISqr = function redISqr () { + assert(this.red, 'redISqr works only with red numbers'); + this.red._verify1(this); + return this.red.isqr(this); + }; + + // Square root over p + BN.prototype.redSqrt = function redSqrt () { + assert(this.red, 'redSqrt works only with red numbers'); + this.red._verify1(this); + return this.red.sqrt(this); + }; + + BN.prototype.redInvm = function redInvm () { + assert(this.red, 'redInvm works only with red numbers'); + this.red._verify1(this); + return this.red.invm(this); + }; + + // Return negative clone of `this` % `red modulo` + BN.prototype.redNeg = function redNeg () { + assert(this.red, 'redNeg works only with red numbers'); + this.red._verify1(this); + return this.red.neg(this); + }; + + BN.prototype.redPow = function redPow (num) { + assert(this.red && !num.red, 'redPow(normalNum)'); + this.red._verify1(this); + return this.red.pow(this, num); + }; + + // Prime numbers with efficient reduction + var primes = { + k256: null, + p224: null, + p192: null, + p25519: null + }; + + // Pseudo-Mersenne prime + function MPrime (name, p) { + // P = 2 ^ N - K + this.name = name; + this.p = new BN(p, 16); + this.n = this.p.bitLength(); + this.k = new BN(1).iushln(this.n).isub(this.p); + + this.tmp = this._tmp(); + } + + MPrime.prototype._tmp = function _tmp () { + var tmp = new BN(null); + tmp.words = new Array(Math.ceil(this.n / 13)); + return tmp; + }; + + MPrime.prototype.ireduce = function ireduce (num) { + // Assumes that `num` is less than `P^2` + // num = HI * (2 ^ N - K) + HI * K + LO = HI * K + LO (mod P) + var r = num; + var rlen; + + do { + this.split(r, this.tmp); + r = this.imulK(r); + r = r.iadd(this.tmp); + rlen = r.bitLength(); + } while (rlen > this.n); + + var cmp = rlen < this.n ? -1 : r.ucmp(this.p); + if (cmp === 0) { + r.words[0] = 0; + r.length = 1; + } else if (cmp > 0) { + r.isub(this.p); + } else { + if (r.strip !== undefined) { + // r is BN v4 instance + r.strip(); + } else { + // r is BN v5 instance + r._strip(); + } + } + + return r; + }; + + MPrime.prototype.split = function split (input, out) { + input.iushrn(this.n, 0, out); + }; + + MPrime.prototype.imulK = function imulK (num) { + return num.imul(this.k); + }; + + function K256 () { + MPrime.call( + this, + 'k256', + 'ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff fffffffe fffffc2f'); + } + inherits(K256, MPrime); + + K256.prototype.split = function split (input, output) { + // 256 = 9 * 26 + 22 + var mask = 0x3fffff; + + var outLen = Math.min(input.length, 9); + for (var i = 0; i < outLen; i++) { + output.words[i] = input.words[i]; + } + output.length = outLen; + + if (input.length <= 9) { + input.words[0] = 0; + input.length = 1; + return; + } + + // Shift by 9 limbs + var prev = input.words[9]; + output.words[output.length++] = prev & mask; + + for (i = 10; i < input.length; i++) { + var next = input.words[i] | 0; + input.words[i - 10] = ((next & mask) << 4) | (prev >>> 22); + prev = next; + } + prev >>>= 22; + input.words[i - 10] = prev; + if (prev === 0 && input.length > 10) { + input.length -= 10; + } else { + input.length -= 9; + } + }; + + K256.prototype.imulK = function imulK (num) { + // K = 0x1000003d1 = [ 0x40, 0x3d1 ] + num.words[num.length] = 0; + num.words[num.length + 1] = 0; + num.length += 2; + + // bounded at: 0x40 * 0x3ffffff + 0x3d0 = 0x100000390 + var lo = 0; + for (var i = 0; i < num.length; i++) { + var w = num.words[i] | 0; + lo += w * 0x3d1; + num.words[i] = lo & 0x3ffffff; + lo = w * 0x40 + ((lo / 0x4000000) | 0); + } + + // Fast length reduction + if (num.words[num.length - 1] === 0) { + num.length--; + if (num.words[num.length - 1] === 0) { + num.length--; + } + } + return num; + }; + + function P224 () { + MPrime.call( + this, + 'p224', + 'ffffffff ffffffff ffffffff ffffffff 00000000 00000000 00000001'); + } + inherits(P224, MPrime); + + function P192 () { + MPrime.call( + this, + 'p192', + 'ffffffff ffffffff ffffffff fffffffe ffffffff ffffffff'); + } + inherits(P192, MPrime); + + function P25519 () { + // 2 ^ 255 - 19 + MPrime.call( + this, + '25519', + '7fffffffffffffff ffffffffffffffff ffffffffffffffff ffffffffffffffed'); + } + inherits(P25519, MPrime); + + P25519.prototype.imulK = function imulK (num) { + // K = 0x13 + var carry = 0; + for (var i = 0; i < num.length; i++) { + var hi = (num.words[i] | 0) * 0x13 + carry; + var lo = hi & 0x3ffffff; + hi >>>= 26; + + num.words[i] = lo; + carry = hi; + } + if (carry !== 0) { + num.words[num.length++] = carry; + } + return num; + }; + + // Exported mostly for testing purposes, use plain name instead + BN._prime = function prime (name) { + // Cached version of prime + if (primes[name]) return primes[name]; + + var prime; + if (name === 'k256') { + prime = new K256(); + } else if (name === 'p224') { + prime = new P224(); + } else if (name === 'p192') { + prime = new P192(); + } else if (name === 'p25519') { + prime = new P25519(); + } else { + throw new Error('Unknown prime ' + name); + } + primes[name] = prime; + + return prime; + }; + + // + // Base reduction engine + // + function Red (m) { + if (typeof m === 'string') { + var prime = BN._prime(m); + this.m = prime.p; + this.prime = prime; + } else { + assert(m.gtn(1), 'modulus must be greater than 1'); + this.m = m; + this.prime = null; + } + } + + Red.prototype._verify1 = function _verify1 (a) { + assert(a.negative === 0, 'red works only with positives'); + assert(a.red, 'red works only with red numbers'); + }; + + Red.prototype._verify2 = function _verify2 (a, b) { + assert((a.negative | b.negative) === 0, 'red works only with positives'); + assert(a.red && a.red === b.red, + 'red works only with red numbers'); + }; + + Red.prototype.imod = function imod (a) { + if (this.prime) return this.prime.ireduce(a)._forceRed(this); + return a.umod(this.m)._forceRed(this); + }; + + Red.prototype.neg = function neg (a) { + if (a.isZero()) { + return a.clone(); + } + + return this.m.sub(a)._forceRed(this); + }; + + Red.prototype.add = function add (a, b) { + this._verify2(a, b); + + var res = a.add(b); + if (res.cmp(this.m) >= 0) { + res.isub(this.m); + } + return res._forceRed(this); + }; + + Red.prototype.iadd = function iadd (a, b) { + this._verify2(a, b); + + var res = a.iadd(b); + if (res.cmp(this.m) >= 0) { + res.isub(this.m); + } + return res; + }; + + Red.prototype.sub = function sub (a, b) { + this._verify2(a, b); + + var res = a.sub(b); + if (res.cmpn(0) < 0) { + res.iadd(this.m); + } + return res._forceRed(this); + }; + + Red.prototype.isub = function isub (a, b) { + this._verify2(a, b); + + var res = a.isub(b); + if (res.cmpn(0) < 0) { + res.iadd(this.m); + } + return res; + }; + + Red.prototype.shl = function shl (a, num) { + this._verify1(a); + return this.imod(a.ushln(num)); + }; + + Red.prototype.imul = function imul (a, b) { + this._verify2(a, b); + return this.imod(a.imul(b)); + }; + + Red.prototype.mul = function mul (a, b) { + this._verify2(a, b); + return this.imod(a.mul(b)); + }; + + Red.prototype.isqr = function isqr (a) { + return this.imul(a, a.clone()); + }; + + Red.prototype.sqr = function sqr (a) { + return this.mul(a, a); + }; + + Red.prototype.sqrt = function sqrt (a) { + if (a.isZero()) return a.clone(); + + var mod3 = this.m.andln(3); + assert(mod3 % 2 === 1); + + // Fast case + if (mod3 === 3) { + var pow = this.m.add(new BN(1)).iushrn(2); + return this.pow(a, pow); + } + + // Tonelli-Shanks algorithm (Totally unoptimized and slow) + // + // Find Q and S, that Q * 2 ^ S = (P - 1) + var q = this.m.subn(1); + var s = 0; + while (!q.isZero() && q.andln(1) === 0) { + s++; + q.iushrn(1); + } + assert(!q.isZero()); + + var one = new BN(1).toRed(this); + var nOne = one.redNeg(); + + // Find quadratic non-residue + // NOTE: Max is such because of generalized Riemann hypothesis. + var lpow = this.m.subn(1).iushrn(1); + var z = this.m.bitLength(); + z = new BN(2 * z * z).toRed(this); + + while (this.pow(z, lpow).cmp(nOne) !== 0) { + z.redIAdd(nOne); + } + + var c = this.pow(z, q); + var r = this.pow(a, q.addn(1).iushrn(1)); + var t = this.pow(a, q); + var m = s; + while (t.cmp(one) !== 0) { + var tmp = t; + for (var i = 0; tmp.cmp(one) !== 0; i++) { + tmp = tmp.redSqr(); + } + assert(i < m); + var b = this.pow(c, new BN(1).iushln(m - i - 1)); + + r = r.redMul(b); + c = b.redSqr(); + t = t.redMul(c); + m = i; + } + + return r; + }; + + Red.prototype.invm = function invm (a) { + var inv = a._invmp(this.m); + if (inv.negative !== 0) { + inv.negative = 0; + return this.imod(inv).redNeg(); + } else { + return this.imod(inv); + } + }; + + Red.prototype.pow = function pow (a, num) { + if (num.isZero()) return new BN(1).toRed(this); + if (num.cmpn(1) === 0) return a.clone(); + + var windowSize = 4; + var wnd = new Array(1 << windowSize); + wnd[0] = new BN(1).toRed(this); + wnd[1] = a; + for (var i = 2; i < wnd.length; i++) { + wnd[i] = this.mul(wnd[i - 1], a); + } + + var res = wnd[0]; + var current = 0; + var currentLen = 0; + var start = num.bitLength() % 26; + if (start === 0) { + start = 26; + } + + for (i = num.length - 1; i >= 0; i--) { + var word = num.words[i]; + for (var j = start - 1; j >= 0; j--) { + var bit = (word >> j) & 1; + if (res !== wnd[0]) { + res = this.sqr(res); + } + + if (bit === 0 && current === 0) { + currentLen = 0; + continue; + } + + current <<= 1; + current |= bit; + currentLen++; + if (currentLen !== windowSize && (i !== 0 || j !== 0)) continue; + + res = this.mul(res, wnd[current]); + currentLen = 0; + current = 0; + } + start = 26; + } + + return res; + }; + + Red.prototype.convertTo = function convertTo (num) { + var r = num.umod(this.m); + + return r === num ? r.clone() : r; + }; + + Red.prototype.convertFrom = function convertFrom (num) { + var res = num.clone(); + res.red = null; + return res; + }; + + // + // Montgomery method engine + // + + BN.mont = function mont (num) { + return new Mont(num); + }; + + function Mont (m) { + Red.call(this, m); + + this.shift = this.m.bitLength(); + if (this.shift % 26 !== 0) { + this.shift += 26 - (this.shift % 26); + } + + this.r = new BN(1).iushln(this.shift); + this.r2 = this.imod(this.r.sqr()); + this.rinv = this.r._invmp(this.m); + + this.minv = this.rinv.mul(this.r).isubn(1).div(this.m); + this.minv = this.minv.umod(this.r); + this.minv = this.r.sub(this.minv); + } + inherits(Mont, Red); + + Mont.prototype.convertTo = function convertTo (num) { + return this.imod(num.ushln(this.shift)); + }; + + Mont.prototype.convertFrom = function convertFrom (num) { + var r = this.imod(num.mul(this.rinv)); + r.red = null; + return r; + }; + + Mont.prototype.imul = function imul (a, b) { + if (a.isZero() || b.isZero()) { + a.words[0] = 0; + a.length = 1; + return a; + } + + var t = a.imul(b); + var c = t.maskn(this.shift).mul(this.minv).imaskn(this.shift).mul(this.m); + var u = t.isub(c).iushrn(this.shift); + var res = u; + + if (u.cmp(this.m) >= 0) { + res = u.isub(this.m); + } else if (u.cmpn(0) < 0) { + res = u.iadd(this.m); + } + + return res._forceRed(this); + }; + + Mont.prototype.mul = function mul (a, b) { + if (a.isZero() || b.isZero()) return new BN(0)._forceRed(this); + + var t = a.mul(b); + var c = t.maskn(this.shift).mul(this.minv).imaskn(this.shift).mul(this.m); + var u = t.isub(c).iushrn(this.shift); + var res = u; + if (u.cmp(this.m) >= 0) { + res = u.isub(this.m); + } else if (u.cmpn(0) < 0) { + res = u.iadd(this.m); + } + + return res._forceRed(this); + }; + + Mont.prototype.invm = function invm (a) { + // (AR)^-1 * R^2 = (A^-1 * R^-1) * R^2 = A^-1 * R + var res = this.imod(a._invmp(this.m).mul(this.r2)); + return res._forceRed(this); + }; +})(typeof module === 'undefined' || module, this); diff --git a/node_modules/public-encrypt/node_modules/bn.js/package.json b/node_modules/public-encrypt/node_modules/bn.js/package.json new file mode 100644 index 0000000..c91d3c6 --- /dev/null +++ b/node_modules/public-encrypt/node_modules/bn.js/package.json @@ -0,0 +1,64 @@ +{ + "_from": "bn.js@^4.1.0", + "_id": "bn.js@4.11.9", + "_inBundle": false, + "_integrity": "sha512-E6QoYqCKZfgatHTdHzs1RRKP7ip4vvm+EyRUeE2RF0NblwVvb0p6jSVeNTOFxPn26QXN2o6SMfNxKp6kU8zQaw==", + "_location": "/public-encrypt/bn.js", + "_phantomChildren": {}, + "_requested": { + "type": "range", + "registry": true, + "raw": "bn.js@^4.1.0", + "name": "bn.js", + "escapedName": "bn.js", + "rawSpec": "^4.1.0", + "saveSpec": null, + "fetchSpec": "^4.1.0" + }, + "_requiredBy": [ + "/public-encrypt" + ], + "_resolved": "https://registry.npmjs.org/bn.js/-/bn.js-4.11.9.tgz", + "_shasum": "26d556829458f9d1e81fc48952493d0ba3507828", + "_spec": "bn.js@^4.1.0", + "_where": "/home/pruss/Dev/3-minute-website/node_modules/public-encrypt", + "author": { + "name": "Fedor Indutny", + "email": "fedor@indutny.com" + }, + "browser": { + "buffer": false + }, + "bugs": { + "url": "https://github.com/indutny/bn.js/issues" + }, + "bundleDependencies": false, + "deprecated": false, + "description": "Big number implementation in pure javascript", + "devDependencies": { + "istanbul": "^0.3.5", + "mocha": "^2.1.0", + "semistandard": "^7.0.4" + }, + "homepage": "https://github.com/indutny/bn.js", + "keywords": [ + "BN", + "BigNum", + "Big number", + "Modulo", + "Montgomery" + ], + "license": "MIT", + "main": "lib/bn.js", + "name": "bn.js", + "repository": { + "type": "git", + "url": "git+ssh://git@github.com/indutny/bn.js.git" + }, + "scripts": { + "lint": "semistandard", + "test": "npm run lint && npm run unit", + "unit": "mocha --reporter=spec test/*-test.js" + }, + "version": "4.11.9" +} diff --git a/node_modules/public-encrypt/node_modules/bn.js/util/genCombMulTo.js b/node_modules/public-encrypt/node_modules/bn.js/util/genCombMulTo.js new file mode 100644 index 0000000..8b456c7 --- /dev/null +++ b/node_modules/public-encrypt/node_modules/bn.js/util/genCombMulTo.js @@ -0,0 +1,65 @@ +'use strict'; + +// NOTE: This could be potentionally used to generate loop-less multiplications +function genCombMulTo (alen, blen) { + var len = alen + blen - 1; + var src = [ + 'var a = self.words;', + 'var b = num.words;', + 'var o = out.words;', + 'var c = 0;', + 'var lo;', + 'var mid;', + 'var hi;' + ]; + for (var i = 0; i < alen; i++) { + src.push('var a' + i + ' = a[' + i + '] | 0;'); + src.push('var al' + i + ' = a' + i + ' & 0x1fff;'); + src.push('var ah' + i + ' = a' + i + ' >>> 13;'); + } + for (i = 0; i < blen; i++) { + src.push('var b' + i + ' = b[' + i + '] | 0;'); + src.push('var bl' + i + ' = b' + i + ' & 0x1fff;'); + src.push('var bh' + i + ' = b' + i + ' >>> 13;'); + } + src.push(''); + src.push('out.negative = self.negative ^ num.negative;'); + src.push('out.length = ' + len + ';'); + + for (var k = 0; k < len; k++) { + var minJ = Math.max(0, k - alen + 1); + var maxJ = Math.min(k, blen - 1); + + src.push('\/* k = ' + k + ' *\/'); + src.push('var w' + k + ' = c;'); + src.push('c = 0;'); + for (var j = minJ; j <= maxJ; j++) { + i = k - j; + + src.push('lo = Math.imul(al' + i + ', bl' + j + ');'); + src.push('mid = Math.imul(al' + i + ', bh' + j + ');'); + src.push('mid = (mid + Math.imul(ah' + i + ', bl' + j + ')) | 0;'); + src.push('hi = Math.imul(ah' + i + ', bh' + j + ');'); + + src.push('w' + k + ' = (w' + k + ' + lo) | 0;'); + src.push('w' + k + ' = (w' + k + ' + ((mid & 0x1fff) << 13)) | 0;'); + src.push('c = (c + hi) | 0;'); + src.push('c = (c + (mid >>> 13)) | 0;'); + src.push('c = (c + (w' + k + ' >>> 26)) | 0;'); + src.push('w' + k + ' &= 0x3ffffff;'); + } + } + // Store in separate step for better memory access + for (k = 0; k < len; k++) { + src.push('o[' + k + '] = w' + k + ';'); + } + src.push('if (c !== 0) {', + ' o[' + k + '] = c;', + ' out.length++;', + '}', + 'return out;'); + + return src.join('\n'); +} + +console.log(genCombMulTo(10, 10)); diff --git a/node_modules/public-encrypt/node_modules/bn.js/util/genCombMulTo10.js b/node_modules/public-encrypt/node_modules/bn.js/util/genCombMulTo10.js new file mode 100644 index 0000000..cf2e6e8 --- /dev/null +++ b/node_modules/public-encrypt/node_modules/bn.js/util/genCombMulTo10.js @@ -0,0 +1,65 @@ +'use strict'; + +function genCombMulTo (alen, blen) { + var len = alen + blen - 1; + var src = [ + 'var a = self.words;', + 'var b = num.words;', + 'var o = out.words;', + 'var c = 0;', + 'var lo;', + 'var mid;', + 'var hi;' + ]; + for (var i = 0; i < alen; i++) { + src.push('var a' + i + ' = a[' + i + '] | 0;'); + src.push('var al' + i + ' = a' + i + ' & 0x1fff;'); + src.push('var ah' + i + ' = a' + i + ' >>> 13;'); + } + for (i = 0; i < blen; i++) { + src.push('var b' + i + ' = b[' + i + '] | 0;'); + src.push('var bl' + i + ' = b' + i + ' & 0x1fff;'); + src.push('var bh' + i + ' = b' + i + ' >>> 13;'); + } + src.push(''); + src.push('out.negative = self.negative ^ num.negative;'); + src.push('out.length = ' + len + ';'); + + for (var k = 0; k < len; k++) { + var minJ = Math.max(0, k - alen + 1); + var maxJ = Math.min(k, blen - 1); + + src.push('\/* k = ' + k + ' *\/'); + src.push('lo = Math.imul(al' + (k - minJ) + ', bl' + minJ + ');'); + src.push('mid = Math.imul(al' + (k - minJ) + ', bh' + minJ + ');'); + src.push( + 'mid = (mid + Math.imul(ah' + (k - minJ) + ', bl' + minJ + ')) | 0;'); + src.push('hi = Math.imul(ah' + (k - minJ) + ', bh' + minJ + ');'); + + for (var j = minJ + 1; j <= maxJ; j++) { + i = k - j; + + src.push('lo = (lo + Math.imul(al' + i + ', bl' + j + ')) | 0;'); + src.push('mid = (mid + Math.imul(al' + i + ', bh' + j + ')) | 0;'); + src.push('mid = (mid + Math.imul(ah' + i + ', bl' + j + ')) | 0;'); + src.push('hi = (hi + Math.imul(ah' + i + ', bh' + j + ')) | 0;'); + } + + src.push('var w' + k + ' = (((c + lo) | 0) + ((mid & 0x1fff) << 13)) | 0;'); + src.push('c = (((hi + (mid >>> 13)) | 0) + (w' + k + ' >>> 26)) | 0;'); + src.push('w' + k + ' &= 0x3ffffff;'); + } + // Store in separate step for better memory access + for (k = 0; k < len; k++) { + src.push('o[' + k + '] = w' + k + ';'); + } + src.push('if (c !== 0) {', + ' o[' + k + '] = c;', + ' out.length++;', + '}', + 'return out;'); + + return src.join('\n'); +} + +console.log(genCombMulTo(10, 10)); diff --git a/node_modules/public-encrypt/package.json b/node_modules/public-encrypt/package.json new file mode 100644 index 0000000..1d3ac34 --- /dev/null +++ b/node_modules/public-encrypt/package.json @@ -0,0 +1,64 @@ +{ + "_from": "public-encrypt@^4.0.0", + "_id": "public-encrypt@4.0.3", + "_inBundle": false, + "_integrity": "sha512-zVpa8oKZSz5bTMTFClc1fQOnyyEzpl5ozpi1B5YcvBrdohMjH2rfsBtyXcuNuwjsDIXmBYlF2N5FlJYhR29t8Q==", + "_location": "/public-encrypt", + "_phantomChildren": {}, + "_requested": { + "type": "range", + "registry": true, + "raw": "public-encrypt@^4.0.0", + "name": "public-encrypt", + "escapedName": "public-encrypt", + "rawSpec": "^4.0.0", + "saveSpec": null, + "fetchSpec": "^4.0.0" + }, + "_requiredBy": [ + "/crypto-browserify" + ], + "_resolved": "https://registry.npmjs.org/public-encrypt/-/public-encrypt-4.0.3.tgz", + "_shasum": "4fcc9d77a07e48ba7527e7cbe0de33d0701331e0", + "_spec": "public-encrypt@^4.0.0", + "_where": "/home/pruss/Dev/3-minute-website/node_modules/crypto-browserify", + "author": { + "name": "Calvin Metcalf" + }, + "browser": "browser.js", + "bugs": { + "url": "https://github.com/crypto-browserify/publicEncrypt/issues" + }, + "bundleDependencies": false, + "dependencies": { + "bn.js": "^4.1.0", + "browserify-rsa": "^4.0.0", + "create-hash": "^1.1.0", + "parse-asn1": "^5.0.0", + "randombytes": "^2.0.1", + "safe-buffer": "^5.1.2" + }, + "deprecated": false, + "description": "browserify version of publicEncrypt & privateDecrypt", + "devDependencies": { + "standard": "^12.0.0", + "tap-spec": "^2.1.2", + "tape": "^3.0.3" + }, + "directories": { + "test": "test" + }, + "homepage": "https://github.com/crypto-browserify/publicEncrypt", + "license": "MIT", + "main": "index.js", + "name": "public-encrypt", + "repository": { + "type": "git", + "url": "git+https://github.com/crypto-browserify/publicEncrypt.git" + }, + "scripts": { + "lint": "standard", + "test": "node test/index.js | tspec" + }, + "version": "4.0.3" +} diff --git a/node_modules/public-encrypt/privateDecrypt.js b/node_modules/public-encrypt/privateDecrypt.js new file mode 100644 index 0000000..8fc6dfe --- /dev/null +++ b/node_modules/public-encrypt/privateDecrypt.js @@ -0,0 +1,105 @@ +var parseKeys = require('parse-asn1') +var mgf = require('./mgf') +var xor = require('./xor') +var BN = require('bn.js') +var crt = require('browserify-rsa') +var createHash = require('create-hash') +var withPublic = require('./withPublic') +var Buffer = require('safe-buffer').Buffer + +module.exports = function privateDecrypt (privateKey, enc, reverse) { + var padding + if (privateKey.padding) { + padding = privateKey.padding + } else if (reverse) { + padding = 1 + } else { + padding = 4 + } + + var key = parseKeys(privateKey) + var k = key.modulus.byteLength() + if (enc.length > k || new BN(enc).cmp(key.modulus) >= 0) { + throw new Error('decryption error') + } + var msg + if (reverse) { + msg = withPublic(new BN(enc), key) + } else { + msg = crt(enc, key) + } + var zBuffer = Buffer.alloc(k - msg.length) + msg = Buffer.concat([zBuffer, msg], k) + if (padding === 4) { + return oaep(key, msg) + } else if (padding === 1) { + return pkcs1(key, msg, reverse) + } else if (padding === 3) { + return msg + } else { + throw new Error('unknown padding') + } +} + +function oaep (key, msg) { + var k = key.modulus.byteLength() + var iHash = createHash('sha1').update(Buffer.alloc(0)).digest() + var hLen = iHash.length + if (msg[0] !== 0) { + throw new Error('decryption error') + } + var maskedSeed = msg.slice(1, hLen + 1) + var maskedDb = msg.slice(hLen + 1) + var seed = xor(maskedSeed, mgf(maskedDb, hLen)) + var db = xor(maskedDb, mgf(seed, k - hLen - 1)) + if (compare(iHash, db.slice(0, hLen))) { + throw new Error('decryption error') + } + var i = hLen + while (db[i] === 0) { + i++ + } + if (db[i++] !== 1) { + throw new Error('decryption error') + } + return db.slice(i) +} + +function pkcs1 (key, msg, reverse) { + var p1 = msg.slice(0, 2) + var i = 2 + var status = 0 + while (msg[i++] !== 0) { + if (i >= msg.length) { + status++ + break + } + } + var ps = msg.slice(2, i - 1) + + if ((p1.toString('hex') !== '0002' && !reverse) || (p1.toString('hex') !== '0001' && reverse)) { + status++ + } + if (ps.length < 8) { + status++ + } + if (status) { + throw new Error('decryption error') + } + return msg.slice(i) +} +function compare (a, b) { + a = Buffer.from(a) + b = Buffer.from(b) + var dif = 0 + var len = a.length + if (a.length !== b.length) { + dif++ + len = Math.min(a.length, b.length) + } + var i = -1 + while (++i < len) { + dif += (a[i] ^ b[i]) + } + return dif +} diff --git a/node_modules/public-encrypt/publicEncrypt.js b/node_modules/public-encrypt/publicEncrypt.js new file mode 100644 index 0000000..122aa76 --- /dev/null +++ b/node_modules/public-encrypt/publicEncrypt.js @@ -0,0 +1,88 @@ +var parseKeys = require('parse-asn1') +var randomBytes = require('randombytes') +var createHash = require('create-hash') +var mgf = require('./mgf') +var xor = require('./xor') +var BN = require('bn.js') +var withPublic = require('./withPublic') +var crt = require('browserify-rsa') +var Buffer = require('safe-buffer').Buffer + +module.exports = function publicEncrypt (publicKey, msg, reverse) { + var padding + if (publicKey.padding) { + padding = publicKey.padding + } else if (reverse) { + padding = 1 + } else { + padding = 4 + } + var key = parseKeys(publicKey) + var paddedMsg + if (padding === 4) { + paddedMsg = oaep(key, msg) + } else if (padding === 1) { + paddedMsg = pkcs1(key, msg, reverse) + } else if (padding === 3) { + paddedMsg = new BN(msg) + if (paddedMsg.cmp(key.modulus) >= 0) { + throw new Error('data too long for modulus') + } + } else { + throw new Error('unknown padding') + } + if (reverse) { + return crt(paddedMsg, key) + } else { + return withPublic(paddedMsg, key) + } +} + +function oaep (key, msg) { + var k = key.modulus.byteLength() + var mLen = msg.length + var iHash = createHash('sha1').update(Buffer.alloc(0)).digest() + var hLen = iHash.length + var hLen2 = 2 * hLen + if (mLen > k - hLen2 - 2) { + throw new Error('message too long') + } + var ps = Buffer.alloc(k - mLen - hLen2 - 2) + var dblen = k - hLen - 1 + var seed = randomBytes(hLen) + var maskedDb = xor(Buffer.concat([iHash, ps, Buffer.alloc(1, 1), msg], dblen), mgf(seed, dblen)) + var maskedSeed = xor(seed, mgf(maskedDb, hLen)) + return new BN(Buffer.concat([Buffer.alloc(1), maskedSeed, maskedDb], k)) +} +function pkcs1 (key, msg, reverse) { + var mLen = msg.length + var k = key.modulus.byteLength() + if (mLen > k - 11) { + throw new Error('message too long') + } + var ps + if (reverse) { + ps = Buffer.alloc(k - mLen - 3, 0xff) + } else { + ps = nonZero(k - mLen - 3) + } + return new BN(Buffer.concat([Buffer.from([0, reverse ? 1 : 2]), ps, Buffer.alloc(1), msg], k)) +} +function nonZero (len) { + var out = Buffer.allocUnsafe(len) + var i = 0 + var cache = randomBytes(len * 2) + var cur = 0 + var num + while (i < len) { + if (cur === cache.length) { + cache = randomBytes(len * 2) + cur = 0 + } + num = cache[cur++] + if (num) { + out[i++] = num + } + } + return out +} diff --git a/node_modules/public-encrypt/readme.md b/node_modules/public-encrypt/readme.md new file mode 100644 index 0000000..96fe944 --- /dev/null +++ b/node_modules/public-encrypt/readme.md @@ -0,0 +1,8 @@ +publicEncrypt +=== + +[](https://travis-ci.org/crypto-browserify/publicEncrypt) + +publicEncrypt/privateDecrypt for browserify + +[Blog post about the moving parts that have gone into this.](http://calvinmetcalf.com/post/109301244759/porting-nodejs-crypto-to-the-browser-part-3) diff --git a/node_modules/public-encrypt/test/1024.priv b/node_modules/public-encrypt/test/1024.priv new file mode 100644 index 0000000..7206216 --- /dev/null +++ b/node_modules/public-encrypt/test/1024.priv @@ -0,0 +1,16 @@ +-----BEGIN PRIVATE KEY----- +MIICdwIBADANBgkqhkiG9w0BAQEFAASCAmEwggJdAgEAAoGBAKulUTZ8B1qccZ8c +DXRGSY08gW8KvLlcxxxGC4gZHNT3CBUF8n5R4KE30aZyYZ/rtsQZu05juZJxaJ0q +mbe75dlQ5d+Xc9BMXeQg/MpTZw5TAN7OIdGYYpFBe+1PLZ6wEfjkYrMqMUcfq2Lq +hTLdAbvBJnuRcYZLqmBeOQ8FTrKrAgMBAAECgYEAnkHRbEPU3/WISSQrP36iyCb2 +S/SBZwKkzmvCrBxDWhPeDswp9c/2JY76rNWfLzy8iXgUG8WUzvHje61Qh3gmBcKe +bUaTGl4Vy8Ha1YBADo5RfRrdm0FE4tvgvu/TkqFqpBBZweu54285hk5zlG7n/D7Y +dnNXUpu5MlNb5x3gW0kCQQDUL//cwcXUxY/evaJP4jSe+ZwEQZo+zXRLiPUulBoV +aw28CVMuxdgwqAo1X1IKefPeUaf7RQu8gCKaRnpGuEuXAkEAzxZTfMmvmCUDIew4 +5Gk6bK265XQWdhcgiq254lpBGOYmDj9yCE7yA+zmASQwMsXTdQOi1hOCEyrXuSJ5 +c++EDQJAFh3WrnzoEPByuYXMmET8tSFRWMQ5vpgNqh3haHR5b4gUC2hxaiunCBNL +1RpVY9AoUiDywGcG/SPh93CnKB3niwJBAKP7AtsifZgVXtiizB4aMThTjVYaSZrz +D0Kg9DuHylpkDChmFu77TGrNUQgAVuYtfhb/bRblVa/F0hJ4eQHT3JUCQBVT68tb +OgRUk0aP9tC3021VN82X6+klowSQN8oBPX8+TfDWSUilp/+j24Hky+Z29Do7yR/R +qutnL92CvBlVLV4= +-----END PRIVATE KEY----- diff --git a/node_modules/public-encrypt/test/1024.pub b/node_modules/public-encrypt/test/1024.pub new file mode 100644 index 0000000..2dba785 --- /dev/null +++ b/node_modules/public-encrypt/test/1024.pub @@ -0,0 +1,6 @@ +-----BEGIN PUBLIC KEY----- +MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQCrpVE2fAdanHGfHA10RkmNPIFv +Cry5XMccRguIGRzU9wgVBfJ+UeChN9GmcmGf67bEGbtOY7mScWidKpm3u+XZUOXf +l3PQTF3kIPzKU2cOUwDeziHRmGKRQXvtTy2esBH45GKzKjFHH6ti6oUy3QG7wSZ7 +kXGGS6pgXjkPBU6yqwIDAQAB +-----END PUBLIC KEY----- diff --git a/node_modules/public-encrypt/test/ec.pass.priv b/node_modules/public-encrypt/test/ec.pass.priv new file mode 100644 index 0000000..bf1836d --- /dev/null +++ b/node_modules/public-encrypt/test/ec.pass.priv @@ -0,0 +1,7 @@ +-----BEGIN ENCRYPTED PRIVATE KEY----- +MIHeMEkGCSqGSIb3DQEFDTA8MBsGCSqGSIb3DQEFDDAOBAi9LqZQx4JFXAICCAAw +HQYJYIZIAWUDBAECBBA+js1fG4Rv/yRN7oZvxbgyBIGQ/D4yj86M1x8lMsnAHQ/K +7/ryb/baDNHqN9LTZanEGBuyxgrTzt08SiL+h91yFGMoaly029K1VgEI8Lxu5Np/ +A+LK7ewh73ABzsbuxYdcXI+rKnrvLN9Tt6veDs4GlqTTsWwq5wF0C+6gaYRBXA74 +T1b6NykGh2UNL5U5pHZEYdOVLz+lRJL7gYqlweNHP/S3 +-----END ENCRYPTED PRIVATE KEY----- diff --git a/node_modules/public-encrypt/test/ec.priv b/node_modules/public-encrypt/test/ec.priv new file mode 100644 index 0000000..25fffbd --- /dev/null +++ b/node_modules/public-encrypt/test/ec.priv @@ -0,0 +1,5 @@ +-----BEGIN EC PRIVATE KEY----- +MHQCAQEEIDF6Xv8Sv//wGUWD+c780ppGrU0QdZWCAzxAQPQX8r/uoAcGBSuBBAAK +oUQDQgAEIZeowDylls4K/wfBjO18bYo7gGx8nYQRija4e/qEMikOHJai7geeUreU +r5Xky/Ax7s2dGtegsPNsPgGe5MpQvg== +-----END EC PRIVATE KEY----- diff --git a/node_modules/public-encrypt/test/ec.pub b/node_modules/public-encrypt/test/ec.pub new file mode 100644 index 0000000..2e39e5b --- /dev/null +++ b/node_modules/public-encrypt/test/ec.pub @@ -0,0 +1,4 @@ +-----BEGIN PUBLIC KEY----- +MFYwEAYHKoZIzj0CAQYFK4EEAAoDQgAEIZeowDylls4K/wfBjO18bYo7gGx8nYQR +ija4e/qEMikOHJai7geeUreUr5Xky/Ax7s2dGtegsPNsPgGe5MpQvg== +-----END PUBLIC KEY----- diff --git a/node_modules/public-encrypt/test/index.js b/node_modules/public-encrypt/test/index.js new file mode 100644 index 0000000..85b32e3 --- /dev/null +++ b/node_modules/public-encrypt/test/index.js @@ -0,0 +1,113 @@ +var test = require('tape') +var fs = require('fs') +var parseKeys = require('parse-asn1') +var Buffer = require('safe-buffer').Buffer +var path = require('path') + +require('./nodeTests') +var rsa1024 = { + private: fs.readFileSync(path.join(__dirname, 'rsa.1024.priv')), + public: fs.readFileSync(path.join(__dirname, 'rsa.1024.pub')) +} +var rsa1024priv = { + private: fs.readFileSync(path.join(__dirname, 'rsa.1024.priv')), + public: fs.readFileSync(path.join(__dirname, 'rsa.1024.priv')) +} + +var rsa2028 = { + private: fs.readFileSync(path.join(__dirname, 'rsa.2028.priv')), + public: fs.readFileSync(path.join(__dirname, 'rsa.2028.pub')) +} +var nonrsa1024 = { + private: fs.readFileSync(path.join(__dirname, '1024.priv')), + public: fs.readFileSync(path.join(__dirname, '1024.pub')) +} +var nonrsa1024str = { + private: fs.readFileSync(path.join(__dirname, '1024.priv')).toString(), + public: fs.readFileSync(path.join(__dirname, '1024.pub')).toString() +} +var pass1024 = { + private: { + passphrase: 'fooo', + key: fs.readFileSync(path.join(__dirname, 'pass.1024.priv')) + }, + public: fs.readFileSync(path.join(__dirname, 'pass.1024.pub')) +} +var pass2028 = { + private: { + passphrase: 'password', + key: fs.readFileSync(path.join(__dirname, 'rsa.pass.priv')) + }, + public: fs.readFileSync(path.join(__dirname, 'rsa.pass.pub')) +} + +var nodeCrypto = require('../') +var myCrypto = require('../browser') +function _testIt (keys, message, t) { + var pub = keys.public + var priv = keys.private + t.test(message.toString(), function (t) { + t.plan(8) + + var myEnc = myCrypto.publicEncrypt(pub, message) + var nodeEnc = nodeCrypto.publicEncrypt(pub, message) + t.equals(myCrypto.privateDecrypt(priv, myEnc).toString('hex'), message.toString('hex'), 'my decrypter my message') + t.equals(myCrypto.privateDecrypt(priv, nodeEnc).toString('hex'), message.toString('hex'), 'my decrypter node\'s message') + t.equals(nodeCrypto.privateDecrypt(priv, myEnc).toString('hex'), message.toString('hex'), 'node decrypter my message') + t.equals(nodeCrypto.privateDecrypt(priv, nodeEnc).toString('hex'), message.toString('hex'), 'node decrypter node\'s message') + myEnc = myCrypto.privateEncrypt(priv, message) + nodeEnc = nodeCrypto.privateEncrypt(priv, message) + t.equals(myCrypto.publicDecrypt(pub, myEnc).toString('hex'), message.toString('hex'), 'reverse methods my decrypter my message') + t.equals(myCrypto.publicDecrypt(pub, nodeEnc).toString('hex'), message.toString('hex'), 'reverse methods my decrypter node\'s message') + t.equals(nodeCrypto.publicDecrypt(pub, myEnc).toString('hex'), message.toString('hex'), 'reverse methods node decrypter my message') + t.equals(nodeCrypto.publicDecrypt(pub, nodeEnc).toString('hex'), message.toString('hex'), 'reverse methods node decrypter node\'s message') + }) +} +function testIt (keys, message, t) { + _testIt(keys, message, t) + _testIt(paddingObject(keys, 1), Buffer.concat([message, Buffer.from(' with RSA_PKCS1_PADDING')]), t) + var parsedKey = parseKeys(keys.public) + var k = parsedKey.modulus.byteLength() + var zBuf = Buffer.alloc(k) + var msg = Buffer.concat([zBuf, message, Buffer.from(' with no padding')]).slice(-k) + _testIt(paddingObject(keys, 3), msg, t) +} +function paddingObject (keys, padding) { + return { + public: addPadding(keys.public, padding), + private: addPadding(keys.private, padding) + } +} +function addPadding (key, padding) { + if (typeof key === 'string' || Buffer.isBuffer(key)) { + return { + key: key, + padding: padding + } + } + var out = { + key: key.key, + padding: padding + } + if ('passphrase' in key) { + out.passphrase = key.passphrase + } + return out +} +function testRun (i) { + test('run ' + i, function (t) { + testIt(rsa1024priv, Buffer.from('1024 2 private keys'), t) + testIt(rsa1024, Buffer.from('1024 keys'), t) + testIt(rsa2028, Buffer.from('2028 keys'), t) + testIt(nonrsa1024, Buffer.from('1024 keys non-rsa key'), t) + testIt(pass1024, Buffer.from('1024 keys and password'), t) + testIt(nonrsa1024str, Buffer.from('1024 keys non-rsa key as a string'), t) + testIt(pass2028, Buffer.from('2028 rsa key with variant passwords'), t) + }) +} + +var i = 0 +var num = 20 +while (++i <= num) { + testRun(i) +} diff --git a/node_modules/public-encrypt/test/nodeTests.js b/node_modules/public-encrypt/test/nodeTests.js new file mode 100644 index 0000000..f022e07 --- /dev/null +++ b/node_modules/public-encrypt/test/nodeTests.js @@ -0,0 +1,51 @@ +var crypto = require('../browser') +var test = require('tape') +var fs = require('fs') +var Buffer = require('safe-buffer').Buffer +var path = require('path') +// Test RSA encryption/decryption +test('node tests', function (t) { + var keyPem = fs.readFileSync(path.join(__dirname, 'test_key.pem'), 'ascii') + var rsaPubPem = fs.readFileSync(path.join(__dirname, 'test_rsa_pubkey.pem'), + 'ascii') + var rsaKeyPem = fs.readFileSync(path.join(__dirname, 'test_rsa_privkey.pem'), + 'ascii') + var rsaKeyPemEncrypted = fs.readFileSync(path.join( + __dirname, 'test_rsa_privkey_encrypted.pem'), 'ascii') + var input = 'I AM THE WALRUS' + var bufferToEncrypt = Buffer.from(input) + + var encryptedBuffer = crypto.publicEncrypt(rsaPubPem, bufferToEncrypt) + + var decryptedBuffer = crypto.privateDecrypt(rsaKeyPem, encryptedBuffer) + t.equal(input, decryptedBuffer.toString()) + + var decryptedBufferWithPassword = crypto.privateDecrypt({ + key: rsaKeyPemEncrypted, + passphrase: 'password' + }, encryptedBuffer) + t.equal(input, decryptedBufferWithPassword.toString()) + + // encryptedBuffer = crypto.publicEncrypt(certPem, bufferToEncrypt); + + // decryptedBuffer = crypto.privateDecrypt(keyPem, encryptedBuffer); + // t.equal(input, decryptedBuffer.toString()); + + encryptedBuffer = crypto.publicEncrypt(keyPem, bufferToEncrypt) + + decryptedBuffer = crypto.privateDecrypt(keyPem, encryptedBuffer) + t.equal(input, decryptedBuffer.toString()) + + encryptedBuffer = crypto.privateEncrypt(keyPem, bufferToEncrypt) + + decryptedBuffer = crypto.publicDecrypt(keyPem, encryptedBuffer) + t.equal(input, decryptedBuffer.toString()) + + t.throws(function () { + crypto.privateDecrypt({ + key: rsaKeyPemEncrypted, + passphrase: 'wrong' + }, encryptedBuffer) + }) + t.end() +}) diff --git a/node_modules/public-encrypt/test/pass.1024.priv b/node_modules/public-encrypt/test/pass.1024.priv new file mode 100644 index 0000000..b9f3884 --- /dev/null +++ b/node_modules/public-encrypt/test/pass.1024.priv @@ -0,0 +1,18 @@ +-----BEGIN ENCRYPTED PRIVATE KEY----- +MIICzzBJBgkqhkiG9w0BBQ0wPDAbBgkqhkiG9w0BBQwwDgQIji3ZZ6JbsA4CAggA +MB0GCWCGSAFlAwQBFgQQC6MKblq8zyX90/KmgotsMQSCAoDghNf+yxPC/KRh7F3O +k0lMgtDkV+wCLDv7aBvUqy8Ry2zqFPIlfLb8XtSW943XEu6KUI13IZPEr8p9h1ve +Iye6L0g6uAgbFxBE2DwBBSI7mYr7lokr4v0k+inMKf4JeRdI9XWgwOILKTGf1vH7 +PhvBnqLhOg6BIOuF426qpiyYlmRda74d0Th4o6ZyhyMSzPI1XbWSg719Ew3N/tLe +OHdYl0eFrgNjq+xO4Ev+W7eNIh/XBMQtk9wo+mxeNdldRnX822HxTsL8fSSPs+9T +W5M/2EBTJMSsswSjZyFkq8ehtxovI2u0IBX1IiPulyUZLnSNPDV1eUVClK6rk+q1 +kVsfJhUr2qvIjNlQWlbEXQj4VwGtgl0++l8vdpj59MuN2J3Nx5TNMLjA6BYAa/tr +Bu928QoT7ET+SGx5XKCwKb5fwXmDlV5zZC4kZWTaF/d/Icvj5F+fDZuYFg1JOXNZ ++q2oA1qMYaHGX6lF3pbO84ebg1iwQTDM8iIqFeSMGUJTnk/3a7sqfaWQbEQwGb+X +fXnSTwkF+wO2rriPbFvWyzecWu67zDCP0ZWUgGb86sSJCM7xRGShESwCjOrb88F1 +5SZjyIqogrkc3IWiLH9gc5U8d86qoFjJnP6BfwYks1UIyXNGKfZTCqICpMphV+IS +b0N2jprjLTkWR6nxYGSH1bkKMs7x1M0FBLWWLAZqPn9X3pe6JwIBds04O6XjF0un +oxwDjcJdoxVs7PgRiM5d1Tubqu2zmpCCmXNiqi9B0+rV9/jHg9IA5gUfvYdCcEv+ +oAr90I+2+PuBFa9lgdbDV6DtZk4bSYluqamxVeLPg/vrewYfVfDv6jftfY1D0DEy +69H0 +-----END ENCRYPTED PRIVATE KEY----- diff --git a/node_modules/public-encrypt/test/pass.1024.pub b/node_modules/public-encrypt/test/pass.1024.pub new file mode 100644 index 0000000..617e7fb --- /dev/null +++ b/node_modules/public-encrypt/test/pass.1024.pub @@ -0,0 +1,6 @@ +-----BEGIN PUBLIC KEY----- +MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQDSK/7i5BV0x+gmX16Wrm7kRkCZ +y1QUt6wiM2g+SAZTYR0381VnSMX2cv7CpN3499lZj1rL5S7YTaZZwX3RvU5fz56/ +eDX6ciL/PZsbclN2KdkMWYgmcb9J1zUeoMQ3cjfFUCdQZ/ZvDWa+wY2Zg8os2Bow +AoufHtYHm3eOly/cWwIDAQAB +-----END PUBLIC KEY----- diff --git a/node_modules/public-encrypt/test/rsa.1024.priv b/node_modules/public-encrypt/test/rsa.1024.priv new file mode 100644 index 0000000..d3b5fda --- /dev/null +++ b/node_modules/public-encrypt/test/rsa.1024.priv @@ -0,0 +1,15 @@ +-----BEGIN RSA PRIVATE KEY----- +MIICVAIBAAJ/OwswbFo/uyC8ltGf/yA1A+gV5IGdnAgPbUSI3GzbHCA+x+TLG/tL +vbRw3r1smppY/jkkpiVW1ErSMuN0uixp5gb78Z9rH1XpWb5WWgp3WaY/9EHMjMdO +kQ/9LVZvRvl/M/Fi6owP+q+amJI1BEjECYfbhGL3rmlVdq4qXc40QwIDAQABAn8I +VZ0BPoAOhyF33KFMHxy8r28fsVgxJUYgM3NqQgdv4fFawCYXjhJz9duU5YJGFJGJ +WUGeHlkyYFlpi4f3m7tY7JawmQUWB0MNSoKHI3cgDX4/tfBN8ni+cO0eSoR5czBY +EsAHBU47p1awNFAHwd+ZEuv9H4RmMn7p279rQTtpAkAH3Nqs2/vrRF2cZUN4fIXf +4xHsQBByUayGq8a3J0UGaSFWv68zTUKFherr9uZotNp7NJ4jBXiARw0q8docXUG1 +AkAHgmOKHoORtAmikqpmFEJZOtsXMaLCIm4EszPo5ciYoLMBcVit09AdiQlt7ZJL +DY02svU1b0agCZ97kDkmHDkXAkACa8M9JELuDs/P/vIGYDkMVatIFfW6bWF02eFG +taWwMqCcSEsWvbw0xqYt34jURpNbCjmCyQVwYfAw/+TLhP9dAkAFwRjdwjw37qpj +ddg1mNiu37b7swFxmkiMOXZRxaNNsfb56A14RpN3zob3QdGUybGodMIKTFbmU/lu +CjqAxafJAkAG2yf6RWbwFIWfMyt7WYCh0VaGBCcgy574AinVieEo3ZZyFfC63+xm +3uoaNy4iLoJv4GCjqUBz3ZfcVaO/DDWG +-----END RSA PRIVATE KEY----- diff --git a/node_modules/public-encrypt/test/rsa.1024.pub b/node_modules/public-encrypt/test/rsa.1024.pub new file mode 100644 index 0000000..7ba0636 --- /dev/null +++ b/node_modules/public-encrypt/test/rsa.1024.pub @@ -0,0 +1,5 @@ +-----BEGIN RSA PUBLIC KEY----- +MIGGAn87CzBsWj+7ILyW0Z//IDUD6BXkgZ2cCA9tRIjcbNscID7H5Msb+0u9tHDe +vWyamlj+OSSmJVbUStIy43S6LGnmBvvxn2sfVelZvlZaCndZpj/0QcyMx06RD/0t +Vm9G+X8z8WLqjA/6r5qYkjUESMQJh9uEYveuaVV2ripdzjRDAgMBAAE= +-----END RSA PUBLIC KEY----- diff --git a/node_modules/public-encrypt/test/rsa.2028.priv b/node_modules/public-encrypt/test/rsa.2028.priv new file mode 100644 index 0000000..10e651d --- /dev/null +++ b/node_modules/public-encrypt/test/rsa.2028.priv @@ -0,0 +1,27 @@ +-----BEGIN RSA PRIVATE KEY----- +MIIEjwIBAAKB/gy7mjaWgPeFdVYDZWRCA9BNiv3pPb0es27+FKY0hszLaOw47ExC +tAWpDsH48TXAfyHBYwBLguayfk4LGIupxb+CGMbRo3xEp0CbfY1Jby26T9vGjRC1 +foHDDUJG84uaRbyHqaf4i6zt4gVR+xlAEIjkaFAAK8cOoXAT1CVqGLLljUCchL8P +jaHj/yriZ/S7rdwlI3LnABxwwmLrmR/v71WtpmO/aNG8N+1po+QwaghTkyQ59E/Z +vAuOkFWHok2q/R6PYAa2jdZ9zim0FqOP+nkQaEDRbBFBmBqTv5fFGfk2WsAfKf/R +G0/VFd+ZeM5251TeTvXH695nlSGauVl9AgMBAAECgf4LrWHY/l54ouThZWvvbrug +pfz6sJX2g9l7yXmWlEWsPECVo/7SUbpYFpt6OZy99zSg+IKbGqWKfdhoKrTwIVtC +L0YZ0NlmdnANSIz0roxQG7ZxkL5+vHSw/PmD9x4Uwf+Cz8hATCmNBv1qc60dkyuW +4CLqe72qaTiVWRoO1iagQghNcLoo6vSy65ExLaCDTPha7yu2vw4hFZpWiEjW4dxf +rFdLiix52BC86YlAlxME/rLg8IJVvilbyo9aWdXmxOaUTLRv6PkFD1/gVdw8V9Qr +SLN9FlK2kkjiX0dzoibvZw3tMnt3yydAx0X87+sMRVahC1bp3kVPz4Hy0EWX4QJ/ +PM31vGiuITk2NCd51DXt1Ltn2OP5FaJSmCaEjh0XkU4qouYyjXWt8Bu6BTCl2vua +Fg0Uji9C+IkPLmaUMbMIOwaTk8cWqLthSxsLe70J5OkGrgfKUM/w+BHH1Pt/Pjzj +C++l0kiFaOVDVaAV9GpLPLCBoK/PC9Rb/rxMMoCCNwJ/NZuedIny2w3LMii77h/T +zSvergNGhjY6Rnva8lLXJ6dlrkcPAyps3gWwxqj4NR0T+GM0bDUPVLb7M07XV7SX +v7VJGm52JbRGwM1ss+r8XTTNemeGk+WRxG7TgtsMqYGXLfB8Qxk/f5/Mcc00Tl8u +wXFNsfxJxmt6AbsTr3g36wJ/IhOnibz9Ad+nchlBnN3QeW3CKHqzaR18voqvtVm2 +kJfHK15prH/sSGmxmiEGgrCJTZxtDbaNCO7/VBjnKudUUIhCAwsLtuq0/zub9vAd +8G1scfIpv5qaSNzmKoX8bOwArvrS6wP7yKrcTsuWIlHD8rJVI7IEDnQoTp5G8fK1 +hwJ/MIh8M5v0r5dUYEv6oIJWGcle6AH1JmsP5WIafgq72Z2288pHcCFHwNY8Dg9J +76QswVLnUhPTlmm3EOOPGEtam2iAD5r0Afytlb4lbNoQsj2szeXONDXB+6oueajh +VNELUr8HcSP5lgzRZjJW6aFIzj9LDRmQnUAOjGSXVOQtEwJ/MCQZ7N/v4dIKeDRA +8d8UExZ3+gGHumziztGRJ0tQryZH2PakP5I7V+1l7qEUnJ2c3mF+e1v41Ep9LCvh +bzrPKw9dxh18g4b+7bMpsWPnsraKh6ipxc7aaOaZV0Dxgez4zcZu0P1olO0cN3KM +nxJ0Pds3R8bAhNCDdS2JZaRp5Q== +-----END RSA PRIVATE KEY----- diff --git a/node_modules/public-encrypt/test/rsa.2028.pub b/node_modules/public-encrypt/test/rsa.2028.pub new file mode 100644 index 0000000..b36dca4 --- /dev/null +++ b/node_modules/public-encrypt/test/rsa.2028.pub @@ -0,0 +1,8 @@ +-----BEGIN RSA PUBLIC KEY----- +MIIBBgKB/gy7mjaWgPeFdVYDZWRCA9BNiv3pPb0es27+FKY0hszLaOw47ExCtAWp +DsH48TXAfyHBYwBLguayfk4LGIupxb+CGMbRo3xEp0CbfY1Jby26T9vGjRC1foHD +DUJG84uaRbyHqaf4i6zt4gVR+xlAEIjkaFAAK8cOoXAT1CVqGLLljUCchL8PjaHj +/yriZ/S7rdwlI3LnABxwwmLrmR/v71WtpmO/aNG8N+1po+QwaghTkyQ59E/ZvAuO +kFWHok2q/R6PYAa2jdZ9zim0FqOP+nkQaEDRbBFBmBqTv5fFGfk2WsAfKf/RG0/V +Fd+ZeM5251TeTvXH695nlSGauVl9AgMBAAE= +-----END RSA PUBLIC KEY----- diff --git a/node_modules/public-encrypt/test/rsa.pass.priv b/node_modules/public-encrypt/test/rsa.pass.priv new file mode 100644 index 0000000..99e8213 --- /dev/null +++ b/node_modules/public-encrypt/test/rsa.pass.priv @@ -0,0 +1,30 @@ +-----BEGIN RSA PRIVATE KEY----- +Proc-Type: 4,ENCRYPTED +DEK-Info: AES-256-CBC,7A6A055AD675947A657041422F06D439 + +HQdjzAKUuqqKhZHmpzzY/monfqFhiHnZ5c24jtR9fM4aQJXf/e1fz6MEhyIz6XON +sb4CnXZstnxUuVWDkHEu6KWQ/dKALgiDUuT+UdMawVoVPGdgyWZp35pQPWi3fT2V +XZn58YkG8bO3Y403eZPyhadOefD1VtuFuK6/f90jjzx6ZDnwveXpYgFV7Jy1/pFd +cLLMf07C+hbk416nX6UVipWe4GH+ADFom5ZCfAaUotM7n8i149dULNF4YYi2wP31 +1YaDH5vf1CqiaieDY7xLzpEixwJz6ZEg3gLXaUvz2MpF8owiGI3eP0g7voWp3xt4 +TQx/qDURlaXiaRriWdWtpKyW1MFuJ5+KdNtR1/kXr2BLPB/ZLwyqtynUy8ZYpb4+ +WIRYpUGeb//ZHGhlCH7CRMdABsal4wTwnzi9fW4Ax96ecJ2SlwCuKxwS7iEq2y1/ +FAfGwsE+XufHhme5p6XjKfiHx+zJMIB2NMkrm+wm4PbMTrGVnw5/41/r6XxOB8fe +iKi12Jth4dusc1vYGYfzKop9uEM6CZ6+Chqzb+Zyh/xUiZVlCX/BYnxr7yXUm9aR +PHQgxkn2Act8FgQB3Kgs3jCiCRIJrlsnybeWzQ3YO9TjC4MxygmmwODDBpsOKnEi +kXXS54+cZFjcsva4uJVwhAywRPVUkLzmTkH0tGiwCHjeQNECm+TLahkkEIXrVTb9 +c9creNXMgE6jVVz+R43HXsGvTcgMcBLyFRQJe2nVaj/dQ5JbF4uqNnQzRjAbD34K +uTpFaJ/kmlgcmeScRLnwaoYwFlmhSC+bK0dfY1Jr6AQRA6IDP7nIjqWNDCHNBB8r +Qj1v2KWoVQe3xNHaXhkbJPbA2DKlUIqffkBVtMKtt9KuG3Rccf3bVYAW6oid73/D +z7DMAF5G/OpVR8VbGh1WxXuR7zEVDUwpwsp9ek5dqN8BnBz1ppdZNIKqzszneckU +s2l/6mZBmgV1Nfy/cQU6U5s3S1Xc75UDQVLms3CIOpFTRIpecNTdfa31fYy/svy0 +M2lWTbCva0dOyuvMUhTgBL4I7Qa2dUMPXHMZatV5ooHYq/BZJA1r84C5cM5r+umE +2LLv/BlUr7RaQHhaKGn4Qhpzo5yRDE9mEqDpLVkbg8SxMsdf/pEF5/VyUwA9t8RT +fKVsInRd386tDqJSDbSFqKTvLztr/5YCyzZzvC2YB1voko/caOGd2d/G51Ij+bXU +xEN8U4fHDBsHwPUGb31uZUhTXpL37KiOqZmXFoH2usmuvx882XvyGcV0F4tstMaR +KLKzl2PwqzAYGFexLkYKMz0TYIeN6h3b86ETazPPU49nkaEU23Dx21J2Rb3UlH+I +lDQF3wuH1QlYiTnlcVa/Zu4QQg0/iP8ALkZ06mvn9e9mOtnA8gsh4B2oLqc19VLU +bcpv40dV1H3W9Lcx9B8JYUp0c/Oyno1D7Yj3tjGcwMKECmUpHi4kksehVo0/P933 +xmFmC6eyWYVdO9upvY/vKSB7b1dMt85iWr3gnMsSfRYc6jsbSxdjOPST46UsIzjx +wa1DS6+Bv5tiaC4uC6X+0tCAZo+UOQMYUbTGRR/7g/c= +-----END RSA PRIVATE KEY----- diff --git a/node_modules/public-encrypt/test/rsa.pass.pub b/node_modules/public-encrypt/test/rsa.pass.pub new file mode 100644 index 0000000..655cc3a --- /dev/null +++ b/node_modules/public-encrypt/test/rsa.pass.pub @@ -0,0 +1,9 @@ +-----BEGIN PUBLIC KEY----- +MIIBHjANBgkqhkiG9w0BAQEFAAOCAQsAMIIBBgKB/gy7mjaWgPeFdVYDZWRCA9BN +iv3pPb0es27+FKY0hszLaOw47ExCtAWpDsH48TXAfyHBYwBLguayfk4LGIupxb+C +GMbRo3xEp0CbfY1Jby26T9vGjRC1foHDDUJG84uaRbyHqaf4i6zt4gVR+xlAEIjk +aFAAK8cOoXAT1CVqGLLljUCchL8PjaHj/yriZ/S7rdwlI3LnABxwwmLrmR/v71Wt +pmO/aNG8N+1po+QwaghTkyQ59E/ZvAuOkFWHok2q/R6PYAa2jdZ9zim0FqOP+nkQ +aEDRbBFBmBqTv5fFGfk2WsAfKf/RG0/VFd+ZeM5251TeTvXH695nlSGauVl9AgMB +AAE= +-----END PUBLIC KEY----- diff --git a/node_modules/public-encrypt/test/test_cert.pem b/node_modules/public-encrypt/test/test_cert.pem new file mode 100644 index 0000000..a3c1e4a --- /dev/null +++ b/node_modules/public-encrypt/test/test_cert.pem @@ -0,0 +1,20 @@ +-----BEGIN CERTIFICATE----- +MIIDXDCCAsWgAwIBAgIJAKL0UG+mRkSPMA0GCSqGSIb3DQEBBQUAMH0xCzAJBgNV +BAYTAlVLMRQwEgYDVQQIEwtBY2tuYWNrIEx0ZDETMBEGA1UEBxMKUmh5cyBKb25l +czEQMA4GA1UEChMHbm9kZS5qczEdMBsGA1UECxMUVGVzdCBUTFMgQ2VydGlmaWNh +dGUxEjAQBgNVBAMTCWxvY2FsaG9zdDAeFw0wOTExMTEwOTUyMjJaFw0yOTExMDYw +OTUyMjJaMH0xCzAJBgNVBAYTAlVLMRQwEgYDVQQIEwtBY2tuYWNrIEx0ZDETMBEG +A1UEBxMKUmh5cyBKb25lczEQMA4GA1UEChMHbm9kZS5qczEdMBsGA1UECxMUVGVz +dCBUTFMgQ2VydGlmaWNhdGUxEjAQBgNVBAMTCWxvY2FsaG9zdDCBnzANBgkqhkiG +9w0BAQEFAAOBjQAwgYkCgYEA8d8Hc6atq78Jt1HLp9agA/wpQfsFvkYUdZ1YsdvO +kL2janjwHQgMMCy/Njal3FUEW0OLPebKZUJ8L44JBXSlVxU4zyiiSOWld8EkTetR +AVT3WKQq3ud+cnxv7g8rGRQp1UHZwmdbZ1wEfAYq8QjYx6m1ciMgRo7DaDQhD29k +d+UCAwEAAaOB4zCB4DAdBgNVHQ4EFgQUL9miTJn+HKNuTmx/oMWlZP9cd4QwgbAG +A1UdIwSBqDCBpYAUL9miTJn+HKNuTmx/oMWlZP9cd4ShgYGkfzB9MQswCQYDVQQG +EwJVSzEUMBIGA1UECBMLQWNrbmFjayBMdGQxEzARBgNVBAcTClJoeXMgSm9uZXMx +EDAOBgNVBAoTB25vZGUuanMxHTAbBgNVBAsTFFRlc3QgVExTIENlcnRpZmljYXRl +MRIwEAYDVQQDEwlsb2NhbGhvc3SCCQCi9FBvpkZEjzAMBgNVHRMEBTADAQH/MA0G +CSqGSIb3DQEBBQUAA4GBADRXXA2xSUK5W1i3oLYWW6NEDVWkTQ9RveplyeS9MOkP +e7yPcpz0+O0ZDDrxR9chAiZ7fmdBBX1Tr+pIuCrG/Ud49SBqeS5aMJGVwiSd7o1n +dhU2Sz3Q60DwJEL1VenQHiVYlWWtqXBThe9ggqRPnCfsCRTP8qifKkjk45zWPcpN +-----END CERTIFICATE----- diff --git a/node_modules/public-encrypt/test/test_key.pem b/node_modules/public-encrypt/test/test_key.pem new file mode 100644 index 0000000..48fd93c --- /dev/null +++ b/node_modules/public-encrypt/test/test_key.pem @@ -0,0 +1,15 @@ +-----BEGIN RSA PRIVATE KEY----- +MIICXQIBAAKBgQDx3wdzpq2rvwm3Ucun1qAD/ClB+wW+RhR1nVix286QvaNqePAd +CAwwLL82NqXcVQRbQ4s95splQnwvjgkFdKVXFTjPKKJI5aV3wSRN61EBVPdYpCre +535yfG/uDysZFCnVQdnCZ1tnXAR8BirxCNjHqbVyIyBGjsNoNCEPb2R35QIDAQAB +AoGBAJNem9C4ftrFNGtQ2DB0Udz7uDuucepkErUy4MbFsc947GfENjDKJXr42Kx0 +kYx09ImS1vUpeKpH3xiuhwqe7tm4FsCBg4TYqQle14oxxm7TNeBwwGC3OB7hiokb +aAjbPZ1hAuNs6ms3Ybvvj6Lmxzx42m8O5DXCG2/f+KMvaNUhAkEA/ekrOsWkNoW9 +2n3m+msdVuxeek4B87EoTOtzCXb1dybIZUVv4J48VAiM43hhZHWZck2boD/hhwjC +M5NWd4oY6QJBAPPcgBVNdNZSZ8hR4ogI4nzwWrQhl9MRbqqtfOn2TK/tjMv10ALg +lPmn3SaPSNRPKD2hoLbFuHFERlcS79pbCZ0CQQChX3PuIna/gDitiJ8oQLOg7xEM +wk9TRiDK4kl2lnhjhe6PDpaQN4E4F0cTuwqLAoLHtrNWIcOAQvzKMrYdu1MhAkBm +Et3qDMnjDAs05lGT72QeN90/mPAcASf5eTTYGahv21cb6IBxM+AnwAPpqAAsHhYR +9h13Y7uYbaOjvuF23LRhAkBoI9eaSMn+l81WXOVUHnzh3ZwB4GuTyxMXXNOhuiFd +0z4LKAMh99Z4xQmqSoEkXsfM4KPpfhYjF/bwIcP5gOei +-----END RSA PRIVATE KEY----- diff --git a/node_modules/public-encrypt/test/test_rsa_privkey.pem b/node_modules/public-encrypt/test/test_rsa_privkey.pem new file mode 100644 index 0000000..425518a --- /dev/null +++ b/node_modules/public-encrypt/test/test_rsa_privkey.pem @@ -0,0 +1,15 @@ +-----BEGIN RSA PRIVATE KEY----- +MIICXgIBAAKBgQDCFENGw33yGihy92pDjZQhl0C36rPJj+CvfSC8+q28hxA161QF +NUd13wuCTUcq0Qd2qsBe/2hFyc2DCJJg0h1L78+6Z4UMR7EOcpfdUE9Hf3m/hs+F +UR45uBJeDK1HSFHD8bHKD6kv8FPGfJTotc+2xjJwoYi+1hqp1fIekaxsyQIDAQAB +AoGBAJR8ZkCUvx5kzv+utdl7T5MnordT1TvoXXJGXK7ZZ+UuvMNUCdN2QPc4sBiA +QWvLw1cSKt5DsKZ8UETpYPy8pPYnnDEz2dDYiaew9+xEpubyeW2oH4Zx71wqBtOK +kqwrXa/pzdpiucRRjk6vE6YY7EBBs/g7uanVpGibOVAEsqH1AkEA7DkjVH28WDUg +f1nqvfn2Kj6CT7nIcE3jGJsZZ7zlZmBmHFDONMLUrXR/Zm3pR5m0tCmBqa5RK95u +412jt1dPIwJBANJT3v8pnkth48bQo/fKel6uEYyboRtA5/uHuHkZ6FQF7OUkGogc +mSJluOdc5t6hI1VsLn0QZEjQZMEOWr+wKSMCQQCC4kXJEsHAve77oP6HtG/IiEn7 +kpyUXRNvFsDE0czpJJBvL/aRFUJxuRK91jhjC68sA7NsKMGg5OXb5I5Jj36xAkEA +gIT7aFOYBFwGgQAQkWNKLvySgKbAZRTeLBacpHMuQdl1DfdntvAyqpAZ0lY0RKmW +G6aFKaqQfOXKCyWoUiVknQJAXrlgySFci/2ueKlIE1QqIiLSZ8V8OlpFLRnb1pzI +7U1yQXnTAEFYM560yJlzUpOb1V4cScGd365tiSMvxLOvTA== +-----END RSA PRIVATE KEY----- diff --git a/node_modules/public-encrypt/test/test_rsa_privkey_encrypted.pem b/node_modules/public-encrypt/test/test_rsa_privkey_encrypted.pem new file mode 100644 index 0000000..08e7617 --- /dev/null +++ b/node_modules/public-encrypt/test/test_rsa_privkey_encrypted.pem @@ -0,0 +1,18 @@ +-----BEGIN RSA PRIVATE KEY----- +Proc-Type: 4,ENCRYPTED +DEK-Info: AES-128-CBC,9D916E00476DFF9E70FA4BA9E3A6CB0E + +oj0VC35ShSEqlfJ0rLGgkqJCyIK+mXSsa/X/xAur+lI/RVOVTWd7oQQGTdI/0rLX +PdQR02Na3X9Rptezh6J04PfMGeFysxdT6RpC+rkHRPVbN0F4TqxSNNXzkwK70+EF +dSuDMyVKv9YN4wWDf0g6VKe4ShAH/sqICQBrVyzWyYLvH/hwZmZZ1QEab6ylIKtb +EJunwu9BxVVA04bbuATKkKjJOqDn0fG8hb4bYbyD02dJwgLePzzn36F31kcBCEHI +tESlD3RsS+EtfpfgPkplXNOhqYzkD9auDb7Zy+ZwL20fjnJb75OSGu8gOg3KTljt +mApZOg0nJ5Jk9ATAdyzyVSFOM1Hhcw12ws06Dq9KRnXgO6bbuadLTFRDdvSYDFvD +ijUb+97UolQfYIXQMqXli3EIvHr7CTWe/3mpoDgK1mtr0+923Bm97XgE7KSr0L46 +n5QpNjCZf1vbXldNmW+TRifiJMgtVdS7x0N4vqDPNEe+FelVv3U4Pz3HIOtFuWLr +ZCxlgVxJY4IsyYlV0ItQjIv8fJiAyemZdO2lA9K6h0eEF+9Apr3i79JGWUi74p5D +Ooak4le0Va9O34f6FxCGn/a54A6bhKu24Ub/0gr/e4WRa7693euEdgIAZXhtMu2Z +taU5SKjjXPzjmRCM2kINHTCENlaU4oFzTmj3TYY/jdKyNP1bHa07NhlomladkIHK +GD6HaYkcbuwvh8hOPsopSwuS+NqjnGPq9Vv4ecBC+9veDEmpIE1iR6FK9Hjrre88 +kLoMQNmA+vuc8jG4/FIHM3SauQiR1ZJ6+zkz97kcmOf+X7LRaS4j6lfFR6qHiJ6y +-----END RSA PRIVATE KEY----- diff --git a/node_modules/public-encrypt/test/test_rsa_pubkey.pem b/node_modules/public-encrypt/test/test_rsa_pubkey.pem new file mode 100644 index 0000000..b3bbf6c --- /dev/null +++ b/node_modules/public-encrypt/test/test_rsa_pubkey.pem @@ -0,0 +1,6 @@ +-----BEGIN PUBLIC KEY----- +MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQDCFENGw33yGihy92pDjZQhl0C3 +6rPJj+CvfSC8+q28hxA161QFNUd13wuCTUcq0Qd2qsBe/2hFyc2DCJJg0h1L78+6 +Z4UMR7EOcpfdUE9Hf3m/hs+FUR45uBJeDK1HSFHD8bHKD6kv8FPGfJTotc+2xjJw +oYi+1hqp1fIekaxsyQIDAQAB +-----END PUBLIC KEY----- diff --git a/node_modules/public-encrypt/withPublic.js b/node_modules/public-encrypt/withPublic.js new file mode 100644 index 0000000..417a1bf --- /dev/null +++ b/node_modules/public-encrypt/withPublic.js @@ -0,0 +1,12 @@ +var BN = require('bn.js') +var Buffer = require('safe-buffer').Buffer + +function withPublic (paddedMsg, key) { + return Buffer.from(paddedMsg + .toRed(BN.mont(key.modulus)) + .redPow(new BN(key.publicExponent)) + .fromRed() + .toArray()) +} + +module.exports = withPublic diff --git a/node_modules/public-encrypt/xor.js b/node_modules/public-encrypt/xor.js new file mode 100644 index 0000000..10d2764 --- /dev/null +++ b/node_modules/public-encrypt/xor.js @@ -0,0 +1,8 @@ +module.exports = function xor (a, b) { + var len = a.length + var i = -1 + while (++i < len) { + a[i] ^= b[i] + } + return a +} |