<!DOCTYPE html>
<html>
<head>
<link rel="stylesheet" href="style.css">
<script src="crypto.js"></script>
<script src="ellipticcurve.js"></script>
<script src="kherwa.js"></script>
<script>
function getAddress() {
KherwaJS.getBitcoinAddress(1).then(function(objArray) {
if (objArray && objArray[0].bitcoinAddr) {
document.getElementById("addr").textContent = objArray[0].bitcoinAddr;
document.getElementById("pub").textContent = objArray[0].pk;
document.getElementById("wif").textContent = KherwaJS.privkeyToWIF(objArray[0].sk);
document.getElementById("seck").textContent = objArray[0].sk;
} else {
throw new TypeError("Couldn't Generate Address");
}
});
}
</script>
</head>
<body>
<button onClick="getAddress()">Get Bitcoin Address</button>
<h3>Bitcoin Address</h3>
<div id="addr"></div>
<h3>Public Key</h3>
<div id="pub"></div>
<h3>Private key in WIF</h3>
<div id="wif"></div>
<h3>Private key</h3>
<div id="seck"></div>
</body>
</html>
/*
Author: Rajesh Kherwa
*/
var KherwaJS = KherwaJS || ( function(){
var K = function() {
this.c = CryptoJS;
this.enc = CryptoJS.enc;
this.ec = EllipticCurve;
this.URL = 'https://qrng.anu.edu.au/API/jsonI.php?type=hex16&size=32&length=';
this.compressed = false;
};
/**
* Returns a Promise with Object Array of Bitcoin Addresses with Secret Key
**/
K.prototype.getBitcoinAddress = function(num) {
var url = this.URL.concat(num);
var objArray = [];
var that = this;
return this.fetchEntropy(url).then(function(keyArray) {
objArray = keyArray.map(function(key) {
return that.formatAddress(key);
});
return objArray;
});
},
K.prototype.getPubKey = function(secretKeyHex) {
var keyBigInt = BigInteger.fromByteArrayUnsigned(this.util.hexToBytes(secretKeyHex));
var ecparams = this.ec.getSECCurveByName('secp256k1');
var curvePt = ecparams.getG().multiply(keyBigInt);
var x = curvePt.getX().toBigInteger();
var y = curvePt.getY().toBigInteger();
var publicKeyBytes = this.ec.integerToBytes(x, 32);
publicKeyBytes = publicKeyBytes.concat(this.ec.integerToBytes(y,32));
publicKeyBytes.unshift(0x04);
return publicKeyBytes;
},
K.prototype.privkeyToWIF = function(key) {
var r = this.util.hexToBytes(key);
var priv = 0x80;
if (this.compressed) {
r.push(0x01);
}
r.unshift(priv);
var hexStr = this.util.bytesToHex(r);
var hashHex = this.doubleHashSHA256(hexStr).toString();
var checksum = hashHex.slice(0, 8);
hexStr = hexStr.concat(checksum);
return this.Base58.encode(this.util.hexToBytes(hexStr));
},
K.prototype.wifToPrivkey = function(wif) {
var compressed = false;
var decode = this.Base58.decode(wif);
var key = decode.slice(0, decode.length-4);
key = key.slice(1, key.length);
if(key.length>=33 && key[key.length-1]==0x01){
key = key.slice(0, key.length-1);
compressed = true;
}
return {'privkey': this.util.bytesToHex(key), 'compressed':compressed};
},
K.prototype.formatAddress = function(key) {
var pubkey = this.util.bytesToHex(this.getPubKey(key.toUpperCase())).toUpperCase();
var hashHex = this.hashSHA256RIPMED160(pubkey).toString();
// Prefix Version hex 0x00 for bitcoin, 0x26 for bitcoin GOLD
hashHex = "00".concat(hashHex);
var doubleHashHex = this.doubleHashSHA256(hashHex).toString();
var checksum = doubleHashHex.slice(0,8);
// Suffix Checksum Bytes
hashHex = hashHex.concat(checksum);
// Base58 Encoding
addStr = this.Base58.encode(this.util.hexToBytes(hashHex));
/* var urlBal = 'https://blockchain.info/q/addressbalance/'
urlBal = urlBal.concat(addStr);
var bal = false;
fetch(urlBal).then(function(response){bal = response;}); */
return { sk:key.toUpperCase(),pk:pubkey,bitcoinAddr:addStr}; //,balance:bal};
},
/**
* Get random entropy from qrng.anu.edu.au
**/
K.prototype.fetchEntropy = function(url) {
return fetch(url).then(function(response) {
var contentType = response.headers.get("content-type");
if(contentType && contentType.includes("application/json")) {
return response.json();
}
throw new TypeError("Oops, we haven't got JSON!"); }).then(function(json) {
return json.data;
});
},
K.prototype.hashSHA256RIPMED160 = function(hexStr) {
return this.c.RIPEMD160(this.c.SHA256(this.enc.Hex.parse(hexStr)));
},
K.prototype.doubleHashSHA256 = function(hexStr) {
return this.c.SHA256(this.c.SHA256(this.enc.Hex.parse(hexStr)));
}
var k = new K();
k.util = {
// Convert a byte array to a hex string
bytesToHex : function (bytes) {
for (var hex = [], i = 0; i < bytes.length; i++) {
hex.push((bytes[i] >>> 4).toString(16));
hex.push((bytes[i] & 0xF).toString(16));
}
return hex.join("");
},
// Convert a hex string to a byte array
hexToBytes : function (hex) {
for (var bytes = [], c = 0; c < hex.length; c += 2)
bytes.push(parseInt(hex.substr(c, 2), 16));
return bytes;
}
};
var B58 = k.Base58 = {
alphabet: "123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz",
validRegex: /^[1-9A-HJ-NP-Za-km-z]+$/,
base: BigInteger.valueOf(58),
/**
* Convert a byte array to a base58-encoded string.
*
* Written by Mike Hearn for BitcoinJ.
* Copyright (c) 2011 Google Inc.
*
* Ported to JavaScript by Stefan Thomas.
*/
encode: function (input) {
var bi = BigInteger.fromByteArrayUnsigned(input);
var chars = [];
while (bi.compareTo(B58.base) >= 0) {
var mod = bi.mod(B58.base);
chars.unshift(B58.alphabet[mod.intValue()]);
bi = bi.subtract(mod).divide(B58.base);
}
chars.unshift(B58.alphabet[bi.intValue()]);
// Convert leading zeros too.
for (var i = 0; i < input.length; i++) {
if (input[i] == 0x00) {
chars.unshift(B58.alphabet[0]);
} else break;
}
return chars.join('');
},
/**
* Convert a base58-encoded string to a byte array.
*
* Written by Mike Hearn for BitcoinJ.
* Copyright (c) 2011 Google Inc.
*
* Ported to JavaScript by Stefan Thomas.
*/
decode: function (input) {
var bi = BigInteger.valueOf(0);
var leadingZerosNum = 0;
for (var i = input.length - 1; i >= 0; i--) {
var alphaIndex = B58.alphabet.indexOf(input[i]);
if (alphaIndex < 0) {
throw "Invalid character";
}
bi = bi.add(BigInteger.valueOf(alphaIndex)
.multiply(B58.base.pow(input.length - 1 - i)));
// This counts leading zero bytes
if (input[i] == "1") leadingZerosNum++;
else leadingZerosNum = 0;
}
var bytes = bi.toByteArrayUnsigned();
// Add leading zeros
while (leadingZerosNum-- > 0) bytes.unshift(0);
return bytes;
}
};
return k;
}());
/* Styles go here */
/*
CryptoJS v3.1.2
code.google.com/p/crypto-js
(c) 2009-2013 by Jeff Mott. All rights reserved.
code.google.com/p/crypto-js/wiki/License
*/
/**
* CryptoJS core components.
*/
var CryptoJS = CryptoJS || (function (Math, undefined) {
/**
* CryptoJS namespace.
*/
var C = {};
/**
* Library namespace.
*/
var C_lib = C.lib = {};
/**
* Base object for prototypal inheritance.
*/
var Base = C_lib.Base = (function () {
function F() {}
return {
/**
* Creates a new object that inherits from this object.
*
* @param {Object} overrides Properties to copy into the new object.
*
* @return {Object} The new object.
*
* @static
*
* @example
*
* var MyType = CryptoJS.lib.Base.extend({
* field: 'value',
*
* method: function () {
* }
* });
*/
extend: function (overrides) {
// Spawn
F.prototype = this;
var subtype = new F();
// Augment
if (overrides) {
subtype.mixIn(overrides);
}
// Create default initializer
if (!subtype.hasOwnProperty('init')) {
subtype.init = function () {
subtype.$super.init.apply(this, arguments);
};
}
// Initializer's prototype is the subtype object
subtype.init.prototype = subtype;
// Reference supertype
subtype.$super = this;
return subtype;
},
/**
* Extends this object and runs the init method.
* Arguments to create() will be passed to init().
*
* @return {Object} The new object.
*
* @static
*
* @example
*
* var instance = MyType.create();
*/
create: function () {
var instance = this.extend();
instance.init.apply(instance, arguments);
return instance;
},
/**
* Initializes a newly created object.
* Override this method to add some logic when your objects are created.
*
* @example
*
* var MyType = CryptoJS.lib.Base.extend({
* init: function () {
* // ...
* }
* });
*/
init: function () {
},
/**
* Copies properties into this object.
*
* @param {Object} properties The properties to mix in.
*
* @example
*
* MyType.mixIn({
* field: 'value'
* });
*/
mixIn: function (properties) {
for (var propertyName in properties) {
if (properties.hasOwnProperty(propertyName)) {
this[propertyName] = properties[propertyName];
}
}
// IE won't copy toString using the loop above
if (properties.hasOwnProperty('toString')) {
this.toString = properties.toString;
}
},
/**
* Creates a copy of this object.
*
* @return {Object} The clone.
*
* @example
*
* var clone = instance.clone();
*/
clone: function () {
return this.init.prototype.extend(this);
}
};
}());
/**
* An array of 32-bit words.
*
* @property {Array} words The array of 32-bit words.
* @property {number} sigBytes The number of significant bytes in this word array.
*/
var WordArray = C_lib.WordArray = Base.extend({
/**
* Initializes a newly created word array.
*
* @param {Array} words (Optional) An array of 32-bit words.
* @param {number} sigBytes (Optional) The number of significant bytes in the words.
*
* @example
*
* var wordArray = CryptoJS.lib.WordArray.create();
* var wordArray = CryptoJS.lib.WordArray.create([0x00010203, 0x04050607]);
* var wordArray = CryptoJS.lib.WordArray.create([0x00010203, 0x04050607], 6);
*/
init: function (words, sigBytes) {
words = this.words = words || [];
if (sigBytes != undefined) {
this.sigBytes = sigBytes;
} else {
this.sigBytes = words.length * 4;
}
},
/**
* Converts this word array to a string.
*
* @param {Encoder} encoder (Optional) The encoding strategy to use. Default: CryptoJS.enc.Hex
*
* @return {string} The stringified word array.
*
* @example
*
* var string = wordArray + '';
* var string = wordArray.toString();
* var string = wordArray.toString(CryptoJS.enc.Utf8);
*/
toString: function (encoder) {
return (encoder || Hex).stringify(this);
},
/**
* Concatenates a word array to this word array.
*
* @param {WordArray} wordArray The word array to append.
*
* @return {WordArray} This word array.
*
* @example
*
* wordArray1.concat(wordArray2);
*/
concat: function (wordArray) {
// Shortcuts
var thisWords = this.words;
var thatWords = wordArray.words;
var thisSigBytes = this.sigBytes;
var thatSigBytes = wordArray.sigBytes;
// Clamp excess bits
this.clamp();
// Concat
if (thisSigBytes % 4) {
// Copy one byte at a time
for (var i = 0; i < thatSigBytes; i++) {
var thatByte = (thatWords[i >>> 2] >>> (24 - (i % 4) * 8)) & 0xff;
thisWords[(thisSigBytes + i) >>> 2] |= thatByte << (24 - ((thisSigBytes + i) % 4) * 8);
}
} else if (thatWords.length > 0xffff) {
// Copy one word at a time
for (var i = 0; i < thatSigBytes; i += 4) {
thisWords[(thisSigBytes + i) >>> 2] = thatWords[i >>> 2];
}
} else {
// Copy all words at once
thisWords.push.apply(thisWords, thatWords);
}
this.sigBytes += thatSigBytes;
// Chainable
return this;
},
/**
* Removes insignificant bits.
*
* @example
*
* wordArray.clamp();
*/
clamp: function () {
// Shortcuts
var words = this.words;
var sigBytes = this.sigBytes;
// Clamp
words[sigBytes >>> 2] &= 0xffffffff << (32 - (sigBytes % 4) * 8);
words.length = Math.ceil(sigBytes / 4);
},
/**
* Creates a copy of this word array.
*
* @return {WordArray} The clone.
*
* @example
*
* var clone = wordArray.clone();
*/
clone: function () {
var clone = Base.clone.call(this);
clone.words = this.words.slice(0);
return clone;
},
/**
* Creates a word array filled with random bytes.
*
* @param {number} nBytes The number of random bytes to generate.
*
* @return {WordArray} The random word array.
*
* @static
*
* @example
*
* var wordArray = CryptoJS.lib.WordArray.random(16);
*/
random: function (nBytes) {
var words = [];
for (var i = 0; i < nBytes; i += 4) {
words.push((Math.random() * 0x100000000) | 0);
}
return new WordArray.init(words, nBytes);
}
});
/**
* Encoder namespace.
*/
var C_enc = C.enc = {};
/**
* Hex encoding strategy.
*/
var Hex = C_enc.Hex = {
/**
* Converts a word array to a hex string.
*
* @param {WordArray} wordArray The word array.
*
* @return {string} The hex string.
*
* @static
*
* @example
*
* var hexString = CryptoJS.enc.Hex.stringify(wordArray);
*/
stringify: function (wordArray) {
// Shortcuts
var words = wordArray.words;
var sigBytes = wordArray.sigBytes;
// Convert
var hexChars = [];
for (var i = 0; i < sigBytes; i++) {
var bite = (words[i >>> 2] >>> (24 - (i % 4) * 8)) & 0xff;
hexChars.push((bite >>> 4).toString(16));
hexChars.push((bite & 0x0f).toString(16));
}
return hexChars.join('');
},
/**
* Converts a hex string to a word array.
*
* @param {string} hexStr The hex string.
*
* @return {WordArray} The word array.
*
* @static
*
* @example
*
* var wordArray = CryptoJS.enc.Hex.parse(hexString);
*/
parse: function (hexStr) {
// Shortcut
var hexStrLength = hexStr.length;
// Convert
var words = [];
for (var i = 0; i < hexStrLength; i += 2) {
words[i >>> 3] |= parseInt(hexStr.substr(i, 2), 16) << (24 - (i % 8) * 4);
}
return new WordArray.init(words, hexStrLength / 2);
}
};
/**
* Latin1 encoding strategy.
*/
var Latin1 = C_enc.Latin1 = {
/**
* Converts a word array to a Latin1 string.
*
* @param {WordArray} wordArray The word array.
*
* @return {string} The Latin1 string.
*
* @static
*
* @example
*
* var latin1String = CryptoJS.enc.Latin1.stringify(wordArray);
*/
stringify: function (wordArray) {
// Shortcuts
var words = wordArray.words;
var sigBytes = wordArray.sigBytes;
// Convert
var latin1Chars = [];
for (var i = 0; i < sigBytes; i++) {
var bite = (words[i >>> 2] >>> (24 - (i % 4) * 8)) & 0xff;
latin1Chars.push(String.fromCharCode(bite));
}
return latin1Chars.join('');
},
/**
* Converts a Latin1 string to a word array.
*
* @param {string} latin1Str The Latin1 string.
*
* @return {WordArray} The word array.
*
* @static
*
* @example
*
* var wordArray = CryptoJS.enc.Latin1.parse(latin1String);
*/
parse: function (latin1Str) {
// Shortcut
var latin1StrLength = latin1Str.length;
// Convert
var words = [];
for (var i = 0; i < latin1StrLength; i++) {
words[i >>> 2] |= (latin1Str.charCodeAt(i) & 0xff) << (24 - (i % 4) * 8);
}
return new WordArray.init(words, latin1StrLength);
}
};
/**
* UTF-8 encoding strategy.
*/
var Utf8 = C_enc.Utf8 = {
/**
* Converts a word array to a UTF-8 string.
*
* @param {WordArray} wordArray The word array.
*
* @return {string} The UTF-8 string.
*
* @static
*
* @example
*
* var utf8String = CryptoJS.enc.Utf8.stringify(wordArray);
*/
stringify: function (wordArray) {
try {
return decodeURIComponent(escape(Latin1.stringify(wordArray)));
} catch (e) {
throw new Error('Malformed UTF-8 data');
}
},
/**
* Converts a UTF-8 string to a word array.
*
* @param {string} utf8Str The UTF-8 string.
*
* @return {WordArray} The word array.
*
* @static
*
* @example
*
* var wordArray = CryptoJS.enc.Utf8.parse(utf8String);
*/
parse: function (utf8Str) {
return Latin1.parse(unescape(encodeURIComponent(utf8Str)));
}
};
/**
* Abstract buffered block algorithm template.
*
* The property blockSize must be implemented in a concrete subtype.
*
* @property {number} _minBufferSize The number of blocks that should be kept unprocessed in the buffer. Default: 0
*/
var BufferedBlockAlgorithm = C_lib.BufferedBlockAlgorithm = Base.extend({
/**
* Resets this block algorithm's data buffer to its initial state.
*
* @example
*
* bufferedBlockAlgorithm.reset();
*/
reset: function () {
// Initial values
this._data = new WordArray.init();
this._nDataBytes = 0;
},
/**
* Adds new data to this block algorithm's buffer.
*
* @param {WordArray|string} data The data to append. Strings are converted to a WordArray using UTF-8.
*
* @example
*
* bufferedBlockAlgorithm._append('data');
* bufferedBlockAlgorithm._append(wordArray);
*/
_append: function (data) {
// Convert string to WordArray, else assume WordArray already
if (typeof data == 'string') {
data = Utf8.parse(data);
}
// Append
this._data.concat(data);
this._nDataBytes += data.sigBytes;
},
/**
* Processes available data blocks.
*
* This method invokes _doProcessBlock(offset), which must be implemented by a concrete subtype.
*
* @param {boolean} doFlush Whether all blocks and partial blocks should be processed.
*
* @return {WordArray} The processed data.
*
* @example
*
* var processedData = bufferedBlockAlgorithm._process();
* var processedData = bufferedBlockAlgorithm._process(!!'flush');
*/
_process: function (doFlush) {
// Shortcuts
var data = this._data;
var dataWords = data.words;
var dataSigBytes = data.sigBytes;
var blockSize = this.blockSize;
var blockSizeBytes = blockSize * 4;
// Count blocks ready
var nBlocksReady = dataSigBytes / blockSizeBytes;
if (doFlush) {
// Round up to include partial blocks
nBlocksReady = Math.ceil(nBlocksReady);
} else {
// Round down to include only full blocks,
// less the number of blocks that must remain in the buffer
nBlocksReady = Math.max((nBlocksReady | 0) - this._minBufferSize, 0);
}
// Count words ready
var nWordsReady = nBlocksReady * blockSize;
// Count bytes ready
var nBytesReady = Math.min(nWordsReady * 4, dataSigBytes);
// Process blocks
if (nWordsReady) {
for (var offset = 0; offset < nWordsReady; offset += blockSize) {
// Perform concrete-algorithm logic
this._doProcessBlock(dataWords, offset);
}
// Remove processed words
var processedWords = dataWords.splice(0, nWordsReady);
data.sigBytes -= nBytesReady;
}
// Return processed words
return new WordArray.init(processedWords, nBytesReady);
},
/**
* Creates a copy of this object.
*
* @return {Object} The clone.
*
* @example
*
* var clone = bufferedBlockAlgorithm.clone();
*/
clone: function () {
var clone = Base.clone.call(this);
clone._data = this._data.clone();
return clone;
},
_minBufferSize: 0
});
/**
* Abstract hasher template.
*
* @property {number} blockSize The number of 32-bit words this hasher operates on. Default: 16 (512 bits)
*/
var Hasher = C_lib.Hasher = BufferedBlockAlgorithm.extend({
/**
* Configuration options.
*/
cfg: Base.extend(),
/**
* Initializes a newly created hasher.
*
* @param {Object} cfg (Optional) The configuration options to use for this hash computation.
*
* @example
*
* var hasher = CryptoJS.algo.SHA256.create();
*/
init: function (cfg) {
// Apply config defaults
this.cfg = this.cfg.extend(cfg);
// Set initial values
this.reset();
},
/**
* Resets this hasher to its initial state.
*
* @example
*
* hasher.reset();
*/
reset: function () {
// Reset data buffer
BufferedBlockAlgorithm.reset.call(this);
// Perform concrete-hasher logic
this._doReset();
},
/**
* Updates this hasher with a message.
*
* @param {WordArray|string} messageUpdate The message to append.
*
* @return {Hasher} This hasher.
*
* @example
*
* hasher.update('message');
* hasher.update(wordArray);
*/
update: function (messageUpdate) {
// Append
this._append(messageUpdate);
// Update the hash
this._process();
// Chainable
return this;
},
/**
* Finalizes the hash computation.
* Note that the finalize operation is effectively a destructive, read-once operation.
*
* @param {WordArray|string} messageUpdate (Optional) A final message update.
*
* @return {WordArray} The hash.
*
* @example
*
* var hash = hasher.finalize();
* var hash = hasher.finalize('message');
* var hash = hasher.finalize(wordArray);
*/
finalize: function (messageUpdate) {
// Final message update
if (messageUpdate) {
this._append(messageUpdate);
}
// Perform concrete-hasher logic
var hash = this._doFinalize();
return hash;
},
blockSize: 512/32,
/**
* Creates a shortcut function to a hasher's object interface.
*
* @param {Hasher} hasher The hasher to create a helper for.
*
* @return {Function} The shortcut function.
*
* @static
*
* @example
*
* var SHA256 = CryptoJS.lib.Hasher._createHelper(CryptoJS.algo.SHA256);
*/
_createHelper: function (hasher) {
return function (message, cfg) {
return new hasher.init(cfg).finalize(message);
};
},
/**
* Creates a shortcut function to the HMAC's object interface.
*
* @param {Hasher} hasher The hasher to use in this HMAC helper.
*
* @return {Function} The shortcut function.
*
* @static
*
* @example
*
* var HmacSHA256 = CryptoJS.lib.Hasher._createHmacHelper(CryptoJS.algo.SHA256);
*/
_createHmacHelper: function (hasher) {
return function (message, key) {
return new C_algo.HMAC.init(hasher, key).finalize(message);
};
}
});
/**
* Algorithm namespace.
*/
var C_algo = C.algo = {};
return C;
}(Math));
/*
CryptoJS v3.1.2
code.google.com/p/crypto-js
(c) 2009-2013 by Jeff Mott. All rights reserved.
code.google.com/p/crypto-js/wiki/License
*/
(function (Math) {
// Shortcuts
var C = CryptoJS;
var C_lib = C.lib;
var WordArray = C_lib.WordArray;
var Hasher = C_lib.Hasher;
var C_algo = C.algo;
// Initialization and round constants tables
var H = [];
var K = [];
// Compute constants
(function () {
function isPrime(n) {
var sqrtN = Math.sqrt(n);
for (var factor = 2; factor <= sqrtN; factor++) {
if (!(n % factor)) {
return false;
}
}
return true;
}
function getFractionalBits(n) {
return ((n - (n | 0)) * 0x100000000) | 0;
}
var n = 2;
var nPrime = 0;
while (nPrime < 64) {
if (isPrime(n)) {
if (nPrime < 8) {
H[nPrime] = getFractionalBits(Math.pow(n, 1 / 2));
}
K[nPrime] = getFractionalBits(Math.pow(n, 1 / 3));
nPrime++;
}
n++;
}
}());
// Reusable object
var W = [];
/**
* SHA-256 hash algorithm.
*/
var SHA256 = C_algo.SHA256 = Hasher.extend({
_doReset: function () {
this._hash = new WordArray.init(H.slice(0));
},
_doProcessBlock: function (M, offset) {
// Shortcut
var H = this._hash.words;
// Working variables
var a = H[0];
var b = H[1];
var c = H[2];
var d = H[3];
var e = H[4];
var f = H[5];
var g = H[6];
var h = H[7];
// Computation
for (var i = 0; i < 64; i++) {
if (i < 16) {
W[i] = M[offset + i] | 0;
} else {
var gamma0x = W[i - 15];
var gamma0 = ((gamma0x << 25) | (gamma0x >>> 7)) ^
((gamma0x << 14) | (gamma0x >>> 18)) ^
(gamma0x >>> 3);
var gamma1x = W[i - 2];
var gamma1 = ((gamma1x << 15) | (gamma1x >>> 17)) ^
((gamma1x << 13) | (gamma1x >>> 19)) ^
(gamma1x >>> 10);
W[i] = gamma0 + W[i - 7] + gamma1 + W[i - 16];
}
var ch = (e & f) ^ (~e & g);
var maj = (a & b) ^ (a & c) ^ (b & c);
var sigma0 = ((a << 30) | (a >>> 2)) ^ ((a << 19) | (a >>> 13)) ^ ((a << 10) | (a >>> 22));
var sigma1 = ((e << 26) | (e >>> 6)) ^ ((e << 21) | (e >>> 11)) ^ ((e << 7) | (e >>> 25));
var t1 = h + sigma1 + ch + K[i] + W[i];
var t2 = sigma0 + maj;
h = g;
g = f;
f = e;
e = (d + t1) | 0;
d = c;
c = b;
b = a;
a = (t1 + t2) | 0;
}
// Intermediate hash value
H[0] = (H[0] + a) | 0;
H[1] = (H[1] + b) | 0;
H[2] = (H[2] + c) | 0;
H[3] = (H[3] + d) | 0;
H[4] = (H[4] + e) | 0;
H[5] = (H[5] + f) | 0;
H[6] = (H[6] + g) | 0;
H[7] = (H[7] + h) | 0;
},
_doFinalize: function () {
// Shortcuts
var data = this._data;
var dataWords = data.words;
var nBitsTotal = this._nDataBytes * 8;
var nBitsLeft = data.sigBytes * 8;
// Add padding
dataWords[nBitsLeft >>> 5] |= 0x80 << (24 - nBitsLeft % 32);
dataWords[(((nBitsLeft + 64) >>> 9) << 4) + 14] = Math.floor(nBitsTotal / 0x100000000);
dataWords[(((nBitsLeft + 64) >>> 9) << 4) + 15] = nBitsTotal;
data.sigBytes = dataWords.length * 4;
// Hash final blocks
this._process();
// Return final computed hash
return this._hash;
},
clone: function () {
var clone = Hasher.clone.call(this);
clone._hash = this._hash.clone();
return clone;
}
});
/**
* Shortcut function to the hasher's object interface.
*
* @param {WordArray|string} message The message to hash.
*
* @return {WordArray} The hash.
*
* @static
*
* @example
*
* var hash = CryptoJS.SHA256('message');
* var hash = CryptoJS.SHA256(wordArray);
*/
C.SHA256 = Hasher._createHelper(SHA256);
/**
* Shortcut function to the HMAC's object interface.
*
* @param {WordArray|string} message The message to hash.
* @param {WordArray|string} key The secret key.
*
* @return {WordArray} The HMAC.
*
* @static
*
* @example
*
* var hmac = CryptoJS.HmacSHA256(message, key);
*/
C.HmacSHA256 = Hasher._createHmacHelper(SHA256);
}(Math));
/*
CryptoJS v3.1.2
code.google.com/p/crypto-js
(c) 2009-2013 by Jeff Mott. All rights reserved.
code.google.com/p/crypto-js/wiki/License
*/
/** @preserve
(c) 2012 by Cédric Mesnil. All rights reserved.
Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:
- Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.
- Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.
THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
(function (Math) {
// Shortcuts
var C = CryptoJS;
var C_lib = C.lib;
var WordArray = C_lib.WordArray;
var Hasher = C_lib.Hasher;
var C_algo = C.algo;
// Constants table
var _zl = WordArray.create([
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
7, 4, 13, 1, 10, 6, 15, 3, 12, 0, 9, 5, 2, 14, 11, 8,
3, 10, 14, 4, 9, 15, 8, 1, 2, 7, 0, 6, 13, 11, 5, 12,
1, 9, 11, 10, 0, 8, 12, 4, 13, 3, 7, 15, 14, 5, 6, 2,
4, 0, 5, 9, 7, 12, 2, 10, 14, 1, 3, 8, 11, 6, 15, 13]);
var _zr = WordArray.create([
5, 14, 7, 0, 9, 2, 11, 4, 13, 6, 15, 8, 1, 10, 3, 12,
6, 11, 3, 7, 0, 13, 5, 10, 14, 15, 8, 12, 4, 9, 1, 2,
15, 5, 1, 3, 7, 14, 6, 9, 11, 8, 12, 2, 10, 0, 4, 13,
8, 6, 4, 1, 3, 11, 15, 0, 5, 12, 2, 13, 9, 7, 10, 14,
12, 15, 10, 4, 1, 5, 8, 7, 6, 2, 13, 14, 0, 3, 9, 11]);
var _sl = WordArray.create([
11, 14, 15, 12, 5, 8, 7, 9, 11, 13, 14, 15, 6, 7, 9, 8,
7, 6, 8, 13, 11, 9, 7, 15, 7, 12, 15, 9, 11, 7, 13, 12,
11, 13, 6, 7, 14, 9, 13, 15, 14, 8, 13, 6, 5, 12, 7, 5,
11, 12, 14, 15, 14, 15, 9, 8, 9, 14, 5, 6, 8, 6, 5, 12,
9, 15, 5, 11, 6, 8, 13, 12, 5, 12, 13, 14, 11, 8, 5, 6 ]);
var _sr = WordArray.create([
8, 9, 9, 11, 13, 15, 15, 5, 7, 7, 8, 11, 14, 14, 12, 6,
9, 13, 15, 7, 12, 8, 9, 11, 7, 7, 12, 7, 6, 15, 13, 11,
9, 7, 15, 11, 8, 6, 6, 14, 12, 13, 5, 14, 13, 13, 7, 5,
15, 5, 8, 11, 14, 14, 6, 14, 6, 9, 12, 9, 12, 5, 15, 8,
8, 5, 12, 9, 12, 5, 14, 6, 8, 13, 6, 5, 15, 13, 11, 11 ]);
var _hl = WordArray.create([ 0x00000000, 0x5A827999, 0x6ED9EBA1, 0x8F1BBCDC, 0xA953FD4E]);
var _hr = WordArray.create([ 0x50A28BE6, 0x5C4DD124, 0x6D703EF3, 0x7A6D76E9, 0x00000000]);
/**
* RIPEMD160 hash algorithm.
*/
var RIPEMD160 = C_algo.RIPEMD160 = Hasher.extend({
_doReset: function () {
this._hash = WordArray.create([0x67452301, 0xEFCDAB89, 0x98BADCFE, 0x10325476, 0xC3D2E1F0]);
},
_doProcessBlock: function (M, offset) {
// Swap endian
for (var i = 0; i < 16; i++) {
// Shortcuts
var offset_i = offset + i;
var M_offset_i = M[offset_i];
// Swap
M[offset_i] = (
(((M_offset_i << 8) | (M_offset_i >>> 24)) & 0x00ff00ff) |
(((M_offset_i << 24) | (M_offset_i >>> 8)) & 0xff00ff00)
);
}
// Shortcut
var H = this._hash.words;
var hl = _hl.words;
var hr = _hr.words;
var zl = _zl.words;
var zr = _zr.words;
var sl = _sl.words;
var sr = _sr.words;
// Working variables
var al, bl, cl, dl, el;
var ar, br, cr, dr, er;
ar = al = H[0];
br = bl = H[1];
cr = cl = H[2];
dr = dl = H[3];
er = el = H[4];
// Computation
var t;
for (var i = 0; i < 80; i += 1) {
t = (al + M[offset+zl[i]])|0;
if (i<16){
t += f1(bl,cl,dl) + hl[0];
} else if (i<32) {
t += f2(bl,cl,dl) + hl[1];
} else if (i<48) {
t += f3(bl,cl,dl) + hl[2];
} else if (i<64) {
t += f4(bl,cl,dl) + hl[3];
} else {// if (i<80) {
t += f5(bl,cl,dl) + hl[4];
}
t = t|0;
t = rotl(t,sl[i]);
t = (t+el)|0;
al = el;
el = dl;
dl = rotl(cl, 10);
cl = bl;
bl = t;
t = (ar + M[offset+zr[i]])|0;
if (i<16){
t += f5(br,cr,dr) + hr[0];
} else if (i<32) {
t += f4(br,cr,dr) + hr[1];
} else if (i<48) {
t += f3(br,cr,dr) + hr[2];
} else if (i<64) {
t += f2(br,cr,dr) + hr[3];
} else {// if (i<80) {
t += f1(br,cr,dr) + hr[4];
}
t = t|0;
t = rotl(t,sr[i]) ;
t = (t+er)|0;
ar = er;
er = dr;
dr = rotl(cr, 10);
cr = br;
br = t;
}
// Intermediate hash value
t = (H[1] + cl + dr)|0;
H[1] = (H[2] + dl + er)|0;
H[2] = (H[3] + el + ar)|0;
H[3] = (H[4] + al + br)|0;
H[4] = (H[0] + bl + cr)|0;
H[0] = t;
},
_doFinalize: function () {
// Shortcuts
var data = this._data;
var dataWords = data.words;
var nBitsTotal = this._nDataBytes * 8;
var nBitsLeft = data.sigBytes * 8;
// Add padding
dataWords[nBitsLeft >>> 5] |= 0x80 << (24 - nBitsLeft % 32);
dataWords[(((nBitsLeft + 64) >>> 9) << 4) + 14] = (
(((nBitsTotal << 8) | (nBitsTotal >>> 24)) & 0x00ff00ff) |
(((nBitsTotal << 24) | (nBitsTotal >>> 8)) & 0xff00ff00)
);
data.sigBytes = (dataWords.length + 1) * 4;
// Hash final blocks
this._process();
// Shortcuts
var hash = this._hash;
var H = hash.words;
// Swap endian
for (var i = 0; i < 5; i++) {
// Shortcut
var H_i = H[i];
// Swap
H[i] = (((H_i << 8) | (H_i >>> 24)) & 0x00ff00ff) |
(((H_i << 24) | (H_i >>> 8)) & 0xff00ff00);
}
// Return final computed hash
return hash;
},
clone: function () {
var clone = Hasher.clone.call(this);
clone._hash = this._hash.clone();
return clone;
}
});
function f1(x, y, z) {
return ((x) ^ (y) ^ (z));
}
function f2(x, y, z) {
return (((x)&(y)) | ((~x)&(z)));
}
function f3(x, y, z) {
return (((x) | (~(y))) ^ (z));
}
function f4(x, y, z) {
return (((x) & (z)) | ((y)&(~(z))));
}
function f5(x, y, z) {
return ((x) ^ ((y) |(~(z))));
}
function rotl(x,n) {
return (x<<n) | (x>>>(32-n));
}
/**
* Shortcut function to the hasher's object interface.
*
* @param {WordArray|string} message The message to hash.
*
* @return {WordArray} The hash.
*
* @static
*
* @example
*
* var hash = CryptoJS.RIPEMD160('message');
* var hash = CryptoJS.RIPEMD160(wordArray);
*/
C.RIPEMD160 = Hasher._createHelper(RIPEMD160);
/**
* Shortcut function to the HMAC's object interface.
*
* @param {WordArray|string} message The message to hash.
* @param {WordArray|string} key The secret key.
*
* @return {WordArray} The HMAC.
*
* @static
*
* @example
*
* var hmac = CryptoJS.HmacRIPEMD160(message, key);
*/
C.HmacRIPEMD160 = Hasher._createHmacHelper(RIPEMD160);
}(Math));
// Upstream 'BigInteger' here:
// Original Author: http://www-cs-students.stanford.edu/~tjw/jsbn/
// Follows 'jsbn' on Github: https://github.com/jasondavies/jsbn
// Review and Testing: https://github.com/cryptocoinjs/bigi/
/*!
* Basic JavaScript BN library - subset useful for RSA encryption. v1.4
*
* Copyright (c) 2005 Tom Wu
* All Rights Reserved.
* BSD License
* http://www-cs-students.stanford.edu/~tjw/jsbn/LICENSE
*
* Copyright Stephan Thomas
* Copyright pointbiz
*/
(function () {
// (public) Constructor function of Global BigInteger object
var BigInteger = window.BigInteger = function BigInteger(a, b, c) {
if (!(this instanceof BigInteger))
return new BigInteger(a, b, c);
if (a != null)
if ("number" == typeof a) this.fromNumber(a, b, c);
else if (b == null && "string" != typeof a) this.fromString(a, 256);
else this.fromString(a, b);
};
// Bits per digit
var dbits;
// JavaScript engine analysis
var canary = 0xdeadbeefcafe;
var j_lm = ((canary & 0xffffff) == 0xefcafe);
// return new, unset BigInteger
function nbi() { return new BigInteger(null); }
// am: Compute w_j += (x*this_i), propagate carries,
// c is initial carry, returns final carry.
// c < 3*dvalue, x < 2*dvalue, this_i < dvalue
// We need to select the fastest one that works in this environment.
// am1: use a single mult and divide to get the high bits,
// max digit bits should be 26 because
// max internal value = 2*dvalue^2-2*dvalue (< 2^53)
function am1(i, x, w, j, c, n) {
while (--n >= 0) {
var v = x * this[i++] + w[j] + c;
c = Math.floor(v / 0x4000000);
w[j++] = v & 0x3ffffff;
}
return c;
}
// am2 avoids a big mult-and-extract completely.
// Max digit bits should be <= 30 because we do bitwise ops
// on values up to 2*hdvalue^2-hdvalue-1 (< 2^31)
function am2(i, x, w, j, c, n) {
var xl = x & 0x7fff, xh = x >> 15;
while (--n >= 0) {
var l = this[i] & 0x7fff;
var h = this[i++] >> 15;
var m = xh * l + h * xl;
l = xl * l + ((m & 0x7fff) << 15) + w[j] + (c & 0x3fffffff);
c = (l >>> 30) + (m >>> 15) + xh * h + (c >>> 30);
w[j++] = l & 0x3fffffff;
}
return c;
}
// Alternately, set max digit bits to 28 since some
// browsers slow down when dealing with 32-bit numbers.
function am3(i, x, w, j, c, n) {
var xl = x & 0x3fff, xh = x >> 14;
while (--n >= 0) {
var l = this[i] & 0x3fff;
var h = this[i++] >> 14;
var m = xh * l + h * xl;
l = xl * l + ((m & 0x3fff) << 14) + w[j] + c;
c = (l >> 28) + (m >> 14) + xh * h;
w[j++] = l & 0xfffffff;
}
return c;
}
if (j_lm && (navigator.appName == "Microsoft Internet Explorer")) {
BigInteger.prototype.am = am2;
dbits = 30;
}
else if (j_lm && (navigator.appName != "Netscape")) {
BigInteger.prototype.am = am1;
dbits = 26;
}
else { // Mozilla/Netscape seems to prefer am3
BigInteger.prototype.am = am3;
dbits = 28;
}
BigInteger.prototype.DB = dbits;
BigInteger.prototype.DM = ((1 << dbits) - 1);
BigInteger.prototype.DV = (1 << dbits);
var BI_FP = 52;
BigInteger.prototype.FV = Math.pow(2, BI_FP);
BigInteger.prototype.F1 = BI_FP - dbits;
BigInteger.prototype.F2 = 2 * dbits - BI_FP;
// Digit conversions
var BI_RM = "0123456789abcdefghijklmnopqrstuvwxyz";
var BI_RC = new Array();
var rr, vv;
rr = "0".charCodeAt(0);
for (vv = 0; vv <= 9; ++vv) BI_RC[rr++] = vv;
rr = "a".charCodeAt(0);
for (vv = 10; vv < 36; ++vv) BI_RC[rr++] = vv;
rr = "A".charCodeAt(0);
for (vv = 10; vv < 36; ++vv) BI_RC[rr++] = vv;
function int2char(n) { return BI_RM.charAt(n); }
function intAt(s, i) {
var c = BI_RC[s.charCodeAt(i)];
return (c == null) ? -1 : c;
}
// return bigint initialized to value
function nbv(i) { var r = nbi(); r.fromInt(i); return r; }
// returns bit length of the integer x
function nbits(x) {
var r = 1, t;
if ((t = x >>> 16) != 0) { x = t; r += 16; }
if ((t = x >> 8) != 0) { x = t; r += 8; }
if ((t = x >> 4) != 0) { x = t; r += 4; }
if ((t = x >> 2) != 0) { x = t; r += 2; }
if ((t = x >> 1) != 0) { x = t; r += 1; }
return r;
}
// (protected) copy this to r
BigInteger.prototype.copyTo = function (r) {
for (var i = this.t - 1; i >= 0; --i) r[i] = this[i];
r.t = this.t;
r.s = this.s;
};
// (protected) set from integer value x, -DV <= x < DV
BigInteger.prototype.fromInt = function (x) {
this.t = 1;
this.s = (x < 0) ? -1 : 0;
if (x > 0) this[0] = x;
else if (x < -1) this[0] = x + this.DV;
else this.t = 0;
};
// (protected) set from string and radix
BigInteger.prototype.fromString = function (s, b) {
var k;
if (b == 16) k = 4;
else if (b == 8) k = 3;
else if (b == 256) k = 8; // byte array
else if (b == 2) k = 1;
else if (b == 32) k = 5;
else if (b == 4) k = 2;
else { this.fromRadix(s, b); return; }
this.t = 0;
this.s = 0;
var i = s.length, mi = false, sh = 0;
while (--i >= 0) {
var x = (k == 8) ? s[i] & 0xff : intAt(s, i);
if (x < 0) {
if (s.charAt(i) == "-") mi = true;
continue;
}
mi = false;
if (sh == 0)
this[this.t++] = x;
else if (sh + k > this.DB) {
this[this.t - 1] |= (x & ((1 << (this.DB - sh)) - 1)) << sh;
this[this.t++] = (x >> (this.DB - sh));
}
else
this[this.t - 1] |= x << sh;
sh += k;
if (sh >= this.DB) sh -= this.DB;
}
if (k == 8 && (s[0] & 0x80) != 0) {
this.s = -1;
if (sh > 0) this[this.t - 1] |= ((1 << (this.DB - sh)) - 1) << sh;
}
this.clamp();
if (mi) BigInteger.ZERO.subTo(this, this);
};
// (protected) clamp off excess high words
BigInteger.prototype.clamp = function () {
var c = this.s & this.DM;
while (this.t > 0 && this[this.t - 1] == c) --this.t;
};
// (protected) r = this << n*DB
BigInteger.prototype.dlShiftTo = function (n, r) {
var i;
for (i = this.t - 1; i >= 0; --i) r[i + n] = this[i];
for (i = n - 1; i >= 0; --i) r[i] = 0;
r.t = this.t + n;
r.s = this.s;
};
// (protected) r = this >> n*DB
BigInteger.prototype.drShiftTo = function (n, r) {
for (var i = n; i < this.t; ++i) r[i - n] = this[i];
r.t = Math.max(this.t - n, 0);
r.s = this.s;
};
// (protected) r = this << n
BigInteger.prototype.lShiftTo = function (n, r) {
var bs = n % this.DB;
var cbs = this.DB - bs;
var bm = (1 << cbs) - 1;
var ds = Math.floor(n / this.DB), c = (this.s << bs) & this.DM, i;
for (i = this.t - 1; i >= 0; --i) {
r[i + ds + 1] = (this[i] >> cbs) | c;
c = (this[i] & bm) << bs;
}
for (i = ds - 1; i >= 0; --i) r[i] = 0;
r[ds] = c;
r.t = this.t + ds + 1;
r.s = this.s;
r.clamp();
};
// (protected) r = this >> n
BigInteger.prototype.rShiftTo = function (n, r) {
r.s = this.s;
var ds = Math.floor(n / this.DB);
if (ds >= this.t) { r.t = 0; return; }
var bs = n % this.DB;
var cbs = this.DB - bs;
var bm = (1 << bs) - 1;
r[0] = this[ds] >> bs;
for (var i = ds + 1; i < this.t; ++i) {
r[i - ds - 1] |= (this[i] & bm) << cbs;
r[i - ds] = this[i] >> bs;
}
if (bs > 0) r[this.t - ds - 1] |= (this.s & bm) << cbs;
r.t = this.t - ds;
r.clamp();
};
// (protected) r = this - a
BigInteger.prototype.subTo = function (a, r) {
var i = 0, c = 0, m = Math.min(a.t, this.t);
while (i < m) {
c += this[i] - a[i];
r[i++] = c & this.DM;
c >>= this.DB;
}
if (a.t < this.t) {
c -= a.s;
while (i < this.t) {
c += this[i];
r[i++] = c & this.DM;
c >>= this.DB;
}
c += this.s;
}
else {
c += this.s;
while (i < a.t) {
c -= a[i];
r[i++] = c & this.DM;
c >>= this.DB;
}
c -= a.s;
}
r.s = (c < 0) ? -1 : 0;
if (c < -1) r[i++] = this.DV + c;
else if (c > 0) r[i++] = c;
r.t = i;
r.clamp();
};
// (protected) r = this * a, r != this,a (HAC 14.12)
// "this" should be the larger one if appropriate.
BigInteger.prototype.multiplyTo = function (a, r) {
var x = this.abs(), y = a.abs();
var i = x.t;
r.t = i + y.t;
while (--i >= 0) r[i] = 0;
for (i = 0; i < y.t; ++i) r[i + x.t] = x.am(0, y[i], r, i, 0, x.t);
r.s = 0;
r.clamp();
if (this.s != a.s) BigInteger.ZERO.subTo(r, r);
};
// (protected) r = this^2, r != this (HAC 14.16)
BigInteger.prototype.squareTo = function (r) {
var x = this.abs();
var i = r.t = 2 * x.t;
while (--i >= 0) r[i] = 0;
for (i = 0; i < x.t - 1; ++i) {
var c = x.am(i, x[i], r, 2 * i, 0, 1);
if ((r[i + x.t] += x.am(i + 1, 2 * x[i], r, 2 * i + 1, c, x.t - i - 1)) >= x.DV) {
r[i + x.t] -= x.DV;
r[i + x.t + 1] = 1;
}
}
if (r.t > 0) r[r.t - 1] += x.am(i, x[i], r, 2 * i, 0, 1);
r.s = 0;
r.clamp();
};
// (protected) divide this by m, quotient and remainder to q, r (HAC 14.20)
// r != q, this != m. q or r may be null.
BigInteger.prototype.divRemTo = function (m, q, r) {
var pm = m.abs();
if (pm.t <= 0) return;
var pt = this.abs();
if (pt.t < pm.t) {
if (q != null) q.fromInt(0);
if (r != null) this.copyTo(r);
return;
}
if (r == null) r = nbi();
var y = nbi(), ts = this.s, ms = m.s;
var nsh = this.DB - nbits(pm[pm.t - 1]); // normalize modulus
if (nsh > 0) { pm.lShiftTo(nsh, y); pt.lShiftTo(nsh, r); }
else { pm.copyTo(y); pt.copyTo(r); }
var ys = y.t;
var y0 = y[ys - 1];
if (y0 == 0) return;
var yt = y0 * (1 << this.F1) + ((ys > 1) ? y[ys - 2] >> this.F2 : 0);
var d1 = this.FV / yt, d2 = (1 << this.F1) / yt, e = 1 << this.F2;
var i = r.t, j = i - ys, t = (q == null) ? nbi() : q;
y.dlShiftTo(j, t);
if (r.compareTo(t) >= 0) {
r[r.t++] = 1;
r.subTo(t, r);
}
BigInteger.ONE.dlShiftTo(ys, t);
t.subTo(y, y); // "negative" y so we can replace sub with am later
while (y.t < ys) y[y.t++] = 0;
while (--j >= 0) {
// Estimate quotient digit
var qd = (r[--i] == y0) ? this.DM : Math.floor(r[i] * d1 + (r[i - 1] + e) * d2);
if ((r[i] += y.am(0, qd, r, j, 0, ys)) < qd) { // Try it out
y.dlShiftTo(j, t);
r.subTo(t, r);
while (r[i] < --qd) r.subTo(t, r);
}
}
if (q != null) {
r.drShiftTo(ys, q);
if (ts != ms) BigInteger.ZERO.subTo(q, q);
}
r.t = ys;
r.clamp();
if (nsh > 0) r.rShiftTo(nsh, r); // Denormalize remainder
if (ts < 0) BigInteger.ZERO.subTo(r, r);
};
// (protected) return "-1/this % 2^DB"; useful for Mont. reduction
// justification:
// xy == 1 (mod m)
// xy = 1+km
// xy(2-xy) = (1+km)(1-km)
// x[y(2-xy)] = 1-k^2m^2
// x[y(2-xy)] == 1 (mod m^2)
// if y is 1/x mod m, then y(2-xy) is 1/x mod m^2
// should reduce x and y(2-xy) by m^2 at each step to keep size bounded.
// JS multiply "overflows" differently from C/C++, so care is needed here.
BigInteger.prototype.invDigit = function () {
if (this.t < 1) return 0;
var x = this[0];
if ((x & 1) == 0) return 0;
var y = x & 3; // y == 1/x mod 2^2
y = (y * (2 - (x & 0xf) * y)) & 0xf; // y == 1/x mod 2^4
y = (y * (2 - (x & 0xff) * y)) & 0xff; // y == 1/x mod 2^8
y = (y * (2 - (((x & 0xffff) * y) & 0xffff))) & 0xffff; // y == 1/x mod 2^16
// last step - calculate inverse mod DV directly;
// assumes 16 < DB <= 32 and assumes ability to handle 48-bit ints
y = (y * (2 - x * y % this.DV)) % this.DV; // y == 1/x mod 2^dbits
// we really want the negative inverse, and -DV < y < DV
return (y > 0) ? this.DV - y : -y;
};
// (protected) true iff this is even
BigInteger.prototype.isEven = function () { return ((this.t > 0) ? (this[0] & 1) : this.s) == 0; };
// (protected) this^e, e < 2^32, doing sqr and mul with "r" (HAC 14.79)
BigInteger.prototype.exp = function (e, z) {
if (e > 0xffffffff || e < 1) return BigInteger.ONE;
var r = nbi(), r2 = nbi(), g = z.convert(this), i = nbits(e) - 1;
g.copyTo(r);
while (--i >= 0) {
z.sqrTo(r, r2);
if ((e & (1 << i)) > 0) z.mulTo(r2, g, r);
else { var t = r; r = r2; r2 = t; }
}
return z.revert(r);
};
// (public) return string representation in given radix
BigInteger.prototype.toString = function (b) {
if (this.s < 0) return "-" + this.negate().toString(b);
var k;
if (b == 16) k = 4;
else if (b == 8) k = 3;
else if (b == 2) k = 1;
else if (b == 32) k = 5;
else if (b == 4) k = 2;
else return this.toRadix(b);
var km = (1 << k) - 1, d, m = false, r = "", i = this.t;
var p = this.DB - (i * this.DB) % k;
if (i-- > 0) {
if (p < this.DB && (d = this[i] >> p) > 0) { m = true; r = int2char(d); }
while (i >= 0) {
if (p < k) {
d = (this[i] & ((1 << p) - 1)) << (k - p);
d |= this[--i] >> (p += this.DB - k);
}
else {
d = (this[i] >> (p -= k)) & km;
if (p <= 0) { p += this.DB; --i; }
}
if (d > 0) m = true;
if (m) r += int2char(d);
}
}
return m ? r : "0";
};
// (public) -this
BigInteger.prototype.negate = function () { var r = nbi(); BigInteger.ZERO.subTo(this, r); return r; };
// (public) |this|
BigInteger.prototype.abs = function () { return (this.s < 0) ? this.negate() : this; };
// (public) return + if this > a, - if this < a, 0 if equal
BigInteger.prototype.compareTo = function (a) {
var r = this.s - a.s;
if (r != 0) return r;
var i = this.t;
r = i - a.t;
if (r != 0) return (this.s < 0) ? -r : r;
while (--i >= 0) if ((r = this[i] - a[i]) != 0) return r;
return 0;
}
// (public) return the number of bits in "this"
BigInteger.prototype.bitLength = function () {
if (this.t <= 0) return 0;
return this.DB * (this.t - 1) + nbits(this[this.t - 1] ^ (this.s & this.DM));
};
// (public) this mod a
BigInteger.prototype.mod = function (a) {
var r = nbi();
this.abs().divRemTo(a, null, r);
if (this.s < 0 && r.compareTo(BigInteger.ZERO) > 0) a.subTo(r, r);
return r;
}
// (public) this^e % m, 0 <= e < 2^32
BigInteger.prototype.modPowInt = function (e, m) {
var z;
if (e < 256 || m.isEven()) z = new Classic(m); else z = new Montgomery(m);
return this.exp(e, z);
};
// "constants"
BigInteger.ZERO = nbv(0);
BigInteger.ONE = nbv(1);
// Copyright (c) 2005-2009 Tom Wu
// All Rights Reserved.
// See "LICENSE" for details.
// Extended JavaScript BN functions, required for RSA private ops.
// Version 1.1: new BigInteger("0", 10) returns "proper" zero
// Version 1.2: square() API, isProbablePrime fix
// return index of lowest 1-bit in x, x < 2^31
function lbit(x) {
if (x == 0) return -1;
var r = 0;
if ((x & 0xffff) == 0) { x >>= 16; r += 16; }
if ((x & 0xff) == 0) { x >>= 8; r += 8; }
if ((x & 0xf) == 0) { x >>= 4; r += 4; }
if ((x & 3) == 0) { x >>= 2; r += 2; }
if ((x & 1) == 0) ++r;
return r;
}
// return number of 1 bits in x
function cbit(x) {
var r = 0;
while (x != 0) { x &= x - 1; ++r; }
return r;
}
var lowprimes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997];
var lplim = (1 << 26) / lowprimes[lowprimes.length - 1];
// (protected) return x s.t. r^x < DV
BigInteger.prototype.chunkSize = function (r) { return Math.floor(Math.LN2 * this.DB / Math.log(r)); };
// (protected) convert to radix string
BigInteger.prototype.toRadix = function (b) {
if (b == null) b = 10;
if (this.signum() == 0 || b < 2 || b > 36) return "0";
var cs = this.chunkSize(b);
var a = Math.pow(b, cs);
var d = nbv(a), y = nbi(), z = nbi(), r = "";
this.divRemTo(d, y, z);
while (y.signum() > 0) {
r = (a + z.intValue()).toString(b).substr(1) + r;
y.divRemTo(d, y, z);
}
return z.intValue().toString(b) + r;
};
// (protected) convert from radix string
BigInteger.prototype.fromRadix = function (s, b) {
this.fromInt(0);
if (b == null) b = 10;
var cs = this.chunkSize(b);
var d = Math.pow(b, cs), mi = false, j = 0, w = 0;
for (var i = 0; i < s.length; ++i) {
var x = intAt(s, i);
if (x < 0) {
if (s.charAt(i) == "-" && this.signum() == 0) mi = true;
continue;
}
w = b * w + x;
if (++j >= cs) {
this.dMultiply(d);
this.dAddOffset(w, 0);
j = 0;
w = 0;
}
}
if (j > 0) {
this.dMultiply(Math.pow(b, j));
this.dAddOffset(w, 0);
}
if (mi) BigInteger.ZERO.subTo(this, this);
};
// (protected) alternate constructor
BigInteger.prototype.fromNumber = function (a, b, c) {
if ("number" == typeof b) {
// new BigInteger(int,int,RNG)
if (a < 2) this.fromInt(1);
else {
this.fromNumber(a, c);
if (!this.testBit(a - 1)) // force MSB set
this.bitwiseTo(BigInteger.ONE.shiftLeft(a - 1), op_or, this);
if (this.isEven()) this.dAddOffset(1, 0); // force odd
while (!this.isProbablePrime(b)) {
this.dAddOffset(2, 0);
if (this.bitLength() > a) this.subTo(BigInteger.ONE.shiftLeft(a - 1), this);
}
}
}
else {
// new BigInteger(int,RNG)
var x = new Array(), t = a & 7;
x.length = (a >> 3) + 1;
b.nextBytes(x);
if (t > 0) x[0] &= ((1 << t) - 1); else x[0] = 0;
this.fromString(x, 256);
}
};
// (protected) r = this op a (bitwise)
BigInteger.prototype.bitwiseTo = function (a, op, r) {
var i, f, m = Math.min(a.t, this.t);
for (i = 0; i < m; ++i) r[i] = op(this[i], a[i]);
if (a.t < this.t) {
f = a.s & this.DM;
for (i = m; i < this.t; ++i) r[i] = op(this[i], f);
r.t = this.t;
}
else {
f = this.s & this.DM;
for (i = m; i < a.t; ++i) r[i] = op(f, a[i]);
r.t = a.t;
}
r.s = op(this.s, a.s);
r.clamp();
};
// (protected) this op (1<<n)
BigInteger.prototype.changeBit = function (n, op) {
var r = BigInteger.ONE.shiftLeft(n);
this.bitwiseTo(r, op, r);
return r;
};
// (protected) r = this + a
BigInteger.prototype.addTo = function (a, r) {
var i = 0, c = 0, m = Math.min(a.t, this.t);
while (i < m) {
c += this[i] + a[i];
r[i++] = c & this.DM;
c >>= this.DB;
}
if (a.t < this.t) {
c += a.s;
while (i < this.t) {
c += this[i];
r[i++] = c & this.DM;
c >>= this.DB;
}
c += this.s;
}
else {
c += this.s;
while (i < a.t) {
c += a[i];
r[i++] = c & this.DM;
c >>= this.DB;
}
c += a.s;
}
r.s = (c < 0) ? -1 : 0;
if (c > 0) r[i++] = c;
else if (c < -1) r[i++] = this.DV + c;
r.t = i;
r.clamp();
};
// (protected) this *= n, this >= 0, 1 < n < DV
BigInteger.prototype.dMultiply = function (n) {
this[this.t] = this.am(0, n - 1, this, 0, 0, this.t);
++this.t;
this.clamp();
};
// (protected) this += n << w words, this >= 0
BigInteger.prototype.dAddOffset = function (n, w) {
if (n == 0) return;
while (this.t <= w) this[this.t++] = 0;
this[w] += n;
while (this[w] >= this.DV) {
this[w] -= this.DV;
if (++w >= this.t) this[this.t++] = 0;
++this[w];
}
};
// (protected) r = lower n words of "this * a", a.t <= n
// "this" should be the larger one if appropriate.
BigInteger.prototype.multiplyLowerTo = function (a, n, r) {
var i = Math.min(this.t + a.t, n);
r.s = 0; // assumes a,this >= 0
r.t = i;
while (i > 0) r[--i] = 0;
var j;
for (j = r.t - this.t; i < j; ++i) r[i + this.t] = this.am(0, a[i], r, i, 0, this.t);
for (j = Math.min(a.t, n); i < j; ++i) this.am(0, a[i], r, i, 0, n - i);
r.clamp();
};
// (protected) r = "this * a" without lower n words, n > 0
// "this" should be the larger one if appropriate.
BigInteger.prototype.multiplyUpperTo = function (a, n, r) {
--n;
var i = r.t = this.t + a.t - n;
r.s = 0; // assumes a,this >= 0
while (--i >= 0) r[i] = 0;
for (i = Math.max(n - this.t, 0); i < a.t; ++i)
r[this.t + i - n] = this.am(n - i, a[i], r, 0, 0, this.t + i - n);
r.clamp();
r.drShiftTo(1, r);
};
// (protected) this % n, n < 2^26
BigInteger.prototype.modInt = function (n) {
if (n <= 0) return 0;
var d = this.DV % n, r = (this.s < 0) ? n - 1 : 0;
if (this.t > 0)
if (d == 0) r = this[0] % n;
else for (var i = this.t - 1; i >= 0; --i) r = (d * r + this[i]) % n;
return r;
};
// (protected) true if probably prime (HAC 4.24, Miller-Rabin)
BigInteger.prototype.millerRabin = function (t) {
var n1 = this.subtract(BigInteger.ONE);
var k = n1.getLowestSetBit();
if (k <= 0) return false;
var r = n1.shiftRight(k);
t = (t + 1) >> 1;
if (t > lowprimes.length) t = lowprimes.length;
var a = nbi();
for (var i = 0; i < t; ++i) {
//Pick bases at random, instead of starting at 2
a.fromInt(lowprimes[Math.floor(Math.random() * lowprimes.length)]);
var y = a.modPow(r, this);
if (y.compareTo(BigInteger.ONE) != 0 && y.compareTo(n1) != 0) {
var j = 1;
while (j++ < k && y.compareTo(n1) != 0) {
y = y.modPowInt(2, this);
if (y.compareTo(BigInteger.ONE) == 0) return false;
}
if (y.compareTo(n1) != 0) return false;
}
}
return true;
};
// (public)
BigInteger.prototype.clone = function () { var r = nbi(); this.copyTo(r); return r; };
// (public) return value as integer
BigInteger.prototype.intValue = function () {
if (this.s < 0) {
if (this.t == 1) return this[0] - this.DV;
else if (this.t == 0) return -1;
}
else if (this.t == 1) return this[0];
else if (this.t == 0) return 0;
// assumes 16 < DB < 32
return ((this[1] & ((1 << (32 - this.DB)) - 1)) << this.DB) | this[0];
};
// (public) return value as byte
BigInteger.prototype.byteValue = function () { return (this.t == 0) ? this.s : (this[0] << 24) >> 24; };
// (public) return value as short (assumes DB>=16)
BigInteger.prototype.shortValue = function () { return (this.t == 0) ? this.s : (this[0] << 16) >> 16; };
// (public) 0 if this == 0, 1 if this > 0
BigInteger.prototype.signum = function () {
if (this.s < 0) return -1;
else if (this.t <= 0 || (this.t == 1 && this[0] <= 0)) return 0;
else return 1;
};
// (public) convert to bigendian byte array
BigInteger.prototype.toByteArray = function () {
var i = this.t, r = new Array();
r[0] = this.s;
var p = this.DB - (i * this.DB) % 8, d, k = 0;
if (i-- > 0) {
if (p < this.DB && (d = this[i] >> p) != (this.s & this.DM) >> p)
r[k++] = d | (this.s << (this.DB - p));
while (i >= 0) {
if (p < 8) {
d = (this[i] & ((1 << p) - 1)) << (8 - p);
d |= this[--i] >> (p += this.DB - 8);
}
else {
d = (this[i] >> (p -= 8)) & 0xff;
if (p <= 0) { p += this.DB; --i; }
}
if ((d & 0x80) != 0) d |= -256;
if (k == 0 && (this.s & 0x80) != (d & 0x80)) ++k;
if (k > 0 || d != this.s) r[k++] = d;
}
}
return r;
};
BigInteger.prototype.equals = function (a) { return (this.compareTo(a) == 0); };
BigInteger.prototype.min = function (a) { return (this.compareTo(a) < 0) ? this : a; };
BigInteger.prototype.max = function (a) { return (this.compareTo(a) > 0) ? this : a; };
// (public) this & a
function op_and(x, y) { return x & y; }
BigInteger.prototype.and = function (a) { var r = nbi(); this.bitwiseTo(a, op_and, r); return r; };
// (public) this | a
function op_or(x, y) { return x | y; }
BigInteger.prototype.or = function (a) { var r = nbi(); this.bitwiseTo(a, op_or, r); return r; };
// (public) this ^ a
function op_xor(x, y) { return x ^ y; }
BigInteger.prototype.xor = function (a) { var r = nbi(); this.bitwiseTo(a, op_xor, r); return r; };
// (public) this & ~a
function op_andnot(x, y) { return x & ~y; }
BigInteger.prototype.andNot = function (a) { var r = nbi(); this.bitwiseTo(a, op_andnot, r); return r; };
// (public) ~this
BigInteger.prototype.not = function () {
var r = nbi();
for (var i = 0; i < this.t; ++i) r[i] = this.DM & ~this[i];
r.t = this.t;
r.s = ~this.s;
return r;
};
// (public) this << n
BigInteger.prototype.shiftLeft = function (n) {
var r = nbi();
if (n < 0) this.rShiftTo(-n, r); else this.lShiftTo(n, r);
return r;
};
// (public) this >> n
BigInteger.prototype.shiftRight = function (n) {
var r = nbi();
if (n < 0) this.lShiftTo(-n, r); else this.rShiftTo(n, r);
return r;
};
// (public) returns index of lowest 1-bit (or -1 if none)
BigInteger.prototype.getLowestSetBit = function () {
for (var i = 0; i < this.t; ++i)
if (this[i] != 0) return i * this.DB + lbit(this[i]);
if (this.s < 0) return this.t * this.DB;
return -1;
};
// (public) return number of set bits
BigInteger.prototype.bitCount = function () {
var r = 0, x = this.s & this.DM;
for (var i = 0; i < this.t; ++i) r += cbit(this[i] ^ x);
return r;
};
// (public) true iff nth bit is set
BigInteger.prototype.testBit = function (n) {
var j = Math.floor(n / this.DB);
if (j >= this.t) return (this.s != 0);
return ((this[j] & (1 << (n % this.DB))) != 0);
};
// (public) this | (1<<n)
BigInteger.prototype.setBit = function (n) { return this.changeBit(n, op_or); };
// (public) this & ~(1<<n)
BigInteger.prototype.clearBit = function (n) { return this.changeBit(n, op_andnot); };
// (public) this ^ (1<<n)
BigInteger.prototype.flipBit = function (n) { return this.changeBit(n, op_xor); };
// (public) this + a
BigInteger.prototype.add = function (a) { var r = nbi(); this.addTo(a, r); return r; };
// (public) this - a
BigInteger.prototype.subtract = function (a) { var r = nbi(); this.subTo(a, r); return r; };
// (public) this * a
BigInteger.prototype.multiply = function (a) { var r = nbi(); this.multiplyTo(a, r); return r; };
// (public) this / a
BigInteger.prototype.divide = function (a) { var r = nbi(); this.divRemTo(a, r, null); return r; };
// (public) this % a
BigInteger.prototype.remainder = function (a) { var r = nbi(); this.divRemTo(a, null, r); return r; };
// (public) [this/a,this%a]
BigInteger.prototype.divideAndRemainder = function (a) {
var q = nbi(), r = nbi();
this.divRemTo(a, q, r);
return new Array(q, r);
};
// (public) this^e % m (HAC 14.85)
BigInteger.prototype.modPow = function (e, m) {
var i = e.bitLength(), k, r = nbv(1), z;
if (i <= 0) return r;
else if (i < 18) k = 1;
else if (i < 48) k = 3;
else if (i < 144) k = 4;
else if (i < 768) k = 5;
else k = 6;
if (i < 8)
z = new Classic(m);
else if (m.isEven())
z = new Barrett(m);
else
z = new Montgomery(m);
// precomputation
var g = new Array(), n = 3, k1 = k - 1, km = (1 << k) - 1;
g[1] = z.convert(this);
if (k > 1) {
var g2 = nbi();
z.sqrTo(g[1], g2);
while (n <= km) {
g[n] = nbi();
z.mulTo(g2, g[n - 2], g[n]);
n += 2;
}
}
var j = e.t - 1, w, is1 = true, r2 = nbi(), t;
i = nbits(e[j]) - 1;
while (j >= 0) {
if (i >= k1) w = (e[j] >> (i - k1)) & km;
else {
w = (e[j] & ((1 << (i + 1)) - 1)) << (k1 - i);
if (j > 0) w |= e[j - 1] >> (this.DB + i - k1);
}
n = k;
while ((w & 1) == 0) { w >>= 1; --n; }
if ((i -= n) < 0) { i += this.DB; --j; }
if (is1) { // ret == 1, don't bother squaring or multiplying it
g[w].copyTo(r);
is1 = false;
}
else {
while (n > 1) { z.sqrTo(r, r2); z.sqrTo(r2, r); n -= 2; }
if (n > 0) z.sqrTo(r, r2); else { t = r; r = r2; r2 = t; }
z.mulTo(r2, g[w], r);
}
while (j >= 0 && (e[j] & (1 << i)) == 0) {
z.sqrTo(r, r2); t = r; r = r2; r2 = t;
if (--i < 0) { i = this.DB - 1; --j; }
}
}
return z.revert(r);
};
// (public) 1/this % m (HAC 14.61)
BigInteger.prototype.modInverse = function (m) {
var ac = m.isEven();
if (this.signum() === 0) throw new Error('division by zero');
if ((this.isEven() && ac) || m.signum() == 0) return BigInteger.ZERO;
var u = m.clone(), v = this.clone();
var a = nbv(1), b = nbv(0), c = nbv(0), d = nbv(1);
while (u.signum() != 0) {
while (u.isEven()) {
u.rShiftTo(1, u);
if (ac) {
if (!a.isEven() || !b.isEven()) { a.addTo(this, a); b.subTo(m, b); }
a.rShiftTo(1, a);
}
else if (!b.isEven()) b.subTo(m, b);
b.rShiftTo(1, b);
}
while (v.isEven()) {
v.rShiftTo(1, v);
if (ac) {
if (!c.isEven() || !d.isEven()) { c.addTo(this, c); d.subTo(m, d); }
c.rShiftTo(1, c);
}
else if (!d.isEven()) d.subTo(m, d);
d.rShiftTo(1, d);
}
if (u.compareTo(v) >= 0) {
u.subTo(v, u);
if (ac) a.subTo(c, a);
b.subTo(d, b);
}
else {
v.subTo(u, v);
if (ac) c.subTo(a, c);
d.subTo(b, d);
}
}
if (v.compareTo(BigInteger.ONE) != 0) return BigInteger.ZERO;
while (d.compareTo(m) >= 0) d.subTo(m, d);
while (d.signum() < 0) d.addTo(m, d);
return d;
};
// (public) this^e
BigInteger.prototype.pow = function (e) { return this.exp(e, new NullExp()); };
// (public) gcd(this,a) (HAC 14.54)
BigInteger.prototype.gcd = function (a) {
var x = (this.s < 0) ? this.negate() : this.clone();
var y = (a.s < 0) ? a.negate() : a.clone();
if (x.compareTo(y) < 0) { var t = x; x = y; y = t; }
var i = x.getLowestSetBit(), g = y.getLowestSetBit();
if (g < 0) return x;
if (i < g) g = i;
if (g > 0) {
x.rShiftTo(g, x);
y.rShiftTo(g, y);
}
while (x.signum() > 0) {
if ((i = x.getLowestSetBit()) > 0) x.rShiftTo(i, x);
if ((i = y.getLowestSetBit()) > 0) y.rShiftTo(i, y);
if (x.compareTo(y) >= 0) {
x.subTo(y, x);
x.rShiftTo(1, x);
}
else {
y.subTo(x, y);
y.rShiftTo(1, y);
}
}
if (g > 0) y.lShiftTo(g, y);
return y;
};
// (public) test primality with certainty >= 1-.5^t
BigInteger.prototype.isProbablePrime = function (t) {
var i, x = this.abs();
if (x.t == 1 && x[0] <= lowprimes[lowprimes.length - 1]) {
for (i = 0; i < lowprimes.length; ++i)
if (x[0] == lowprimes[i]) return true;
return false;
}
if (x.isEven()) return false;
i = 1;
while (i < lowprimes.length) {
var m = lowprimes[i], j = i + 1;
while (j < lowprimes.length && m < lplim) m *= lowprimes[j++];
m = x.modInt(m);
while (i < j) if (m % lowprimes[i++] == 0) return false;
}
return x.millerRabin(t);
};
// JSBN-specific extension
// (public) this^2
BigInteger.prototype.square = function () { var r = nbi(); this.squareTo(r); return r; };
// NOTE: BigInteger interfaces not implemented in jsbn:
// BigInteger(int signum, byte[] magnitude)
// double doubleValue()
// float floatValue()
// int hashCode()
// long longValue()
// static BigInteger valueOf(long val)
// Copyright Stephan Thomas (start) --- //
// https://raw.github.com/bitcoinjs/bitcoinjs-lib/07f9d55ccb6abd962efb6befdd37671f85ea4ff9/src/util.js
// BigInteger monkey patching
BigInteger.valueOf = nbv;
/**
* Returns a byte array representation of the big integer.
*
* This returns the absolute of the contained value in big endian
* form. A value of zero results in an empty array.
*/
BigInteger.prototype.toByteArrayUnsigned = function () {
var ba = this.abs().toByteArray();
if (ba.length) {
if (ba[0] == 0) {
ba = ba.slice(1);
}
return ba.map(function (v) {
return (v < 0) ? v + 256 : v;
});
} else {
// Empty array, nothing to do
return ba;
}
};
/**
* Turns a byte array into a big integer.
*
* This function will interpret a byte array as a big integer in big
* endian notation and ignore leading zeros.
*/
BigInteger.fromByteArrayUnsigned = function (ba) {
if (!ba.length) {
return ba.valueOf(0);
} else if (ba[0] & 0x80) {
// Prepend a zero so the BigInteger class doesn't mistake this
// for a negative integer.
return new BigInteger([0].concat(ba));
} else {
return new BigInteger(ba);
}
};
/**
* Converts big integer to signed byte representation.
*
* The format for this value uses a the most significant bit as a sign
* bit. If the most significant bit is already occupied by the
* absolute value, an extra byte is prepended and the sign bit is set
* there.
*
* Examples:
*
* 0 => 0x00
* 1 => 0x01
* -1 => 0x81
* 127 => 0x7f
* -127 => 0xff
* 128 => 0x0080
* -128 => 0x8080
* 255 => 0x00ff
* -255 => 0x80ff
* 16300 => 0x3fac
* -16300 => 0xbfac
* 62300 => 0x00f35c
* -62300 => 0x80f35c
*/
BigInteger.prototype.toByteArraySigned = function () {
var val = this.abs().toByteArrayUnsigned();
var neg = this.compareTo(BigInteger.ZERO) < 0;
if (neg) {
if (val[0] & 0x80) {
val.unshift(0x80);
} else {
val[0] |= 0x80;
}
} else {
if (val[0] & 0x80) {
val.unshift(0x00);
}
}
return val;
};
/**
* Parse a signed big integer byte representation.
*
* For details on the format please see BigInteger.toByteArraySigned.
*/
BigInteger.fromByteArraySigned = function (ba) {
// Check for negative value
if (ba[0] & 0x80) {
// Remove sign bit
ba[0] &= 0x7f;
return BigInteger.fromByteArrayUnsigned(ba).negate();
} else {
return BigInteger.fromByteArrayUnsigned(ba);
}
};
// Copyright Stephan Thomas (end) --- //
// ****** REDUCTION ******* //
// Modular reduction using "classic" algorithm
var Classic = window.Classic = function Classic(m) { this.m = m; }
Classic.prototype.convert = function (x) {
if (x.s < 0 || x.compareTo(this.m) >= 0) return x.mod(this.m);
else return x;
};
Classic.prototype.revert = function (x) { return x; };
Classic.prototype.reduce = function (x) { x.divRemTo(this.m, null, x); };
Classic.prototype.mulTo = function (x, y, r) { x.multiplyTo(y, r); this.reduce(r); };
Classic.prototype.sqrTo = function (x, r) { x.squareTo(r); this.reduce(r); };
// Montgomery reduction
var Montgomery = window.Montgomery = function Montgomery(m) {
this.m = m;
this.mp = m.invDigit();
this.mpl = this.mp & 0x7fff;
this.mph = this.mp >> 15;
this.um = (1 << (m.DB - 15)) - 1;
this.mt2 = 2 * m.t;
}
// xR mod m
Montgomery.prototype.convert = function (x) {
var r = nbi();
x.abs().dlShiftTo(this.m.t, r);
r.divRemTo(this.m, null, r);
if (x.s < 0 && r.compareTo(BigInteger.ZERO) > 0) this.m.subTo(r, r);
return r;
}
// x/R mod m
Montgomery.prototype.revert = function (x) {
var r = nbi();
x.copyTo(r);
this.reduce(r);
return r;
};
// x = x/R mod m (HAC 14.32)
Montgomery.prototype.reduce = function (x) {
while (x.t <= this.mt2) // pad x so am has enough room later
x[x.t++] = 0;
for (var i = 0; i < this.m.t; ++i) {
// faster way of calculating u0 = x[i]*mp mod DV
var j = x[i] & 0x7fff;
var u0 = (j * this.mpl + (((j * this.mph + (x[i] >> 15) * this.mpl) & this.um) << 15)) & x.DM;
// use am to combine the multiply-shift-add into one call
j = i + this.m.t;
x[j] += this.m.am(0, u0, x, i, 0, this.m.t);
// propagate carry
while (x[j] >= x.DV) { x[j] -= x.DV; x[++j]++; }
}
x.clamp();
x.drShiftTo(this.m.t, x);
if (x.compareTo(this.m) >= 0) x.subTo(this.m, x);
};
// r = "xy/R mod m"; x,y != r
Montgomery.prototype.mulTo = function (x, y, r) { x.multiplyTo(y, r); this.reduce(r); };
// r = "x^2/R mod m"; x != r
Montgomery.prototype.sqrTo = function (x, r) { x.squareTo(r); this.reduce(r); };
// A "null" reducer
var NullExp = window.NullExp = function NullExp() { }
NullExp.prototype.convert = function (x) { return x; };
NullExp.prototype.revert = function (x) { return x; };
NullExp.prototype.mulTo = function (x, y, r) { x.multiplyTo(y, r); };
NullExp.prototype.sqrTo = function (x, r) { x.squareTo(r); };
// Barrett modular reduction
var Barrett = window.Barrett = function Barrett(m) {
// setup Barrett
this.r2 = nbi();
this.q3 = nbi();
BigInteger.ONE.dlShiftTo(2 * m.t, this.r2);
this.mu = this.r2.divide(m);
this.m = m;
}
Barrett.prototype.convert = function (x) {
if (x.s < 0 || x.t > 2 * this.m.t) return x.mod(this.m);
else if (x.compareTo(this.m) < 0) return x;
else { var r = nbi(); x.copyTo(r); this.reduce(r); return r; }
};
Barrett.prototype.revert = function (x) { return x; };
// x = x mod m (HAC 14.42)
Barrett.prototype.reduce = function (x) {
x.drShiftTo(this.m.t - 1, this.r2);
if (x.t > this.m.t + 1) { x.t = this.m.t + 1; x.clamp(); }
this.mu.multiplyUpperTo(this.r2, this.m.t + 1, this.q3);
this.m.multiplyLowerTo(this.q3, this.m.t + 1, this.r2);
while (x.compareTo(this.r2) < 0) x.dAddOffset(1, this.m.t + 1);
x.subTo(this.r2, x);
while (x.compareTo(this.m) >= 0) x.subTo(this.m, x);
};
// r = x*y mod m; x,y != r
Barrett.prototype.mulTo = function (x, y, r) { x.multiplyTo(y, r); this.reduce(r); };
// r = x^2 mod m; x != r
Barrett.prototype.sqrTo = function (x, r) { x.squareTo(r); this.reduce(r); };
})();
/*!
* Basic Javascript Elliptic Curve implementation
* Ported loosely from BouncyCastle's Java EC code
* Only Fp curves implemented for now
*
* Copyright Tom Wu, bitaddress.org BSD License.
* http://www-cs-students.stanford.edu/~tjw/jsbn/LICENSE
*/
(function () {
// Constructor function of Global EllipticCurve object
var ec = window.EllipticCurve = function () { };
// ----------------
// ECFieldElementFp constructor
// q instanceof BigInteger
// x instanceof BigInteger
ec.FieldElementFp = function (q, x) {
this.x = x;
// TODO if(x.compareTo(q) >= 0) error
this.q = q;
};
ec.FieldElementFp.prototype.equals = function (other) {
if (other == this) return true;
return (this.q.equals(other.q) && this.x.equals(other.x));
};
ec.FieldElementFp.prototype.toBigInteger = function () {
return this.x;
};
ec.FieldElementFp.prototype.negate = function () {
return new ec.FieldElementFp(this.q, this.x.negate().mod(this.q));
};
ec.FieldElementFp.prototype.add = function (b) {
return new ec.FieldElementFp(this.q, this.x.add(b.toBigInteger()).mod(this.q));
};
ec.FieldElementFp.prototype.subtract = function (b) {
return new ec.FieldElementFp(this.q, this.x.subtract(b.toBigInteger()).mod(this.q));
};
ec.FieldElementFp.prototype.multiply = function (b) {
return new ec.FieldElementFp(this.q, this.x.multiply(b.toBigInteger()).mod(this.q));
};
ec.FieldElementFp.prototype.square = function () {
return new ec.FieldElementFp(this.q, this.x.square().mod(this.q));
};
ec.FieldElementFp.prototype.divide = function (b) {
return new ec.FieldElementFp(this.q, this.x.multiply(b.toBigInteger().modInverse(this.q)).mod(this.q));
};
ec.FieldElementFp.prototype.getByteLength = function () {
return Math.floor((this.toBigInteger().bitLength() + 7) / 8);
};
// D.1.4 91
/**
* return a sqrt root - the routine verifies that the calculation
* returns the right value - if none exists it returns null.
*
* Copyright (c) 2000 - 2011 The Legion Of The Bouncy Castle (http://www.bouncycastle.org)
* Ported to JavaScript by bitaddress.org
*/
ec.FieldElementFp.prototype.sqrt = function () {
if (!this.q.testBit(0)) throw new Error("even value of q");
// p mod 4 == 3
if (this.q.testBit(1)) {
// z = g^(u+1) + p, p = 4u + 3
var z = new ec.FieldElementFp(this.q, this.x.modPow(this.q.shiftRight(2).add(BigInteger.ONE), this.q));
return z.square().equals(this) ? z : null;
}
// p mod 4 == 1
var qMinusOne = this.q.subtract(BigInteger.ONE);
var legendreExponent = qMinusOne.shiftRight(1);
if (!(this.x.modPow(legendreExponent, this.q).equals(BigInteger.ONE))) return null;
var u = qMinusOne.shiftRight(2);
var k = u.shiftLeft(1).add(BigInteger.ONE);
var Q = this.x;
var fourQ = Q.shiftLeft(2).mod(this.q);
var U, V;
do {
var rand = new SecureRandom();
var P;
do {
P = new BigInteger(this.q.bitLength(), rand);
}
while (P.compareTo(this.q) >= 0 || !(P.multiply(P).subtract(fourQ).modPow(legendreExponent, this.q).equals(qMinusOne)));
var result = ec.FieldElementFp.fastLucasSequence(this.q, P, Q, k);
U = result[0];
V = result[1];
if (V.multiply(V).mod(this.q).equals(fourQ)) {
// Integer division by 2, mod q
if (V.testBit(0)) {
V = V.add(this.q);
}
V = V.shiftRight(1);
return new ec.FieldElementFp(this.q, V);
}
}
while (U.equals(BigInteger.ONE) || U.equals(qMinusOne));
return null;
};
/*
* Copyright (c) 2000 - 2011 The Legion Of The Bouncy Castle (http://www.bouncycastle.org)
* Ported to JavaScript by bitaddress.org
*/
ec.FieldElementFp.fastLucasSequence = function (p, P, Q, k) {
// TODO Research and apply "common-multiplicand multiplication here"
var n = k.bitLength();
var s = k.getLowestSetBit();
var Uh = BigInteger.ONE;
var Vl = BigInteger.TWO;
var Vh = P;
var Ql = BigInteger.ONE;
var Qh = BigInteger.ONE;
for (var j = n - 1; j >= s + 1; --j) {
Ql = Ql.multiply(Qh).mod(p);
if (k.testBit(j)) {
Qh = Ql.multiply(Q).mod(p);
Uh = Uh.multiply(Vh).mod(p);
Vl = Vh.multiply(Vl).subtract(P.multiply(Ql)).mod(p);
Vh = Vh.multiply(Vh).subtract(Qh.shiftLeft(1)).mod(p);
}
else {
Qh = Ql;
Uh = Uh.multiply(Vl).subtract(Ql).mod(p);
Vh = Vh.multiply(Vl).subtract(P.multiply(Ql)).mod(p);
Vl = Vl.multiply(Vl).subtract(Ql.shiftLeft(1)).mod(p);
}
}
Ql = Ql.multiply(Qh).mod(p);
Qh = Ql.multiply(Q).mod(p);
Uh = Uh.multiply(Vl).subtract(Ql).mod(p);
Vl = Vh.multiply(Vl).subtract(P.multiply(Ql)).mod(p);
Ql = Ql.multiply(Qh).mod(p);
for (var j = 1; j <= s; ++j) {
Uh = Uh.multiply(Vl).mod(p);
Vl = Vl.multiply(Vl).subtract(Ql.shiftLeft(1)).mod(p);
Ql = Ql.multiply(Ql).mod(p);
}
return [Uh, Vl];
};
// ----------------
// ECPointFp constructor
ec.PointFp = function (curve, x, y, z, compressed) {
this.curve = curve;
this.x = x;
this.y = y;
// Projective coordinates: either zinv == null or z * zinv == 1
// z and zinv are just BigIntegers, not fieldElements
if (z == null) {
this.z = BigInteger.ONE;
}
else {
this.z = z;
}
this.zinv = null;
// compression flag
this.compressed = !!compressed;
};
ec.PointFp.prototype.getX = function () {
if (this.zinv == null) {
this.zinv = this.z.modInverse(this.curve.q);
}
var r = this.x.toBigInteger().multiply(this.zinv);
this.curve.reduce(r);
return this.curve.fromBigInteger(r);
};
ec.PointFp.prototype.getY = function () {
if (this.zinv == null) {
this.zinv = this.z.modInverse(this.curve.q);
}
var r = this.y.toBigInteger().multiply(this.zinv);
this.curve.reduce(r);
return this.curve.fromBigInteger(r);
};
ec.PointFp.prototype.equals = function (other) {
if (other == this) return true;
if (this.isInfinity()) return other.isInfinity();
if (other.isInfinity()) return this.isInfinity();
var u, v;
// u = Y2 * Z1 - Y1 * Z2
u = other.y.toBigInteger().multiply(this.z).subtract(this.y.toBigInteger().multiply(other.z)).mod(this.curve.q);
if (!u.equals(BigInteger.ZERO)) return false;
// v = X2 * Z1 - X1 * Z2
v = other.x.toBigInteger().multiply(this.z).subtract(this.x.toBigInteger().multiply(other.z)).mod(this.curve.q);
return v.equals(BigInteger.ZERO);
};
ec.PointFp.prototype.isInfinity = function () {
if ((this.x == null) && (this.y == null)) return true;
return this.z.equals(BigInteger.ZERO) && !this.y.toBigInteger().equals(BigInteger.ZERO);
};
ec.PointFp.prototype.negate = function () {
return new ec.PointFp(this.curve, this.x, this.y.negate(), this.z);
};
ec.PointFp.prototype.add = function (b) {
if (this.isInfinity()) return b;
if (b.isInfinity()) return this;
// u = Y2 * Z1 - Y1 * Z2
var u = b.y.toBigInteger().multiply(this.z).subtract(this.y.toBigInteger().multiply(b.z)).mod(this.curve.q);
// v = X2 * Z1 - X1 * Z2
var v = b.x.toBigInteger().multiply(this.z).subtract(this.x.toBigInteger().multiply(b.z)).mod(this.curve.q);
if (BigInteger.ZERO.equals(v)) {
if (BigInteger.ZERO.equals(u)) {
return this.twice(); // this == b, so double
}
return this.curve.getInfinity(); // this = -b, so infinity
}
var THREE = new BigInteger("3");
var x1 = this.x.toBigInteger();
var y1 = this.y.toBigInteger();
var x2 = b.x.toBigInteger();
var y2 = b.y.toBigInteger();
var v2 = v.square();
var v3 = v2.multiply(v);
var x1v2 = x1.multiply(v2);
var zu2 = u.square().multiply(this.z);
// x3 = v * (z2 * (z1 * u^2 - 2 * x1 * v^2) - v^3)
var x3 = zu2.subtract(x1v2.shiftLeft(1)).multiply(b.z).subtract(v3).multiply(v).mod(this.curve.q);
// y3 = z2 * (3 * x1 * u * v^2 - y1 * v^3 - z1 * u^3) + u * v^3
var y3 = x1v2.multiply(THREE).multiply(u).subtract(y1.multiply(v3)).subtract(zu2.multiply(u)).multiply(b.z).add(u.multiply(v3)).mod(this.curve.q);
// z3 = v^3 * z1 * z2
var z3 = v3.multiply(this.z).multiply(b.z).mod(this.curve.q);
return new ec.PointFp(this.curve, this.curve.fromBigInteger(x3), this.curve.fromBigInteger(y3), z3);
};
ec.PointFp.prototype.twice = function () {
if (this.isInfinity()) return this;
if (this.y.toBigInteger().signum() == 0) return this.curve.getInfinity();
// TODO: optimized handling of constants
var THREE = new BigInteger("3");
var x1 = this.x.toBigInteger();
var y1 = this.y.toBigInteger();
var y1z1 = y1.multiply(this.z);
var y1sqz1 = y1z1.multiply(y1).mod(this.curve.q);
var a = this.curve.a.toBigInteger();
// w = 3 * x1^2 + a * z1^2
var w = x1.square().multiply(THREE);
if (!BigInteger.ZERO.equals(a)) {
w = w.add(this.z.square().multiply(a));
}
w = w.mod(this.curve.q);
//this.curve.reduce(w);
// x3 = 2 * y1 * z1 * (w^2 - 8 * x1 * y1^2 * z1)
var x3 = w.square().subtract(x1.shiftLeft(3).multiply(y1sqz1)).shiftLeft(1).multiply(y1z1).mod(this.curve.q);
// y3 = 4 * y1^2 * z1 * (3 * w * x1 - 2 * y1^2 * z1) - w^3
var y3 = w.multiply(THREE).multiply(x1).subtract(y1sqz1.shiftLeft(1)).shiftLeft(2).multiply(y1sqz1).subtract(w.square().multiply(w)).mod(this.curve.q);
// z3 = 8 * (y1 * z1)^3
var z3 = y1z1.square().multiply(y1z1).shiftLeft(3).mod(this.curve.q);
return new ec.PointFp(this.curve, this.curve.fromBigInteger(x3), this.curve.fromBigInteger(y3), z3);
};
// Simple NAF (Non-Adjacent Form) multiplication algorithm
// TODO: modularize the multiplication algorithm
ec.PointFp.prototype.multiply = function (k) {
if (this.isInfinity()) return this;
if (k.signum() == 0) return this.curve.getInfinity();
var e = k;
var h = e.multiply(new BigInteger("3"));
var neg = this.negate();
var R = this;
var i;
for (i = h.bitLength() - 2; i > 0; --i) {
R = R.twice();
var hBit = h.testBit(i);
var eBit = e.testBit(i);
if (hBit != eBit) {
R = R.add(hBit ? this : neg);
}
}
return R;
};
// Compute this*j + x*k (simultaneous multiplication)
ec.PointFp.prototype.multiplyTwo = function (j, x, k) {
var i;
if (j.bitLength() > k.bitLength())
i = j.bitLength() - 1;
else
i = k.bitLength() - 1;
var R = this.curve.getInfinity();
var both = this.add(x);
while (i >= 0) {
R = R.twice();
if (j.testBit(i)) {
if (k.testBit(i)) {
R = R.add(both);
}
else {
R = R.add(this);
}
}
else {
if (k.testBit(i)) {
R = R.add(x);
}
}
--i;
}
return R;
};
// patched by bitaddress.org and Casascius for use with Bitcoin.ECKey
// patched by coretechs to support compressed public keys
ec.PointFp.prototype.getEncoded = function (compressed) {
var x = this.getX().toBigInteger();
var y = this.getY().toBigInteger();
var len = 32; // integerToBytes will zero pad if integer is less than 32 bytes. 32 bytes length is required by the Bitcoin protocol.
var enc = ec.integerToBytes(x, len);
// when compressed prepend byte depending if y point is even or odd
if (compressed) {
if (y.isEven()) {
enc.unshift(0x02);
}
else {
enc.unshift(0x03);
}
}
else {
enc.unshift(0x04);
enc = enc.concat(ec.integerToBytes(y, len)); // uncompressed public key appends the bytes of the y point
}
return enc;
};
ec.PointFp.decodeFrom = function (curve, enc) {
var type = enc[0];
var dataLen = enc.length - 1;
// Extract x and y as byte arrays
var xBa = enc.slice(1, 1 + dataLen / 2);
var yBa = enc.slice(1 + dataLen / 2, 1 + dataLen);
// Prepend zero byte to prevent interpretation as negative integer
xBa.unshift(0);
yBa.unshift(0);
// Convert to BigIntegers
var x = new BigInteger(xBa);
var y = new BigInteger(yBa);
// Return point
return new ec.PointFp(curve, curve.fromBigInteger(x), curve.fromBigInteger(y));
};
ec.PointFp.prototype.add2D = function (b) {
if (this.isInfinity()) return b;
if (b.isInfinity()) return this;
if (this.x.equals(b.x)) {
if (this.y.equals(b.y)) {
// this = b, i.e. this must be doubled
return this.twice();
}
// this = -b, i.e. the result is the point at infinity
return this.curve.getInfinity();
}
var x_x = b.x.subtract(this.x);
var y_y = b.y.subtract(this.y);
var gamma = y_y.divide(x_x);
var x3 = gamma.square().subtract(this.x).subtract(b.x);
var y3 = gamma.multiply(this.x.subtract(x3)).subtract(this.y);
return new ec.PointFp(this.curve, x3, y3);
};
ec.PointFp.prototype.twice2D = function () {
if (this.isInfinity()) return this;
if (this.y.toBigInteger().signum() == 0) {
// if y1 == 0, then (x1, y1) == (x1, -y1)
// and hence this = -this and thus 2(x1, y1) == infinity
return this.curve.getInfinity();
}
var TWO = this.curve.fromBigInteger(BigInteger.valueOf(2));
var THREE = this.curve.fromBigInteger(BigInteger.valueOf(3));
var gamma = this.x.square().multiply(THREE).add(this.curve.a).divide(this.y.multiply(TWO));
var x3 = gamma.square().subtract(this.x.multiply(TWO));
var y3 = gamma.multiply(this.x.subtract(x3)).subtract(this.y);
return new ec.PointFp(this.curve, x3, y3);
};
ec.PointFp.prototype.multiply2D = function (k) {
if (this.isInfinity()) return this;
if (k.signum() == 0) return this.curve.getInfinity();
var e = k;
var h = e.multiply(new BigInteger("3"));
var neg = this.negate();
var R = this;
var i;
for (i = h.bitLength() - 2; i > 0; --i) {
R = R.twice();
var hBit = h.testBit(i);
var eBit = e.testBit(i);
if (hBit != eBit) {
R = R.add2D(hBit ? this : neg);
}
}
return R;
};
ec.PointFp.prototype.isOnCurve = function () {
var x = this.getX().toBigInteger();
var y = this.getY().toBigInteger();
var a = this.curve.getA().toBigInteger();
var b = this.curve.getB().toBigInteger();
var n = this.curve.getQ();
var lhs = y.multiply(y).mod(n);
var rhs = x.multiply(x).multiply(x).add(a.multiply(x)).add(b).mod(n);
return lhs.equals(rhs);
};
ec.PointFp.prototype.toString = function () {
return '(' + this.getX().toBigInteger().toString() + ',' + this.getY().toBigInteger().toString() + ')';
};
/**
* Validate an elliptic curve point.
*
* See SEC 1, section 3.2.2.1: Elliptic Curve Public Key Validation Primitive
*/
ec.PointFp.prototype.validate = function () {
var n = this.curve.getQ();
// Check Q != O
if (this.isInfinity()) {
throw new Error("Point is at infinity.");
}
// Check coordinate bounds
var x = this.getX().toBigInteger();
var y = this.getY().toBigInteger();
if (x.compareTo(BigInteger.ONE) < 0 || x.compareTo(n.subtract(BigInteger.ONE)) > 0) {
throw new Error('x coordinate out of bounds');
}
if (y.compareTo(BigInteger.ONE) < 0 || y.compareTo(n.subtract(BigInteger.ONE)) > 0) {
throw new Error('y coordinate out of bounds');
}
// Check y^2 = x^3 + ax + b (mod n)
if (!this.isOnCurve()) {
throw new Error("Point is not on the curve.");
}
// Check nQ = 0 (Q is a scalar multiple of G)
if (this.multiply(n).isInfinity()) {
// TODO: This check doesn't work - fix.
throw new Error("Point is not a scalar multiple of G.");
}
return true;
};
// ----------------
// ECCurveFp constructor
ec.CurveFp = function (q, a, b) {
this.q = q;
this.a = this.fromBigInteger(a);
this.b = this.fromBigInteger(b);
this.infinity = new ec.PointFp(this, null, null);
this.reducer = new Barrett(this.q);
}
ec.CurveFp.prototype.getQ = function () {
return this.q;
};
ec.CurveFp.prototype.getA = function () {
return this.a;
};
ec.CurveFp.prototype.getB = function () {
return this.b;
};
ec.CurveFp.prototype.equals = function (other) {
if (other == this) return true;
return (this.q.equals(other.q) && this.a.equals(other.a) && this.b.equals(other.b));
};
ec.CurveFp.prototype.getInfinity = function () {
return this.infinity;
};
ec.CurveFp.prototype.fromBigInteger = function (x) {
return new ec.FieldElementFp(this.q, x);
};
ec.CurveFp.prototype.reduce = function (x) {
this.reducer.reduce(x);
};
// for now, work with hex strings because they're easier in JS
// compressed support added by bitaddress.org
ec.CurveFp.prototype.decodePointHex = function (s) {
var firstByte = parseInt(s.substr(0, 2), 16);
switch (firstByte) { // first byte
case 0:
return this.infinity;
case 2: // compressed
case 3: // compressed
var yTilde = firstByte & 1;
var xHex = s.substr(2, s.length - 2);
var X1 = new BigInteger(xHex, 16);
return this.decompressPoint(yTilde, X1);
case 4: // uncompressed
case 6: // hybrid
case 7: // hybrid
var len = (s.length - 2) / 2;
var xHex = s.substr(2, len);
var yHex = s.substr(len + 2, len);
return new ec.PointFp(this,
this.fromBigInteger(new BigInteger(xHex, 16)),
this.fromBigInteger(new BigInteger(yHex, 16)));
default: // unsupported
return null;
}
};
ec.CurveFp.prototype.encodePointHex = function (p) {
if (p.isInfinity()) return "00";
var xHex = p.getX().toBigInteger().toString(16);
var yHex = p.getY().toBigInteger().toString(16);
var oLen = this.getQ().toString(16).length;
if ((oLen % 2) != 0) oLen++;
while (xHex.length < oLen) {
xHex = "0" + xHex;
}
while (yHex.length < oLen) {
yHex = "0" + yHex;
}
return "04" + xHex + yHex;
};
/*
* Copyright (c) 2000 - 2011 The Legion Of The Bouncy Castle (http://www.bouncycastle.org)
* Ported to JavaScript by bitaddress.org
*
* Number yTilde
* BigInteger X1
*/
ec.CurveFp.prototype.decompressPoint = function (yTilde, X1) {
var x = this.fromBigInteger(X1);
var alpha = x.multiply(x.square().add(this.getA())).add(this.getB());
var beta = alpha.sqrt();
// if we can't find a sqrt we haven't got a point on the curve - run!
if (beta == null) throw new Error("Invalid point compression");
var betaValue = beta.toBigInteger();
var bit0 = betaValue.testBit(0) ? 1 : 0;
if (bit0 != yTilde) {
// Use the other root
beta = this.fromBigInteger(this.getQ().subtract(betaValue));
}
return new ec.PointFp(this, x, beta, null, true);
};
ec.fromHex = function (s) { return new BigInteger(s, 16); };
ec.integerToBytes = function (i, len) {
var bytes = i.toByteArrayUnsigned();
if (len < bytes.length) {
bytes = bytes.slice(bytes.length - len);
} else while (len > bytes.length) {
bytes.unshift(0);
}
return bytes;
};
// Named EC curves
// ----------------
// X9ECParameters constructor
ec.X9Parameters = function (curve, g, n, h) {
this.curve = curve;
this.g = g;
this.n = n;
this.h = h;
}
ec.X9Parameters.prototype.getCurve = function () { return this.curve; };
ec.X9Parameters.prototype.getG = function () { return this.g; };
ec.X9Parameters.prototype.getN = function () { return this.n; };
ec.X9Parameters.prototype.getH = function () { return this.h; };
// secp256k1 is the Curve used by Bitcoin
ec.secNamedCurves = {
// used by Bitcoin
"secp256k1": function () {
// p = 2^256 - 2^32 - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1
var p = ec.fromHex("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F");
var a = BigInteger.ZERO;
var b = ec.fromHex("7");
var n = ec.fromHex("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141");
var h = BigInteger.ONE;
var curve = new ec.CurveFp(p, a, b);
var G = curve.decodePointHex("04"
+ "79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798"
+ "483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8");
return new ec.X9Parameters(curve, G, n, h);
}
};
// secp256k1 called by Bitcoin's ECKEY
ec.getSECCurveByName = function (name) {
if (ec.secNamedCurves[name] == undefined) return null;
return ec.secNamedCurves[name]();
}
})();