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