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