| 1 | /* |
| 2 | * Basic JavaScript BN library - subset useful for RSA encryption. |
| 3 | * |
| 4 | * Copyright (c) 2003-2005 Tom Wu |
| 5 | * All Rights Reserved. |
| 6 | * |
| 7 | * Permission is hereby granted, free of charge, to any person obtaining |
| 8 | * a copy of this software and associated documentation files (the |
| 9 | * "Software"), to deal in the Software without restriction, including |
| 10 | * without limitation the rights to use, copy, modify, merge, publish, |
| 11 | * distribute, sublicense, and/or sell copies of the Software, and to |
| 12 | * permit persons to whom the Software is furnished to do so, subject to |
| 13 | * the following conditions: |
| 14 | * |
| 15 | * The above copyright notice and this permission notice shall be |
| 16 | * included in all copies or substantial portions of the Software. |
| 17 | * |
| 18 | * THE SOFTWARE IS PROVIDED "AS-IS" AND WITHOUT WARRANTY OF ANY KIND, |
| 19 | * EXPRESS, IMPLIED OR OTHERWISE, INCLUDING WITHOUT LIMITATION, ANY |
| 20 | * WARRANTY OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. |
| 21 | * |
| 22 | * IN NO EVENT SHALL TOM WU BE LIABLE FOR ANY SPECIAL, INCIDENTAL, |
| 23 | * INDIRECT OR CONSEQUENTIAL DAMAGES OF ANY KIND, OR ANY DAMAGES WHATSOEVER |
| 24 | * RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER OR NOT ADVISED OF |
| 25 | * THE POSSIBILITY OF DAMAGE, AND ON ANY THEORY OF LIABILITY, ARISING OUT |
| 26 | * OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. |
| 27 | * |
| 28 | * In addition, the following condition applies: |
| 29 | * |
| 30 | * All redistributions must retain an intact copy of this copyright notice |
| 31 | * and disclaimer. |
| 32 | */ |
| 33 | |
| 34 | /* |
| 35 | * Added Node.js Buffers support |
| 36 | * 2014 rzcoder |
| 37 | */ |
| 38 | |
| 39 | var crypt = require('crypto'); |
| 40 | |
| 41 | //var isNumber = require('lodash.isnumber'); // Remove this dependency to limit supply chain risks |
| 42 | function isObjectLike(value) { return !!value && typeof value == 'object'; } |
| 43 | const isNumber = function isNumber(value) { return typeof value == 'number' || (isObjectLike(value) && Object.prototype.toString.call(value) == '[object Number]'); } |
| 44 | |
| 45 | // Bits per digit |
| 46 | var dbits; |
| 47 | |
| 48 | // JavaScript engine analysis |
| 49 | var canary = 0xdeadbeefcafe; |
| 50 | var j_lm = ((canary & 0xffffff) == 0xefcafe); |
| 51 | |
| 52 | // (public) Constructor |
| 53 | function BigInteger(a, b) { |
| 54 | if (a != null) { |
| 55 | if ("number" == typeof a) { |
| 56 | this.fromNumber(a, b); |
| 57 | } else if (Buffer.isBuffer(a)) { |
| 58 | this.fromBuffer(a); |
| 59 | } else if (b == null && "string" != typeof a) { |
| 60 | this.fromByteArray(a); |
| 61 | } else { |
| 62 | this.fromString(a, b); |
| 63 | } |
| 64 | } |
| 65 | } |
| 66 | |
| 67 | // return new, unset BigInteger |
| 68 | function nbi() { |
| 69 | return new BigInteger(null); |
| 70 | } |
| 71 | |
| 72 | // am: Compute w_j += (x*this_i), propagate carries, |
| 73 | // c is initial carry, returns final carry. |
| 74 | // c < 3*dvalue, x < 2*dvalue, this_i < dvalue |
| 75 | // We need to select the fastest one that works in this environment. |
| 76 | |
| 77 | // am1: use a single mult and divide to get the high bits, |
| 78 | // max digit bits should be 26 because |
| 79 | // max internal value = 2*dvalue^2-2*dvalue (< 2^53) |
| 80 | function am1(i, x, w, j, c, n) { |
| 81 | while (--n >= 0) { |
| 82 | var v = x * this[i++] + w[j] + c; |
| 83 | c = Math.floor(v / 0x4000000); |
| 84 | w[j++] = v & 0x3ffffff; |
| 85 | } |
| 86 | return c; |
| 87 | } |
| 88 | // am2 avoids a big mult-and-extract completely. |
| 89 | // Max digit bits should be <= 30 because we do bitwise ops |
| 90 | // on values up to 2*hdvalue^2-hdvalue-1 (< 2^31) |
| 91 | function am2(i, x, w, j, c, n) { |
| 92 | var xl = x & 0x7fff, xh = x >> 15; |
| 93 | while (--n >= 0) { |
| 94 | var l = this[i] & 0x7fff; |
| 95 | var h = this[i++] >> 15; |
| 96 | var m = xh * l + h * xl; |
| 97 | l = xl * l + ((m & 0x7fff) << 15) + w[j] + (c & 0x3fffffff); |
| 98 | c = (l >>> 30) + (m >>> 15) + xh * h + (c >>> 30); |
| 99 | w[j++] = l & 0x3fffffff; |
| 100 | } |
| 101 | return c; |
| 102 | } |
| 103 | // Alternately, set max digit bits to 28 since some |
| 104 | // browsers slow down when dealing with 32-bit numbers. |
| 105 | function am3(i, x, w, j, c, n) { |
| 106 | var xl = x & 0x3fff, xh = x >> 14; |
| 107 | while (--n >= 0) { |
| 108 | var l = this[i] & 0x3fff; |
| 109 | var h = this[i++] >> 14; |
| 110 | var m = xh * l + h * xl; |
| 111 | l = xl * l + ((m & 0x3fff) << 14) + w[j] + c; |
| 112 | c = (l >> 28) + (m >> 14) + xh * h; |
| 113 | w[j++] = l & 0xfffffff; |
| 114 | } |
| 115 | return c; |
| 116 | } |
| 117 | |
| 118 | // We need to select the fastest one that works in this environment. |
| 119 | //if (j_lm && (navigator.appName == "Microsoft Internet Explorer")) { |
| 120 | // BigInteger.prototype.am = am2; |
| 121 | // dbits = 30; |
| 122 | //} else if (j_lm && (navigator.appName != "Netscape")) { |
| 123 | // BigInteger.prototype.am = am1; |
| 124 | // dbits = 26; |
| 125 | //} else { // Mozilla/Netscape seems to prefer am3 |
| 126 | // BigInteger.prototype.am = am3; |
| 127 | // dbits = 28; |
| 128 | //} |
| 129 | |
| 130 | // For node.js, we pick am3 with max dbits to 28. |
| 131 | BigInteger.prototype.am = am3; |
| 132 | dbits = 28; |
| 133 | |
| 134 | BigInteger.prototype.DB = dbits; |
| 135 | BigInteger.prototype.DM = ((1 << dbits) - 1); |
| 136 | BigInteger.prototype.DV = (1 << dbits); |
| 137 | |
| 138 | var BI_FP = 52; |
| 139 | BigInteger.prototype.FV = Math.pow(2, BI_FP); |
| 140 | BigInteger.prototype.F1 = BI_FP - dbits; |
| 141 | BigInteger.prototype.F2 = 2 * dbits - BI_FP; |
| 142 | |
| 143 | // Digit conversions |
| 144 | var BI_RM = "0123456789abcdefghijklmnopqrstuvwxyz"; |
| 145 | var BI_RC = new Array(); |
| 146 | var rr, vv; |
| 147 | rr = "0".charCodeAt(0); |
| 148 | for (vv = 0; vv <= 9; ++vv) BI_RC[rr++] = vv; |
| 149 | rr = "a".charCodeAt(0); |
| 150 | for (vv = 10; vv < 36; ++vv) BI_RC[rr++] = vv; |
| 151 | rr = "A".charCodeAt(0); |
| 152 | for (vv = 10; vv < 36; ++vv) BI_RC[rr++] = vv; |
| 153 | |
| 154 | function int2char(n) { |
| 155 | return BI_RM.charAt(n); |
| 156 | } |
| 157 | function intAt(s, i) { |
| 158 | var c = BI_RC[s.charCodeAt(i)]; |
| 159 | return (c == null) ? -1 : c; |
| 160 | } |
| 161 | |
| 162 | // (protected) copy this to r |
| 163 | function bnpCopyTo(r) { |
| 164 | for (var i = this.t - 1; i >= 0; --i) r[i] = this[i]; |
| 165 | r.t = this.t; |
| 166 | r.s = this.s; |
| 167 | } |
| 168 | |
| 169 | // (protected) set from integer value x, -DV <= x < DV |
| 170 | function bnpFromInt(x) { |
| 171 | this.t = 1; |
| 172 | this.s = (x < 0) ? -1 : 0; |
| 173 | if (x > 0) this[0] = x; |
| 174 | else if (x < -1) this[0] = x + DV; |
| 175 | else this.t = 0; |
| 176 | } |
| 177 | |
| 178 | // return bigint initialized to value |
| 179 | function nbv(i) { |
| 180 | var r = nbi(); |
| 181 | r.fromInt(i); |
| 182 | return r; |
| 183 | } |
| 184 | |
| 185 | // (protected) set from string and radix |
| 186 | function bnpFromString(data, radix, unsigned) { |
| 187 | var k; |
| 188 | switch (radix) { |
| 189 | case 2: |
| 190 | k = 1; |
| 191 | break; |
| 192 | case 4: |
| 193 | k = 2; |
| 194 | break; |
| 195 | case 8: |
| 196 | k = 3; |
| 197 | break; |
| 198 | case 16: |
| 199 | k = 4; |
| 200 | break; |
| 201 | case 32: |
| 202 | k = 5; |
| 203 | break; |
| 204 | case 256: |
| 205 | k = 8; |
| 206 | break; |
| 207 | default: |
| 208 | this.fromRadix(data, radix); |
| 209 | return; |
| 210 | } |
| 211 | |
| 212 | this.t = 0; |
| 213 | this.s = 0; |
| 214 | |
| 215 | var i = data.length; |
| 216 | var mi = false; |
| 217 | var sh = 0; |
| 218 | |
| 219 | while (--i >= 0) { |
| 220 | var x = (k == 8) ? data[i] & 0xff : intAt(data, i); |
| 221 | if (x < 0) { |
| 222 | if (data.charAt(i) == "-") mi = true; |
| 223 | continue; |
| 224 | } |
| 225 | mi = false; |
| 226 | if (sh === 0) |
| 227 | this[this.t++] = x; |
| 228 | else if (sh + k > this.DB) { |
| 229 | this[this.t - 1] |= (x & ((1 << (this.DB - sh)) - 1)) << sh; |
| 230 | this[this.t++] = (x >> (this.DB - sh)); |
| 231 | } |
| 232 | else |
| 233 | this[this.t - 1] |= x << sh; |
| 234 | sh += k; |
| 235 | if (sh >= this.DB) sh -= this.DB; |
| 236 | } |
| 237 | if ((!unsigned) && k == 8 && (data[0] & 0x80) != 0) { |
| 238 | this.s = -1; |
| 239 | if (sh > 0) this[this.t - 1] |= ((1 << (this.DB - sh)) - 1) << sh; |
| 240 | } |
| 241 | this.clamp(); |
| 242 | if (mi) BigInteger.ZERO.subTo(this, this); |
| 243 | } |
| 244 | |
| 245 | function bnpFromByteArray(a, unsigned) { |
| 246 | this.fromString(a, 256, unsigned) |
| 247 | } |
| 248 | |
| 249 | function bnpFromBuffer(a) { |
| 250 | this.fromString(a, 256, true) |
| 251 | } |
| 252 | |
| 253 | // (protected) clamp off excess high words |
| 254 | function bnpClamp() { |
| 255 | var c = this.s & this.DM; |
| 256 | while (this.t > 0 && this[this.t - 1] == c) --this.t; |
| 257 | } |
| 258 | |
| 259 | // (public) return string representation in given radix |
| 260 | function bnToString(b) { |
| 261 | if (this.s < 0) return "-" + this.negate().toString(b); |
| 262 | var k; |
| 263 | if (b == 16) k = 4; |
| 264 | else if (b == 8) k = 3; |
| 265 | else if (b == 2) k = 1; |
| 266 | else if (b == 32) k = 5; |
| 267 | else if (b == 4) k = 2; |
| 268 | else return this.toRadix(b); |
| 269 | var km = (1 << k) - 1, d, m = false, r = "", i = this.t; |
| 270 | var p = this.DB - (i * this.DB) % k; |
| 271 | if (i-- > 0) { |
| 272 | if (p < this.DB && (d = this[i] >> p) > 0) { |
| 273 | m = true; |
| 274 | r = int2char(d); |
| 275 | } |
| 276 | while (i >= 0) { |
| 277 | if (p < k) { |
| 278 | d = (this[i] & ((1 << p) - 1)) << (k - p); |
| 279 | d |= this[--i] >> (p += this.DB - k); |
| 280 | } |
| 281 | else { |
| 282 | d = (this[i] >> (p -= k)) & km; |
| 283 | if (p <= 0) { |
| 284 | p += this.DB; |
| 285 | --i; |
| 286 | } |
| 287 | } |
| 288 | if (d > 0) m = true; |
| 289 | if (m) r += int2char(d); |
| 290 | } |
| 291 | } |
| 292 | return m ? r : "0"; |
| 293 | } |
| 294 | |
| 295 | // (public) -this |
| 296 | function bnNegate() { |
| 297 | var r = nbi(); |
| 298 | BigInteger.ZERO.subTo(this, r); |
| 299 | return r; |
| 300 | } |
| 301 | |
| 302 | // (public) |this| |
| 303 | function bnAbs() { |
| 304 | return (this.s < 0) ? this.negate() : this; |
| 305 | } |
| 306 | |
| 307 | // (public) return + if this > a, - if this < a, 0 if equal |
| 308 | function bnCompareTo(a) { |
| 309 | var r = this.s - a.s; |
| 310 | if (r != 0) return r; |
| 311 | var i = this.t; |
| 312 | r = i - a.t; |
| 313 | if (r != 0) return (this.s < 0) ? -r : r; |
| 314 | while (--i >= 0) if ((r = this[i] - a[i]) != 0) return r; |
| 315 | return 0; |
| 316 | } |
| 317 | |
| 318 | // returns bit length of the integer x |
| 319 | function nbits(x) { |
| 320 | var r = 1, t; |
| 321 | if ((t = x >>> 16) != 0) { |
| 322 | x = t; |
| 323 | r += 16; |
| 324 | } |
| 325 | if ((t = x >> 8) != 0) { |
| 326 | x = t; |
| 327 | r += 8; |
| 328 | } |
| 329 | if ((t = x >> 4) != 0) { |
| 330 | x = t; |
| 331 | r += 4; |
| 332 | } |
| 333 | if ((t = x >> 2) != 0) { |
| 334 | x = t; |
| 335 | r += 2; |
| 336 | } |
| 337 | if ((t = x >> 1) != 0) { |
| 338 | x = t; |
| 339 | r += 1; |
| 340 | } |
| 341 | return r; |
| 342 | } |
| 343 | |
| 344 | // (public) return the number of bits in "this" |
| 345 | function bnBitLength() { |
| 346 | if (this.t <= 0) return 0; |
| 347 | return this.DB * (this.t - 1) + nbits(this[this.t - 1] ^ (this.s & this.DM)); |
| 348 | } |
| 349 | |
| 350 | // (protected) r = this << n*DB |
| 351 | function bnpDLShiftTo(n, r) { |
| 352 | var i; |
| 353 | for (i = this.t - 1; i >= 0; --i) r[i + n] = this[i]; |
| 354 | for (i = n - 1; i >= 0; --i) r[i] = 0; |
| 355 | r.t = this.t + n; |
| 356 | r.s = this.s; |
| 357 | } |
| 358 | |
| 359 | // (protected) r = this >> n*DB |
| 360 | function bnpDRShiftTo(n, r) { |
| 361 | for (var i = n; i < this.t; ++i) r[i - n] = this[i]; |
| 362 | r.t = Math.max(this.t - n, 0); |
| 363 | r.s = this.s; |
| 364 | } |
| 365 | |
| 366 | // (protected) r = this << n |
| 367 | function bnpLShiftTo(n, r) { |
| 368 | var bs = n % this.DB; |
| 369 | var cbs = this.DB - bs; |
| 370 | var bm = (1 << cbs) - 1; |
| 371 | var ds = Math.floor(n / this.DB), c = (this.s << bs) & this.DM, i; |
| 372 | for (i = this.t - 1; i >= 0; --i) { |
| 373 | r[i + ds + 1] = (this[i] >> cbs) | c; |
| 374 | c = (this[i] & bm) << bs; |
| 375 | } |
| 376 | for (i = ds - 1; i >= 0; --i) r[i] = 0; |
| 377 | r[ds] = c; |
| 378 | r.t = this.t + ds + 1; |
| 379 | r.s = this.s; |
| 380 | r.clamp(); |
| 381 | } |
| 382 | |
| 383 | // (protected) r = this >> n |
| 384 | function bnpRShiftTo(n, r) { |
| 385 | r.s = this.s; |
| 386 | var ds = Math.floor(n / this.DB); |
| 387 | if (ds >= this.t) { |
| 388 | r.t = 0; |
| 389 | return; |
| 390 | } |
| 391 | var bs = n % this.DB; |
| 392 | var cbs = this.DB - bs; |
| 393 | var bm = (1 << bs) - 1; |
| 394 | r[0] = this[ds] >> bs; |
| 395 | for (var i = ds + 1; i < this.t; ++i) { |
| 396 | r[i - ds - 1] |= (this[i] & bm) << cbs; |
| 397 | r[i - ds] = this[i] >> bs; |
| 398 | } |
| 399 | if (bs > 0) r[this.t - ds - 1] |= (this.s & bm) << cbs; |
| 400 | r.t = this.t - ds; |
| 401 | r.clamp(); |
| 402 | } |
| 403 | |
| 404 | // (protected) r = this - a |
| 405 | function bnpSubTo(a, r) { |
| 406 | var i = 0, c = 0, m = Math.min(a.t, this.t); |
| 407 | while (i < m) { |
| 408 | c += this[i] - a[i]; |
| 409 | r[i++] = c & this.DM; |
| 410 | c >>= this.DB; |
| 411 | } |
| 412 | if (a.t < this.t) { |
| 413 | c -= a.s; |
| 414 | while (i < this.t) { |
| 415 | c += this[i]; |
| 416 | r[i++] = c & this.DM; |
| 417 | c >>= this.DB; |
| 418 | } |
| 419 | c += this.s; |
| 420 | } |
| 421 | else { |
| 422 | c += this.s; |
| 423 | while (i < a.t) { |
| 424 | c -= a[i]; |
| 425 | r[i++] = c & this.DM; |
| 426 | c >>= this.DB; |
| 427 | } |
| 428 | c -= a.s; |
| 429 | } |
| 430 | r.s = (c < 0) ? -1 : 0; |
| 431 | if (c < -1) r[i++] = this.DV + c; |
| 432 | else if (c > 0) r[i++] = c; |
| 433 | r.t = i; |
| 434 | r.clamp(); |
| 435 | } |
| 436 | |
| 437 | // (protected) r = this * a, r != this,a (HAC 14.12) |
| 438 | // "this" should be the larger one if appropriate. |
| 439 | function bnpMultiplyTo(a, r) { |
| 440 | var x = this.abs(), y = a.abs(); |
| 441 | var i = x.t; |
| 442 | r.t = i + y.t; |
| 443 | while (--i >= 0) r[i] = 0; |
| 444 | for (i = 0; i < y.t; ++i) r[i + x.t] = x.am(0, y[i], r, i, 0, x.t); |
| 445 | r.s = 0; |
| 446 | r.clamp(); |
| 447 | if (this.s != a.s) BigInteger.ZERO.subTo(r, r); |
| 448 | } |
| 449 | |
| 450 | // (protected) r = this^2, r != this (HAC 14.16) |
| 451 | function bnpSquareTo(r) { |
| 452 | var x = this.abs(); |
| 453 | var i = r.t = 2 * x.t; |
| 454 | while (--i >= 0) r[i] = 0; |
| 455 | for (i = 0; i < x.t - 1; ++i) { |
| 456 | var c = x.am(i, x[i], r, 2 * i, 0, 1); |
| 457 | if ((r[i + x.t] += x.am(i + 1, 2 * x[i], r, 2 * i + 1, c, x.t - i - 1)) >= x.DV) { |
| 458 | r[i + x.t] -= x.DV; |
| 459 | r[i + x.t + 1] = 1; |
| 460 | } |
| 461 | } |
| 462 | if (r.t > 0) r[r.t - 1] += x.am(i, x[i], r, 2 * i, 0, 1); |
| 463 | r.s = 0; |
| 464 | r.clamp(); |
| 465 | } |
| 466 | |
| 467 | // (protected) divide this by m, quotient and remainder to q, r (HAC 14.20) |
| 468 | // r != q, this != m. q or r may be null. |
| 469 | function bnpDivRemTo(m, q, r) { |
| 470 | var pm = m.abs(); |
| 471 | if (pm.t <= 0) return; |
| 472 | var pt = this.abs(); |
| 473 | if (pt.t < pm.t) { |
| 474 | if (q != null) q.fromInt(0); |
| 475 | if (r != null) this.copyTo(r); |
| 476 | return; |
| 477 | } |
| 478 | if (r == null) r = nbi(); |
| 479 | var y = nbi(), ts = this.s, ms = m.s; |
| 480 | var nsh = this.DB - nbits(pm[pm.t - 1]); // normalize modulus |
| 481 | if (nsh > 0) { |
| 482 | pm.lShiftTo(nsh, y); |
| 483 | pt.lShiftTo(nsh, r); |
| 484 | } |
| 485 | else { |
| 486 | pm.copyTo(y); |
| 487 | pt.copyTo(r); |
| 488 | } |
| 489 | var ys = y.t; |
| 490 | var y0 = y[ys - 1]; |
| 491 | if (y0 === 0) return; |
| 492 | var yt = y0 * (1 << this.F1) + ((ys > 1) ? y[ys - 2] >> this.F2 : 0); |
| 493 | var d1 = this.FV / yt, d2 = (1 << this.F1) / yt, e = 1 << this.F2; |
| 494 | var i = r.t, j = i - ys, t = (q == null) ? nbi() : q; |
| 495 | y.dlShiftTo(j, t); |
| 496 | if (r.compareTo(t) >= 0) { |
| 497 | r[r.t++] = 1; |
| 498 | r.subTo(t, r); |
| 499 | } |
| 500 | BigInteger.ONE.dlShiftTo(ys, t); |
| 501 | t.subTo(y, y); // "negative" y so we can replace sub with am later |
| 502 | while (y.t < ys) y[y.t++] = 0; |
| 503 | while (--j >= 0) { |
| 504 | // Estimate quotient digit |
| 505 | var qd = (r[--i] == y0) ? this.DM : Math.floor(r[i] * d1 + (r[i - 1] + e) * d2); |
| 506 | if ((r[i] += y.am(0, qd, r, j, 0, ys)) < qd) { // Try it out |
| 507 | y.dlShiftTo(j, t); |
| 508 | r.subTo(t, r); |
| 509 | while (r[i] < --qd) r.subTo(t, r); |
| 510 | } |
| 511 | } |
| 512 | if (q != null) { |
| 513 | r.drShiftTo(ys, q); |
| 514 | if (ts != ms) BigInteger.ZERO.subTo(q, q); |
| 515 | } |
| 516 | r.t = ys; |
| 517 | r.clamp(); |
| 518 | if (nsh > 0) r.rShiftTo(nsh, r); // Denormalize remainder |
| 519 | if (ts < 0) BigInteger.ZERO.subTo(r, r); |
| 520 | } |
| 521 | |
| 522 | // (public) this mod a |
| 523 | function bnMod(a) { |
| 524 | var r = nbi(); |
| 525 | this.abs().divRemTo(a, null, r); |
| 526 | if (this.s < 0 && r.compareTo(BigInteger.ZERO) > 0) a.subTo(r, r); |
| 527 | return r; |
| 528 | } |
| 529 | |
| 530 | // Modular reduction using "classic" algorithm |
| 531 | function Classic(m) { |
| 532 | this.m = m; |
| 533 | } |
| 534 | function cConvert(x) { |
| 535 | if (x.s < 0 || x.compareTo(this.m) >= 0) return x.mod(this.m); |
| 536 | else return x; |
| 537 | } |
| 538 | function cRevert(x) { |
| 539 | return x; |
| 540 | } |
| 541 | function cReduce(x) { |
| 542 | x.divRemTo(this.m, null, x); |
| 543 | } |
| 544 | function cMulTo(x, y, r) { |
| 545 | x.multiplyTo(y, r); |
| 546 | this.reduce(r); |
| 547 | } |
| 548 | function cSqrTo(x, r) { |
| 549 | x.squareTo(r); |
| 550 | this.reduce(r); |
| 551 | } |
| 552 | |
| 553 | Classic.prototype.convert = cConvert; |
| 554 | Classic.prototype.revert = cRevert; |
| 555 | Classic.prototype.reduce = cReduce; |
| 556 | Classic.prototype.mulTo = cMulTo; |
| 557 | Classic.prototype.sqrTo = cSqrTo; |
| 558 | |
| 559 | // (protected) return "-1/this % 2^DB"; useful for Mont. reduction |
| 560 | // justification: |
| 561 | // xy == 1 (mod m) |
| 562 | // xy = 1+km |
| 563 | // xy(2-xy) = (1+km)(1-km) |
| 564 | // x[y(2-xy)] = 1-k^2m^2 |
| 565 | // x[y(2-xy)] == 1 (mod m^2) |
| 566 | // if y is 1/x mod m, then y(2-xy) is 1/x mod m^2 |
| 567 | // should reduce x and y(2-xy) by m^2 at each step to keep size bounded. |
| 568 | // JS multiply "overflows" differently from C/C++, so care is needed here. |
| 569 | function bnpInvDigit() { |
| 570 | if (this.t < 1) return 0; |
| 571 | var x = this[0]; |
| 572 | if ((x & 1) === 0) return 0; |
| 573 | var y = x & 3; // y == 1/x mod 2^2 |
| 574 | y = (y * (2 - (x & 0xf) * y)) & 0xf; // y == 1/x mod 2^4 |
| 575 | y = (y * (2 - (x & 0xff) * y)) & 0xff; // y == 1/x mod 2^8 |
| 576 | y = (y * (2 - (((x & 0xffff) * y) & 0xffff))) & 0xffff; // y == 1/x mod 2^16 |
| 577 | // last step - calculate inverse mod DV directly; |
| 578 | // assumes 16 < DB <= 32 and assumes ability to handle 48-bit ints |
| 579 | y = (y * (2 - x * y % this.DV)) % this.DV; // y == 1/x mod 2^dbits |
| 580 | // we really want the negative inverse, and -DV < y < DV |
| 581 | return (y > 0) ? this.DV - y : -y; |
| 582 | } |
| 583 | |
| 584 | // Montgomery reduction |
| 585 | function Montgomery(m) { |
| 586 | this.m = m; |
| 587 | this.mp = m.invDigit(); |
| 588 | this.mpl = this.mp & 0x7fff; |
| 589 | this.mph = this.mp >> 15; |
| 590 | this.um = (1 << (m.DB - 15)) - 1; |
| 591 | this.mt2 = 2 * m.t; |
| 592 | } |
| 593 | |
| 594 | // xR mod m |
| 595 | function montConvert(x) { |
| 596 | var r = nbi(); |
| 597 | x.abs().dlShiftTo(this.m.t, r); |
| 598 | r.divRemTo(this.m, null, r); |
| 599 | if (x.s < 0 && r.compareTo(BigInteger.ZERO) > 0) this.m.subTo(r, r); |
| 600 | return r; |
| 601 | } |
| 602 | |
| 603 | // x/R mod m |
| 604 | function montRevert(x) { |
| 605 | var r = nbi(); |
| 606 | x.copyTo(r); |
| 607 | this.reduce(r); |
| 608 | return r; |
| 609 | } |
| 610 | |
| 611 | // x = x/R mod m (HAC 14.32) |
| 612 | function montReduce(x) { |
| 613 | while (x.t <= this.mt2) // pad x so am has enough room later |
| 614 | x[x.t++] = 0; |
| 615 | for (var i = 0; i < this.m.t; ++i) { |
| 616 | // faster way of calculating u0 = x[i]*mp mod DV |
| 617 | var j = x[i] & 0x7fff; |
| 618 | var u0 = (j * this.mpl + (((j * this.mph + (x[i] >> 15) * this.mpl) & this.um) << 15)) & x.DM; |
| 619 | // use am to combine the multiply-shift-add into one call |
| 620 | j = i + this.m.t; |
| 621 | x[j] += this.m.am(0, u0, x, i, 0, this.m.t); |
| 622 | // propagate carry |
| 623 | while (x[j] >= x.DV) { |
| 624 | x[j] -= x.DV; |
| 625 | x[++j]++; |
| 626 | } |
| 627 | } |
| 628 | x.clamp(); |
| 629 | x.drShiftTo(this.m.t, x); |
| 630 | if (x.compareTo(this.m) >= 0) x.subTo(this.m, x); |
| 631 | } |
| 632 | |
| 633 | // r = "x^2/R mod m"; x != r |
| 634 | function montSqrTo(x, r) { |
| 635 | x.squareTo(r); |
| 636 | this.reduce(r); |
| 637 | } |
| 638 | |
| 639 | // r = "xy/R mod m"; x,y != r |
| 640 | function montMulTo(x, y, r) { |
| 641 | x.multiplyTo(y, r); |
| 642 | this.reduce(r); |
| 643 | } |
| 644 | |
| 645 | Montgomery.prototype.convert = montConvert; |
| 646 | Montgomery.prototype.revert = montRevert; |
| 647 | Montgomery.prototype.reduce = montReduce; |
| 648 | Montgomery.prototype.mulTo = montMulTo; |
| 649 | Montgomery.prototype.sqrTo = montSqrTo; |
| 650 | |
| 651 | // (protected) true iff this is even |
| 652 | function bnpIsEven() { |
| 653 | return ((this.t > 0) ? (this[0] & 1) : this.s) === 0; |
| 654 | } |
| 655 | |
| 656 | // (protected) this^e, e < 2^32, doing sqr and mul with "r" (HAC 14.79) |
| 657 | function bnpExp(e, z) { |
| 658 | if (e > 0xffffffff || e < 1) return BigInteger.ONE; |
| 659 | var r = nbi(), r2 = nbi(), g = z.convert(this), i = nbits(e) - 1; |
| 660 | g.copyTo(r); |
| 661 | while (--i >= 0) { |
| 662 | z.sqrTo(r, r2); |
| 663 | if ((e & (1 << i)) > 0) z.mulTo(r2, g, r); |
| 664 | else { |
| 665 | var t = r; |
| 666 | r = r2; |
| 667 | r2 = t; |
| 668 | } |
| 669 | } |
| 670 | return z.revert(r); |
| 671 | } |
| 672 | |
| 673 | // (public) this^e % m, 0 <= e < 2^32 |
| 674 | function bnModPowInt(e, m) { |
| 675 | var z; |
| 676 | if (e < 256 || m.isEven()) z = new Classic(m); else z = new Montgomery(m); |
| 677 | return this.exp(e, z); |
| 678 | } |
| 679 | |
| 680 | // Copyright (c) 2005-2009 Tom Wu |
| 681 | // All Rights Reserved. |
| 682 | // See "LICENSE" for details. |
| 683 | |
| 684 | // Extended JavaScript BN functions, required for RSA private ops. |
| 685 | |
| 686 | // Version 1.1: new BigInteger("0", 10) returns "proper" zero |
| 687 | // Version 1.2: square() API, isProbablePrime fix |
| 688 | |
| 689 | //(public) |
| 690 | function bnClone() { |
| 691 | var r = nbi(); |
| 692 | this.copyTo(r); |
| 693 | return r; |
| 694 | } |
| 695 | |
| 696 | //(public) return value as integer |
| 697 | function bnIntValue() { |
| 698 | if (this.s < 0) { |
| 699 | if (this.t == 1) return this[0] - this.DV; |
| 700 | else if (this.t === 0) return -1; |
| 701 | } |
| 702 | else if (this.t == 1) return this[0]; |
| 703 | else if (this.t === 0) return 0; |
| 704 | // assumes 16 < DB < 32 |
| 705 | return ((this[1] & ((1 << (32 - this.DB)) - 1)) << this.DB) | this[0]; |
| 706 | } |
| 707 | |
| 708 | //(public) return value as byte |
| 709 | function bnByteValue() { |
| 710 | return (this.t == 0) ? this.s : (this[0] << 24) >> 24; |
| 711 | } |
| 712 | |
| 713 | //(public) return value as short (assumes DB>=16) |
| 714 | function bnShortValue() { |
| 715 | return (this.t == 0) ? this.s : (this[0] << 16) >> 16; |
| 716 | } |
| 717 | |
| 718 | //(protected) return x s.t. r^x < DV |
| 719 | function bnpChunkSize(r) { |
| 720 | return Math.floor(Math.LN2 * this.DB / Math.log(r)); |
| 721 | } |
| 722 | |
| 723 | //(public) 0 if this === 0, 1 if this > 0 |
| 724 | function bnSigNum() { |
| 725 | if (this.s < 0) return -1; |
| 726 | else if (this.t <= 0 || (this.t == 1 && this[0] <= 0)) return 0; |
| 727 | else return 1; |
| 728 | } |
| 729 | |
| 730 | //(protected) convert to radix string |
| 731 | function bnpToRadix(b) { |
| 732 | if (b == null) b = 10; |
| 733 | if (this.signum() === 0 || b < 2 || b > 36) return "0"; |
| 734 | var cs = this.chunkSize(b); |
| 735 | var a = Math.pow(b, cs); |
| 736 | var d = nbv(a), y = nbi(), z = nbi(), r = ""; |
| 737 | this.divRemTo(d, y, z); |
| 738 | while (y.signum() > 0) { |
| 739 | r = (a + z.intValue()).toString(b).substr(1) + r; |
| 740 | y.divRemTo(d, y, z); |
| 741 | } |
| 742 | return z.intValue().toString(b) + r; |
| 743 | } |
| 744 | |
| 745 | //(protected) convert from radix string |
| 746 | function bnpFromRadix(s, b) { |
| 747 | this.fromInt(0); |
| 748 | if (b == null) b = 10; |
| 749 | var cs = this.chunkSize(b); |
| 750 | var d = Math.pow(b, cs), mi = false, j = 0, w = 0; |
| 751 | for (var i = 0; i < s.length; ++i) { |
| 752 | var x = intAt(s, i); |
| 753 | if (x < 0) { |
| 754 | if (s.charAt(i) == "-" && this.signum() === 0) mi = true; |
| 755 | continue; |
| 756 | } |
| 757 | w = b * w + x; |
| 758 | if (++j >= cs) { |
| 759 | this.dMultiply(d); |
| 760 | this.dAddOffset(w, 0); |
| 761 | j = 0; |
| 762 | w = 0; |
| 763 | } |
| 764 | } |
| 765 | if (j > 0) { |
| 766 | this.dMultiply(Math.pow(b, j)); |
| 767 | this.dAddOffset(w, 0); |
| 768 | } |
| 769 | if (mi) BigInteger.ZERO.subTo(this, this); |
| 770 | } |
| 771 | |
| 772 | //(protected) alternate constructor |
| 773 | function bnpFromNumber(a, b) { |
| 774 | if ("number" == typeof b) { |
| 775 | // new BigInteger(int,int,RNG) |
| 776 | if (a < 2) this.fromInt(1); |
| 777 | else { |
| 778 | this.fromNumber(a); |
| 779 | if (!this.testBit(a - 1)) // force MSB set |
| 780 | this.bitwiseTo(BigInteger.ONE.shiftLeft(a - 1), op_or, this); |
| 781 | if (this.isEven()) this.dAddOffset(1, 0); // force odd |
| 782 | while (!this.isProbablePrime(b)) { |
| 783 | this.dAddOffset(2, 0); |
| 784 | if (this.bitLength() > a) this.subTo(BigInteger.ONE.shiftLeft(a - 1), this); |
| 785 | } |
| 786 | } |
| 787 | } else { |
| 788 | // new BigInteger(int,RNG) |
| 789 | var x = crypt.randomBytes((a >> 3) + 1) |
| 790 | var t = a & 7; |
| 791 | |
| 792 | if (t > 0) |
| 793 | x[0] &= ((1 << t) - 1); |
| 794 | else |
| 795 | x[0] = 0; |
| 796 | |
| 797 | this.fromByteArray(x); |
| 798 | } |
| 799 | } |
| 800 | |
| 801 | //(public) convert to bigendian byte array |
| 802 | function bnToByteArray() { |
| 803 | var i = this.t, r = new Array(); |
| 804 | r[0] = this.s; |
| 805 | var p = this.DB - (i * this.DB) % 8, d, k = 0; |
| 806 | if (i-- > 0) { |
| 807 | if (p < this.DB && (d = this[i] >> p) != (this.s & this.DM) >> p) |
| 808 | r[k++] = d | (this.s << (this.DB - p)); |
| 809 | while (i >= 0) { |
| 810 | if (p < 8) { |
| 811 | d = (this[i] & ((1 << p) - 1)) << (8 - p); |
| 812 | d |= this[--i] >> (p += this.DB - 8); |
| 813 | } |
| 814 | else { |
| 815 | d = (this[i] >> (p -= 8)) & 0xff; |
| 816 | if (p <= 0) { |
| 817 | p += this.DB; |
| 818 | --i; |
| 819 | } |
| 820 | } |
| 821 | if ((d & 0x80) != 0) d |= -256; |
| 822 | if (k === 0 && (this.s & 0x80) != (d & 0x80)) ++k; |
| 823 | if (k > 0 || d != this.s) r[k++] = d; |
| 824 | } |
| 825 | } |
| 826 | return r; |
| 827 | } |
| 828 | |
| 829 | /** |
| 830 | * return Buffer object |
| 831 | * @param trim {boolean} slice buffer if first element == 0 |
| 832 | * @returns {Buffer} |
| 833 | */ |
| 834 | function bnToBuffer(trimOrSize) { |
| 835 | var res = Buffer.from(this.toByteArray()); |
| 836 | if (trimOrSize === true && res[0] === 0) { |
| 837 | res = res.slice(1); |
| 838 | } else if (isNumber(trimOrSize)) { |
| 839 | if (res.length > trimOrSize) { |
| 840 | for (var i = 0; i < res.length - trimOrSize; i++) { |
| 841 | if (res[i] !== 0) { |
| 842 | return null; |
| 843 | } |
| 844 | } |
| 845 | return res.slice(res.length - trimOrSize); |
| 846 | } else if (res.length < trimOrSize) { |
| 847 | var padded = Buffer.alloc(trimOrSize); |
| 848 | padded.fill(0, 0, trimOrSize - res.length); |
| 849 | res.copy(padded, trimOrSize - res.length); |
| 850 | return padded; |
| 851 | } |
| 852 | } |
| 853 | return res; |
| 854 | } |
| 855 | |
| 856 | function bnEquals(a) { |
| 857 | return (this.compareTo(a) == 0); |
| 858 | } |
| 859 | function bnMin(a) { |
| 860 | return (this.compareTo(a) < 0) ? this : a; |
| 861 | } |
| 862 | function bnMax(a) { |
| 863 | return (this.compareTo(a) > 0) ? this : a; |
| 864 | } |
| 865 | |
| 866 | //(protected) r = this op a (bitwise) |
| 867 | function bnpBitwiseTo(a, op, r) { |
| 868 | var i, f, m = Math.min(a.t, this.t); |
| 869 | for (i = 0; i < m; ++i) r[i] = op(this[i], a[i]); |
| 870 | if (a.t < this.t) { |
| 871 | f = a.s & this.DM; |
| 872 | for (i = m; i < this.t; ++i) r[i] = op(this[i], f); |
| 873 | r.t = this.t; |
| 874 | } |
| 875 | else { |
| 876 | f = this.s & this.DM; |
| 877 | for (i = m; i < a.t; ++i) r[i] = op(f, a[i]); |
| 878 | r.t = a.t; |
| 879 | } |
| 880 | r.s = op(this.s, a.s); |
| 881 | r.clamp(); |
| 882 | } |
| 883 | |
| 884 | //(public) this & a |
| 885 | function op_and(x, y) { |
| 886 | return x & y; |
| 887 | } |
| 888 | function bnAnd(a) { |
| 889 | var r = nbi(); |
| 890 | this.bitwiseTo(a, op_and, r); |
| 891 | return r; |
| 892 | } |
| 893 | |
| 894 | //(public) this | a |
| 895 | function op_or(x, y) { |
| 896 | return x | y; |
| 897 | } |
| 898 | function bnOr(a) { |
| 899 | var r = nbi(); |
| 900 | this.bitwiseTo(a, op_or, r); |
| 901 | return r; |
| 902 | } |
| 903 | |
| 904 | //(public) this ^ a |
| 905 | function op_xor(x, y) { |
| 906 | return x ^ y; |
| 907 | } |
| 908 | function bnXor(a) { |
| 909 | var r = nbi(); |
| 910 | this.bitwiseTo(a, op_xor, r); |
| 911 | return r; |
| 912 | } |
| 913 | |
| 914 | //(public) this & ~a |
| 915 | function op_andnot(x, y) { |
| 916 | return x & ~y; |
| 917 | } |
| 918 | function bnAndNot(a) { |
| 919 | var r = nbi(); |
| 920 | this.bitwiseTo(a, op_andnot, r); |
| 921 | return r; |
| 922 | } |
| 923 | |
| 924 | //(public) ~this |
| 925 | function bnNot() { |
| 926 | var r = nbi(); |
| 927 | for (var i = 0; i < this.t; ++i) r[i] = this.DM & ~this[i]; |
| 928 | r.t = this.t; |
| 929 | r.s = ~this.s; |
| 930 | return r; |
| 931 | } |
| 932 | |
| 933 | //(public) this << n |
| 934 | function bnShiftLeft(n) { |
| 935 | var r = nbi(); |
| 936 | if (n < 0) this.rShiftTo(-n, r); else this.lShiftTo(n, r); |
| 937 | return r; |
| 938 | } |
| 939 | |
| 940 | //(public) this >> n |
| 941 | function bnShiftRight(n) { |
| 942 | var r = nbi(); |
| 943 | if (n < 0) this.lShiftTo(-n, r); else this.rShiftTo(n, r); |
| 944 | return r; |
| 945 | } |
| 946 | |
| 947 | //return index of lowest 1-bit in x, x < 2^31 |
| 948 | function lbit(x) { |
| 949 | if (x === 0) return -1; |
| 950 | var r = 0; |
| 951 | if ((x & 0xffff) === 0) { |
| 952 | x >>= 16; |
| 953 | r += 16; |
| 954 | } |
| 955 | if ((x & 0xff) === 0) { |
| 956 | x >>= 8; |
| 957 | r += 8; |
| 958 | } |
| 959 | if ((x & 0xf) === 0) { |
| 960 | x >>= 4; |
| 961 | r += 4; |
| 962 | } |
| 963 | if ((x & 3) === 0) { |
| 964 | x >>= 2; |
| 965 | r += 2; |
| 966 | } |
| 967 | if ((x & 1) === 0) ++r; |
| 968 | return r; |
| 969 | } |
| 970 | |
| 971 | //(public) returns index of lowest 1-bit (or -1 if none) |
| 972 | function bnGetLowestSetBit() { |
| 973 | for (var i = 0; i < this.t; ++i) |
| 974 | if (this[i] != 0) return i * this.DB + lbit(this[i]); |
| 975 | if (this.s < 0) return this.t * this.DB; |
| 976 | return -1; |
| 977 | } |
| 978 | |
| 979 | //return number of 1 bits in x |
| 980 | function cbit(x) { |
| 981 | var r = 0; |
| 982 | while (x != 0) { |
| 983 | x &= x - 1; |
| 984 | ++r; |
| 985 | } |
| 986 | return r; |
| 987 | } |
| 988 | |
| 989 | //(public) return number of set bits |
| 990 | function bnBitCount() { |
| 991 | var r = 0, x = this.s & this.DM; |
| 992 | for (var i = 0; i < this.t; ++i) r += cbit(this[i] ^ x); |
| 993 | return r; |
| 994 | } |
| 995 | |
| 996 | //(public) true iff nth bit is set |
| 997 | function bnTestBit(n) { |
| 998 | var j = Math.floor(n / this.DB); |
| 999 | if (j >= this.t) return (this.s != 0); |
| 1000 | return ((this[j] & (1 << (n % this.DB))) != 0); |
| 1001 | } |
| 1002 | |
| 1003 | //(protected) this op (1<<n) |
| 1004 | function bnpChangeBit(n, op) { |
| 1005 | var r = BigInteger.ONE.shiftLeft(n); |
| 1006 | this.bitwiseTo(r, op, r); |
| 1007 | return r; |
| 1008 | } |
| 1009 | |
| 1010 | //(public) this | (1<<n) |
| 1011 | function bnSetBit(n) { |
| 1012 | return this.changeBit(n, op_or); |
| 1013 | } |
| 1014 | |
| 1015 | //(public) this & ~(1<<n) |
| 1016 | function bnClearBit(n) { |
| 1017 | return this.changeBit(n, op_andnot); |
| 1018 | } |
| 1019 | |
| 1020 | //(public) this ^ (1<<n) |
| 1021 | function bnFlipBit(n) { |
| 1022 | return this.changeBit(n, op_xor); |
| 1023 | } |
| 1024 | |
| 1025 | //(protected) r = this + a |
| 1026 | function bnpAddTo(a, r) { |
| 1027 | var i = 0, c = 0, m = Math.min(a.t, this.t); |
| 1028 | while (i < m) { |
| 1029 | c += this[i] + a[i]; |
| 1030 | r[i++] = c & this.DM; |
| 1031 | c >>= this.DB; |
| 1032 | } |
| 1033 | if (a.t < this.t) { |
| 1034 | c += a.s; |
| 1035 | while (i < this.t) { |
| 1036 | c += this[i]; |
| 1037 | r[i++] = c & this.DM; |
| 1038 | c >>= this.DB; |
| 1039 | } |
| 1040 | c += this.s; |
| 1041 | } |
| 1042 | else { |
| 1043 | c += this.s; |
| 1044 | while (i < a.t) { |
| 1045 | c += a[i]; |
| 1046 | r[i++] = c & this.DM; |
| 1047 | c >>= this.DB; |
| 1048 | } |
| 1049 | c += a.s; |
| 1050 | } |
| 1051 | r.s = (c < 0) ? -1 : 0; |
| 1052 | if (c > 0) r[i++] = c; |
| 1053 | else if (c < -1) r[i++] = this.DV + c; |
| 1054 | r.t = i; |
| 1055 | r.clamp(); |
| 1056 | } |
| 1057 | |
| 1058 | //(public) this + a |
| 1059 | function bnAdd(a) { |
| 1060 | var r = nbi(); |
| 1061 | this.addTo(a, r); |
| 1062 | return r; |
| 1063 | } |
| 1064 | |
| 1065 | //(public) this - a |
| 1066 | function bnSubtract(a) { |
| 1067 | var r = nbi(); |
| 1068 | this.subTo(a, r); |
| 1069 | return r; |
| 1070 | } |
| 1071 | |
| 1072 | //(public) this * a |
| 1073 | function bnMultiply(a) { |
| 1074 | var r = nbi(); |
| 1075 | this.multiplyTo(a, r); |
| 1076 | return r; |
| 1077 | } |
| 1078 | |
| 1079 | // (public) this^2 |
| 1080 | function bnSquare() { |
| 1081 | var r = nbi(); |
| 1082 | this.squareTo(r); |
| 1083 | return r; |
| 1084 | } |
| 1085 | |
| 1086 | //(public) this / a |
| 1087 | function bnDivide(a) { |
| 1088 | var r = nbi(); |
| 1089 | this.divRemTo(a, r, null); |
| 1090 | return r; |
| 1091 | } |
| 1092 | |
| 1093 | //(public) this % a |
| 1094 | function bnRemainder(a) { |
| 1095 | var r = nbi(); |
| 1096 | this.divRemTo(a, null, r); |
| 1097 | return r; |
| 1098 | } |
| 1099 | |
| 1100 | //(public) [this/a,this%a] |
| 1101 | function bnDivideAndRemainder(a) { |
| 1102 | var q = nbi(), r = nbi(); |
| 1103 | this.divRemTo(a, q, r); |
| 1104 | return new Array(q, r); |
| 1105 | } |
| 1106 | |
| 1107 | //(protected) this *= n, this >= 0, 1 < n < DV |
| 1108 | function bnpDMultiply(n) { |
| 1109 | this[this.t] = this.am(0, n - 1, this, 0, 0, this.t); |
| 1110 | ++this.t; |
| 1111 | this.clamp(); |
| 1112 | } |
| 1113 | |
| 1114 | //(protected) this += n << w words, this >= 0 |
| 1115 | function bnpDAddOffset(n, w) { |
| 1116 | if (n === 0) return; |
| 1117 | while (this.t <= w) this[this.t++] = 0; |
| 1118 | this[w] += n; |
| 1119 | while (this[w] >= this.DV) { |
| 1120 | this[w] -= this.DV; |
| 1121 | if (++w >= this.t) this[this.t++] = 0; |
| 1122 | ++this[w]; |
| 1123 | } |
| 1124 | } |
| 1125 | |
| 1126 | //A "null" reducer |
| 1127 | function NullExp() { |
| 1128 | } |
| 1129 | function nNop(x) { |
| 1130 | return x; |
| 1131 | } |
| 1132 | function nMulTo(x, y, r) { |
| 1133 | x.multiplyTo(y, r); |
| 1134 | } |
| 1135 | function nSqrTo(x, r) { |
| 1136 | x.squareTo(r); |
| 1137 | } |
| 1138 | |
| 1139 | NullExp.prototype.convert = nNop; |
| 1140 | NullExp.prototype.revert = nNop; |
| 1141 | NullExp.prototype.mulTo = nMulTo; |
| 1142 | NullExp.prototype.sqrTo = nSqrTo; |
| 1143 | |
| 1144 | //(public) this^e |
| 1145 | function bnPow(e) { |
| 1146 | return this.exp(e, new NullExp()); |
| 1147 | } |
| 1148 | |
| 1149 | //(protected) r = lower n words of "this * a", a.t <= n |
| 1150 | //"this" should be the larger one if appropriate. |
| 1151 | function bnpMultiplyLowerTo(a, n, r) { |
| 1152 | var i = Math.min(this.t + a.t, n); |
| 1153 | r.s = 0; // assumes a,this >= 0 |
| 1154 | r.t = i; |
| 1155 | while (i > 0) r[--i] = 0; |
| 1156 | var j; |
| 1157 | for (j = r.t - this.t; i < j; ++i) r[i + this.t] = this.am(0, a[i], r, i, 0, this.t); |
| 1158 | for (j = Math.min(a.t, n); i < j; ++i) this.am(0, a[i], r, i, 0, n - i); |
| 1159 | r.clamp(); |
| 1160 | } |
| 1161 | |
| 1162 | //(protected) r = "this * a" without lower n words, n > 0 |
| 1163 | //"this" should be the larger one if appropriate. |
| 1164 | function bnpMultiplyUpperTo(a, n, r) { |
| 1165 | --n; |
| 1166 | var i = r.t = this.t + a.t - n; |
| 1167 | r.s = 0; // assumes a,this >= 0 |
| 1168 | while (--i >= 0) r[i] = 0; |
| 1169 | for (i = Math.max(n - this.t, 0); i < a.t; ++i) |
| 1170 | r[this.t + i - n] = this.am(n - i, a[i], r, 0, 0, this.t + i - n); |
| 1171 | r.clamp(); |
| 1172 | r.drShiftTo(1, r); |
| 1173 | } |
| 1174 | |
| 1175 | //Barrett modular reduction |
| 1176 | function Barrett(m) { |
| 1177 | // setup Barrett |
| 1178 | this.r2 = nbi(); |
| 1179 | this.q3 = nbi(); |
| 1180 | BigInteger.ONE.dlShiftTo(2 * m.t, this.r2); |
| 1181 | this.mu = this.r2.divide(m); |
| 1182 | this.m = m; |
| 1183 | } |
| 1184 | |
| 1185 | function barrettConvert(x) { |
| 1186 | if (x.s < 0 || x.t > 2 * this.m.t) return x.mod(this.m); |
| 1187 | else if (x.compareTo(this.m) < 0) return x; |
| 1188 | else { |
| 1189 | var r = nbi(); |
| 1190 | x.copyTo(r); |
| 1191 | this.reduce(r); |
| 1192 | return r; |
| 1193 | } |
| 1194 | } |
| 1195 | |
| 1196 | function barrettRevert(x) { |
| 1197 | return x; |
| 1198 | } |
| 1199 | |
| 1200 | //x = x mod m (HAC 14.42) |
| 1201 | function barrettReduce(x) { |
| 1202 | x.drShiftTo(this.m.t - 1, this.r2); |
| 1203 | if (x.t > this.m.t + 1) { |
| 1204 | x.t = this.m.t + 1; |
| 1205 | x.clamp(); |
| 1206 | } |
| 1207 | this.mu.multiplyUpperTo(this.r2, this.m.t + 1, this.q3); |
| 1208 | this.m.multiplyLowerTo(this.q3, this.m.t + 1, this.r2); |
| 1209 | while (x.compareTo(this.r2) < 0) x.dAddOffset(1, this.m.t + 1); |
| 1210 | x.subTo(this.r2, x); |
| 1211 | while (x.compareTo(this.m) >= 0) x.subTo(this.m, x); |
| 1212 | } |
| 1213 | |
| 1214 | //r = x^2 mod m; x != r |
| 1215 | function barrettSqrTo(x, r) { |
| 1216 | x.squareTo(r); |
| 1217 | this.reduce(r); |
| 1218 | } |
| 1219 | |
| 1220 | //r = x*y mod m; x,y != r |
| 1221 | function barrettMulTo(x, y, r) { |
| 1222 | x.multiplyTo(y, r); |
| 1223 | this.reduce(r); |
| 1224 | } |
| 1225 | |
| 1226 | Barrett.prototype.convert = barrettConvert; |
| 1227 | Barrett.prototype.revert = barrettRevert; |
| 1228 | Barrett.prototype.reduce = barrettReduce; |
| 1229 | Barrett.prototype.mulTo = barrettMulTo; |
| 1230 | Barrett.prototype.sqrTo = barrettSqrTo; |
| 1231 | |
| 1232 | //(public) this^e % m (HAC 14.85) |
| 1233 | function bnModPow(e, m) { |
| 1234 | var i = e.bitLength(), k, r = nbv(1), z; |
| 1235 | if (i <= 0) return r; |
| 1236 | else if (i < 18) k = 1; |
| 1237 | else if (i < 48) k = 3; |
| 1238 | else if (i < 144) k = 4; |
| 1239 | else if (i < 768) k = 5; |
| 1240 | else k = 6; |
| 1241 | if (i < 8) |
| 1242 | z = new Classic(m); |
| 1243 | else if (m.isEven()) |
| 1244 | z = new Barrett(m); |
| 1245 | else |
| 1246 | z = new Montgomery(m); |
| 1247 | |
| 1248 | // precomputation |
| 1249 | var g = new Array(), n = 3, k1 = k - 1, km = (1 << k) - 1; |
| 1250 | g[1] = z.convert(this); |
| 1251 | if (k > 1) { |
| 1252 | var g2 = nbi(); |
| 1253 | z.sqrTo(g[1], g2); |
| 1254 | while (n <= km) { |
| 1255 | g[n] = nbi(); |
| 1256 | z.mulTo(g2, g[n - 2], g[n]); |
| 1257 | n += 2; |
| 1258 | } |
| 1259 | } |
| 1260 | |
| 1261 | var j = e.t - 1, w, is1 = true, r2 = nbi(), t; |
| 1262 | i = nbits(e[j]) - 1; |
| 1263 | while (j >= 0) { |
| 1264 | if (i >= k1) w = (e[j] >> (i - k1)) & km; |
| 1265 | else { |
| 1266 | w = (e[j] & ((1 << (i + 1)) - 1)) << (k1 - i); |
| 1267 | if (j > 0) w |= e[j - 1] >> (this.DB + i - k1); |
| 1268 | } |
| 1269 | |
| 1270 | n = k; |
| 1271 | while ((w & 1) === 0) { |
| 1272 | w >>= 1; |
| 1273 | --n; |
| 1274 | } |
| 1275 | if ((i -= n) < 0) { |
| 1276 | i += this.DB; |
| 1277 | --j; |
| 1278 | } |
| 1279 | if (is1) { // ret == 1, don't bother squaring or multiplying it |
| 1280 | g[w].copyTo(r); |
| 1281 | is1 = false; |
| 1282 | } |
| 1283 | else { |
| 1284 | while (n > 1) { |
| 1285 | z.sqrTo(r, r2); |
| 1286 | z.sqrTo(r2, r); |
| 1287 | n -= 2; |
| 1288 | } |
| 1289 | if (n > 0) z.sqrTo(r, r2); else { |
| 1290 | t = r; |
| 1291 | r = r2; |
| 1292 | r2 = t; |
| 1293 | } |
| 1294 | z.mulTo(r2, g[w], r); |
| 1295 | } |
| 1296 | |
| 1297 | while (j >= 0 && (e[j] & (1 << i)) === 0) { |
| 1298 | z.sqrTo(r, r2); |
| 1299 | t = r; |
| 1300 | r = r2; |
| 1301 | r2 = t; |
| 1302 | if (--i < 0) { |
| 1303 | i = this.DB - 1; |
| 1304 | --j; |
| 1305 | } |
| 1306 | } |
| 1307 | } |
| 1308 | return z.revert(r); |
| 1309 | } |
| 1310 | |
| 1311 | //(public) gcd(this,a) (HAC 14.54) |
| 1312 | function bnGCD(a) { |
| 1313 | var x = (this.s < 0) ? this.negate() : this.clone(); |
| 1314 | var y = (a.s < 0) ? a.negate() : a.clone(); |
| 1315 | if (x.compareTo(y) < 0) { |
| 1316 | var t = x; |
| 1317 | x = y; |
| 1318 | y = t; |
| 1319 | } |
| 1320 | var i = x.getLowestSetBit(), g = y.getLowestSetBit(); |
| 1321 | if (g < 0) return x; |
| 1322 | if (i < g) g = i; |
| 1323 | if (g > 0) { |
| 1324 | x.rShiftTo(g, x); |
| 1325 | y.rShiftTo(g, y); |
| 1326 | } |
| 1327 | while (x.signum() > 0) { |
| 1328 | if ((i = x.getLowestSetBit()) > 0) x.rShiftTo(i, x); |
| 1329 | if ((i = y.getLowestSetBit()) > 0) y.rShiftTo(i, y); |
| 1330 | if (x.compareTo(y) >= 0) { |
| 1331 | x.subTo(y, x); |
| 1332 | x.rShiftTo(1, x); |
| 1333 | } |
| 1334 | else { |
| 1335 | y.subTo(x, y); |
| 1336 | y.rShiftTo(1, y); |
| 1337 | } |
| 1338 | } |
| 1339 | if (g > 0) y.lShiftTo(g, y); |
| 1340 | return y; |
| 1341 | } |
| 1342 | |
| 1343 | //(protected) this % n, n < 2^26 |
| 1344 | function bnpModInt(n) { |
| 1345 | if (n <= 0) return 0; |
| 1346 | var d = this.DV % n, r = (this.s < 0) ? n - 1 : 0; |
| 1347 | if (this.t > 0) |
| 1348 | if (d === 0) r = this[0] % n; |
| 1349 | else for (var i = this.t - 1; i >= 0; --i) r = (d * r + this[i]) % n; |
| 1350 | return r; |
| 1351 | } |
| 1352 | |
| 1353 | //(public) 1/this % m (HAC 14.61) |
| 1354 | function bnModInverse(m) { |
| 1355 | var ac = m.isEven(); |
| 1356 | if ((this.isEven() && ac) || m.signum() === 0) return BigInteger.ZERO; |
| 1357 | var u = m.clone(), v = this.clone(); |
| 1358 | var a = nbv(1), b = nbv(0), c = nbv(0), d = nbv(1); |
| 1359 | while (u.signum() != 0) { |
| 1360 | while (u.isEven()) { |
| 1361 | u.rShiftTo(1, u); |
| 1362 | if (ac) { |
| 1363 | if (!a.isEven() || !b.isEven()) { |
| 1364 | a.addTo(this, a); |
| 1365 | b.subTo(m, b); |
| 1366 | } |
| 1367 | a.rShiftTo(1, a); |
| 1368 | } |
| 1369 | else if (!b.isEven()) b.subTo(m, b); |
| 1370 | b.rShiftTo(1, b); |
| 1371 | } |
| 1372 | while (v.isEven()) { |
| 1373 | v.rShiftTo(1, v); |
| 1374 | if (ac) { |
| 1375 | if (!c.isEven() || !d.isEven()) { |
| 1376 | c.addTo(this, c); |
| 1377 | d.subTo(m, d); |
| 1378 | } |
| 1379 | c.rShiftTo(1, c); |
| 1380 | } |
| 1381 | else if (!d.isEven()) d.subTo(m, d); |
| 1382 | d.rShiftTo(1, d); |
| 1383 | } |
| 1384 | if (u.compareTo(v) >= 0) { |
| 1385 | u.subTo(v, u); |
| 1386 | if (ac) a.subTo(c, a); |
| 1387 | b.subTo(d, b); |
| 1388 | } |
| 1389 | else { |
| 1390 | v.subTo(u, v); |
| 1391 | if (ac) c.subTo(a, c); |
| 1392 | d.subTo(b, d); |
| 1393 | } |
| 1394 | } |
| 1395 | if (v.compareTo(BigInteger.ONE) != 0) return BigInteger.ZERO; |
| 1396 | if (d.compareTo(m) >= 0) return d.subtract(m); |
| 1397 | if (d.signum() < 0) d.addTo(m, d); else return d; |
| 1398 | if (d.signum() < 0) return d.add(m); else return d; |
| 1399 | } |
| 1400 | |
| 1401 | 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]; |
| 1402 | var lplim = (1 << 26) / lowprimes[lowprimes.length - 1]; |
| 1403 | |
| 1404 | //(public) test primality with certainty >= 1-.5^t |
| 1405 | function bnIsProbablePrime(t) { |
| 1406 | var i, x = this.abs(); |
| 1407 | if (x.t == 1 && x[0] <= lowprimes[lowprimes.length - 1]) { |
| 1408 | for (i = 0; i < lowprimes.length; ++i) |
| 1409 | if (x[0] == lowprimes[i]) return true; |
| 1410 | return false; |
| 1411 | } |
| 1412 | if (x.isEven()) return false; |
| 1413 | i = 1; |
| 1414 | while (i < lowprimes.length) { |
| 1415 | var m = lowprimes[i], j = i + 1; |
| 1416 | while (j < lowprimes.length && m < lplim) m *= lowprimes[j++]; |
| 1417 | m = x.modInt(m); |
| 1418 | while (i < j) if (m % lowprimes[i++] === 0) return false; |
| 1419 | } |
| 1420 | return x.millerRabin(t); |
| 1421 | } |
| 1422 | |
| 1423 | //(protected) true if probably prime (HAC 4.24, Miller-Rabin) |
| 1424 | function bnpMillerRabin(t) { |
| 1425 | var n1 = this.subtract(BigInteger.ONE); |
| 1426 | var k = n1.getLowestSetBit(); |
| 1427 | if (k <= 0) return false; |
| 1428 | var r = n1.shiftRight(k); |
| 1429 | t = (t + 1) >> 1; |
| 1430 | if (t > lowprimes.length) t = lowprimes.length; |
| 1431 | var a = nbi(); |
| 1432 | for (var i = 0; i < t; ++i) { |
| 1433 | //Pick bases at random, instead of starting at 2 |
| 1434 | a.fromInt(lowprimes[Math.floor(Math.random() * lowprimes.length)]); |
| 1435 | var y = a.modPow(r, this); |
| 1436 | if (y.compareTo(BigInteger.ONE) != 0 && y.compareTo(n1) != 0) { |
| 1437 | var j = 1; |
| 1438 | while (j++ < k && y.compareTo(n1) != 0) { |
| 1439 | y = y.modPowInt(2, this); |
| 1440 | if (y.compareTo(BigInteger.ONE) === 0) return false; |
| 1441 | } |
| 1442 | if (y.compareTo(n1) != 0) return false; |
| 1443 | } |
| 1444 | } |
| 1445 | return true; |
| 1446 | } |
| 1447 | |
| 1448 | // protected |
| 1449 | BigInteger.prototype.copyTo = bnpCopyTo; |
| 1450 | BigInteger.prototype.fromInt = bnpFromInt; |
| 1451 | BigInteger.prototype.fromString = bnpFromString; |
| 1452 | BigInteger.prototype.fromByteArray = bnpFromByteArray; |
| 1453 | BigInteger.prototype.fromBuffer = bnpFromBuffer; |
| 1454 | BigInteger.prototype.clamp = bnpClamp; |
| 1455 | BigInteger.prototype.dlShiftTo = bnpDLShiftTo; |
| 1456 | BigInteger.prototype.drShiftTo = bnpDRShiftTo; |
| 1457 | BigInteger.prototype.lShiftTo = bnpLShiftTo; |
| 1458 | BigInteger.prototype.rShiftTo = bnpRShiftTo; |
| 1459 | BigInteger.prototype.subTo = bnpSubTo; |
| 1460 | BigInteger.prototype.multiplyTo = bnpMultiplyTo; |
| 1461 | BigInteger.prototype.squareTo = bnpSquareTo; |
| 1462 | BigInteger.prototype.divRemTo = bnpDivRemTo; |
| 1463 | BigInteger.prototype.invDigit = bnpInvDigit; |
| 1464 | BigInteger.prototype.isEven = bnpIsEven; |
| 1465 | BigInteger.prototype.exp = bnpExp; |
| 1466 | |
| 1467 | BigInteger.prototype.chunkSize = bnpChunkSize; |
| 1468 | BigInteger.prototype.toRadix = bnpToRadix; |
| 1469 | BigInteger.prototype.fromRadix = bnpFromRadix; |
| 1470 | BigInteger.prototype.fromNumber = bnpFromNumber; |
| 1471 | BigInteger.prototype.bitwiseTo = bnpBitwiseTo; |
| 1472 | BigInteger.prototype.changeBit = bnpChangeBit; |
| 1473 | BigInteger.prototype.addTo = bnpAddTo; |
| 1474 | BigInteger.prototype.dMultiply = bnpDMultiply; |
| 1475 | BigInteger.prototype.dAddOffset = bnpDAddOffset; |
| 1476 | BigInteger.prototype.multiplyLowerTo = bnpMultiplyLowerTo; |
| 1477 | BigInteger.prototype.multiplyUpperTo = bnpMultiplyUpperTo; |
| 1478 | BigInteger.prototype.modInt = bnpModInt; |
| 1479 | BigInteger.prototype.millerRabin = bnpMillerRabin; |
| 1480 | |
| 1481 | |
| 1482 | // public |
| 1483 | BigInteger.prototype.toString = bnToString; |
| 1484 | BigInteger.prototype.negate = bnNegate; |
| 1485 | BigInteger.prototype.abs = bnAbs; |
| 1486 | BigInteger.prototype.compareTo = bnCompareTo; |
| 1487 | BigInteger.prototype.bitLength = bnBitLength; |
| 1488 | BigInteger.prototype.mod = bnMod; |
| 1489 | BigInteger.prototype.modPowInt = bnModPowInt; |
| 1490 | |
| 1491 | BigInteger.prototype.clone = bnClone; |
| 1492 | BigInteger.prototype.intValue = bnIntValue; |
| 1493 | BigInteger.prototype.byteValue = bnByteValue; |
| 1494 | BigInteger.prototype.shortValue = bnShortValue; |
| 1495 | BigInteger.prototype.signum = bnSigNum; |
| 1496 | BigInteger.prototype.toByteArray = bnToByteArray; |
| 1497 | BigInteger.prototype.toBuffer = bnToBuffer; |
| 1498 | BigInteger.prototype.equals = bnEquals; |
| 1499 | BigInteger.prototype.min = bnMin; |
| 1500 | BigInteger.prototype.max = bnMax; |
| 1501 | BigInteger.prototype.and = bnAnd; |
| 1502 | BigInteger.prototype.or = bnOr; |
| 1503 | BigInteger.prototype.xor = bnXor; |
| 1504 | BigInteger.prototype.andNot = bnAndNot; |
| 1505 | BigInteger.prototype.not = bnNot; |
| 1506 | BigInteger.prototype.shiftLeft = bnShiftLeft; |
| 1507 | BigInteger.prototype.shiftRight = bnShiftRight; |
| 1508 | BigInteger.prototype.getLowestSetBit = bnGetLowestSetBit; |
| 1509 | BigInteger.prototype.bitCount = bnBitCount; |
| 1510 | BigInteger.prototype.testBit = bnTestBit; |
| 1511 | BigInteger.prototype.setBit = bnSetBit; |
| 1512 | BigInteger.prototype.clearBit = bnClearBit; |
| 1513 | BigInteger.prototype.flipBit = bnFlipBit; |
| 1514 | BigInteger.prototype.add = bnAdd; |
| 1515 | BigInteger.prototype.subtract = bnSubtract; |
| 1516 | BigInteger.prototype.multiply = bnMultiply; |
| 1517 | BigInteger.prototype.divide = bnDivide; |
| 1518 | BigInteger.prototype.remainder = bnRemainder; |
| 1519 | BigInteger.prototype.divideAndRemainder = bnDivideAndRemainder; |
| 1520 | BigInteger.prototype.modPow = bnModPow; |
| 1521 | BigInteger.prototype.modInverse = bnModInverse; |
| 1522 | BigInteger.prototype.pow = bnPow; |
| 1523 | BigInteger.prototype.gcd = bnGCD; |
| 1524 | BigInteger.prototype.isProbablePrime = bnIsProbablePrime; |
| 1525 | BigInteger.int2char = int2char; |
| 1526 | |
| 1527 | // "constants" |
| 1528 | BigInteger.ZERO = nbv(0); |
| 1529 | BigInteger.ONE = nbv(1); |
| 1530 | |
| 1531 | // JSBN-specific extension |
| 1532 | BigInteger.prototype.square = bnSquare; |
| 1533 | |
| 1534 | //BigInteger interfaces not implemented in jsbn: |
| 1535 | |
| 1536 | //BigInteger(int signum, byte[] magnitude) |
| 1537 | //double doubleValue() |
| 1538 | //float floatValue() |
| 1539 | //int hashCode() |
| 1540 | //long longValue() |
| 1541 | //static BigInteger valueOf(long val) |
| 1542 | |
| 1543 | module.exports = BigInteger; |