|
1 //////////////////////////////////////////////////////////////////////////////////////// |
|
2 // Big Integer Library v. 5.1 |
|
3 // Created 2000, last modified 2007 |
|
4 // Leemon Baird |
|
5 // www.leemon.com |
|
6 // |
|
7 // Version history: |
|
8 // |
|
9 // v 5.1 8 Oct 2007 |
|
10 // - renamed inverseModInt_ to inverseModInt since it doesn't change its parameters |
|
11 // - added functions GCD and randBigInt, which call GCD_ and randBigInt_ |
|
12 // - fixed a bug found by Rob Visser (see comment with his name below) |
|
13 // - improved comments |
|
14 // |
|
15 // This file is public domain. You can use it for any purpose without restriction. |
|
16 // I do not guarantee that it is correct, so use it at your own risk. If you use |
|
17 // it for something interesting, I'd appreciate hearing about it. If you find |
|
18 // any bugs or make any improvements, I'd appreciate hearing about those too. |
|
19 // It would also be nice if my name and address were left in the comments. |
|
20 // But none of that is required. |
|
21 // |
|
22 // This code defines a bigInt library for arbitrary-precision integers. |
|
23 // A bigInt is an array of integers storing the value in chunks of bpe bits, |
|
24 // little endian (buff[0] is the least significant word). |
|
25 // Negative bigInts are stored two's complement. |
|
26 // Some functions assume their parameters have at least one leading zero element. |
|
27 // Functions with an underscore at the end of the name have unpredictable behavior in case of overflow, |
|
28 // so the caller must make sure the arrays must be big enough to hold the answer. |
|
29 // For each function where a parameter is modified, that same |
|
30 // variable must not be used as another argument too. |
|
31 // So, you cannot square x by doing multMod_(x,x,n). |
|
32 // You must use squareMod_(x,n) instead, or do y=dup(x); multMod_(x,y,n). |
|
33 // |
|
34 // These functions are designed to avoid frequent dynamic memory allocation in the inner loop. |
|
35 // For most functions, if it needs a BigInt as a local variable it will actually use |
|
36 // a global, and will only allocate to it only when it's not the right size. This ensures |
|
37 // that when a function is called repeatedly with same-sized parameters, it only allocates |
|
38 // memory on the first call. |
|
39 // |
|
40 // Note that for cryptographic purposes, the calls to Math.random() must |
|
41 // be replaced with calls to a better pseudorandom number generator. |
|
42 // |
|
43 // In the following, "bigInt" means a bigInt with at least one leading zero element, |
|
44 // and "integer" means a nonnegative integer less than radix. In some cases, integer |
|
45 // can be negative. Negative bigInts are 2s complement. |
|
46 // |
|
47 // The following functions do not modify their inputs. |
|
48 // Those returning a bigInt, string, or Array will dynamically allocate memory for that value. |
|
49 // Those returning a boolean will return the integer 0 (false) or 1 (true). |
|
50 // Those returning boolean or int will not allocate memory except possibly on the first time they're called with a given parameter size. |
|
51 // |
|
52 // bigInt add(x,y) //return (x+y) for bigInts x and y. |
|
53 // bigInt addInt(x,n) //return (x+n) where x is a bigInt and n is an integer. |
|
54 // string bigInt2str(x,base) //return a string form of bigInt x in a given base, with 2 <= base <= 95 |
|
55 // int bitSize(x) //return how many bits long the bigInt x is, not counting leading zeros |
|
56 // bigInt dup(x) //return a copy of bigInt x |
|
57 // boolean equals(x,y) //is the bigInt x equal to the bigint y? |
|
58 // boolean equalsInt(x,y) //is bigint x equal to integer y? |
|
59 // bigInt expand(x,n) //return a copy of x with at least n elements, adding leading zeros if needed |
|
60 // Array findPrimes(n) //return array of all primes less than integer n |
|
61 // bigInt GCD(x,y) //return greatest common divisor of bigInts x and y (each with same number of elements). |
|
62 // boolean greater(x,y) //is x>y? (x and y are nonnegative bigInts) |
|
63 // boolean greaterShift(x,y,shift)//is (x <<(shift*bpe)) > y? |
|
64 // bigInt int2bigInt(t,n,m) //return a bigInt equal to integer t, with at least n bits and m array elements |
|
65 // bigInt inverseMod(x,n) //return (x**(-1) mod n) for bigInts x and n. If no inverse exists, it returns null |
|
66 // int inverseModInt(x,n) //return x**(-1) mod n, for integers x and n. Return 0 if there is no inverse |
|
67 // boolean isZero(x) //is the bigInt x equal to zero? |
|
68 // boolean millerRabin(x,b) //does one round of Miller-Rabin base integer b say that bigInt x is possibly prime (as opposed to definitely composite)? |
|
69 // bigInt mod(x,n) //return a new bigInt equal to (x mod n) for bigInts x and n. |
|
70 // int modInt(x,n) //return x mod n for bigInt x and integer n. |
|
71 // bigInt mult(x,y) //return x*y for bigInts x and y. This is faster when y<x. |
|
72 // bigInt multMod(x,y,n) //return (x*y mod n) for bigInts x,y,n. For greater speed, let y<x. |
|
73 // boolean negative(x) //is bigInt x negative? |
|
74 // bigInt powMod(x,y,n) //return (x**y mod n) where x,y,n are bigInts and ** is exponentiation. 0**0=1. Faster for odd n. |
|
75 // bigInt randBigInt(n,s) //return an n-bit random BigInt (n>=1). If s=1, then the most significant of those n bits is set to 1. |
|
76 // bigInt randTruePrime(k) //return a new, random, k-bit, true prime bigInt using Maurer's algorithm. |
|
77 // bigInt str2bigInt(s,b,n,m) //return a bigInt for number represented in string s in base b with at least n bits and m array elements |
|
78 // bigInt sub(x,y) //return (x-y) for bigInts x and y. Negative answers will be 2s complement |
|
79 // bigInt bigint_trim(x,k) //return a copy of x with exactly k leading zero elements |
|
80 // |
|
81 // |
|
82 // The following functions each have a non-underscored version, which most users should call instead. |
|
83 // These functions each write to a single parameter, and the caller is responsible for ensuring the array |
|
84 // passed in is large enough to hold the result. |
|
85 // |
|
86 // void addInt_(x,n) //do x=x+n where x is a bigInt and n is an integer |
|
87 // void add_(x,y) //do x=x+y for bigInts x and y |
|
88 // void copy_(x,y) //do x=y on bigInts x and y |
|
89 // void copyInt_(x,n) //do x=n on bigInt x and integer n |
|
90 // void GCD_(x,y) //set x to the greatest common divisor of bigInts x and y, (y is destroyed). (This never overflows its array). |
|
91 // boolean inverseMod_(x,n) //do x=x**(-1) mod n, for bigInts x and n. Returns 1 (0) if inverse does (doesn't) exist |
|
92 // void mod_(x,n) //do x=x mod n for bigInts x and n. (This never overflows its array). |
|
93 // void mult_(x,y) //do x=x*y for bigInts x and y. |
|
94 // void multMod_(x,y,n) //do x=x*y mod n for bigInts x,y,n. |
|
95 // void powMod_(x,y,n) //do x=x**y mod n, where x,y,n are bigInts (n is odd) and ** is exponentiation. 0**0=1. |
|
96 // void randBigInt_(b,n,s) //do b = an n-bit random BigInt. if s=1, then nth bit (most significant bit) is set to 1. n>=1. |
|
97 // void randTruePrime_(ans,k) //do ans = a random k-bit true random prime (not just probable prime) with 1 in the msb. |
|
98 // void sub_(x,y) //do x=x-y for bigInts x and y. Negative answers will be 2s complement. |
|
99 // |
|
100 // The following functions do NOT have a non-underscored version. |
|
101 // They each write a bigInt result to one or more parameters. The caller is responsible for |
|
102 // ensuring the arrays passed in are large enough to hold the results. |
|
103 // |
|
104 // void addShift_(x,y,ys) //do x=x+(y<<(ys*bpe)) |
|
105 // void carry_(x) //do carries and borrows so each element of the bigInt x fits in bpe bits. |
|
106 // void divide_(x,y,q,r) //divide x by y giving quotient q and remainder r |
|
107 // int divInt_(x,n) //do x=floor(x/n) for bigInt x and integer n, and return the remainder. (This never overflows its array). |
|
108 // int eGCD_(x,y,d,a,b) //sets a,b,d to positive bigInts such that d = GCD_(x,y) = a*x-b*y |
|
109 // void halve_(x) //do x=floor(|x|/2)*sgn(x) for bigInt x in 2's complement. (This never overflows its array). |
|
110 // void leftShift_(x,n) //left shift bigInt x by n bits. n<bpe. |
|
111 // void linComb_(x,y,a,b) //do x=a*x+b*y for bigInts x and y and integers a and b |
|
112 // void linCombShift_(x,y,b,ys) //do x=x+b*(y<<(ys*bpe)) for bigInts x and y, and integers b and ys |
|
113 // void mont_(x,y,n,np) //Montgomery multiplication (see comments where the function is defined) |
|
114 // void multInt_(x,n) //do x=x*n where x is a bigInt and n is an integer. |
|
115 // void rightShift_(x,n) //right shift bigInt x by n bits. 0 <= n < bpe. (This never overflows its array). |
|
116 // void squareMod_(x,n) //do x=x*x mod n for bigInts x,n |
|
117 // void subShift_(x,y,ys) //do x=x-(y<<(ys*bpe)). Negative answers will be 2s complement. |
|
118 // |
|
119 // The following functions are based on algorithms from the _Handbook of Applied Cryptography_ |
|
120 // powMod_() = algorithm 14.94, Montgomery exponentiation |
|
121 // eGCD_,inverseMod_() = algorithm 14.61, Binary extended GCD_ |
|
122 // GCD_() = algorothm 14.57, Lehmer's algorithm |
|
123 // mont_() = algorithm 14.36, Montgomery multiplication |
|
124 // divide_() = algorithm 14.20 Multiple-precision division |
|
125 // squareMod_() = algorithm 14.16 Multiple-precision squaring |
|
126 // randTruePrime_() = algorithm 4.62, Maurer's algorithm |
|
127 // millerRabin() = algorithm 4.24, Miller-Rabin algorithm |
|
128 // |
|
129 // Profiling shows: |
|
130 // randTruePrime_() spends: |
|
131 // 10% of its time in calls to powMod_() |
|
132 // 85% of its time in calls to millerRabin() |
|
133 // millerRabin() spends: |
|
134 // 99% of its time in calls to powMod_() (always with a base of 2) |
|
135 // powMod_() spends: |
|
136 // 94% of its time in calls to mont_() (almost always with x==y) |
|
137 // |
|
138 // This suggests there are several ways to speed up this library slightly: |
|
139 // - convert powMod_ to use a Montgomery form of k-ary window (or maybe a Montgomery form of sliding window) |
|
140 // -- this should especially focus on being fast when raising 2 to a power mod n |
|
141 // - convert randTruePrime_() to use a minimum r of 1/3 instead of 1/2 with the appropriate change to the test |
|
142 // - tune the parameters in randTruePrime_(), including c, m, and recLimit |
|
143 // - speed up the single loop in mont_() that takes 95% of the runtime, perhaps by reducing checking |
|
144 // within the loop when all the parameters are the same length. |
|
145 // |
|
146 // There are several ideas that look like they wouldn't help much at all: |
|
147 // - replacing trial division in randTruePrime_() with a sieve (that speeds up something taking almost no time anyway) |
|
148 // - increase bpe from 15 to 30 (that would help if we had a 32*32->64 multiplier, but not with JavaScript's 32*32->32) |
|
149 // - speeding up mont_(x,y,n,np) when x==y by doing a non-modular, non-Montgomery square |
|
150 // followed by a Montgomery reduction. The intermediate answer will be twice as long as x, so that |
|
151 // method would be slower. This is unfortunate because the code currently spends almost all of its time |
|
152 // doing mont_(x,x,...), both for randTruePrime_() and powMod_(). A faster method for Montgomery squaring |
|
153 // would have a large impact on the speed of randTruePrime_() and powMod_(). HAC has a couple of poorly-worded |
|
154 // sentences that seem to imply it's faster to do a non-modular square followed by a single |
|
155 // Montgomery reduction, but that's obviously wrong. |
|
156 //////////////////////////////////////////////////////////////////////////////////////// |
|
157 |
|
158 //globals |
|
159 bpe=0; //bits stored per array element |
|
160 mask=0; //AND this with an array element to chop it down to bpe bits |
|
161 radix=mask+1; //equals 2^bpe. A single 1 bit to the left of the last bit of mask. |
|
162 |
|
163 //the digits for converting to different bases |
|
164 digitsStr='0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz_=!@#$%^&*()[]{}|;:,.<>/?`~ \\\'\"+-'; |
|
165 |
|
166 //initialize the global variables |
|
167 for (bpe=0; (1<<(bpe+1)) > (1<<bpe); bpe++); //bpe=number of bits in the mantissa on this platform |
|
168 bpe>>=1; //bpe=number of bits in one element of the array representing the bigInt |
|
169 mask=(1<<bpe)-1; //AND the mask with an integer to get its bpe least significant bits |
|
170 radix=mask+1; //2^bpe. a single 1 bit to the left of the first bit of mask |
|
171 one=int2bigInt(1,1,1); //constant used in powMod_() |
|
172 |
|
173 //the following global variables are scratchpad memory to |
|
174 //reduce dynamic memory allocation in the inner loop |
|
175 t=new Array(0); |
|
176 ss=t; //used in mult_() |
|
177 s0=t; //used in multMod_(), squareMod_() |
|
178 s1=t; //used in powMod_(), multMod_(), squareMod_() |
|
179 s2=t; //used in powMod_(), multMod_() |
|
180 s3=t; //used in powMod_() |
|
181 s4=t; s5=t; //used in mod_() |
|
182 s6=t; //used in bigInt2str() |
|
183 s7=t; //used in powMod_() |
|
184 T=t; //used in GCD_() |
|
185 sa=t; //used in mont_() |
|
186 mr_x1=t; mr_r=t; mr_a=t; //used in millerRabin() |
|
187 eg_v=t; eg_u=t; eg_A=t; eg_B=t; eg_C=t; eg_D=t; //used in eGCD_(), inverseMod_() |
|
188 md_q1=t; md_q2=t; md_q3=t; md_r=t; md_r1=t; md_r2=t; md_tt=t; //used in mod_() |
|
189 |
|
190 primes=t; pows=t; s_i=t; s_i2=t; s_R=t; s_rm=t; s_q=t; s_n1=t; |
|
191 s_a=t; s_r2=t; s_n=t; s_b=t; s_d=t; s_x1=t; s_x2=t, s_aa=t; //used in randTruePrime_() |
|
192 |
|
193 //////////////////////////////////////////////////////////////////////////////////////// |
|
194 |
|
195 //return array of all primes less than integer n |
|
196 function findPrimes(n) { |
|
197 var i,s,p,ans; |
|
198 s=new Array(n); |
|
199 for (i=0;i<n;i++) |
|
200 s[i]=0; |
|
201 s[0]=2; |
|
202 p=0; //first p elements of s are primes, the rest are a sieve |
|
203 for(;s[p]<n;) { //s[p] is the pth prime |
|
204 for(i=s[p]*s[p]; i<n; i+=s[p]) //mark multiples of s[p] |
|
205 s[i]=1; |
|
206 p++; |
|
207 s[p]=s[p-1]+1; |
|
208 for(; s[p]<n && s[s[p]]; s[p]++); //find next prime (where s[p]==0) |
|
209 } |
|
210 ans=new Array(p); |
|
211 for(i=0;i<p;i++) |
|
212 ans[i]=s[i]; |
|
213 return ans; |
|
214 } |
|
215 |
|
216 //does a single round of Miller-Rabin base b consider x to be a possible prime? |
|
217 //x is a bigInt, and b is an integer |
|
218 function millerRabin(x,b) { |
|
219 var i,j,k,s; |
|
220 |
|
221 if (mr_x1.length!=x.length) { |
|
222 mr_x1=dup(x); |
|
223 mr_r=dup(x); |
|
224 mr_a=dup(x); |
|
225 } |
|
226 |
|
227 copyInt_(mr_a,b); |
|
228 copy_(mr_r,x); |
|
229 copy_(mr_x1,x); |
|
230 |
|
231 addInt_(mr_r,-1); |
|
232 addInt_(mr_x1,-1); |
|
233 |
|
234 //s=the highest power of two that divides mr_r |
|
235 k=0; |
|
236 for (i=0;i<mr_r.length;i++) |
|
237 for (j=1;j<mask;j<<=1) |
|
238 if (x[i] & j) { |
|
239 s=(k<mr_r.length+bpe ? k : 0); |
|
240 i=mr_r.length; |
|
241 j=mask; |
|
242 } else |
|
243 k++; |
|
244 |
|
245 if (s) |
|
246 rightShift_(mr_r,s); |
|
247 |
|
248 powMod_(mr_a,mr_r,x); |
|
249 |
|
250 if (!equalsInt(mr_a,1) && !equals(mr_a,mr_x1)) { |
|
251 j=1; |
|
252 while (j<=s-1 && !equals(mr_a,mr_x1)) { |
|
253 squareMod_(mr_a,x); |
|
254 if (equalsInt(mr_a,1)) { |
|
255 return 0; |
|
256 } |
|
257 j++; |
|
258 } |
|
259 if (!equals(mr_a,mr_x1)) { |
|
260 return 0; |
|
261 } |
|
262 } |
|
263 return 1; |
|
264 } |
|
265 |
|
266 //returns how many bits long the bigInt is, not counting leading zeros. |
|
267 function bitSize(x) { |
|
268 var j,z,w; |
|
269 for (j=x.length-1; (x[j]==0) && (j>0); j--); |
|
270 for (z=0,w=x[j]; w; (w>>=1),z++); |
|
271 z+=bpe*j; |
|
272 return z; |
|
273 } |
|
274 |
|
275 //return a copy of x with at least n elements, adding leading zeros if needed |
|
276 function expand(x,n) { |
|
277 var ans=int2bigInt(0,(x.length>n ? x.length : n)*bpe,0); |
|
278 copy_(ans,x); |
|
279 return ans; |
|
280 } |
|
281 |
|
282 //return a k-bit true random prime using Maurer's algorithm. |
|
283 function randTruePrime(k) { |
|
284 var ans=int2bigInt(0,k,0); |
|
285 randTruePrime_(ans,k); |
|
286 return bigint_trim(ans,1); |
|
287 } |
|
288 |
|
289 //return a new bigInt equal to (x mod n) for bigInts x and n. |
|
290 function mod(x,n) { |
|
291 var ans=dup(x); |
|
292 mod_(ans,n); |
|
293 return bigint_trim(ans,1); |
|
294 } |
|
295 |
|
296 //return (x+n) where x is a bigInt and n is an integer. |
|
297 function addInt(x,n) { |
|
298 var ans=expand(x,x.length+1); |
|
299 addInt_(ans,n); |
|
300 return bigint_trim(ans,1); |
|
301 } |
|
302 |
|
303 //return x*y for bigInts x and y. This is faster when y<x. |
|
304 function mult(x,y) { |
|
305 var ans=expand(x,x.length+y.length); |
|
306 mult_(ans,y); |
|
307 return bigint_trim(ans,1); |
|
308 } |
|
309 |
|
310 //return (x**y mod n) where x,y,n are bigInts and ** is exponentiation. 0**0=1. Faster for odd n. |
|
311 function powMod(x,y,n) { |
|
312 var ans=expand(x,n.length); |
|
313 powMod_(ans,bigint_trim(y,2),bigint_trim(n,2),0); //this should work without the trim, but doesn't |
|
314 return bigint_trim(ans,1); |
|
315 } |
|
316 |
|
317 //return (x-y) for bigInts x and y. Negative answers will be 2s complement |
|
318 function sub(x,y) { |
|
319 var ans=expand(x,(x.length>y.length ? x.length+1 : y.length+1)); |
|
320 sub_(ans,y); |
|
321 return bigint_trim(ans,1); |
|
322 } |
|
323 |
|
324 //return (x+y) for bigInts x and y. |
|
325 function add(x,y) { |
|
326 var ans=expand(x,(x.length>y.length ? x.length+1 : y.length+1)); |
|
327 add_(ans,y); |
|
328 return bigint_trim(ans,1); |
|
329 } |
|
330 |
|
331 //return (x**(-1) mod n) for bigInts x and n. If no inverse exists, it returns null |
|
332 function inverseMod(x,n) { |
|
333 var ans=expand(x,n.length); |
|
334 var s; |
|
335 s=inverseMod_(ans,n); |
|
336 return s ? bigint_trim(ans,1) : null; |
|
337 } |
|
338 |
|
339 //return (x*y mod n) for bigInts x,y,n. For greater speed, let y<x. |
|
340 function multMod(x,y,n) { |
|
341 var ans=expand(x,n.length); |
|
342 multMod_(ans,y,n); |
|
343 return bigint_trim(ans,1); |
|
344 } |
|
345 |
|
346 //generate a k-bit true random prime using Maurer's algorithm, |
|
347 //and put it into ans. The bigInt ans must be large enough to hold it. |
|
348 function randTruePrime_(ans,k) { |
|
349 var c,m,pm,dd,j,r,B,divisible,z,zz,recSize; |
|
350 |
|
351 if (primes.length==0) |
|
352 primes=findPrimes(30000); //check for divisibility by primes <=30000 |
|
353 |
|
354 if (pows.length==0) { |
|
355 pows=new Array(512); |
|
356 for (j=0;j<512;j++) { |
|
357 pows[j]=Math.pow(2,j/511.-1.); |
|
358 } |
|
359 } |
|
360 |
|
361 //c and m should be tuned for a particular machine and value of k, to maximize speed |
|
362 c=0.1; //c=0.1 in HAC |
|
363 m=20; //generate this k-bit number by first recursively generating a number that has between k/2 and k-m bits |
|
364 recLimit=20; //stop recursion when k <=recLimit. Must have recLimit >= 2 |
|
365 |
|
366 if (s_i2.length!=ans.length) { |
|
367 s_i2=dup(ans); |
|
368 s_R =dup(ans); |
|
369 s_n1=dup(ans); |
|
370 s_r2=dup(ans); |
|
371 s_d =dup(ans); |
|
372 s_x1=dup(ans); |
|
373 s_x2=dup(ans); |
|
374 s_b =dup(ans); |
|
375 s_n =dup(ans); |
|
376 s_i =dup(ans); |
|
377 s_rm=dup(ans); |
|
378 s_q =dup(ans); |
|
379 s_a =dup(ans); |
|
380 s_aa=dup(ans); |
|
381 } |
|
382 |
|
383 if (k <= recLimit) { //generate small random primes by trial division up to its square root |
|
384 pm=(1<<((k+2)>>1))-1; //pm is binary number with all ones, just over sqrt(2^k) |
|
385 copyInt_(ans,0); |
|
386 for (dd=1;dd;) { |
|
387 dd=0; |
|
388 ans[0]= 1 | (1<<(k-1)) | Math.floor(Math.random()*(1<<k)); //random, k-bit, odd integer, with msb 1 |
|
389 for (j=1;(j<primes.length) && ((primes[j]&pm)==primes[j]);j++) { //trial division by all primes 3...sqrt(2^k) |
|
390 if (0==(ans[0]%primes[j])) { |
|
391 dd=1; |
|
392 break; |
|
393 } |
|
394 } |
|
395 } |
|
396 carry_(ans); |
|
397 return; |
|
398 } |
|
399 |
|
400 B=c*k*k; //try small primes up to B (or all the primes[] array if the largest is less than B). |
|
401 if (k>2*m) //generate this k-bit number by first recursively generating a number that has between k/2 and k-m bits |
|
402 for (r=1; k-k*r<=m; ) |
|
403 r=pows[Math.floor(Math.random()*512)]; //r=Math.pow(2,Math.random()-1); |
|
404 else |
|
405 r=.5; |
|
406 |
|
407 //simulation suggests the more complex algorithm using r=.333 is only slightly faster. |
|
408 |
|
409 recSize=Math.floor(r*k)+1; |
|
410 |
|
411 randTruePrime_(s_q,recSize); |
|
412 copyInt_(s_i2,0); |
|
413 s_i2[Math.floor((k-2)/bpe)] |= (1<<((k-2)%bpe)); //s_i2=2^(k-2) |
|
414 divide_(s_i2,s_q,s_i,s_rm); //s_i=floor((2^(k-1))/(2q)) |
|
415 |
|
416 z=bitSize(s_i); |
|
417 |
|
418 for (;;) { |
|
419 for (;;) { //generate z-bit numbers until one falls in the range [0,s_i-1] |
|
420 randBigInt_(s_R,z,0); |
|
421 if (greater(s_i,s_R)) |
|
422 break; |
|
423 } //now s_R is in the range [0,s_i-1] |
|
424 addInt_(s_R,1); //now s_R is in the range [1,s_i] |
|
425 add_(s_R,s_i); //now s_R is in the range [s_i+1,2*s_i] |
|
426 |
|
427 copy_(s_n,s_q); |
|
428 mult_(s_n,s_R); |
|
429 multInt_(s_n,2); |
|
430 addInt_(s_n,1); //s_n=2*s_R*s_q+1 |
|
431 |
|
432 copy_(s_r2,s_R); |
|
433 multInt_(s_r2,2); //s_r2=2*s_R |
|
434 |
|
435 //check s_n for divisibility by small primes up to B |
|
436 for (divisible=0,j=0; (j<primes.length) && (primes[j]<B); j++) |
|
437 if (modInt(s_n,primes[j])==0) { |
|
438 divisible=1; |
|
439 break; |
|
440 } |
|
441 |
|
442 if (!divisible) //if it passes small primes check, then try a single Miller-Rabin base 2 |
|
443 if (!millerRabin(s_n,2)) //this line represents 75% of the total runtime for randTruePrime_ |
|
444 divisible=1; |
|
445 |
|
446 if (!divisible) { //if it passes that test, continue checking s_n |
|
447 addInt_(s_n,-3); |
|
448 for (j=s_n.length-1;(s_n[j]==0) && (j>0); j--); //strip leading zeros |
|
449 for (zz=0,w=s_n[j]; w; (w>>=1),zz++); |
|
450 zz+=bpe*j; //zz=number of bits in s_n, ignoring leading zeros |
|
451 for (;;) { //generate z-bit numbers until one falls in the range [0,s_n-1] |
|
452 randBigInt_(s_a,zz,0); |
|
453 if (greater(s_n,s_a)) |
|
454 break; |
|
455 } //now s_a is in the range [0,s_n-1] |
|
456 addInt_(s_n,3); //now s_a is in the range [0,s_n-4] |
|
457 addInt_(s_a,2); //now s_a is in the range [2,s_n-2] |
|
458 copy_(s_b,s_a); |
|
459 copy_(s_n1,s_n); |
|
460 addInt_(s_n1,-1); |
|
461 powMod_(s_b,s_n1,s_n); //s_b=s_a^(s_n-1) modulo s_n |
|
462 addInt_(s_b,-1); |
|
463 if (isZero(s_b)) { |
|
464 copy_(s_b,s_a); |
|
465 powMod_(s_b,s_r2,s_n); |
|
466 addInt_(s_b,-1); |
|
467 copy_(s_aa,s_n); |
|
468 copy_(s_d,s_b); |
|
469 GCD_(s_d,s_n); //if s_b and s_n are relatively prime, then s_n is a prime |
|
470 if (equalsInt(s_d,1)) { |
|
471 copy_(ans,s_aa); |
|
472 return; //if we've made it this far, then s_n is absolutely guaranteed to be prime |
|
473 } |
|
474 } |
|
475 } |
|
476 } |
|
477 } |
|
478 |
|
479 //Return an n-bit random BigInt (n>=1). If s=1, then the most significant of those n bits is set to 1. |
|
480 function randBigInt(n,s) { |
|
481 var a,b; |
|
482 a=Math.floor((n-1)/bpe)+2; //# array elements to hold the BigInt with a leading 0 element |
|
483 b=int2bigInt(0,0,a); |
|
484 randBigInt_(b,n,s); |
|
485 return b; |
|
486 } |
|
487 |
|
488 //Set b to an n-bit random BigInt. If s=1, then the most significant of those n bits is set to 1. |
|
489 //Array b must be big enough to hold the result. Must have n>=1 |
|
490 function randBigInt_(b,n,s) { |
|
491 var i,a; |
|
492 for (i=0;i<b.length;i++) |
|
493 b[i]=0; |
|
494 a=Math.floor((n-1)/bpe)+1; //# array elements to hold the BigInt |
|
495 for (i=0;i<a;i++) { |
|
496 b[i]=Math.floor(Math.random()*(1<<(bpe-1))); |
|
497 } |
|
498 b[a-1] &= (2<<((n-1)%bpe))-1; |
|
499 if (s==1) |
|
500 b[a-1] |= (1<<((n-1)%bpe)); |
|
501 } |
|
502 |
|
503 //Return the greatest common divisor of bigInts x and y (each with same number of elements). |
|
504 function GCD(x,y) { |
|
505 var xc,yc; |
|
506 xc=dup(x); |
|
507 yc=dup(y); |
|
508 GCD_(xc,yc); |
|
509 return xc; |
|
510 } |
|
511 |
|
512 //set x to the greatest common divisor of bigInts x and y (each with same number of elements). |
|
513 //y is destroyed. |
|
514 function GCD_(x,y) { |
|
515 var i,xp,yp,A,B,C,D,q,sing; |
|
516 if (T.length!=x.length) |
|
517 T=dup(x); |
|
518 |
|
519 sing=1; |
|
520 while (sing) { //while y has nonzero elements other than y[0] |
|
521 sing=0; |
|
522 for (i=1;i<y.length;i++) //check if y has nonzero elements other than 0 |
|
523 if (y[i]) { |
|
524 sing=1; |
|
525 break; |
|
526 } |
|
527 if (!sing) break; //quit when y all zero elements except possibly y[0] |
|
528 |
|
529 for (i=x.length;!x[i] && i>=0;i--); //find most significant element of x |
|
530 xp=x[i]; |
|
531 yp=y[i]; |
|
532 A=1; B=0; C=0; D=1; |
|
533 while ((yp+C) && (yp+D)) { |
|
534 q =Math.floor((xp+A)/(yp+C)); |
|
535 qp=Math.floor((xp+B)/(yp+D)); |
|
536 if (q!=qp) |
|
537 break; |
|
538 t= A-q*C; A=C; C=t; // do (A,B,xp, C,D,yp) = (C,D,yp, A,B,xp) - q*(0,0,0, C,D,yp) |
|
539 t= B-q*D; B=D; D=t; |
|
540 t=xp-q*yp; xp=yp; yp=t; |
|
541 } |
|
542 if (B) { |
|
543 copy_(T,x); |
|
544 linComb_(x,y,A,B); //x=A*x+B*y |
|
545 linComb_(y,T,D,C); //y=D*y+C*T |
|
546 } else { |
|
547 mod_(x,y); |
|
548 copy_(T,x); |
|
549 copy_(x,y); |
|
550 copy_(y,T); |
|
551 } |
|
552 } |
|
553 if (y[0]==0) |
|
554 return; |
|
555 t=modInt(x,y[0]); |
|
556 copyInt_(x,y[0]); |
|
557 y[0]=t; |
|
558 while (y[0]) { |
|
559 x[0]%=y[0]; |
|
560 t=x[0]; x[0]=y[0]; y[0]=t; |
|
561 } |
|
562 } |
|
563 |
|
564 //do x=x**(-1) mod n, for bigInts x and n. |
|
565 //If no inverse exists, it sets x to zero and returns 0, else it returns 1. |
|
566 //The x array must be at least as large as the n array. |
|
567 function inverseMod_(x,n) { |
|
568 var k=1+2*Math.max(x.length,n.length); |
|
569 |
|
570 if(!(x[0]&1) && !(n[0]&1)) { //if both inputs are even, then inverse doesn't exist |
|
571 copyInt_(x,0); |
|
572 return 0; |
|
573 } |
|
574 |
|
575 if (eg_u.length!=k) { |
|
576 eg_u=new Array(k); |
|
577 eg_v=new Array(k); |
|
578 eg_A=new Array(k); |
|
579 eg_B=new Array(k); |
|
580 eg_C=new Array(k); |
|
581 eg_D=new Array(k); |
|
582 } |
|
583 |
|
584 copy_(eg_u,x); |
|
585 copy_(eg_v,n); |
|
586 copyInt_(eg_A,1); |
|
587 copyInt_(eg_B,0); |
|
588 copyInt_(eg_C,0); |
|
589 copyInt_(eg_D,1); |
|
590 for (;;) { |
|
591 while(!(eg_u[0]&1)) { //while eg_u is even |
|
592 halve_(eg_u); |
|
593 if (!(eg_A[0]&1) && !(eg_B[0]&1)) { //if eg_A==eg_B==0 mod 2 |
|
594 halve_(eg_A); |
|
595 halve_(eg_B); |
|
596 } else { |
|
597 add_(eg_A,n); halve_(eg_A); |
|
598 sub_(eg_B,x); halve_(eg_B); |
|
599 } |
|
600 } |
|
601 |
|
602 while (!(eg_v[0]&1)) { //while eg_v is even |
|
603 halve_(eg_v); |
|
604 if (!(eg_C[0]&1) && !(eg_D[0]&1)) { //if eg_C==eg_D==0 mod 2 |
|
605 halve_(eg_C); |
|
606 halve_(eg_D); |
|
607 } else { |
|
608 add_(eg_C,n); halve_(eg_C); |
|
609 sub_(eg_D,x); halve_(eg_D); |
|
610 } |
|
611 } |
|
612 |
|
613 if (!greater(eg_v,eg_u)) { //eg_v <= eg_u |
|
614 sub_(eg_u,eg_v); |
|
615 sub_(eg_A,eg_C); |
|
616 sub_(eg_B,eg_D); |
|
617 } else { //eg_v > eg_u |
|
618 sub_(eg_v,eg_u); |
|
619 sub_(eg_C,eg_A); |
|
620 sub_(eg_D,eg_B); |
|
621 } |
|
622 |
|
623 if (equalsInt(eg_u,0)) { |
|
624 if (negative(eg_C)) //make sure answer is nonnegative |
|
625 add_(eg_C,n); |
|
626 copy_(x,eg_C); |
|
627 |
|
628 if (!equalsInt(eg_v,1)) { //if GCD_(x,n)!=1, then there is no inverse |
|
629 copyInt_(x,0); |
|
630 return 0; |
|
631 } |
|
632 return 1; |
|
633 } |
|
634 } |
|
635 } |
|
636 |
|
637 //return x**(-1) mod n, for integers x and n. Return 0 if there is no inverse |
|
638 function inverseModInt(x,n) { |
|
639 var a=1,b=0,t; |
|
640 for (;;) { |
|
641 if (x==1) return a; |
|
642 if (x==0) return 0; |
|
643 b-=a*Math.floor(n/x); |
|
644 n%=x; |
|
645 |
|
646 if (n==1) return b; //to avoid negatives, change this b to n-b, and each -= to += |
|
647 if (n==0) return 0; |
|
648 a-=b*Math.floor(x/n); |
|
649 x%=n; |
|
650 } |
|
651 } |
|
652 |
|
653 //this deprecated function is for backward compatibility only. |
|
654 function inverseModInt_(x,n) { |
|
655 return inverseModInt(x,n); |
|
656 } |
|
657 |
|
658 |
|
659 //Given positive bigInts x and y, change the bigints v, a, and b to positive bigInts such that: |
|
660 // v = GCD_(x,y) = a*x-b*y |
|
661 //The bigInts v, a, b, must have exactly as many elements as the larger of x and y. |
|
662 function eGCD_(x,y,v,a,b) { |
|
663 var g=0; |
|
664 var k=Math.max(x.length,y.length); |
|
665 if (eg_u.length!=k) { |
|
666 eg_u=new Array(k); |
|
667 eg_A=new Array(k); |
|
668 eg_B=new Array(k); |
|
669 eg_C=new Array(k); |
|
670 eg_D=new Array(k); |
|
671 } |
|
672 while(!(x[0]&1) && !(y[0]&1)) { //while x and y both even |
|
673 halve_(x); |
|
674 halve_(y); |
|
675 g++; |
|
676 } |
|
677 copy_(eg_u,x); |
|
678 copy_(v,y); |
|
679 copyInt_(eg_A,1); |
|
680 copyInt_(eg_B,0); |
|
681 copyInt_(eg_C,0); |
|
682 copyInt_(eg_D,1); |
|
683 for (;;) { |
|
684 while(!(eg_u[0]&1)) { //while u is even |
|
685 halve_(eg_u); |
|
686 if (!(eg_A[0]&1) && !(eg_B[0]&1)) { //if A==B==0 mod 2 |
|
687 halve_(eg_A); |
|
688 halve_(eg_B); |
|
689 } else { |
|
690 add_(eg_A,y); halve_(eg_A); |
|
691 sub_(eg_B,x); halve_(eg_B); |
|
692 } |
|
693 } |
|
694 |
|
695 while (!(v[0]&1)) { //while v is even |
|
696 halve_(v); |
|
697 if (!(eg_C[0]&1) && !(eg_D[0]&1)) { //if C==D==0 mod 2 |
|
698 halve_(eg_C); |
|
699 halve_(eg_D); |
|
700 } else { |
|
701 add_(eg_C,y); halve_(eg_C); |
|
702 sub_(eg_D,x); halve_(eg_D); |
|
703 } |
|
704 } |
|
705 |
|
706 if (!greater(v,eg_u)) { //v<=u |
|
707 sub_(eg_u,v); |
|
708 sub_(eg_A,eg_C); |
|
709 sub_(eg_B,eg_D); |
|
710 } else { //v>u |
|
711 sub_(v,eg_u); |
|
712 sub_(eg_C,eg_A); |
|
713 sub_(eg_D,eg_B); |
|
714 } |
|
715 if (equalsInt(eg_u,0)) { |
|
716 if (negative(eg_C)) { //make sure a (C)is nonnegative |
|
717 add_(eg_C,y); |
|
718 sub_(eg_D,x); |
|
719 } |
|
720 multInt_(eg_D,-1); ///make sure b (D) is nonnegative |
|
721 copy_(a,eg_C); |
|
722 copy_(b,eg_D); |
|
723 leftShift_(v,g); |
|
724 return; |
|
725 } |
|
726 } |
|
727 } |
|
728 |
|
729 |
|
730 //is bigInt x negative? |
|
731 function negative(x) { |
|
732 return ((x[x.length-1]>>(bpe-1))&1); |
|
733 } |
|
734 |
|
735 |
|
736 //is (x << (shift*bpe)) > y? |
|
737 //x and y are nonnegative bigInts |
|
738 //shift is a nonnegative integer |
|
739 function greaterShift(x,y,shift) { |
|
740 var kx=x.length, ky=y.length; |
|
741 k=((kx+shift)<ky) ? (kx+shift) : ky; |
|
742 for (i=ky-1-shift; i<kx && i>=0; i++) |
|
743 if (x[i]>0) |
|
744 return 1; //if there are nonzeros in x to the left of the first column of y, then x is bigger |
|
745 for (i=kx-1+shift; i<ky; i++) |
|
746 if (y[i]>0) |
|
747 return 0; //if there are nonzeros in y to the left of the first column of x, then x is not bigger |
|
748 for (i=k-1; i>=shift; i--) |
|
749 if (x[i-shift]>y[i]) return 1; |
|
750 else if (x[i-shift]<y[i]) return 0; |
|
751 return 0; |
|
752 } |
|
753 |
|
754 //is x > y? (x and y both nonnegative) |
|
755 function greater(x,y) { |
|
756 var i; |
|
757 var k=(x.length<y.length) ? x.length : y.length; |
|
758 |
|
759 for (i=x.length;i<y.length;i++) |
|
760 if (y[i]) |
|
761 return 0; //y has more digits |
|
762 |
|
763 for (i=y.length;i<x.length;i++) |
|
764 if (x[i]) |
|
765 return 1; //x has more digits |
|
766 |
|
767 for (i=k-1;i>=0;i--) |
|
768 if (x[i]>y[i]) |
|
769 return 1; |
|
770 else if (x[i]<y[i]) |
|
771 return 0; |
|
772 return 0; |
|
773 } |
|
774 |
|
775 //divide x by y giving quotient q and remainder r. (q=floor(x/y), r=x mod y). All 4 are bigints. |
|
776 //x must have at least one leading zero element. |
|
777 //y must be nonzero. |
|
778 //q and r must be arrays that are exactly the same length as x. (Or q can have more). |
|
779 //Must have x.length >= y.length >= 2. |
|
780 function divide_(x,y,q,r) { |
|
781 var kx, ky; |
|
782 var i,j,y1,y2,c,a,b; |
|
783 copy_(r,x); |
|
784 for (ky=y.length;y[ky-1]==0;ky--); //ky is number of elements in y, not including leading zeros |
|
785 |
|
786 //normalize: ensure the most significant element of y has its highest bit set |
|
787 b=y[ky-1]; |
|
788 for (a=0; b; a++) |
|
789 b>>=1; |
|
790 a=bpe-a; //a is how many bits to shift so that the high order bit of y is leftmost in its array element |
|
791 leftShift_(y,a); //multiply both by 1<<a now, then divide both by that at the end |
|
792 leftShift_(r,a); |
|
793 |
|
794 //Rob Visser discovered a bug: the following line was originally just before the normalization. |
|
795 for (kx=r.length;r[kx-1]==0 && kx>ky;kx--); //kx is number of elements in normalized x, not including leading zeros |
|
796 |
|
797 copyInt_(q,0); // q=0 |
|
798 while (!greaterShift(y,r,kx-ky)) { // while (leftShift_(y,kx-ky) <= r) { |
|
799 subShift_(r,y,kx-ky); // r=r-leftShift_(y,kx-ky) |
|
800 q[kx-ky]++; // q[kx-ky]++; |
|
801 } // } |
|
802 |
|
803 for (i=kx-1; i>=ky; i--) { |
|
804 if (r[i]==y[ky-1]) |
|
805 q[i-ky]=mask; |
|
806 else |
|
807 q[i-ky]=Math.floor((r[i]*radix+r[i-1])/y[ky-1]); |
|
808 |
|
809 //The following for(;;) loop is equivalent to the commented while loop, |
|
810 //except that the uncommented version avoids overflow. |
|
811 //The commented loop comes from HAC, which assumes r[-1]==y[-1]==0 |
|
812 // while (q[i-ky]*(y[ky-1]*radix+y[ky-2]) > r[i]*radix*radix+r[i-1]*radix+r[i-2]) |
|
813 // q[i-ky]--; |
|
814 for (;;) { |
|
815 y2=(ky>1 ? y[ky-2] : 0)*q[i-ky]; |
|
816 c=y2>>bpe; |
|
817 y2=y2 & mask; |
|
818 y1=c+q[i-ky]*y[ky-1]; |
|
819 c=y1>>bpe; |
|
820 y1=y1 & mask; |
|
821 |
|
822 if (c==r[i] ? y1==r[i-1] ? y2>(i>1 ? r[i-2] : 0) : y1>r[i-1] : c>r[i]) |
|
823 q[i-ky]--; |
|
824 else |
|
825 break; |
|
826 } |
|
827 |
|
828 linCombShift_(r,y,-q[i-ky],i-ky); //r=r-q[i-ky]*leftShift_(y,i-ky) |
|
829 if (negative(r)) { |
|
830 addShift_(r,y,i-ky); //r=r+leftShift_(y,i-ky) |
|
831 q[i-ky]--; |
|
832 } |
|
833 } |
|
834 |
|
835 rightShift_(y,a); //undo the normalization step |
|
836 rightShift_(r,a); //undo the normalization step |
|
837 } |
|
838 |
|
839 //do carries and borrows so each element of the bigInt x fits in bpe bits. |
|
840 function carry_(x) { |
|
841 var i,k,c,b; |
|
842 k=x.length; |
|
843 c=0; |
|
844 for (i=0;i<k;i++) { |
|
845 c+=x[i]; |
|
846 b=0; |
|
847 if (c<0) { |
|
848 b=-(c>>bpe); |
|
849 c+=b*radix; |
|
850 } |
|
851 x[i]=c & mask; |
|
852 c=(c>>bpe)-b; |
|
853 } |
|
854 } |
|
855 |
|
856 //return x mod n for bigInt x and integer n. |
|
857 function modInt(x,n) { |
|
858 var i,c=0; |
|
859 for (i=x.length-1; i>=0; i--) |
|
860 c=(c*radix+x[i])%n; |
|
861 return c; |
|
862 } |
|
863 |
|
864 //convert the integer t into a bigInt with at least the given number of bits. |
|
865 //the returned array stores the bigInt in bpe-bit chunks, little endian (buff[0] is least significant word) |
|
866 //Pad the array with leading zeros so that it has at least minSize elements. |
|
867 //There will always be at least one leading 0 element. |
|
868 function int2bigInt(t,bits,minSize) { |
|
869 var i,k; |
|
870 k=Math.ceil(bits/bpe)+1; |
|
871 k=minSize>k ? minSize : k; |
|
872 buff=new Array(k); |
|
873 copyInt_(buff,t); |
|
874 return buff; |
|
875 } |
|
876 |
|
877 //return the bigInt given a string representation in a given base. |
|
878 //Pad the array with leading zeros so that it has at least minSize elements. |
|
879 //If base=-1, then it reads in a space-separated list of array elements in decimal. |
|
880 //The array will always have at least one leading zero, unless base=-1. |
|
881 function str2bigInt(s,base,minSize) { |
|
882 var d, i, j, x, y, kk; |
|
883 var k=s.length; |
|
884 if (base==-1) { //comma-separated list of array elements in decimal |
|
885 x=new Array(0); |
|
886 for (;;) { |
|
887 y=new Array(x.length+1); |
|
888 for (i=0;i<x.length;i++) |
|
889 y[i+1]=x[i]; |
|
890 y[0]=parseInt(s,10); |
|
891 x=y; |
|
892 d=s.indexOf(',',0); |
|
893 if (d<1) |
|
894 break; |
|
895 s=s.substring(d+1); |
|
896 if (s.length==0) |
|
897 break; |
|
898 } |
|
899 if (x.length<minSize) { |
|
900 y=new Array(minSize); |
|
901 copy_(y,x); |
|
902 return y; |
|
903 } |
|
904 return x; |
|
905 } |
|
906 |
|
907 x=int2bigInt(0,base*k,0); |
|
908 for (i=0;i<k;i++) { |
|
909 d=digitsStr.indexOf(s.substring(i,i+1),0); |
|
910 if (base<=36 && d>=36) //convert lowercase to uppercase if base<=36 |
|
911 d-=26; |
|
912 if (d<base && d>=0) { //ignore illegal characters |
|
913 multInt_(x,base); |
|
914 addInt_(x,d); |
|
915 } |
|
916 } |
|
917 |
|
918 for (k=x.length;k>0 && !x[k-1];k--); //strip off leading zeros |
|
919 k=minSize>k+1 ? minSize : k+1; |
|
920 y=new Array(k); |
|
921 kk=k<x.length ? k : x.length; |
|
922 for (i=0;i<kk;i++) |
|
923 y[i]=x[i]; |
|
924 for (;i<k;i++) |
|
925 y[i]=0; |
|
926 return y; |
|
927 } |
|
928 |
|
929 //is bigint x equal to integer y? |
|
930 //y must have less than bpe bits |
|
931 function equalsInt(x,y) { |
|
932 var i; |
|
933 if (x[0]!=y) |
|
934 return 0; |
|
935 for (i=1;i<x.length;i++) |
|
936 if (x[i]) |
|
937 return 0; |
|
938 return 1; |
|
939 } |
|
940 |
|
941 //are bigints x and y equal? |
|
942 //this works even if x and y are different lengths and have arbitrarily many leading zeros |
|
943 function equals(x,y) { |
|
944 var i; |
|
945 var k=x.length<y.length ? x.length : y.length; |
|
946 for (i=0;i<k;i++) |
|
947 if (x[i]!=y[i]) |
|
948 return 0; |
|
949 if (x.length>y.length) { |
|
950 for (;i<x.length;i++) |
|
951 if (x[i]) |
|
952 return 0; |
|
953 } else { |
|
954 for (;i<y.length;i++) |
|
955 if (y[i]) |
|
956 return 0; |
|
957 } |
|
958 return 1; |
|
959 } |
|
960 |
|
961 //is the bigInt x equal to zero? |
|
962 function isZero(x) { |
|
963 var i; |
|
964 for (i=0;i<x.length;i++) |
|
965 if (x[i]) |
|
966 return 0; |
|
967 return 1; |
|
968 } |
|
969 |
|
970 //convert a bigInt into a string in a given base, from base 2 up to base 95. |
|
971 //Base -1 prints the contents of the array representing the number. |
|
972 function bigInt2str(x,base) { |
|
973 var i,t,s=""; |
|
974 |
|
975 if (s6.length!=x.length) |
|
976 s6=dup(x); |
|
977 else |
|
978 copy_(s6,x); |
|
979 |
|
980 if (base==-1) { //return the list of array contents |
|
981 for (i=x.length-1;i>0;i--) |
|
982 s+=x[i]+','; |
|
983 s+=x[0]; |
|
984 } |
|
985 else { //return it in the given base |
|
986 while (!isZero(s6)) { |
|
987 t=divInt_(s6,base); //t=s6 % base; s6=floor(s6/base); |
|
988 s=digitsStr.substring(t,t+1)+s; |
|
989 } |
|
990 } |
|
991 if (s.length==0) |
|
992 s="0"; |
|
993 return s; |
|
994 } |
|
995 |
|
996 //returns a duplicate of bigInt x |
|
997 function dup(x) { |
|
998 var i; |
|
999 buff=new Array(x.length); |
|
1000 copy_(buff,x); |
|
1001 return buff; |
|
1002 } |
|
1003 |
|
1004 //do x=y on bigInts x and y. x must be an array at least as big as y (not counting the leading zeros in y). |
|
1005 function copy_(x,y) { |
|
1006 var i; |
|
1007 var k=x.length<y.length ? x.length : y.length; |
|
1008 for (i=0;i<k;i++) |
|
1009 x[i]=y[i]; |
|
1010 for (i=k;i<x.length;i++) |
|
1011 x[i]=0; |
|
1012 } |
|
1013 |
|
1014 //do x=y on bigInt x and integer y. |
|
1015 function copyInt_(x,n) { |
|
1016 var i,c; |
|
1017 for (c=n,i=0;i<x.length;i++) { |
|
1018 x[i]=c & mask; |
|
1019 c>>=bpe; |
|
1020 } |
|
1021 } |
|
1022 |
|
1023 //do x=x+n where x is a bigInt and n is an integer. |
|
1024 //x must be large enough to hold the result. |
|
1025 function addInt_(x,n) { |
|
1026 var i,k,c,b; |
|
1027 x[0]+=n; |
|
1028 k=x.length; |
|
1029 c=0; |
|
1030 for (i=0;i<k;i++) { |
|
1031 c+=x[i]; |
|
1032 b=0; |
|
1033 if (c<0) { |
|
1034 b=-(c>>bpe); |
|
1035 c+=b*radix; |
|
1036 } |
|
1037 x[i]=c & mask; |
|
1038 c=(c>>bpe)-b; |
|
1039 if (!c) return; //stop carrying as soon as the carry_ is zero |
|
1040 } |
|
1041 } |
|
1042 |
|
1043 //right shift bigInt x by n bits. 0 <= n < bpe. |
|
1044 function rightShift_(x,n) { |
|
1045 var i; |
|
1046 var k=Math.floor(n/bpe); |
|
1047 if (k) { |
|
1048 for (i=0;i<x.length-k;i++) //right shift x by k elements |
|
1049 x[i]=x[i+k]; |
|
1050 for (;i<x.length;i++) |
|
1051 x[i]=0; |
|
1052 n%=bpe; |
|
1053 } |
|
1054 for (i=0;i<x.length-1;i++) { |
|
1055 x[i]=mask & ((x[i+1]<<(bpe-n)) | (x[i]>>n)); |
|
1056 } |
|
1057 x[i]>>=n; |
|
1058 } |
|
1059 |
|
1060 //do x=floor(|x|/2)*sgn(x) for bigInt x in 2's complement |
|
1061 function halve_(x) { |
|
1062 var i; |
|
1063 for (i=0;i<x.length-1;i++) { |
|
1064 x[i]=mask & ((x[i+1]<<(bpe-1)) | (x[i]>>1)); |
|
1065 } |
|
1066 x[i]=(x[i]>>1) | (x[i] & (radix>>1)); //most significant bit stays the same |
|
1067 } |
|
1068 |
|
1069 //left shift bigInt x by n bits. |
|
1070 function leftShift_(x,n) { |
|
1071 var i; |
|
1072 var k=Math.floor(n/bpe); |
|
1073 if (k) { |
|
1074 for (i=x.length; i>=k; i--) //left shift x by k elements |
|
1075 x[i]=x[i-k]; |
|
1076 for (;i>=0;i--) |
|
1077 x[i]=0; |
|
1078 n%=bpe; |
|
1079 } |
|
1080 if (!n) |
|
1081 return; |
|
1082 for (i=x.length-1;i>0;i--) { |
|
1083 x[i]=mask & ((x[i]<<n) | (x[i-1]>>(bpe-n))); |
|
1084 } |
|
1085 x[i]=mask & (x[i]<<n); |
|
1086 } |
|
1087 |
|
1088 //do x=x*n where x is a bigInt and n is an integer. |
|
1089 //x must be large enough to hold the result. |
|
1090 function multInt_(x,n) { |
|
1091 var i,k,c,b; |
|
1092 if (!n) |
|
1093 return; |
|
1094 k=x.length; |
|
1095 c=0; |
|
1096 for (i=0;i<k;i++) { |
|
1097 c+=x[i]*n; |
|
1098 b=0; |
|
1099 if (c<0) { |
|
1100 b=-(c>>bpe); |
|
1101 c+=b*radix; |
|
1102 } |
|
1103 x[i]=c & mask; |
|
1104 c=(c>>bpe)-b; |
|
1105 } |
|
1106 } |
|
1107 |
|
1108 //do x=floor(x/n) for bigInt x and integer n, and return the remainder |
|
1109 function divInt_(x,n) { |
|
1110 var i,r=0,s; |
|
1111 for (i=x.length-1;i>=0;i--) { |
|
1112 s=r*radix+x[i]; |
|
1113 x[i]=Math.floor(s/n); |
|
1114 r=s%n; |
|
1115 } |
|
1116 return r; |
|
1117 } |
|
1118 |
|
1119 //do the linear combination x=a*x+b*y for bigInts x and y, and integers a and b. |
|
1120 //x must be large enough to hold the answer. |
|
1121 function linComb_(x,y,a,b) { |
|
1122 var i,c,k,kk; |
|
1123 k=x.length<y.length ? x.length : y.length; |
|
1124 kk=x.length; |
|
1125 for (c=0,i=0;i<k;i++) { |
|
1126 c+=a*x[i]+b*y[i]; |
|
1127 x[i]=c & mask; |
|
1128 c>>=bpe; |
|
1129 } |
|
1130 for (i=k;i<kk;i++) { |
|
1131 c+=a*x[i]; |
|
1132 x[i]=c & mask; |
|
1133 c>>=bpe; |
|
1134 } |
|
1135 } |
|
1136 |
|
1137 //do the linear combination x=a*x+b*(y<<(ys*bpe)) for bigInts x and y, and integers a, b and ys. |
|
1138 //x must be large enough to hold the answer. |
|
1139 function linCombShift_(x,y,b,ys) { |
|
1140 var i,c,k,kk; |
|
1141 k=x.length<ys+y.length ? x.length : ys+y.length; |
|
1142 kk=x.length; |
|
1143 for (c=0,i=ys;i<k;i++) { |
|
1144 c+=x[i]+b*y[i-ys]; |
|
1145 x[i]=c & mask; |
|
1146 c>>=bpe; |
|
1147 } |
|
1148 for (i=k;c && i<kk;i++) { |
|
1149 c+=x[i]; |
|
1150 x[i]=c & mask; |
|
1151 c>>=bpe; |
|
1152 } |
|
1153 } |
|
1154 |
|
1155 //do x=x+(y<<(ys*bpe)) for bigInts x and y, and integers a,b and ys. |
|
1156 //x must be large enough to hold the answer. |
|
1157 function addShift_(x,y,ys) { |
|
1158 var i,c,k,kk; |
|
1159 k=x.length<ys+y.length ? x.length : ys+y.length; |
|
1160 kk=x.length; |
|
1161 for (c=0,i=ys;i<k;i++) { |
|
1162 c+=x[i]+y[i-ys]; |
|
1163 x[i]=c & mask; |
|
1164 c>>=bpe; |
|
1165 } |
|
1166 for (i=k;c && i<kk;i++) { |
|
1167 c+=x[i]; |
|
1168 x[i]=c & mask; |
|
1169 c>>=bpe; |
|
1170 } |
|
1171 } |
|
1172 |
|
1173 //do x=x-(y<<(ys*bpe)) for bigInts x and y, and integers a,b and ys. |
|
1174 //x must be large enough to hold the answer. |
|
1175 function subShift_(x,y,ys) { |
|
1176 var i,c,k,kk; |
|
1177 k=x.length<ys+y.length ? x.length : ys+y.length; |
|
1178 kk=x.length; |
|
1179 for (c=0,i=ys;i<k;i++) { |
|
1180 c+=x[i]-y[i-ys]; |
|
1181 x[i]=c & mask; |
|
1182 c>>=bpe; |
|
1183 } |
|
1184 for (i=k;c && i<kk;i++) { |
|
1185 c+=x[i]; |
|
1186 x[i]=c & mask; |
|
1187 c>>=bpe; |
|
1188 } |
|
1189 } |
|
1190 |
|
1191 //do x=x-y for bigInts x and y. |
|
1192 //x must be large enough to hold the answer. |
|
1193 //negative answers will be 2s complement |
|
1194 function sub_(x,y) { |
|
1195 var i,c,k,kk; |
|
1196 k=x.length<y.length ? x.length : y.length; |
|
1197 for (c=0,i=0;i<k;i++) { |
|
1198 c+=x[i]-y[i]; |
|
1199 x[i]=c & mask; |
|
1200 c>>=bpe; |
|
1201 } |
|
1202 for (i=k;c && i<x.length;i++) { |
|
1203 c+=x[i]; |
|
1204 x[i]=c & mask; |
|
1205 c>>=bpe; |
|
1206 } |
|
1207 } |
|
1208 |
|
1209 //do x=x+y for bigInts x and y. |
|
1210 //x must be large enough to hold the answer. |
|
1211 function add_(x,y) { |
|
1212 var i,c,k,kk; |
|
1213 k=x.length<y.length ? x.length : y.length; |
|
1214 for (c=0,i=0;i<k;i++) { |
|
1215 c+=x[i]+y[i]; |
|
1216 x[i]=c & mask; |
|
1217 c>>=bpe; |
|
1218 } |
|
1219 for (i=k;c && i<x.length;i++) { |
|
1220 c+=x[i]; |
|
1221 x[i]=c & mask; |
|
1222 c>>=bpe; |
|
1223 } |
|
1224 } |
|
1225 |
|
1226 //do x=x*y for bigInts x and y. This is faster when y<x. |
|
1227 function mult_(x,y) { |
|
1228 var i; |
|
1229 if (ss.length!=2*x.length) |
|
1230 ss=new Array(2*x.length); |
|
1231 copyInt_(ss,0); |
|
1232 for (i=0;i<y.length;i++) |
|
1233 if (y[i]) |
|
1234 linCombShift_(ss,x,y[i],i); //ss=1*ss+y[i]*(x<<(i*bpe)) |
|
1235 copy_(x,ss); |
|
1236 } |
|
1237 |
|
1238 //do x=x mod n for bigInts x and n. |
|
1239 function mod_(x,n) { |
|
1240 if (s4.length!=x.length) |
|
1241 s4=dup(x); |
|
1242 else |
|
1243 copy_(s4,x); |
|
1244 if (s5.length!=x.length) |
|
1245 s5=dup(x); |
|
1246 divide_(s4,n,s5,x); //x = remainder of s4 / n |
|
1247 } |
|
1248 |
|
1249 //do x=x*y mod n for bigInts x,y,n. |
|
1250 //for greater speed, let y<x. |
|
1251 function multMod_(x,y,n) { |
|
1252 var i; |
|
1253 if (s0.length!=2*x.length) |
|
1254 s0=new Array(2*x.length); |
|
1255 copyInt_(s0,0); |
|
1256 for (i=0;i<y.length;i++) |
|
1257 if (y[i]) |
|
1258 linCombShift_(s0,x,y[i],i); //s0=1*s0+y[i]*(x<<(i*bpe)) |
|
1259 mod_(s0,n); |
|
1260 copy_(x,s0); |
|
1261 } |
|
1262 |
|
1263 //do x=x*x mod n for bigInts x,n. |
|
1264 function squareMod_(x,n) { |
|
1265 var i,j,d,c,kx,kn,k; |
|
1266 for (kx=x.length; kx>0 && !x[kx-1]; kx--); //ignore leading zeros in x |
|
1267 k=kx>n.length ? 2*kx : 2*n.length; //k=# elements in the product, which is twice the elements in the larger of x and n |
|
1268 if (s0.length!=k) |
|
1269 s0=new Array(k); |
|
1270 copyInt_(s0,0); |
|
1271 for (i=0;i<kx;i++) { |
|
1272 c=s0[2*i]+x[i]*x[i]; |
|
1273 s0[2*i]=c & mask; |
|
1274 c>>=bpe; |
|
1275 for (j=i+1;j<kx;j++) { |
|
1276 c=s0[i+j]+2*x[i]*x[j]+c; |
|
1277 s0[i+j]=(c & mask); |
|
1278 c>>=bpe; |
|
1279 } |
|
1280 s0[i+kx]=c; |
|
1281 } |
|
1282 mod_(s0,n); |
|
1283 copy_(x,s0); |
|
1284 } |
|
1285 |
|
1286 //return x with exactly k leading zero elements |
|
1287 function bigint_trim(x,k) { |
|
1288 var i,y; |
|
1289 for (i=x.length; i>0 && !x[i-1]; i--); |
|
1290 y=new Array(i+k); |
|
1291 copy_(y,x); |
|
1292 return y; |
|
1293 } |
|
1294 |
|
1295 //do x=x**y mod n, where x,y,n are bigInts and ** is exponentiation. 0**0=1. |
|
1296 //this is faster when n is odd. x usually needs to have as many elements as n. |
|
1297 function powMod_(x,y,n) { |
|
1298 var k1,k2,kn,np; |
|
1299 if(s7.length!=n.length) |
|
1300 s7=dup(n); |
|
1301 |
|
1302 //for even modulus, use a simple square-and-multiply algorithm, |
|
1303 //rather than using the more complex Montgomery algorithm. |
|
1304 if ((n[0]&1)==0) { |
|
1305 copy_(s7,x); |
|
1306 copyInt_(x,1); |
|
1307 while(!equalsInt(y,0)) { |
|
1308 if (y[0]&1) |
|
1309 multMod_(x,s7,n); |
|
1310 divInt_(y,2); |
|
1311 squareMod_(s7,n); |
|
1312 } |
|
1313 return; |
|
1314 } |
|
1315 |
|
1316 //calculate np from n for the Montgomery multiplications |
|
1317 copyInt_(s7,0); |
|
1318 for (kn=n.length;kn>0 && !n[kn-1];kn--); |
|
1319 np=radix-inverseModInt(modInt(n,radix),radix); |
|
1320 s7[kn]=1; |
|
1321 multMod_(x ,s7,n); // x = x * 2**(kn*bp) mod n |
|
1322 |
|
1323 if (s3.length!=x.length) |
|
1324 s3=dup(x); |
|
1325 else |
|
1326 copy_(s3,x); |
|
1327 |
|
1328 for (k1=y.length-1;k1>0 & !y[k1]; k1--); //k1=first nonzero element of y |
|
1329 if (y[k1]==0) { //anything to the 0th power is 1 |
|
1330 copyInt_(x,1); |
|
1331 return; |
|
1332 } |
|
1333 for (k2=1<<(bpe-1);k2 && !(y[k1] & k2); k2>>=1); //k2=position of first 1 bit in y[k1] |
|
1334 for (;;) { |
|
1335 if (!(k2>>=1)) { //look at next bit of y |
|
1336 k1--; |
|
1337 if (k1<0) { |
|
1338 mont_(x,one,n,np); |
|
1339 return; |
|
1340 } |
|
1341 k2=1<<(bpe-1); |
|
1342 } |
|
1343 mont_(x,x,n,np); |
|
1344 |
|
1345 if (k2 & y[k1]) //if next bit is a 1 |
|
1346 mont_(x,s3,n,np); |
|
1347 } |
|
1348 } |
|
1349 |
|
1350 //do x=x*y*Ri mod n for bigInts x,y,n, |
|
1351 // where Ri = 2**(-kn*bpe) mod n, and kn is the |
|
1352 // number of elements in the n array, not |
|
1353 // counting leading zeros. |
|
1354 //x must be large enough to hold the answer. |
|
1355 //It's OK if x and y are the same variable. |
|
1356 //must have: |
|
1357 // x,y < n |
|
1358 // n is odd |
|
1359 // np = -(n^(-1)) mod radix |
|
1360 function mont_(x,y,n,np) { |
|
1361 var i,j,c,ui,t; |
|
1362 var kn=n.length; |
|
1363 var ky=y.length; |
|
1364 |
|
1365 if (sa.length!=kn) |
|
1366 sa=new Array(kn); |
|
1367 |
|
1368 for (;kn>0 && n[kn-1]==0;kn--); //ignore leading zeros of n |
|
1369 //this function sometimes gives wrong answers when the next line is uncommented |
|
1370 //for (;ky>0 && y[ky-1]==0;ky--); //ignore leading zeros of y |
|
1371 |
|
1372 copyInt_(sa,0); |
|
1373 |
|
1374 //the following loop consumes 95% of the runtime for randTruePrime_() and powMod_() for large keys |
|
1375 for (i=0; i<kn; i++) { |
|
1376 t=sa[0]+x[i]*y[0]; |
|
1377 ui=((t & mask) * np) & mask; //the inner "& mask" is needed on Macintosh MSIE, but not windows MSIE |
|
1378 c=(t+ui*n[0]) >> bpe; |
|
1379 t=x[i]; |
|
1380 |
|
1381 //do sa=(sa+x[i]*y+ui*n)/b where b=2**bpe |
|
1382 for (j=1;j<ky;j++) { |
|
1383 c+=sa[j]+t*y[j]+ui*n[j]; |
|
1384 sa[j-1]=c & mask; |
|
1385 c>>=bpe; |
|
1386 } |
|
1387 for (;j<kn;j++) { |
|
1388 c+=sa[j]+ui*n[j]; |
|
1389 sa[j-1]=c & mask; |
|
1390 c>>=bpe; |
|
1391 } |
|
1392 sa[j-1]=c & mask; |
|
1393 } |
|
1394 |
|
1395 if (!greater(n,sa)) |
|
1396 sub_(sa,n); |
|
1397 copy_(x,sa); |
|
1398 } |
|
1399 |
|
1400 |
|
1401 /* rijndael.js Rijndael Reference Implementation |
|
1402 Copyright (c) 2001 Fritz Schneider |
|
1403 |
|
1404 This software is provided as-is, without express or implied warranty. |
|
1405 Permission to use, copy, modify, distribute or sell this software, with or |
|
1406 without fee, for any purpose and by any individual or organization, is hereby |
|
1407 granted, provided that the above copyright notice and this paragraph appear |
|
1408 in all copies. Distribution as a part of an application or binary must |
|
1409 include the above copyright notice in the documentation and/or other materials |
|
1410 provided with the application or distribution. |
|
1411 |
|
1412 |
|
1413 As the above disclaimer notes, you are free to use this code however you |
|
1414 want. However, I would request that you send me an email |
|
1415 (fritz /at/ cs /dot/ ucsd /dot/ edu) to say hi if you find this code useful |
|
1416 or instructional. Seeing that people are using the code acts as |
|
1417 encouragement for me to continue development. If you *really* want to thank |
|
1418 me you can buy the book I wrote with Thomas Powell, _JavaScript: |
|
1419 _The_Complete_Reference_ :) |
|
1420 |
|
1421 This code is an UNOPTIMIZED REFERENCE implementation of Rijndael. |
|
1422 If there is sufficient interest I can write an optimized (word-based, |
|
1423 table-driven) version, although you might want to consider using a |
|
1424 compiled language if speed is critical to your application. As it stands, |
|
1425 one run of the monte carlo test (10,000 encryptions) can take up to |
|
1426 several minutes, depending upon your processor. You shouldn't expect more |
|
1427 than a few kilobytes per second in throughput. |
|
1428 |
|
1429 Also note that there is very little error checking in these functions. |
|
1430 Doing proper error checking is always a good idea, but the ideal |
|
1431 implementation (using the instanceof operator and exceptions) requires |
|
1432 IE5+/NS6+, and I've chosen to implement this code so that it is compatible |
|
1433 with IE4/NS4. |
|
1434 |
|
1435 And finally, because JavaScript doesn't have an explicit byte/char data |
|
1436 type (although JavaScript 2.0 most likely will), when I refer to "byte" |
|
1437 in this code I generally mean "32 bit integer with value in the interval |
|
1438 [0,255]" which I treat as a byte. |
|
1439 |
|
1440 See http://www-cse.ucsd.edu/~fritz/rijndael.html for more documentation |
|
1441 of the (very simple) API provided by this code. |
|
1442 |
|
1443 Fritz Schneider |
|
1444 fritz at cs.ucsd.edu |
|
1445 |
|
1446 */ |
|
1447 |
|
1448 // Rijndael parameters -- Valid values are 128, 192, or 256 |
|
1449 |
|
1450 var keySizeInBits = ( typeof AES_BITS == 'number' ) ? AES_BITS : 128; |
|
1451 var blockSizeInBits = ( typeof AES_BLOCKSIZE == 'number' ) ? AES_BLOCKSIZE : 128; |
|
1452 |
|
1453 /////// You shouldn't have to modify anything below this line except for |
|
1454 /////// the function getRandomBytes(). |
|
1455 // |
|
1456 // Note: in the following code the two dimensional arrays are indexed as |
|
1457 // you would probably expect, as array[row][column]. The state arrays |
|
1458 // are 2d arrays of the form state[4][Nb]. |
|
1459 |
|
1460 |
|
1461 // The number of rounds for the cipher, indexed by [Nk][Nb] |
|
1462 var roundsArray = [ ,,,,[,,,,10,, 12,, 14],, |
|
1463 [,,,,12,, 12,, 14],, |
|
1464 [,,,,14,, 14,, 14] ]; |
|
1465 |
|
1466 // The number of bytes to shift by in shiftRow, indexed by [Nb][row] |
|
1467 var shiftOffsets = [ ,,,,[,1, 2, 3],,[,1, 2, 3],,[,1, 3, 4] ]; |
|
1468 |
|
1469 // The round constants used in subkey expansion |
|
1470 var Rcon = [ |
|
1471 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, |
|
1472 0x40, 0x80, 0x1b, 0x36, 0x6c, 0xd8, |
|
1473 0xab, 0x4d, 0x9a, 0x2f, 0x5e, 0xbc, |
|
1474 0x63, 0xc6, 0x97, 0x35, 0x6a, 0xd4, |
|
1475 0xb3, 0x7d, 0xfa, 0xef, 0xc5, 0x91 ]; |
|
1476 |
|
1477 // Precomputed lookup table for the SBox |
|
1478 var SBox = [ |
|
1479 99, 124, 119, 123, 242, 107, 111, 197, 48, 1, 103, 43, 254, 215, 171, |
|
1480 118, 202, 130, 201, 125, 250, 89, 71, 240, 173, 212, 162, 175, 156, 164, |
|
1481 114, 192, 183, 253, 147, 38, 54, 63, 247, 204, 52, 165, 229, 241, 113, |
|
1482 216, 49, 21, 4, 199, 35, 195, 24, 150, 5, 154, 7, 18, 128, 226, |
|
1483 235, 39, 178, 117, 9, 131, 44, 26, 27, 110, 90, 160, 82, 59, 214, |
|
1484 179, 41, 227, 47, 132, 83, 209, 0, 237, 32, 252, 177, 91, 106, 203, |
|
1485 190, 57, 74, 76, 88, 207, 208, 239, 170, 251, 67, 77, 51, 133, 69, |
|
1486 249, 2, 127, 80, 60, 159, 168, 81, 163, 64, 143, 146, 157, 56, 245, |
|
1487 188, 182, 218, 33, 16, 255, 243, 210, 205, 12, 19, 236, 95, 151, 68, |
|
1488 23, 196, 167, 126, 61, 100, 93, 25, 115, 96, 129, 79, 220, 34, 42, |
|
1489 144, 136, 70, 238, 184, 20, 222, 94, 11, 219, 224, 50, 58, 10, 73, |
|
1490 6, 36, 92, 194, 211, 172, 98, 145, 149, 228, 121, 231, 200, 55, 109, |
|
1491 141, 213, 78, 169, 108, 86, 244, 234, 101, 122, 174, 8, 186, 120, 37, |
|
1492 46, 28, 166, 180, 198, 232, 221, 116, 31, 75, 189, 139, 138, 112, 62, |
|
1493 181, 102, 72, 3, 246, 14, 97, 53, 87, 185, 134, 193, 29, 158, 225, |
|
1494 248, 152, 17, 105, 217, 142, 148, 155, 30, 135, 233, 206, 85, 40, 223, |
|
1495 140, 161, 137, 13, 191, 230, 66, 104, 65, 153, 45, 15, 176, 84, 187, |
|
1496 22 ]; |
|
1497 |
|
1498 // Precomputed lookup table for the inverse SBox |
|
1499 var SBoxInverse = [ |
|
1500 82, 9, 106, 213, 48, 54, 165, 56, 191, 64, 163, 158, 129, 243, 215, |
|
1501 251, 124, 227, 57, 130, 155, 47, 255, 135, 52, 142, 67, 68, 196, 222, |
|
1502 233, 203, 84, 123, 148, 50, 166, 194, 35, 61, 238, 76, 149, 11, 66, |
|
1503 250, 195, 78, 8, 46, 161, 102, 40, 217, 36, 178, 118, 91, 162, 73, |
|
1504 109, 139, 209, 37, 114, 248, 246, 100, 134, 104, 152, 22, 212, 164, 92, |
|
1505 204, 93, 101, 182, 146, 108, 112, 72, 80, 253, 237, 185, 218, 94, 21, |
|
1506 70, 87, 167, 141, 157, 132, 144, 216, 171, 0, 140, 188, 211, 10, 247, |
|
1507 228, 88, 5, 184, 179, 69, 6, 208, 44, 30, 143, 202, 63, 15, 2, |
|
1508 193, 175, 189, 3, 1, 19, 138, 107, 58, 145, 17, 65, 79, 103, 220, |
|
1509 234, 151, 242, 207, 206, 240, 180, 230, 115, 150, 172, 116, 34, 231, 173, |
|
1510 53, 133, 226, 249, 55, 232, 28, 117, 223, 110, 71, 241, 26, 113, 29, |
|
1511 41, 197, 137, 111, 183, 98, 14, 170, 24, 190, 27, 252, 86, 62, 75, |
|
1512 198, 210, 121, 32, 154, 219, 192, 254, 120, 205, 90, 244, 31, 221, 168, |
|
1513 51, 136, 7, 199, 49, 177, 18, 16, 89, 39, 128, 236, 95, 96, 81, |
|
1514 127, 169, 25, 181, 74, 13, 45, 229, 122, 159, 147, 201, 156, 239, 160, |
|
1515 224, 59, 77, 174, 42, 245, 176, 200, 235, 187, 60, 131, 83, 153, 97, |
|
1516 23, 43, 4, 126, 186, 119, 214, 38, 225, 105, 20, 99, 85, 33, 12, |
|
1517 125 ]; |
|
1518 |
|
1519 function str_split(string, chunklen) |
|
1520 { |
|
1521 if(!chunklen) chunklen = 1; |
|
1522 ret = new Array(); |
|
1523 for ( i = 0; i < string.length; i+=chunklen ) |
|
1524 { |
|
1525 ret[ret.length] = string.slice(i, i+chunklen); |
|
1526 } |
|
1527 return ret; |
|
1528 } |
|
1529 |
|
1530 // This method circularly shifts the array left by the number of elements |
|
1531 // given in its parameter. It returns the resulting array and is used for |
|
1532 // the ShiftRow step. Note that shift() and push() could be used for a more |
|
1533 // elegant solution, but they require IE5.5+, so I chose to do it manually. |
|
1534 |
|
1535 function cyclicShiftLeft(theArray, positions) { |
|
1536 var temp = theArray.slice(0, positions); |
|
1537 theArray = theArray.slice(positions).concat(temp); |
|
1538 return theArray; |
|
1539 } |
|
1540 |
|
1541 // Cipher parameters ... do not change these |
|
1542 var Nk = keySizeInBits / 32; |
|
1543 var Nb = blockSizeInBits / 32; |
|
1544 var Nr = roundsArray[Nk][Nb]; |
|
1545 |
|
1546 // Multiplies the element "poly" of GF(2^8) by x. See the Rijndael spec. |
|
1547 |
|
1548 function xtime(poly) { |
|
1549 poly <<= 1; |
|
1550 return ((poly & 0x100) ? (poly ^ 0x11B) : (poly)); |
|
1551 } |
|
1552 |
|
1553 // Multiplies the two elements of GF(2^8) together and returns the result. |
|
1554 // See the Rijndael spec, but should be straightforward: for each power of |
|
1555 // the indeterminant that has a 1 coefficient in x, add y times that power |
|
1556 // to the result. x and y should be bytes representing elements of GF(2^8) |
|
1557 |
|
1558 function mult_GF256(x, y) { |
|
1559 var bit, result = 0; |
|
1560 |
|
1561 for (bit = 1; bit < 256; bit *= 2, y = xtime(y)) { |
|
1562 if (x & bit) |
|
1563 result ^= y; |
|
1564 } |
|
1565 return result; |
|
1566 } |
|
1567 |
|
1568 // Performs the substitution step of the cipher. State is the 2d array of |
|
1569 // state information (see spec) and direction is string indicating whether |
|
1570 // we are performing the forward substitution ("encrypt") or inverse |
|
1571 // substitution (anything else) |
|
1572 |
|
1573 function byteSub(state, direction) { |
|
1574 var S; |
|
1575 if (direction == "encrypt") // Point S to the SBox we're using |
|
1576 S = SBox; |
|
1577 else |
|
1578 S = SBoxInverse; |
|
1579 for (var i = 0; i < 4; i++) // Substitute for every byte in state |
|
1580 for (var j = 0; j < Nb; j++) |
|
1581 state[i][j] = S[state[i][j]]; |
|
1582 } |
|
1583 |
|
1584 // Performs the row shifting step of the cipher. |
|
1585 |
|
1586 function shiftRow(state, direction) { |
|
1587 for (var i=1; i<4; i++) // Row 0 never shifts |
|
1588 if (direction == "encrypt") |
|
1589 state[i] = cyclicShiftLeft(state[i], shiftOffsets[Nb][i]); |
|
1590 else |
|
1591 state[i] = cyclicShiftLeft(state[i], Nb - shiftOffsets[Nb][i]); |
|
1592 |
|
1593 } |
|
1594 |
|
1595 // Performs the column mixing step of the cipher. Most of these steps can |
|
1596 // be combined into table lookups on 32bit values (at least for encryption) |
|
1597 // to greatly increase the speed. |
|
1598 |
|
1599 function mixColumn(state, direction) { |
|
1600 var b = []; // Result of matrix multiplications |
|
1601 for (var j = 0; j < Nb; j++) { // Go through each column... |
|
1602 for (var i = 0; i < 4; i++) { // and for each row in the column... |
|
1603 if (direction == "encrypt") |
|
1604 b[i] = mult_GF256(state[i][j], 2) ^ // perform mixing |
|
1605 mult_GF256(state[(i+1)%4][j], 3) ^ |
|
1606 state[(i+2)%4][j] ^ |
|
1607 state[(i+3)%4][j]; |
|
1608 else |
|
1609 b[i] = mult_GF256(state[i][j], 0xE) ^ |
|
1610 mult_GF256(state[(i+1)%4][j], 0xB) ^ |
|
1611 mult_GF256(state[(i+2)%4][j], 0xD) ^ |
|
1612 mult_GF256(state[(i+3)%4][j], 9); |
|
1613 } |
|
1614 for (var i = 0; i < 4; i++) // Place result back into column |
|
1615 state[i][j] = b[i]; |
|
1616 } |
|
1617 } |
|
1618 |
|
1619 // Adds the current round key to the state information. Straightforward. |
|
1620 |
|
1621 function addRoundKey(state, roundKey) { |
|
1622 for (var j = 0; j < Nb; j++) { // Step through columns... |
|
1623 state[0][j] ^= (roundKey[j] & 0xFF); // and XOR |
|
1624 state[1][j] ^= ((roundKey[j]>>8) & 0xFF); |
|
1625 state[2][j] ^= ((roundKey[j]>>16) & 0xFF); |
|
1626 state[3][j] ^= ((roundKey[j]>>24) & 0xFF); |
|
1627 } |
|
1628 } |
|
1629 |
|
1630 // This function creates the expanded key from the input (128/192/256-bit) |
|
1631 // key. The parameter key is an array of bytes holding the value of the key. |
|
1632 // The returned value is an array whose elements are the 32-bit words that |
|
1633 // make up the expanded key. |
|
1634 |
|
1635 function keyExpansion(key) { |
|
1636 var expandedKey = new Array(); |
|
1637 var temp; |
|
1638 |
|
1639 // in case the key size or parameters were changed... |
|
1640 Nk = keySizeInBits / 32; |
|
1641 Nb = blockSizeInBits / 32; |
|
1642 Nr = roundsArray[Nk][Nb]; |
|
1643 |
|
1644 for (var j=0; j < Nk; j++) // Fill in input key first |
|
1645 expandedKey[j] = |
|
1646 (key[4*j]) | (key[4*j+1]<<8) | (key[4*j+2]<<16) | (key[4*j+3]<<24); |
|
1647 |
|
1648 // Now walk down the rest of the array filling in expanded key bytes as |
|
1649 // per Rijndael's spec |
|
1650 for (j = Nk; j < Nb * (Nr + 1); j++) { // For each word of expanded key |
|
1651 temp = expandedKey[j - 1]; |
|
1652 if (j % Nk == 0) |
|
1653 temp = ( (SBox[(temp>>8) & 0xFF]) | |
|
1654 (SBox[(temp>>16) & 0xFF]<<8) | |
|
1655 (SBox[(temp>>24) & 0xFF]<<16) | |
|
1656 (SBox[temp & 0xFF]<<24) ) ^ Rcon[Math.floor(j / Nk) - 1]; |
|
1657 else if (Nk > 6 && j % Nk == 4) |
|
1658 temp = (SBox[(temp>>24) & 0xFF]<<24) | |
|
1659 (SBox[(temp>>16) & 0xFF]<<16) | |
|
1660 (SBox[(temp>>8) & 0xFF]<<8) | |
|
1661 (SBox[temp & 0xFF]); |
|
1662 expandedKey[j] = expandedKey[j-Nk] ^ temp; |
|
1663 } |
|
1664 return expandedKey; |
|
1665 } |
|
1666 |
|
1667 // Rijndael's round functions... |
|
1668 |
|
1669 function Round(state, roundKey) { |
|
1670 byteSub(state, "encrypt"); |
|
1671 shiftRow(state, "encrypt"); |
|
1672 mixColumn(state, "encrypt"); |
|
1673 addRoundKey(state, roundKey); |
|
1674 } |
|
1675 |
|
1676 function InverseRound(state, roundKey) { |
|
1677 addRoundKey(state, roundKey); |
|
1678 mixColumn(state, "decrypt"); |
|
1679 shiftRow(state, "decrypt"); |
|
1680 byteSub(state, "decrypt"); |
|
1681 } |
|
1682 |
|
1683 function FinalRound(state, roundKey) { |
|
1684 byteSub(state, "encrypt"); |
|
1685 shiftRow(state, "encrypt"); |
|
1686 addRoundKey(state, roundKey); |
|
1687 } |
|
1688 |
|
1689 function InverseFinalRound(state, roundKey){ |
|
1690 addRoundKey(state, roundKey); |
|
1691 shiftRow(state, "decrypt"); |
|
1692 byteSub(state, "decrypt"); |
|
1693 } |
|
1694 |
|
1695 // encrypt is the basic encryption function. It takes parameters |
|
1696 // block, an array of bytes representing a plaintext block, and expandedKey, |
|
1697 // an array of words representing the expanded key previously returned by |
|
1698 // keyExpansion(). The ciphertext block is returned as an array of bytes. |
|
1699 |
|
1700 function encrypt(block, expandedKey) { |
|
1701 var i; |
|
1702 if (!block || block.length*8 != blockSizeInBits) |
|
1703 return; |
|
1704 if (!expandedKey) |
|
1705 return; |
|
1706 |
|
1707 block = packBytes(block); |
|
1708 addRoundKey(block, expandedKey); |
|
1709 for (i=1; i<Nr; i++) |
|
1710 Round(block, expandedKey.slice(Nb*i, Nb*(i+1))); |
|
1711 FinalRound(block, expandedKey.slice(Nb*Nr)); |
|
1712 return unpackBytes(block); |
|
1713 } |
|
1714 |
|
1715 // decrypt is the basic decryption function. It takes parameters |
|
1716 // block, an array of bytes representing a ciphertext block, and expandedKey, |
|
1717 // an array of words representing the expanded key previously returned by |
|
1718 // keyExpansion(). The decrypted block is returned as an array of bytes. |
|
1719 |
|
1720 function decrypt(block, expandedKey) { |
|
1721 var i; |
|
1722 if (!block || block.length*8 != blockSizeInBits) |
|
1723 return; |
|
1724 if (!expandedKey) |
|
1725 return; |
|
1726 |
|
1727 block = packBytes(block); |
|
1728 InverseFinalRound(block, expandedKey.slice(Nb*Nr)); |
|
1729 for (i = Nr - 1; i>0; i--) |
|
1730 InverseRound(block, expandedKey.slice(Nb*i, Nb*(i+1))); |
|
1731 addRoundKey(block, expandedKey); |
|
1732 return unpackBytes(block); |
|
1733 } |
|
1734 |
|
1735 // This method takes a byte array (byteArray) and converts it to a string by |
|
1736 // applying String.fromCharCode() to each value and concatenating the result. |
|
1737 // The resulting string is returned. Note that this function SKIPS zero bytes |
|
1738 // under the assumption that they are padding added in formatPlaintext(). |
|
1739 // Obviously, do not invoke this method on raw data that can contain zero |
|
1740 // bytes. It is really only appropriate for printable ASCII/Latin-1 |
|
1741 // values. Roll your own function for more robust functionality :) |
|
1742 |
|
1743 function byteArrayToString(byteArray) { |
|
1744 var result = ""; |
|
1745 for(var i=0; i<byteArray.length; i++) |
|
1746 if (byteArray[i] != 0) |
|
1747 result += String.fromCharCode(byteArray[i]); |
|
1748 return result; |
|
1749 } |
|
1750 |
|
1751 // This function takes an array of bytes (byteArray) and converts them |
|
1752 // to a hexadecimal string. Array element 0 is found at the beginning of |
|
1753 // the resulting string, high nibble first. Consecutive elements follow |
|
1754 // similarly, for example [16, 255] --> "10ff". The function returns a |
|
1755 // string. |
|
1756 |
|
1757 function byteArrayToHex(byteArray) { |
|
1758 var result = ""; |
|
1759 if (!byteArray) |
|
1760 return; |
|
1761 for (var i=0; i<byteArray.length; i++) |
|
1762 result += ((byteArray[i]<16) ? "0" : "") + byteArray[i].toString(16); |
|
1763 |
|
1764 return result; |
|
1765 } |
|
1766 |
|
1767 // This function converts a string containing hexadecimal digits to an |
|
1768 // array of bytes. The resulting byte array is filled in the order the |
|
1769 // values occur in the string, for example "10FF" --> [16, 255]. This |
|
1770 // function returns an array. |
|
1771 |
|
1772 function hexToByteArray(hexString) { |
|
1773 /* |
|
1774 var byteArray = []; |
|
1775 if (hexString.length % 2) // must have even length |
|
1776 return; |
|
1777 if (hexString.indexOf("0x") == 0 || hexString.indexOf("0X") == 0) |
|
1778 hexString = hexString.substring(2); |
|
1779 for (var i = 0; i<hexString.length; i += 2) |
|
1780 byteArray[Math.floor(i/2)] = parseInt(hexString.slice(i, i+2), 16); |
|
1781 return byteArray; |
|
1782 */ |
|
1783 var bytes = new Array(); |
|
1784 hexString = str_split(hexString, 2); |
|
1785 //alert(hexString.toString()); |
|
1786 //return false; |
|
1787 for( var i in hexString ) |
|
1788 { |
|
1789 bytes[bytes.length] = parseInt(hexString[i], 16); |
|
1790 } |
|
1791 //alert(bytes.toString()); |
|
1792 return bytes; |
|
1793 } |
|
1794 |
|
1795 // This function packs an array of bytes into the four row form defined by |
|
1796 // Rijndael. It assumes the length of the array of bytes is divisible by |
|
1797 // four. Bytes are filled in according to the Rijndael spec (starting with |
|
1798 // column 0, row 0 to 3). This function returns a 2d array. |
|
1799 |
|
1800 function packBytes(octets) { |
|
1801 var state = new Array(); |
|
1802 if (!octets || octets.length % 4) |
|
1803 return; |
|
1804 |
|
1805 state[0] = new Array(); state[1] = new Array(); |
|
1806 state[2] = new Array(); state[3] = new Array(); |
|
1807 for (var j=0; j<octets.length; j+= 4) { |
|
1808 state[0][j/4] = octets[j]; |
|
1809 state[1][j/4] = octets[j+1]; |
|
1810 state[2][j/4] = octets[j+2]; |
|
1811 state[3][j/4] = octets[j+3]; |
|
1812 } |
|
1813 return state; |
|
1814 } |
|
1815 |
|
1816 // This function unpacks an array of bytes from the four row format preferred |
|
1817 // by Rijndael into a single 1d array of bytes. It assumes the input "packed" |
|
1818 // is a packed array. Bytes are filled in according to the Rijndael spec. |
|
1819 // This function returns a 1d array of bytes. |
|
1820 |
|
1821 function unpackBytes(packed) { |
|
1822 var result = new Array(); |
|
1823 for (var j=0; j<packed[0].length; j++) { |
|
1824 result[result.length] = packed[0][j]; |
|
1825 result[result.length] = packed[1][j]; |
|
1826 result[result.length] = packed[2][j]; |
|
1827 result[result.length] = packed[3][j]; |
|
1828 } |
|
1829 return result; |
|
1830 } |
|
1831 |
|
1832 // This function takes a prospective plaintext (string or array of bytes) |
|
1833 // and pads it with zero bytes if its length is not a multiple of the block |
|
1834 // size. If plaintext is a string, it is converted to an array of bytes |
|
1835 // in the process. The type checking can be made much nicer using the |
|
1836 // instanceof operator, but this operator is not available until IE5.0 so I |
|
1837 // chose to use the heuristic below. |
|
1838 |
|
1839 function formatPlaintext(plaintext) { |
|
1840 var bpb = blockSizeInBits / 8; // bytes per block |
|
1841 var i; |
|
1842 |
|
1843 // if primitive string or String instance |
|
1844 if (typeof plaintext == "string" || plaintext.split) { |
|
1845 // alert('AUUGH you idiot it\'s NOT A STRING ITS A '+typeof(plaintext)+'!!!'); |
|
1846 // return false; |
|
1847 plaintext = plaintext.split(""); |
|
1848 // Unicode issues here (ignoring high byte) |
|
1849 for (i=0; i<plaintext.length; i++) |
|
1850 plaintext[i] = plaintext[i].charCodeAt(0) & 0xFF; |
|
1851 } |
|
1852 |
|
1853 for (i = bpb - (plaintext.length % bpb); i > 0 && i < bpb; i--) |
|
1854 plaintext[plaintext.length] = 0; |
|
1855 |
|
1856 return plaintext; |
|
1857 } |
|
1858 |
|
1859 // Returns an array containing "howMany" random bytes. YOU SHOULD CHANGE THIS |
|
1860 // TO RETURN HIGHER QUALITY RANDOM BYTES IF YOU ARE USING THIS FOR A "REAL" |
|
1861 // APPLICATION. |
|
1862 |
|
1863 function getRandomBytes(howMany) { |
|
1864 var i; |
|
1865 var bytes = new Array(); |
|
1866 for (i=0; i<howMany; i++) |
|
1867 bytes[i] = Math.round(Math.random()*255); |
|
1868 return bytes; |
|
1869 } |
|
1870 |
|
1871 // rijndaelEncrypt(plaintext, key, mode) |
|
1872 // Encrypts the plaintext using the given key and in the given mode. |
|
1873 // The parameter "plaintext" can either be a string or an array of bytes. |
|
1874 // The parameter "key" must be an array of key bytes. If you have a hex |
|
1875 // string representing the key, invoke hexToByteArray() on it to convert it |
|
1876 // to an array of bytes. The third parameter "mode" is a string indicating |
|
1877 // the encryption mode to use, either "ECB" or "CBC". If the parameter is |
|
1878 // omitted, ECB is assumed. |
|
1879 // |
|
1880 // An array of bytes representing the cihpertext is returned. To convert |
|
1881 // this array to hex, invoke byteArrayToHex() on it. If you are using this |
|
1882 // "for real" it is a good idea to change the function getRandomBytes() to |
|
1883 // something that returns truly random bits. |
|
1884 |
|
1885 function rijndaelEncrypt(plaintext, key, mode) { |
|
1886 var expandedKey, i, aBlock; |
|
1887 var bpb = blockSizeInBits / 8; // bytes per block |
|
1888 var ct; // ciphertext |
|
1889 |
|
1890 if (typeof plaintext != 'object' || typeof key != 'object') |
|
1891 { |
|
1892 alert( 'Invalid params\nplaintext: '+typeof(plaintext)+'\nkey: '+typeof(key) ); |
|
1893 return false; |
|
1894 } |
|
1895 if (key.length*8 == keySizeInBits+8) |
|
1896 key.length = keySizeInBits / 8; |
|
1897 if (key.length*8 != keySizeInBits) |
|
1898 { |
|
1899 alert( 'Key length is bad!\nLength: '+key.length+'\nExpected: '+keySizeInBits / 8 ); |
|
1900 return false; |
|
1901 } |
|
1902 if (mode == "CBC") |
|
1903 ct = getRandomBytes(bpb); // get IV |
|
1904 else { |
|
1905 mode = "ECB"; |
|
1906 ct = new Array(); |
|
1907 } |
|
1908 |
|
1909 // convert plaintext to byte array and pad with zeros if necessary. |
|
1910 plaintext = formatPlaintext(plaintext); |
|
1911 |
|
1912 expandedKey = keyExpansion(key); |
|
1913 |
|
1914 for (var block=0; block<plaintext.length / bpb; block++) { |
|
1915 aBlock = plaintext.slice(block*bpb, (block+1)*bpb); |
|
1916 if (mode == "CBC") |
|
1917 for (var i=0; i<bpb; i++) |
|
1918 aBlock[i] ^= ct[block*bpb + i]; |
|
1919 ct = ct.concat(encrypt(aBlock, expandedKey)); |
|
1920 } |
|
1921 |
|
1922 return ct; |
|
1923 } |
|
1924 |
|
1925 // rijndaelDecrypt(ciphertext, key, mode) |
|
1926 // Decrypts the using the given key and mode. The parameter "ciphertext" |
|
1927 // must be an array of bytes. The parameter "key" must be an array of key |
|
1928 // bytes. If you have a hex string representing the ciphertext or key, |
|
1929 // invoke hexToByteArray() on it to convert it to an array of bytes. The |
|
1930 // parameter "mode" is a string, either "CBC" or "ECB". |
|
1931 // |
|
1932 // An array of bytes representing the plaintext is returned. To convert |
|
1933 // this array to a hex string, invoke byteArrayToHex() on it. To convert it |
|
1934 // to a string of characters, you can use byteArrayToString(). |
|
1935 |
|
1936 function rijndaelDecrypt(ciphertext, key, mode) { |
|
1937 var expandedKey; |
|
1938 var bpb = blockSizeInBits / 8; // bytes per block |
|
1939 var pt = new Array(); // plaintext array |
|
1940 var aBlock; // a decrypted block |
|
1941 var block; // current block number |
|
1942 |
|
1943 if (!ciphertext || !key || typeof ciphertext == "string") |
|
1944 return; |
|
1945 if (key.length*8 != keySizeInBits) |
|
1946 return; |
|
1947 if (!mode) |
|
1948 mode = "ECB"; // assume ECB if mode omitted |
|
1949 |
|
1950 expandedKey = keyExpansion(key); |
|
1951 |
|
1952 // work backwards to accomodate CBC mode |
|
1953 for (block=(ciphertext.length / bpb)-1; block>0; block--) { |
|
1954 aBlock = |
|
1955 decrypt(ciphertext.slice(block*bpb,(block+1)*bpb), expandedKey); |
|
1956 if (mode == "CBC") |
|
1957 for (var i=0; i<bpb; i++) |
|
1958 pt[(block-1)*bpb + i] = aBlock[i] ^ ciphertext[(block-1)*bpb + i]; |
|
1959 else |
|
1960 pt = aBlock.concat(pt); |
|
1961 } |
|
1962 |
|
1963 // do last block if ECB (skips the IV in CBC) |
|
1964 if (mode == "ECB") |
|
1965 pt = decrypt(ciphertext.slice(0, bpb), expandedKey).concat(pt); |
|
1966 |
|
1967 return pt; |
|
1968 } |
|
1969 |
|
1970 function stringToByteArray(text) |
|
1971 { |
|
1972 result = new Array(); |
|
1973 for ( i=0; i<text.length; i++ ) |
|
1974 { |
|
1975 result[result.length] = text.charCodeAt(i); |
|
1976 } |
|
1977 return result; |
|
1978 } |
|
1979 |
|
1980 function aes_self_test() |
|
1981 { |
|
1982 // |
|
1983 // Encryption test |
|
1984 // |
|
1985 |
|
1986 var str = ''; |
|
1987 for(i=0;i<keySizeInBits/4;i++) |
|
1988 { |
|
1989 str+='0'; |
|
1990 } |
|
1991 str = hexToByteArray(str); |
|
1992 var ct = rijndaelEncrypt(str, str, 'ECB'); |
|
1993 ct = byteArrayToHex(ct); |
|
1994 var v; |
|
1995 switch(keySizeInBits) |
|
1996 { |
|
1997 // These test vectors are for 128-bit block size. |
|
1998 case 128: |
|
1999 v = '66e94bd4ef8a2c3b884cfa59ca342b2e'; |
|
2000 break; |
|
2001 case 192: |
|
2002 v = 'aae06992acbf52a3e8f4a96ec9300bd7aae06992acbf52a3e8f4a96ec9300bd7'; |
|
2003 break; |
|
2004 case 256: |
|
2005 v = 'dc95c078a2408989ad48a21492842087dc95c078a2408989ad48a21492842087'; |
|
2006 break; |
|
2007 } |
|
2008 return ( ct == v && md5_vm_test() ); |
|
2009 } |
|
2010 |
|
2011 /* |
|
2012 * EnanoMath, an abstraction layer for big-integer (arbitrary precision) |
|
2013 * mathematics. |
|
2014 */ |
|
2015 |
|
2016 var EnanoMathLayers = {}; |
|
2017 |
|
2018 // EnanoMath layer: Leemon (frontend to BigInt library by Leemon Baird) |
|
2019 |
|
2020 EnanoMathLayers.Leemon = { |
|
2021 Base: 10, |
|
2022 PowMod: function(a, b, c) |
|
2023 { |
|
2024 a = str2bigInt(a, this.Base); |
|
2025 b = str2bigInt(b, this.Base); |
|
2026 c = str2bigInt(c, this.Base); |
|
2027 var result = powMod(a, b, c); |
|
2028 result = bigInt2str(result, this.Base); |
|
2029 return result; |
|
2030 }, |
|
2031 RandomInt: function(bits) |
|
2032 { |
|
2033 var result = randBigInt(bits); |
|
2034 return bigInt2str(result, this.Base); |
|
2035 } |
|
2036 } |
|
2037 |
|
2038 var EnanoMath = EnanoMathLayers.Leemon; |
|
2039 |
|
2040 /* |
|
2041 * The Diffie-Hellman key exchange protocol. |
|
2042 */ |
|
2043 |
|
2044 // Our prime number as a base for operations. |
|
2045 var dh_prime = '82818079787776757473727170696867666564636261605958575655545352515049484746454443424140393837363534333231302928272625242322212019181716151413121110987654321'; |
|
2046 |
|
2047 // g, a primitive root used as an exponent |
|
2048 // (2 and 5 are acceptable, but BigInt is faster with odd numbers) |
|
2049 var dh_g = '5'; |
|
2050 |
|
2051 /** |
|
2052 * Generates a Diffie-Hellman private key |
|
2053 * @return string(BigInt) |
|
2054 */ |
|
2055 |
|
2056 function dh_gen_private() |
|
2057 { |
|
2058 return EnanoMath.RandomInt(256); |
|
2059 } |
|
2060 |
|
2061 /** |
|
2062 * Calculates the public key from the private key |
|
2063 * @param string(BigInt) |
|
2064 * @return string(BigInt) |
|
2065 */ |
|
2066 |
|
2067 function dh_gen_public(b) |
|
2068 { |
|
2069 return EnanoMath.PowMod(dh_g, b, dh_prime); |
|
2070 } |
|
2071 |
|
2072 /** |
|
2073 * Calculates the shared secret. |
|
2074 * @param string(BigInt) Our private key |
|
2075 * @param string(BigInt) Remote party's public key |
|
2076 * @return string(BigInt) |
|
2077 */ |
|
2078 |
|
2079 function dh_gen_shared_secret(b, A) |
|
2080 { |
|
2081 return EnanoMath.PowMod(A, b, dh_prime); |
|
2082 } |
|
2083 |
|
2084 /* A JavaScript implementation of the Secure Hash Algorithm, SHA-256 |
|
2085 * Version 0.3 Copyright Angel Marin 2003-2004 - http://anmar.eu.org/ |
|
2086 * Distributed under the BSD License |
|
2087 * Some bits taken from Paul Johnston's SHA-1 implementation |
|
2088 */ |
|
2089 /* |
|
2090 Copyright (c) 2003-2004, Angel Marin |
|
2091 All rights reserved. |
|
2092 |
|
2093 Redistribution and use in source and binary forms, with or without modification, |
|
2094 are permitted provided that the following conditions are met: |
|
2095 |
|
2096 * Redistributions of source code must retain the above copyright notice, this |
|
2097 list of conditions and the following disclaimer. |
|
2098 * Redistributions in binary form must reproduce the above copyright notice, |
|
2099 this list of conditions and the following disclaimer in the documentation |
|
2100 and/or other materials provided with the distribution. |
|
2101 * Neither the name of the <ORGANIZATION> nor the names of its contributors may |
|
2102 be used to endorse or promote products derived from this software without |
|
2103 specific prior written permission. |
|
2104 |
|
2105 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND |
|
2106 ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED |
|
2107 WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. |
|
2108 IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, |
|
2109 INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, |
|
2110 BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
|
2111 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF |
|
2112 LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE |
|
2113 OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED |
|
2114 OF THE POSSIBILITY OF SUCH DAMAGE. |
|
2115 */ |
|
2116 var chrsz = 8; /* bits per input character. 8 - ASCII; 16 - Unicode */ |
|
2117 function safe_add (x, y) { |
|
2118 var lsw = (x & 0xFFFF) + (y & 0xFFFF); |
|
2119 var msw = (x >> 16) + (y >> 16) + (lsw >> 16); |
|
2120 return (msw << 16) | (lsw & 0xFFFF); |
|
2121 } |
|
2122 function S (X, n) {return ( X >>> n ) | (X << (32 - n));} |
|
2123 function R (X, n) {return ( X >>> n );} |
|
2124 function Ch(x, y, z) {return ((x & y) ^ ((~x) & z));} |
|
2125 function Maj(x, y, z) {return ((x & y) ^ (x & z) ^ (y & z));} |
|
2126 function Sigma0256(x) {return (S(x, 2) ^ S(x, 13) ^ S(x, 22));} |
|
2127 function Sigma1256(x) {return (S(x, 6) ^ S(x, 11) ^ S(x, 25));} |
|
2128 function Gamma0256(x) {return (S(x, 7) ^ S(x, 18) ^ R(x, 3));} |
|
2129 function Gamma1256(x) {return (S(x, 17) ^ S(x, 19) ^ R(x, 10));} |
|
2130 function core_sha256 (m, l) { |
|
2131 var K = new Array(0x428A2F98,0x71374491,0xB5C0FBCF,0xE9B5DBA5,0x3956C25B,0x59F111F1,0x923F82A4,0xAB1C5ED5,0xD807AA98,0x12835B01,0x243185BE,0x550C7DC3,0x72BE5D74,0x80DEB1FE,0x9BDC06A7,0xC19BF174,0xE49B69C1,0xEFBE4786,0xFC19DC6,0x240CA1CC,0x2DE92C6F,0x4A7484AA,0x5CB0A9DC,0x76F988DA,0x983E5152,0xA831C66D,0xB00327C8,0xBF597FC7,0xC6E00BF3,0xD5A79147,0x6CA6351,0x14292967,0x27B70A85,0x2E1B2138,0x4D2C6DFC,0x53380D13,0x650A7354,0x766A0ABB,0x81C2C92E,0x92722C85,0xA2BFE8A1,0xA81A664B,0xC24B8B70,0xC76C51A3,0xD192E819,0xD6990624,0xF40E3585,0x106AA070,0x19A4C116,0x1E376C08,0x2748774C,0x34B0BCB5,0x391C0CB3,0x4ED8AA4A,0x5B9CCA4F,0x682E6FF3,0x748F82EE,0x78A5636F,0x84C87814,0x8CC70208,0x90BEFFFA,0xA4506CEB,0xBEF9A3F7,0xC67178F2); |
|
2132 var HASH = new Array(0x6A09E667, 0xBB67AE85, 0x3C6EF372, 0xA54FF53A, 0x510E527F, 0x9B05688C, 0x1F83D9AB, 0x5BE0CD19); |
|
2133 var W = new Array(64); |
|
2134 var a, b, c, d, e, f, g, h, i, j; |
|
2135 var T1, T2; |
|
2136 /* append padding */ |
|
2137 m[l >> 5] |= 0x80 << (24 - l % 32); |
|
2138 m[((l + 64 >> 9) << 4) + 15] = l; |
|
2139 for ( var i = 0; i<m.length; i+=16 ) { |
|
2140 a = HASH[0]; b = HASH[1]; c = HASH[2]; d = HASH[3]; e = HASH[4]; f = HASH[5]; g = HASH[6]; h = HASH[7]; |
|
2141 for ( var j = 0; j<64; j++) { |
|
2142 if (j < 16) W[j] = m[j + i]; |
|
2143 else W[j] = safe_add(safe_add(safe_add(Gamma1256(W[j - 2]), W[j - 7]), Gamma0256(W[j - 15])), W[j - 16]); |
|
2144 T1 = safe_add(safe_add(safe_add(safe_add(h, Sigma1256(e)), Ch(e, f, g)), K[j]), W[j]); |
|
2145 T2 = safe_add(Sigma0256(a), Maj(a, b, c)); |
|
2146 h = g; g = f; f = e; e = safe_add(d, T1); d = c; c = b; b = a; a = safe_add(T1, T2); |
|
2147 } |
|
2148 HASH[0] = safe_add(a, HASH[0]); HASH[1] = safe_add(b, HASH[1]); HASH[2] = safe_add(c, HASH[2]); HASH[3] = safe_add(d, HASH[3]); HASH[4] = safe_add(e, HASH[4]); HASH[5] = safe_add(f, HASH[5]); HASH[6] = safe_add(g, HASH[6]); HASH[7] = safe_add(h, HASH[7]); |
|
2149 } |
|
2150 return HASH; |
|
2151 } |
|
2152 function str2binb (str) { |
|
2153 var bin = Array(); |
|
2154 var mask = (1 << chrsz) - 1; |
|
2155 for(var i = 0; i < str.length * chrsz; i += chrsz) |
|
2156 bin[i>>5] |= (str.charCodeAt(i / chrsz) & mask) << (24 - i%32); |
|
2157 return bin; |
|
2158 } |
|
2159 function binb2hex (binarray) { |
|
2160 var hexcase = 0; /* hex output format. 0 - lowercase; 1 - uppercase */ |
|
2161 var hex_tab = hexcase ? "0123456789ABCDEF" : "0123456789abcdef"; |
|
2162 var str = ""; |
|
2163 for (var i = 0; i < binarray.length * 4; i++) { |
|
2164 str += hex_tab.charAt((binarray[i>>2] >> ((3 - i%4)*8+4)) & 0xF) + hex_tab.charAt((binarray[i>>2] >> ((3 - i%4)*8 )) & 0xF); |
|
2165 } |
|
2166 return str; |
|
2167 } |
|
2168 function hex_sha256(s){return binb2hex(core_sha256(str2binb(s),s.length * chrsz));} |
|
2169 |
|
2170 // Javascript implementation of the and SHA1 hash algorithms - both written by Paul Johnston, licensed under the BSD license |
|
2171 |
|
2172 // MD5 |
|
2173 var hexcase = 0; var b64pad = ""; var chrsz = 8; |
|
2174 function hex_md5(s){ return binl2hex(core_md5(str2binl(s), s.length * chrsz));} |
|
2175 function b64_md5(s){ return binl2b64(core_md5(str2binl(s), s.length * chrsz));} |
|
2176 function str_md5(s){ return binl2str(core_md5(str2binl(s), s.length * chrsz));} |
|
2177 function hex_hmac_md5(key, data) { return binl2hex(core_hmac_md5(key, data)); } |
|
2178 function b64_hmac_md5(key, data) { return binl2b64(core_hmac_md5(key, data)); } |
|
2179 function str_hmac_md5(key, data) { return binl2str(core_hmac_md5(key, data)); } |
|
2180 function md5_vm_test() { return hex_md5("abc") == "900150983cd24fb0d6963f7d28e17f72"; } |
|
2181 function core_md5(x, len) { x[len >> 5] |= 0x80 << ((len) % 32); x[(((len + 64) >>> 9) << 4) + 14] = len; var a = 1732584193; var b = -271733879; var c = -1732584194; var d = 271733878; for(var i = 0; i < x.length; i += 16) { var olda = a; var oldb = b; var oldc = c; var oldd = d; a = md5_ff(a, b, c, d, x[i+ 0], 7 , -680876936);d = md5_ff(d, a, b, c, x[i+ 1], 12, -389564586);c = md5_ff(c, d, a, b, x[i+ 2], 17, 606105819);b = md5_ff(b, c, d, a, x[i+ 3], 22, -1044525330); |
|
2182 a = md5_ff(a, b, c, d, x[i+ 4], 7 , -176418897);d = md5_ff(d, a, b, c, x[i+ 5], 12, 1200080426);c = md5_ff(c, d, a, b, x[i+ 6], 17, -1473231341);b = md5_ff(b, c, d, a, x[i+ 7], 22, -45705983);a = md5_ff(a, b, c, d, x[i+ 8], 7 , 1770035416);d = md5_ff(d, a, b, c, x[i+ 9], 12, -1958414417);c = md5_ff(c, d, a, b, x[i+10], 17, -42063);b = md5_ff(b, c, d, a, x[i+11], 22, -1990404162);a = md5_ff(a, b, c, d, x[i+12], 7 , 1804603682);d = md5_ff(d, a, b, c, x[i+13], 12, -40341101); |
|
2183 c = md5_ff(c, d, a, b, x[i+14], 17, -1502002290);b = md5_ff(b, c, d, a, x[i+15], 22, 1236535329);a = md5_gg(a, b, c, d, x[i+ 1], 5 , -165796510);d = md5_gg(d, a, b, c, x[i+ 6], 9 , -1069501632);c = md5_gg(c, d, a, b, x[i+11], 14, 643717713);b = md5_gg(b, c, d, a, x[i+ 0], 20, -373897302);a = md5_gg(a, b, c, d, x[i+ 5], 5 , -701558691);d = md5_gg(d, a, b, c, x[i+10], 9 , 38016083);c = md5_gg(c, d, a, b, x[i+15], 14, -660478335);b = md5_gg(b, c, d, a, x[i+ 4], 20, -405537848); |
|
2184 a = md5_gg(a, b, c, d, x[i+ 9], 5 , 568446438);d = md5_gg(d, a, b, c, x[i+14], 9 , -1019803690);c = md5_gg(c, d, a, b, x[i+ 3], 14, -187363961);b = md5_gg(b, c, d, a, x[i+ 8], 20, 1163531501);a = md5_gg(a, b, c, d, x[i+13], 5 , -1444681467);d = md5_gg(d, a, b, c, x[i+ 2], 9 , -51403784);c = md5_gg(c, d, a, b, x[i+ 7], 14, 1735328473);b = md5_gg(b, c, d, a, x[i+12], 20, -1926607734);a = md5_hh(a, b, c, d, x[i+ 5], 4 , -378558);d = md5_hh(d, a, b, c, x[i+ 8], 11, -2022574463); |
|
2185 c = md5_hh(c, d, a, b, x[i+11], 16, 1839030562);b = md5_hh(b, c, d, a, x[i+14], 23, -35309556);a = md5_hh(a, b, c, d, x[i+ 1], 4 , -1530992060);d = md5_hh(d, a, b, c, x[i+ 4], 11, 1272893353);c = md5_hh(c, d, a, b, x[i+ 7], 16, -155497632);b = md5_hh(b, c, d, a, x[i+10], 23, -1094730640);a = md5_hh(a, b, c, d, x[i+13], 4 , 681279174);d = md5_hh(d, a, b, c, x[i+ 0], 11, -358537222);c = md5_hh(c, d, a, b, x[i+ 3], 16, -722521979);b = md5_hh(b, c, d, a, x[i+ 6], 23, 76029189); |
|
2186 a = md5_hh(a, b, c, d, x[i+ 9], 4 , -640364487);d = md5_hh(d, a, b, c, x[i+12], 11, -421815835);c = md5_hh(c, d, a, b, x[i+15], 16, 530742520);b = md5_hh(b, c, d, a, x[i+ 2], 23, -995338651);a = md5_ii(a, b, c, d, x[i+ 0], 6 , -198630844);d = md5_ii(d, a, b, c, x[i+ 7], 10, 1126891415);c = md5_ii(c, d, a, b, x[i+14], 15, -1416354905);b = md5_ii(b, c, d, a, x[i+ 5], 21, -57434055);a = md5_ii(a, b, c, d, x[i+12], 6 , 1700485571);d = md5_ii(d, a, b, c, x[i+ 3], 10, -1894986606); |
|
2187 c = md5_ii(c, d, a, b, x[i+10], 15, -1051523);b = md5_ii(b, c, d, a, x[i+ 1], 21, -2054922799);a = md5_ii(a, b, c, d, x[i+ 8], 6 , 1873313359);d = md5_ii(d, a, b, c, x[i+15], 10, -30611744);c = md5_ii(c, d, a, b, x[i+ 6], 15, -1560198380);b = md5_ii(b, c, d, a, x[i+13], 21, 1309151649);a = md5_ii(a, b, c, d, x[i+ 4], 6 , -145523070);d = md5_ii(d, a, b, c, x[i+11], 10, -1120210379);c = md5_ii(c, d, a, b, x[i+ 2], 15, 718787259);b = md5_ii(b, c, d, a, x[i+ 9], 21, -343485551); |
|
2188 a = safe_add(a, olda); b = safe_add(b, oldb); c = safe_add(c, oldc); d = safe_add(d, oldd); } return Array(a, b, c, d); } |
|
2189 function md5_cmn(q, a, b, x, s, t) { return safe_add(bit_rol(safe_add(safe_add(a, q), safe_add(x, t)), s),b); } |
|
2190 function md5_ff(a, b, c, d, x, s, t) { return md5_cmn((b & c) | ((~b) & d), a, b, x, s, t); } |
|
2191 function md5_gg(a, b, c, d, x, s, t) { return md5_cmn((b & d) | (c & (~d)), a, b, x, s, t); } |
|
2192 function md5_hh(a, b, c, d, x, s, t) { return md5_cmn(b ^ c ^ d, a, b, x, s, t); } |
|
2193 function md5_ii(a, b, c, d, x, s, t) { return md5_cmn(c ^ (b | (~d)), a, b, x, s, t); } |
|
2194 function core_hmac_md5(key, data) { var bkey = str2binl(key); if(bkey.length > 16) bkey = core_md5(bkey, key.length * chrsz); var ipad = Array(16), opad = Array(16); for(var i = 0; i < 16; i++) { ipad[i] = bkey[i] ^ 0x36363636; opad[i] = bkey[i] ^ 0x5C5C5C5C; } var hash = core_md5(ipad.concat(str2binl(data)), 512 + data.length * chrsz); return core_md5(opad.concat(hash), 512 + 128); } |
|
2195 function safe_add(x, y) {var lsw = (x & 0xFFFF) + (y & 0xFFFF);var msw = (x >> 16) + (y >> 16) + (lsw >> 16);return (msw << 16) | (lsw & 0xFFFF); } |
|
2196 function bit_rol(num, cnt) { return (num << cnt) | (num >>> (32 - cnt)); } |
|
2197 function str2binl(str) { var bin = Array(); var mask = (1 << chrsz) - 1; for(var i = 0; i < str.length * chrsz; i += chrsz)bin[i>>5] |= (str.charCodeAt(i / chrsz) & mask) << (i%32); return bin;} |
|
2198 function binl2str(bin) { var str = ""; var mask = (1 << chrsz) - 1; for(var i = 0; i < bin.length * 32; i += chrsz) str += String.fromCharCode((bin[i>>5] >>> (i % 32)) & mask); return str; } |
|
2199 function binl2hex(binarray) { var hex_tab = hexcase ? "0123456789ABCDEF" : "0123456789abcdef"; var str = ""; for(var i = 0; i < binarray.length * 4; i++) { str += hex_tab.charAt((binarray[i>>2] >> ((i%4)*8+4)) & 0xF) + hex_tab.charAt((binarray[i>>2] >> ((i%4)*8 )) & 0xF); } return str; } |
|
2200 function binl2b64(binarray) { var tab = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/"; var str = ""; for(var i = 0; i < binarray.length * 4; i += 3) { var triplet = (((binarray[i >> 2] >> 8 * ( i %4)) & 0xFF) << 16) | (((binarray[i+1 >> 2] >> 8 * ((i+1)%4)) & 0xFF) << 8 ) | ((binarray[i+2 >> 2] >> 8 * ((i+2)%4)) & 0xFF); for(var j = 0; j < 4; j++) { if(i * 8 + j * 6 > binarray.length * 32) str += b64pad; else str += tab.charAt((triplet >> 6*(3-j)) & 0x3F); } } return str; } |
|
2201 |
|
2202 // SHA1 |
|
2203 function hex_sha1(s){return binb2hex(core_sha1(str2binb(s),s.length * chrsz));} |
|
2204 function b64_sha1(s){return binb2b64(core_sha1(str2binb(s),s.length * chrsz));} |
|
2205 function str_sha1(s){return binb2str(core_sha1(str2binb(s),s.length * chrsz));} |
|
2206 function hex_hmac_sha1(key, data){ return binb2hex(core_hmac_sha1(key, data));} |
|
2207 function b64_hmac_sha1(key, data){ return binb2b64(core_hmac_sha1(key, data));} |
|
2208 function str_hmac_sha1(key, data){ return binb2str(core_hmac_sha1(key, data));} |
|
2209 function sha1_vm_test() { return hex_sha1("abc") == "a9993e364706816aba3e25717850c26c9cd0d89d"; } |
|
2210 function core_sha1(x, len) { x[len >> 5] |= 0x80 << (24 - len % 32); x[((len + 64 >> 9) << 4) + 15] = len; var w = Array(80); var a = 1732584193; var b = -271733879; var c = -1732584194; var d = 271733878; var e = -1009589776; for(var i = 0; i < x.length; i += 16) { var olda = a; var oldb = b; var oldc = c; var oldd = d; var olde = e; for(var j = 0; j < 80; j++) { if(j < 16) w[j] = x[i + j]; else w[j] = rol(w[j-3] ^ w[j-8] ^ w[j-14] ^ w[j-16], 1); var t = safe_add(safe_add(rol(a, 5), sha1_ft(j, b, c, d)), safe_add(safe_add(e, w[j]), sha1_kt(j))); e = d; d = c; c = rol(b, 30); b = a; a = t; } a = safe_add(a, olda); b = safe_add(b, oldb); c = safe_add(c, oldc); d = safe_add(d, oldd); e = safe_add(e, olde); } return Array(a, b, c, d, e);} |
|
2211 function sha1_ft(t, b, c, d){ if(t < 20) return (b & c) | ((~b) & d); if(t < 40) return b ^ c ^ d; if(t < 60) return (b & c) | (b & d) | (c & d); return b ^ c ^ d;} |
|
2212 function sha1_kt(t){ return (t < 20) ? 1518500249 : (t < 40) ? 1859775393 : (t < 60) ? -1894007588 : -899497514;} |
|
2213 function core_hmac_sha1(key, data){ var bkey = str2binb(key); if(bkey.length > 16) bkey = core_sha1(bkey, key.length * chrsz); var ipad = Array(16), opad = Array(16); for(var i = 0; i < 16; i++) { ipad[i] = bkey[i] ^ 0x36363636; opad[i] = bkey[i] ^ 0x5C5C5C5C; } var hash = core_sha1(ipad.concat(str2binb(data)), 512 + data.length * chrsz); return core_sha1(opad.concat(hash), 512 + 160);} |
|
2214 function safe_add(x, y){ var lsw = (x & 0xFFFF) + (y & 0xFFFF); var msw = (x >> 16) + (y >> 16) + (lsw >> 16); return (msw << 16) | (lsw & 0xFFFF);} |
|
2215 function rol(num, cnt){ return (num << cnt) | (num >>> (32 - cnt));} |
|
2216 function str2binb(str){ var bin = Array(); var mask = (1 << chrsz) - 1; for(var i = 0; i < str.length * chrsz; i += chrsz) bin[i>>5] |= (str.charCodeAt(i / chrsz) & mask) << (32 - chrsz - i%32); return bin;} |
|
2217 function binb2str(bin){ var str = ""; var mask = (1 << chrsz) - 1; for(var i = 0; i < bin.length * 32; i += chrsz) str += String.fromCharCode((bin[i>>5] >>> (32 - chrsz - i%32)) & mask); return str;} |
|
2218 function binb2hex(binarray){ var hex_tab = hexcase ? "0123456789ABCDEF" : "0123456789abcdef"; var str = ""; for(var i = 0; i < binarray.length * 4; i++) { str += hex_tab.charAt((binarray[i>>2] >> ((3 - i%4)*8+4)) & 0xF) + hex_tab.charAt((binarray[i>>2] >> ((3 - i%4)*8 )) & 0xF); } return str;} |
|
2219 function binb2b64(binarray){ var tab = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/"; var str = ""; for(var i = 0; i < binarray.length * 4; i += 3) { var triplet = (((binarray[i >> 2] >> 8 * (3 - i %4)) & 0xFF) << 16) | (((binarray[i+1 >> 2] >> 8 * (3 - (i+1)%4)) & 0xFF) << 8 ) | ((binarray[i+2 >> 2] >> 8 * (3 - (i+2)%4)) & 0xFF); for(var j = 0; j < 4; j++) { if(i * 8 + j * 6 > binarray.length * 32) str += b64pad; else str += tab.charAt((triplet >> 6*(3-j)) & 0x3F); } } return str;} |
|
2220 |