The Tor Browser / file comparison

comparison: js/src/devtools/jint/v8/crypto.js

js/src/devtools/jint/v8/crypto.js

branch
TOR_BUG_9701
changeset 15
b8a032363ba2
equal deleted inserted replaced
-1:000000000000 0:26f94b5b52a7
1 // Copyright 2008 the V8 project authors. All rights reserved.
2 // Redistribution and use in source and binary forms, with or without
3 // modification, are permitted provided that the following conditions are
4 // met:
5 //
6 // * Redistributions of source code must retain the above copyright
7 // notice, this list of conditions and the following disclaimer.
8 // * Redistributions in binary form must reproduce the above
9 // copyright notice, this list of conditions and the following
10 // disclaimer in the documentation and/or other materials provided
11 // with the distribution.
12 // * Neither the name of Google Inc. nor the names of its
13 // contributors may be used to endorse or promote products derived
14 // from this software without specific prior written permission.
15 //
16 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
17 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
18 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
19 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
20 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
21 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
22 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
26 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27
28
29 // Simple framework for running the benchmark suites and
30 // computing a score based on the timing measurements.
31
32
33 // A benchmark has a name (string) and a function that will be run to
34 // do the performance measurement. The optional setup and tearDown
35 // arguments are functions that will be invoked before and after
36 // running the benchmark, but the running time of these functions will
37 // not be accounted for in the benchmark score.
38 function Benchmark(name, run, setup, tearDown) {
39 this.name = name;
40 this.run = run;
41 this.Setup = setup ? setup : function() { };
42 this.TearDown = tearDown ? tearDown : function() { };
43 }
44
45
46 // Benchmark results hold the benchmark and the measured time used to
47 // run the benchmark. The benchmark score is computed later once a
48 // full benchmark suite has run to completion.
49 function BenchmarkResult(benchmark, time) {
50 this.benchmark = benchmark;
51 this.time = time;
52 }
53
54
55 // Automatically convert results to numbers. Used by the geometric
56 // mean computation.
57 BenchmarkResult.prototype.valueOf = function() {
58 return this.time;
59 }
60
61
62 // Suites of benchmarks consist of a name and the set of benchmarks in
63 // addition to the reference timing that the final score will be based
64 // on. This way, all scores are relative to a reference run and higher
65 // scores implies better performance.
66 function BenchmarkSuite(name, reference, benchmarks) {
67 this.name = name;
68 this.reference = reference;
69 this.benchmarks = benchmarks;
70 BenchmarkSuite.suites.push(this);
71 }
72
73
74 // Keep track of all declared benchmark suites.
75 BenchmarkSuite.suites = [];
76
77
78 // Scores are not comparable across versions. Bump the version if
79 // you're making changes that will affect that scores, e.g. if you add
80 // a new benchmark or change an existing one.
81 BenchmarkSuite.version = '5';
82
83
84 // To make the benchmark results predictable, we replace Math.random
85 // with a 100% deterministic alternative.
86 Math.random = (function() {
87 var seed = 49734321;
88 return function() {
89 // Robert Jenkins' 32 bit integer hash function.
90 seed = ((seed + 0x7ed55d16) + (seed << 12)) & 0xffffffff;
91 seed = ((seed ^ 0xc761c23c) ^ (seed >>> 19)) & 0xffffffff;
92 seed = ((seed + 0x165667b1) + (seed << 5)) & 0xffffffff;
93 seed = ((seed + 0xd3a2646c) ^ (seed << 9)) & 0xffffffff;
94 seed = ((seed + 0xfd7046c5) + (seed << 3)) & 0xffffffff;
95 seed = ((seed ^ 0xb55a4f09) ^ (seed >>> 16)) & 0xffffffff;
96 return (seed & 0xfffffff) / 0x10000000;
97 };
98 })();
99
100
101 // Runs all registered benchmark suites and optionally yields between
102 // each individual benchmark to avoid running for too long in the
103 // context of browsers. Once done, the final score is reported to the
104 // runner.
105 BenchmarkSuite.RunSuites = function(runner) {
106 var continuation = null;
107 var suites = BenchmarkSuite.suites;
108 var length = suites.length;
109 BenchmarkSuite.scores = [];
110 var index = 0;
111 function RunStep() {
112 while (continuation || index < length) {
113 if (continuation) {
114 continuation = continuation();
115 } else {
116 var suite = suites[index++];
117 if (runner.NotifyStart) runner.NotifyStart(suite.name);
118 continuation = suite.RunStep(runner);
119 }
120 if (continuation && typeof window != 'undefined' && window.setTimeout) {
121 window.setTimeout(RunStep, 25);
122 return;
123 }
124 }
125 if (runner.NotifyScore) {
126 var score = BenchmarkSuite.GeometricMean(BenchmarkSuite.scores);
127 var formatted = BenchmarkSuite.FormatScore(100 * score);
128 runner.NotifyScore(formatted);
129 }
130 }
131 RunStep();
132 }
133
134
135 // Counts the total number of registered benchmarks. Useful for
136 // showing progress as a percentage.
137 BenchmarkSuite.CountBenchmarks = function() {
138 var result = 0;
139 var suites = BenchmarkSuite.suites;
140 for (var i = 0; i < suites.length; i++) {
141 result += suites[i].benchmarks.length;
142 }
143 return result;
144 }
145
146
147 // Computes the geometric mean of a set of numbers.
148 BenchmarkSuite.GeometricMean = function(numbers) {
149 var log = 0;
150 for (var i = 0; i < numbers.length; i++) {
151 log += Math.log(numbers[i]);
152 }
153 return Math.pow(Math.E, log / numbers.length);
154 }
155
156
157 // Converts a score value to a string with at least three significant
158 // digits.
159 BenchmarkSuite.FormatScore = function(value) {
160 if (value > 100) {
161 return value.toFixed(0);
162 } else {
163 return value.toPrecision(3);
164 }
165 }
166
167 // Notifies the runner that we're done running a single benchmark in
168 // the benchmark suite. This can be useful to report progress.
169 BenchmarkSuite.prototype.NotifyStep = function(result) {
170 this.results.push(result);
171 if (this.runner.NotifyStep) this.runner.NotifyStep(result.benchmark.name);
172 }
173
174
175 // Notifies the runner that we're done with running a suite and that
176 // we have a result which can be reported to the user if needed.
177 BenchmarkSuite.prototype.NotifyResult = function() {
178 var mean = BenchmarkSuite.GeometricMean(this.results);
179 var score = this.reference / mean;
180 BenchmarkSuite.scores.push(score);
181 if (this.runner.NotifyResult) {
182 var formatted = BenchmarkSuite.FormatScore(100 * score);
183 this.runner.NotifyResult(this.name, formatted);
184 }
185 }
186
187
188 // Notifies the runner that running a benchmark resulted in an error.
189 BenchmarkSuite.prototype.NotifyError = function(error) {
190 if (this.runner.NotifyError) {
191 this.runner.NotifyError(this.name, error);
192 }
193 if (this.runner.NotifyStep) {
194 this.runner.NotifyStep(this.name);
195 }
196 }
197
198
199 // Runs a single benchmark for at least a second and computes the
200 // average time it takes to run a single iteration.
201 BenchmarkSuite.prototype.RunSingleBenchmark = function(benchmark) {
202 var elapsed = 0;
203 var start = new Date();
204 for (var n = 0; elapsed < 20; n++) {
205 benchmark.run();
206 elapsed = new Date() - start;
207 }
208 var usec = (elapsed * 1000) / n;
209 this.NotifyStep(new BenchmarkResult(benchmark, usec));
210 }
211
212
213 // This function starts running a suite, but stops between each
214 // individual benchmark in the suite and returns a continuation
215 // function which can be invoked to run the next benchmark. Once the
216 // last benchmark has been executed, null is returned.
217 BenchmarkSuite.prototype.RunStep = function(runner) {
218 this.results = [];
219 this.runner = runner;
220 var length = this.benchmarks.length;
221 var index = 0;
222 var suite = this;
223
224 // Run the setup, the actual benchmark, and the tear down in three
225 // separate steps to allow the framework to yield between any of the
226 // steps.
227
228 function RunNextSetup() {
229 if (index < length) {
230 try {
231 suite.benchmarks[index].Setup();
232 } catch (e) {
233 suite.NotifyError(e);
234 return null;
235 }
236 return RunNextBenchmark;
237 }
238 suite.NotifyResult();
239 return null;
240 }
241
242 function RunNextBenchmark() {
243 try {
244 suite.RunSingleBenchmark(suite.benchmarks[index]);
245 } catch (e) {
246 suite.NotifyError(e);
247 return null;
248 }
249 return RunNextTearDown;
250 }
251
252 function RunNextTearDown() {
253 try {
254 suite.benchmarks[index++].TearDown();
255 } catch (e) {
256 suite.NotifyError(e);
257 return null;
258 }
259 return RunNextSetup;
260 }
261
262 // Start out running the setup.
263 return RunNextSetup();
264 }
265
266 /*
267 * Copyright (c) 2003-2005 Tom Wu
268 * All Rights Reserved.
269 *
270 * Permission is hereby granted, free of charge, to any person obtaining
271 * a copy of this software and associated documentation files (the
272 * "Software"), to deal in the Software without restriction, including
273 * without limitation the rights to use, copy, modify, merge, publish,
274 * distribute, sublicense, and/or sell copies of the Software, and to
275 * permit persons to whom the Software is furnished to do so, subject to
276 * the following conditions:
277 *
278 * The above copyright notice and this permission notice shall be
279 * included in all copies or substantial portions of the Software.
280 *
281 * THE SOFTWARE IS PROVIDED "AS-IS" AND WITHOUT WARRANTY OF ANY KIND,
282 * EXPRESS, IMPLIED OR OTHERWISE, INCLUDING WITHOUT LIMITATION, ANY
283 * WARRANTY OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
284 *
285 * IN NO EVENT SHALL TOM WU BE LIABLE FOR ANY SPECIAL, INCIDENTAL,
286 * INDIRECT OR CONSEQUENTIAL DAMAGES OF ANY KIND, OR ANY DAMAGES WHATSOEVER
287 * RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER OR NOT ADVISED OF
288 * THE POSSIBILITY OF DAMAGE, AND ON ANY THEORY OF LIABILITY, ARISING OUT
289 * OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
290 *
291 * In addition, the following condition applies:
292 *
293 * All redistributions must retain an intact copy of this copyright notice
294 * and disclaimer.
295 */
296
297
298 // The code has been adapted for use as a benchmark by Google.
299 var Crypto = new BenchmarkSuite('Crypto', 203037, [
300 new Benchmark("Encrypt", encrypt),
301 new Benchmark("Decrypt", decrypt)
302 ]);
303
304
305 // Basic JavaScript BN library - subset useful for RSA encryption.
306
307 // Bits per digit
308 var dbits;
309 var BI_DB;
310 var BI_DM;
311 var BI_DV;
312
313 var BI_FP;
314 var BI_FV;
315 var BI_F1;
316 var BI_F2;
317
318 // JavaScript engine analysis
319 var canary = 0xdeadbeefcafe;
320 var j_lm = ((canary&0xffffff)==0xefcafe);
321
322 // (public) Constructor
323 function BigInteger(a,b,c) {
324 this.array = new Array();
325 if(a != null)
326 if("number" == typeof a) this.fromNumber(a,b,c);
327 else if(b == null && "string" != typeof a) this.fromString(a,256);
328 else this.fromString(a,b);
329 }
330
331 // return new, unset BigInteger
332 function nbi() { return new BigInteger(null); }
333
334 // am: Compute w_j += (x*this_i), propagate carries,
335 // c is initial carry, returns final carry.
336 // c < 3*dvalue, x < 2*dvalue, this_i < dvalue
337 // We need to select the fastest one that works in this environment.
338
339 // am1: use a single mult and divide to get the high bits,
340 // max digit bits should be 26 because
341 // max internal value = 2*dvalue^2-2*dvalue (< 2^53)
342 function am1(i,x,w,j,c,n) {
343 var this_array = this.array;
344 var w_array = w.array;
345 /* BEGIN LOOP */
346 while(--n >= 0) {
347 var v = x*this_array[i++]+w_array[j]+c;
348 c = Math.floor(v/0x4000000);
349 w_array[j++] = v&0x3ffffff;
350 }
351 /* END LOOP */
352 return c;
353 }
354
355 // am2 avoids a big mult-and-extract completely.
356 // Max digit bits should be <= 30 because we do bitwise ops
357 // on values up to 2*hdvalue^2-hdvalue-1 (< 2^31)
358 function am2(i,x,w,j,c,n) {
359 var this_array = this.array;
360 var w_array = w.array;
361 var xl = x&0x7fff, xh = x>>15;
362 /* BEGIN LOOP */
363 while(--n >= 0) {
364 var l = this_array[i]&0x7fff;
365 var h = this_array[i++]>>15;
366 var m = xh*l+h*xl;
367 l = xl*l+((m&0x7fff)<<15)+w_array[j]+(c&0x3fffffff);
368 c = (l>>>30)+(m>>>15)+xh*h+(c>>>30);
369 w_array[j++] = l&0x3fffffff;
370 }
371 /* END LOOP */
372 return c;
373 }
374
375 // Alternately, set max digit bits to 28 since some
376 // browsers slow down when dealing with 32-bit numbers.
377 function am3(i,x,w,j,c,n) {
378 var this_array = this.array;
379 var w_array = w.array;
380
381 var xl = x&0x3fff, xh = x>>14;
382 /* BEGIN LOOP */
383 while(--n >= 0) {
384 var l = this_array[i]&0x3fff;
385 var h = this_array[i++]>>14;
386 var m = xh*l+h*xl;
387 l = xl*l+((m&0x3fff)<<14)+w_array[j]+c;
388 c = (l>>28)+(m>>14)+xh*h;
389 w_array[j++] = l&0xfffffff;
390 }
391 /* END LOOP */
392 return c;
393 }
394
395 // This is tailored to VMs with 2-bit tagging. It makes sure
396 // that all the computations stay within the 29 bits available.
397 function am4(i,x,w,j,c,n) {
398 var this_array = this.array;
399 var w_array = w.array;
400
401 var xl = x&0x1fff, xh = x>>13;
402 /* BEGIN LOOP */
403 while(--n >= 0) {
404 var l = this_array[i]&0x1fff;
405 var h = this_array[i++]>>13;
406 var m = xh*l+h*xl;
407 l = xl*l+((m&0x1fff)<<13)+w_array[j]+c;
408 c = (l>>26)+(m>>13)+xh*h;
409 w_array[j++] = l&0x3ffffff;
410 }
411 /* END LOOP */
412 return c;
413 }
414
415 // am3/28 is best for SM, Rhino, but am4/26 is best for v8.
416 // Kestrel (Opera 9.5) gets its best result with am4/26.
417 // IE7 does 9% better with am3/28 than with am4/26.
418 // Firefox (SM) gets 10% faster with am3/28 than with am4/26.
419
420 setupEngine = function(fn, bits) {
421 BigInteger.prototype.am = fn;
422 dbits = bits;
423
424 BI_DB = dbits;
425 BI_DM = ((1<<dbits)-1);
426 BI_DV = (1<<dbits);
427
428 BI_FP = 52;
429 BI_FV = Math.pow(2,BI_FP);
430 BI_F1 = BI_FP-dbits;
431 BI_F2 = 2*dbits-BI_FP;
432 }
433
434
435 // Digit conversions
436 var BI_RM = "0123456789abcdefghijklmnopqrstuvwxyz";
437 var BI_RC = new Array();
438 var rr,vv;
439 rr = "0".charCodeAt(0);
440 /* BEGIN LOOP */
441 for(vv = 0; vv <= 9; ++vv) BI_RC[rr++] = vv;
442 /* END LOOP */
443 rr = "a".charCodeAt(0);
444 /* BEGIN LOOP */
445 for(vv = 10; vv < 36; ++vv) BI_RC[rr++] = vv;
446 /* END LOOP */
447 rr = "A".charCodeAt(0);
448 /* BEGIN LOOP */
449 for(vv = 10; vv < 36; ++vv) BI_RC[rr++] = vv;
450 /* END LOOP */
451
452 function int2char(n) { return BI_RM.charAt(n); }
453 function intAt(s,i) {
454 var c = BI_RC[s.charCodeAt(i)];
455 return (c==null)?-1:c;
456 }
457
458 // (protected) copy this to r
459 function bnpCopyTo(r) {
460 var this_array = this.array;
461 var r_array = r.array;
462
463 /* BEGIN LOOP */
464 for(var i = this.t-1; i >= 0; --i) r_array[i] = this_array[i];
465 /* END LOOP */
466 r.t = this.t;
467 r.s = this.s;
468 }
469
470 // (protected) set from integer value x, -DV <= x < DV
471 function bnpFromInt(x) {
472 var this_array = this.array;
473 this.t = 1;
474 this.s = (x<0)?-1:0;
475 if(x > 0) this_array[0] = x;
476 else if(x < -1) this_array[0] = x+DV;
477 else this.t = 0;
478 }
479
480 // return bigint initialized to value
481 function nbv(i) { var r = nbi(); r.fromInt(i); return r; }
482
483 // (protected) set from string and radix
484 function bnpFromString(s,b) {
485 var this_array = this.array;
486 var k;
487 if(b == 16) k = 4;
488 else if(b == 8) k = 3;
489 else if(b == 256) k = 8; // byte array
490 else if(b == 2) k = 1;
491 else if(b == 32) k = 5;
492 else if(b == 4) k = 2;
493 else { this.fromRadix(s,b); return; }
494 this.t = 0;
495 this.s = 0;
496 var i = s.length, mi = false, sh = 0;
497 /* BEGIN LOOP */
498 while(--i >= 0) {
499 var x = (k==8)?s[i]&0xff:intAt(s,i);
500 if(x < 0) {
501 if(s.charAt(i) == "-") mi = true;
502 continue;
503 }
504 mi = false;
505 if(sh == 0)
506 this_array[this.t++] = x;
507 else if(sh+k > BI_DB) {
508 this_array[this.t-1] |= (x&((1<<(BI_DB-sh))-1))<<sh;
509 this_array[this.t++] = (x>>(BI_DB-sh));
510 }
511 else
512 this_array[this.t-1] |= x<<sh;
513 sh += k;
514 if(sh >= BI_DB) sh -= BI_DB;
515 }
516 /* END LOOP */
517 if(k == 8 && (s[0]&0x80) != 0) {
518 this.s = -1;
519 if(sh > 0) this_array[this.t-1] |= ((1<<(BI_DB-sh))-1)<<sh;
520 }
521 this.clamp();
522 if(mi) BigInteger.ZERO.subTo(this,this);
523 }
524
525 // (protected) clamp off excess high words
526 function bnpClamp() {
527 var this_array = this.array;
528 var c = this.s&BI_DM;
529 /* BEGIN LOOP */
530 while(this.t > 0 && this_array[this.t-1] == c) --this.t;
531 /* END LOOP */
532 }
533
534 // (public) return string representation in given radix
535 function bnToString(b) {
536 var this_array = this.array;
537 if(this.s < 0) return "-"+this.negate().toString(b);
538 var k;
539 if(b == 16) k = 4;
540 else if(b == 8) k = 3;
541 else if(b == 2) k = 1;
542 else if(b == 32) k = 5;
543 else if(b == 4) k = 2;
544 else return this.toRadix(b);
545 var km = (1<<k)-1, d, m = false, r = "", i = this.t;
546 var p = BI_DB-(i*BI_DB)%k;
547 if(i-- > 0) {
548 if(p < BI_DB && (d = this_array[i]>>p) > 0) { m = true; r = int2char(d); }
549 /* BEGIN LOOP */
550 while(i >= 0) {
551 if(p < k) {
552 d = (this_array[i]&((1<<p)-1))<<(k-p);
553 d |= this_array[--i]>>(p+=BI_DB-k);
554 }
555 else {
556 d = (this_array[i]>>(p-=k))&km;
557 if(p <= 0) { p += BI_DB; --i; }
558 }
559 if(d > 0) m = true;
560 if(m) r += int2char(d);
561 }
562 /* END LOOP */
563 }
564 return m?r:"0";
565 }
566
567 // (public) -this
568 function bnNegate() { var r = nbi(); BigInteger.ZERO.subTo(this,r); return r; }
569
570 // (public) |this|
571 function bnAbs() { return (this.s<0)?this.negate():this; }
572
573 // (public) return + if this > a, - if this < a, 0 if equal
574 function bnCompareTo(a) {
575 var this_array = this.array;
576 var a_array = a.array;
577
578 var r = this.s-a.s;
579 if(r != 0) return r;
580 var i = this.t;
581 r = i-a.t;
582 if(r != 0) return r;
583 /* BEGIN LOOP */
584 while(--i >= 0) if((r=this_array[i]-a_array[i]) != 0) return r;
585 /* END LOOP */
586 return 0;
587 }
588
589 // returns bit length of the integer x
590 function nbits(x) {
591 var r = 1, t;
592 if((t=x>>>16) != 0) { x = t; r += 16; }
593 if((t=x>>8) != 0) { x = t; r += 8; }
594 if((t=x>>4) != 0) { x = t; r += 4; }
595 if((t=x>>2) != 0) { x = t; r += 2; }
596 if((t=x>>1) != 0) { x = t; r += 1; }
597 return r;
598 }
599
600 // (public) return the number of bits in "this"
601 function bnBitLength() {
602 var this_array = this.array;
603 if(this.t <= 0) return 0;
604 return BI_DB*(this.t-1)+nbits(this_array[this.t-1]^(this.s&BI_DM));
605 }
606
607 // (protected) r = this << n*DB
608 function bnpDLShiftTo(n,r) {
609 var this_array = this.array;
610 var r_array = r.array;
611 var i;
612 /* BEGIN LOOP */
613 for(i = this.t-1; i >= 0; --i) r_array[i+n] = this_array[i];
614 /* END LOOP */
615 /* BEGIN LOOP */
616 for(i = n-1; i >= 0; --i) r_array[i] = 0;
617 /* END LOOP */
618 r.t = this.t+n;
619 r.s = this.s;
620 }
621
622 // (protected) r = this >> n*DB
623 function bnpDRShiftTo(n,r) {
624 var this_array = this.array;
625 var r_array = r.array;
626 /* BEGIN LOOP */
627 for(var i = n; i < this.t; ++i) r_array[i-n] = this_array[i];
628 /* END LOOP */
629 r.t = Math.max(this.t-n,0);
630 r.s = this.s;
631 }
632
633 // (protected) r = this << n
634 function bnpLShiftTo(n,r) {
635 var this_array = this.array;
636 var r_array = r.array;
637 var bs = n%BI_DB;
638 var cbs = BI_DB-bs;
639 var bm = (1<<cbs)-1;
640 var ds = Math.floor(n/BI_DB), c = (this.s<<bs)&BI_DM, i;
641 /* BEGIN LOOP */
642 for(i = this.t-1; i >= 0; --i) {
643 r_array[i+ds+1] = (this_array[i]>>cbs)|c;
644 c = (this_array[i]&bm)<<bs;
645 }
646 /* END LOOP */
647 /* BEGIN LOOP */
648 for(i = ds-1; i >= 0; --i) r_array[i] = 0;
649 /* END LOOP */
650 r_array[ds] = c;
651 r.t = this.t+ds+1;
652 r.s = this.s;
653 r.clamp();
654 }
655
656 // (protected) r = this >> n
657 function bnpRShiftTo(n,r) {
658 var this_array = this.array;
659 var r_array = r.array;
660 r.s = this.s;
661 var ds = Math.floor(n/BI_DB);
662 if(ds >= this.t) { r.t = 0; return; }
663 var bs = n%BI_DB;
664 var cbs = BI_DB-bs;
665 var bm = (1<<bs)-1;
666 r_array[0] = this_array[ds]>>bs;
667 /* BEGIN LOOP */
668 for(var i = ds+1; i < this.t; ++i) {
669 r_array[i-ds-1] |= (this_array[i]&bm)<<cbs;
670 r_array[i-ds] = this_array[i]>>bs;
671 }
672 /* END LOOP */
673 if(bs > 0) r_array[this.t-ds-1] |= (this.s&bm)<<cbs;
674 r.t = this.t-ds;
675 r.clamp();
676 }
677
678 // (protected) r = this - a
679 function bnpSubTo(a,r) {
680 var this_array = this.array;
681 var r_array = r.array;
682 var a_array = a.array;
683 var i = 0, c = 0, m = Math.min(a.t,this.t);
684 /* BEGIN LOOP */
685 while(i < m) {
686 c += this_array[i]-a_array[i];
687 r_array[i++] = c&BI_DM;
688 c >>= BI_DB;
689 }
690 /* END LOOP */
691 if(a.t < this.t) {
692 c -= a.s;
693 /* BEGIN LOOP */
694 while(i < this.t) {
695 c += this_array[i];
696 r_array[i++] = c&BI_DM;
697 c >>= BI_DB;
698 }
699 /* END LOOP */
700 c += this.s;
701 }
702 else {
703 c += this.s;
704 /* BEGIN LOOP */
705 while(i < a.t) {
706 c -= a_array[i];
707 r_array[i++] = c&BI_DM;
708 c >>= BI_DB;
709 }
710 /* END LOOP */
711 c -= a.s;
712 }
713 r.s = (c<0)?-1:0;
714 if(c < -1) r_array[i++] = BI_DV+c;
715 else if(c > 0) r_array[i++] = c;
716 r.t = i;
717 r.clamp();
718 }
719
720 // (protected) r = this * a, r != this,a (HAC 14.12)
721 // "this" should be the larger one if appropriate.
722 function bnpMultiplyTo(a,r) {
723 var this_array = this.array;
724 var r_array = r.array;
725 var x = this.abs(), y = a.abs();
726 var y_array = y.array;
727
728 var i = x.t;
729 r.t = i+y.t;
730 /* BEGIN LOOP */
731 while(--i >= 0) r_array[i] = 0;
732 /* END LOOP */
733 /* BEGIN LOOP */
734 for(i = 0; i < y.t; ++i) r_array[i+x.t] = x.am(0,y_array[i],r,i,0,x.t);
735 r.s = 0;
736 r.clamp();
737 if(this.s != a.s) BigInteger.ZERO.subTo(r,r);
738 }
739
740 // (protected) r = this^2, r != this (HAC 14.16)
741 function bnpSquareTo(r) {
742 var x = this.abs();
743 var x_array = x.array;
744 var r_array = r.array;
745
746 var i = r.t = 2*x.t;
747 /* BEGIN LOOP */
748 while(--i >= 0) r_array[i] = 0;
749 /* END LOOP */
750 /* BEGIN LOOP */
751 for(i = 0; i < x.t-1; ++i) {
752 var c = x.am(i,x_array[i],r,2*i,0,1);
753 if((r_array[i+x.t]+=x.am(i+1,2*x_array[i],r,2*i+1,c,x.t-i-1)) >= BI_DV) {
754 r_array[i+x.t] -= BI_DV;
755 r_array[i+x.t+1] = 1;
756 }
757 }
758 /* END LOOP */
759 if(r.t > 0) r_array[r.t-1] += x.am(i,x_array[i],r,2*i,0,1);
760 r.s = 0;
761 r.clamp();
762 }
763
764 // (protected) divide this by m, quotient and remainder to q, r (HAC 14.20)
765 // r != q, this != m. q or r may be null.
766 function bnpDivRemTo(m,q,r) {
767 var pm = m.abs();
768 if(pm.t <= 0) return;
769 var pt = this.abs();
770 if(pt.t < pm.t) {
771 if(q != null) q.fromInt(0);
772 if(r != null) this.copyTo(r);
773 return;
774 }
775 if(r == null) r = nbi();
776 var y = nbi(), ts = this.s, ms = m.s;
777 var pm_array = pm.array;
778 var nsh = BI_DB-nbits(pm_array[pm.t-1]); // normalize modulus
779 if(nsh > 0) { pm.lShiftTo(nsh,y); pt.lShiftTo(nsh,r); }
780 else { pm.copyTo(y); pt.copyTo(r); }
781 var ys = y.t;
782
783 var y_array = y.array;
784 var y0 = y_array[ys-1];
785 if(y0 == 0) return;
786 var yt = y0*(1<<BI_F1)+((ys>1)?y_array[ys-2]>>BI_F2:0);
787 var d1 = BI_FV/yt, d2 = (1<<BI_F1)/yt, e = 1<<BI_F2;
788 var i = r.t, j = i-ys, t = (q==null)?nbi():q;
789 y.dlShiftTo(j,t);
790
791 var r_array = r.array;
792 if(r.compareTo(t) >= 0) {
793 r_array[r.t++] = 1;
794 r.subTo(t,r);
795 }
796 BigInteger.ONE.dlShiftTo(ys,t);
797 t.subTo(y,y); // "negative" y so we can replace sub with am later
798 /* BEGIN LOOP */
799 while(y.t < ys) y_array[y.t++] = 0;
800 /* END LOOP */
801 /* BEGIN LOOP */
802 while(--j >= 0) {
803 // Estimate quotient digit
804 var qd = (r_array[--i]==y0)?BI_DM:Math.floor(r_array[i]*d1+(r_array[i-1]+e)*d2);
805 if((r_array[i]+=y.am(0,qd,r,j,0,ys)) < qd) { // Try it out
806 y.dlShiftTo(j,t);
807 r.subTo(t,r);
808 /* BEGIN LOOP */
809 while(r_array[i] < --qd) r.subTo(t,r);
810 /* END LOOP */
811 }
812 }
813 /* END LOOP */
814 if(q != null) {
815 r.drShiftTo(ys,q);
816 if(ts != ms) BigInteger.ZERO.subTo(q,q);
817 }
818 r.t = ys;
819 r.clamp();
820 if(nsh > 0) r.rShiftTo(nsh,r); // Denormalize remainder
821 if(ts < 0) BigInteger.ZERO.subTo(r,r);
822 }
823
824 // (public) this mod a
825 function bnMod(a) {
826 var r = nbi();
827 this.abs().divRemTo(a,null,r);
828 if(this.s < 0 && r.compareTo(BigInteger.ZERO) > 0) a.subTo(r,r);
829 return r;
830 }
831
832 // Modular reduction using "classic" algorithm
833 function Classic(m) { this.m = m; }
834 function cConvert(x) {
835 if(x.s < 0 || x.compareTo(this.m) >= 0) return x.mod(this.m);
836 else return x;
837 }
838 function cRevert(x) { return x; }
839 function cReduce(x) { x.divRemTo(this.m,null,x); }
840 function cMulTo(x,y,r) { x.multiplyTo(y,r); this.reduce(r); }
841 function cSqrTo(x,r) { x.squareTo(r); this.reduce(r); }
842
843 Classic.prototype.convert = cConvert;
844 Classic.prototype.revert = cRevert;
845 Classic.prototype.reduce = cReduce;
846 Classic.prototype.mulTo = cMulTo;
847 Classic.prototype.sqrTo = cSqrTo;
848
849 // (protected) return "-1/this % 2^DB"; useful for Mont. reduction
850 // justification:
851 // xy == 1 (mod m)
852 // xy = 1+km
853 // xy(2-xy) = (1+km)(1-km)
854 // x[y(2-xy)] = 1-k^2m^2
855 // x[y(2-xy)] == 1 (mod m^2)
856 // if y is 1/x mod m, then y(2-xy) is 1/x mod m^2
857 // should reduce x and y(2-xy) by m^2 at each step to keep size bounded.
858 // JS multiply "overflows" differently from C/C++, so care is needed here.
859 function bnpInvDigit() {
860 var this_array = this.array;
861 if(this.t < 1) return 0;
862 var x = this_array[0];
863 if((x&1) == 0) return 0;
864 var y = x&3; // y == 1/x mod 2^2
865 y = (y*(2-(x&0xf)*y))&0xf; // y == 1/x mod 2^4
866 y = (y*(2-(x&0xff)*y))&0xff; // y == 1/x mod 2^8
867 y = (y*(2-(((x&0xffff)*y)&0xffff)))&0xffff; // y == 1/x mod 2^16
868 // last step - calculate inverse mod DV directly;
869 // assumes 16 < DB <= 32 and assumes ability to handle 48-bit ints
870 y = (y*(2-x*y%BI_DV))%BI_DV; // y == 1/x mod 2^dbits
871 // we really want the negative inverse, and -DV < y < DV
872 return (y>0)?BI_DV-y:-y;
873 }
874
875 // Montgomery reduction
876 function Montgomery(m) {
877 this.m = m;
878 this.mp = m.invDigit();
879 this.mpl = this.mp&0x7fff;
880 this.mph = this.mp>>15;
881 this.um = (1<<(BI_DB-15))-1;
882 this.mt2 = 2*m.t;
883 }
884
885 // xR mod m
886 function montConvert(x) {
887 var r = nbi();
888 x.abs().dlShiftTo(this.m.t,r);
889 r.divRemTo(this.m,null,r);
890 if(x.s < 0 && r.compareTo(BigInteger.ZERO) > 0) this.m.subTo(r,r);
891 return r;
892 }
893
894 // x/R mod m
895 function montRevert(x) {
896 var r = nbi();
897 x.copyTo(r);
898 this.reduce(r);
899 return r;
900 }
901
902 // x = x/R mod m (HAC 14.32)
903 function montReduce(x) {
904 var x_array = x.array;
905 /* BEGIN LOOP */
906 while(x.t <= this.mt2) // pad x so am has enough room later
907 x_array[x.t++] = 0;
908 /* END LOOP */
909 /* BEGIN LOOP */
910 for(var i = 0; i < this.m.t; ++i) {
911 // faster way of calculating u0 = x[i]*mp mod DV
912 var j = x_array[i]&0x7fff;
913 var u0 = (j*this.mpl+(((j*this.mph+(x_array[i]>>15)*this.mpl)&this.um)<<15))&BI_DM;
914 // use am to combine the multiply-shift-add into one call
915 j = i+this.m.t;
916 x_array[j] += this.m.am(0,u0,x,i,0,this.m.t);
917 // propagate carry
918 /* BEGIN LOOP */
919 while(x_array[j] >= BI_DV) { x_array[j] -= BI_DV; x_array[++j]++; }
920 /* BEGIN LOOP */
921 }
922 /* END LOOP */
923 x.clamp();
924 x.drShiftTo(this.m.t,x);
925 if(x.compareTo(this.m) >= 0) x.subTo(this.m,x);
926 }
927
928 // r = "x^2/R mod m"; x != r
929 function montSqrTo(x,r) { x.squareTo(r); this.reduce(r); }
930
931 // r = "xy/R mod m"; x,y != r
932 function montMulTo(x,y,r) { x.multiplyTo(y,r); this.reduce(r); }
933
934 Montgomery.prototype.convert = montConvert;
935 Montgomery.prototype.revert = montRevert;
936 Montgomery.prototype.reduce = montReduce;
937 Montgomery.prototype.mulTo = montMulTo;
938 Montgomery.prototype.sqrTo = montSqrTo;
939
940 // (protected) true iff this is even
941 function bnpIsEven() {
942 var this_array = this.array;
943 return ((this.t>0)?(this_array[0]&1):this.s) == 0;
944 }
945
946 // (protected) this^e, e < 2^32, doing sqr and mul with "r" (HAC 14.79)
947 function bnpExp(e,z) {
948 if(e > 0xffffffff || e < 1) return BigInteger.ONE;
949 var r = nbi(), r2 = nbi(), g = z.convert(this), i = nbits(e)-1;
950 g.copyTo(r);
951 /* BEGIN LOOP */
952 while(--i >= 0) {
953 z.sqrTo(r,r2);
954 if((e&(1<<i)) > 0) z.mulTo(r2,g,r);
955 else { var t = r; r = r2; r2 = t; }
956 }
957 /* END LOOP */
958 return z.revert(r);
959 }
960
961 // (public) this^e % m, 0 <= e < 2^32
962 function bnModPowInt(e,m) {
963 var z;
964 if(e < 256 || m.isEven()) z = new Classic(m); else z = new Montgomery(m);
965 return this.exp(e,z);
966 }
967
968 // protected
969 BigInteger.prototype.copyTo = bnpCopyTo;
970 BigInteger.prototype.fromInt = bnpFromInt;
971 BigInteger.prototype.fromString = bnpFromString;
972 BigInteger.prototype.clamp = bnpClamp;
973 BigInteger.prototype.dlShiftTo = bnpDLShiftTo;
974 BigInteger.prototype.drShiftTo = bnpDRShiftTo;
975 BigInteger.prototype.lShiftTo = bnpLShiftTo;
976 BigInteger.prototype.rShiftTo = bnpRShiftTo;
977 BigInteger.prototype.subTo = bnpSubTo;
978 BigInteger.prototype.multiplyTo = bnpMultiplyTo;
979 BigInteger.prototype.squareTo = bnpSquareTo;
980 BigInteger.prototype.divRemTo = bnpDivRemTo;
981 BigInteger.prototype.invDigit = bnpInvDigit;
982 BigInteger.prototype.isEven = bnpIsEven;
983 BigInteger.prototype.exp = bnpExp;
984
985 // public
986 BigInteger.prototype.toString = bnToString;
987 BigInteger.prototype.negate = bnNegate;
988 BigInteger.prototype.abs = bnAbs;
989 BigInteger.prototype.compareTo = bnCompareTo;
990 BigInteger.prototype.bitLength = bnBitLength;
991 BigInteger.prototype.mod = bnMod;
992 BigInteger.prototype.modPowInt = bnModPowInt;
993
994 // "constants"
995 BigInteger.ZERO = nbv(0);
996 BigInteger.ONE = nbv(1);
997 // Copyright (c) 2005 Tom Wu
998 // All Rights Reserved.
999 // See "LICENSE" for details.
1000
1001 // Extended JavaScript BN functions, required for RSA private ops.
1002
1003 // (public)
1004 function bnClone() { var r = nbi(); this.copyTo(r); return r; }
1005
1006 // (public) return value as integer
1007 function bnIntValue() {
1008 var this_array = this.array;
1009 if(this.s < 0) {
1010 if(this.t == 1) return this_array[0]-BI_DV;
1011 else if(this.t == 0) return -1;
1012 }
1013 else if(this.t == 1) return this_array[0];
1014 else if(this.t == 0) return 0;
1015 // assumes 16 < DB < 32
1016 return ((this_array[1]&((1<<(32-BI_DB))-1))<<BI_DB)|this_array[0];
1017 }
1018
1019 // (public) return value as byte
1020 function bnByteValue() {
1021 var this_array = this.array;
1022 return (this.t==0)?this.s:(this_array[0]<<24)>>24;
1023 }
1024
1025 // (public) return value as short (assumes DB>=16)
1026 function bnShortValue() {
1027 var this_array = this.array;
1028 return (this.t==0)?this.s:(this_array[0]<<16)>>16;
1029 }
1030
1031 // (protected) return x s.t. r^x < DV
1032 function bnpChunkSize(r) { return Math.floor(Math.LN2*BI_DB/Math.log(r)); }
1033
1034 // (public) 0 if this == 0, 1 if this > 0
1035 function bnSigNum() {
1036 var this_array = this.array;
1037 if(this.s < 0) return -1;
1038 else if(this.t <= 0 || (this.t == 1 && this_array[0] <= 0)) return 0;
1039 else return 1;
1040 }
1041
1042 // (protected) convert to radix string
1043 function bnpToRadix(b) {
1044 if(b == null) b = 10;
1045 if(this.signum() == 0 || b < 2 || b > 36) return "0";
1046 var cs = this.chunkSize(b);
1047 var a = Math.pow(b,cs);
1048 var d = nbv(a), y = nbi(), z = nbi(), r = "";
1049 this.divRemTo(d,y,z);
1050 /* BEGIN LOOP */
1051 while(y.signum() > 0) {
1052 r = (a+z.intValue()).toString(b).substr(1) + r;
1053 y.divRemTo(d,y,z);
1054 }
1055 /* END LOOP */
1056 return z.intValue().toString(b) + r;
1057 }
1058
1059 // (protected) convert from radix string
1060 function bnpFromRadix(s,b) {
1061 this.fromInt(0);
1062 if(b == null) b = 10;
1063 var cs = this.chunkSize(b);
1064 var d = Math.pow(b,cs), mi = false, j = 0, w = 0;
1065 /* BEGIN LOOP */
1066 for(var i = 0; i < s.length; ++i) {
1067 var x = intAt(s,i);
1068 if(x < 0) {
1069 if(s.charAt(i) == "-" && this.signum() == 0) mi = true;
1070 continue;
1071 }
1072 w = b*w+x;
1073 if(++j >= cs) {
1074 this.dMultiply(d);
1075 this.dAddOffset(w,0);
1076 j = 0;
1077 w = 0;
1078 }
1079 }
1080 /* END LOOP */
1081 if(j > 0) {
1082 this.dMultiply(Math.pow(b,j));
1083 this.dAddOffset(w,0);
1084 }
1085 if(mi) BigInteger.ZERO.subTo(this,this);
1086 }
1087
1088 // (protected) alternate constructor
1089 function bnpFromNumber(a,b,c) {
1090 if("number" == typeof b) {
1091 // new BigInteger(int,int,RNG)
1092 if(a < 2) this.fromInt(1);
1093 else {
1094 this.fromNumber(a,c);
1095 if(!this.testBit(a-1)) // force MSB set
1096 this.bitwiseTo(BigInteger.ONE.shiftLeft(a-1),op_or,this);
1097 if(this.isEven()) this.dAddOffset(1,0); // force odd
1098 /* BEGIN LOOP */
1099 while(!this.isProbablePrime(b)) {
1100 this.dAddOffset(2,0);
1101 if(this.bitLength() > a) this.subTo(BigInteger.ONE.shiftLeft(a-1),this);
1102 }
1103 /* END LOOP */
1104 }
1105 }
1106 else {
1107 // new BigInteger(int,RNG)
1108 var x = new Array(), t = a&7;
1109 x.length = (a>>3)+1;
1110 b.nextBytes(x);
1111 if(t > 0) x[0] &= ((1<<t)-1); else x[0] = 0;
1112 this.fromString(x,256);
1113 }
1114 }
1115
1116 // (public) convert to bigendian byte array
1117 function bnToByteArray() {
1118 var this_array = this.array;
1119 var i = this.t, r = new Array();
1120 r[0] = this.s;
1121 var p = BI_DB-(i*BI_DB)%8, d, k = 0;
1122 if(i-- > 0) {
1123 if(p < BI_DB && (d = this_array[i]>>p) != (this.s&BI_DM)>>p)
1124 r[k++] = d|(this.s<<(BI_DB-p));
1125 /* BEGIN LOOP */
1126 while(i >= 0) {
1127 if(p < 8) {
1128 d = (this_array[i]&((1<<p)-1))<<(8-p);
1129 d |= this_array[--i]>>(p+=BI_DB-8);
1130 }
1131 else {
1132 d = (this_array[i]>>(p-=8))&0xff;
1133 if(p <= 0) { p += BI_DB; --i; }
1134 }
1135 if((d&0x80) != 0) d |= -256;
1136 if(k == 0 && (this.s&0x80) != (d&0x80)) ++k;
1137 if(k > 0 || d != this.s) r[k++] = d;
1138 }
1139 /* END LOOP */
1140 }
1141 return r;
1142 }
1143
1144 function bnEquals(a) { return(this.compareTo(a)==0); }
1145 function bnMin(a) { return(this.compareTo(a)<0)?this:a; }
1146 function bnMax(a) { return(this.compareTo(a)>0)?this:a; }
1147
1148 // (protected) r = this op a (bitwise)
1149 function bnpBitwiseTo(a,op,r) {
1150 var this_array = this.array;
1151 var a_array = a.array;
1152 var r_array = r.array;
1153 var i, f, m = Math.min(a.t,this.t);
1154 /* BEGIN LOOP */
1155 for(i = 0; i < m; ++i) r_array[i] = op(this_array[i],a_array[i]);
1156 /* END LOOP */
1157 if(a.t < this.t) {
1158 f = a.s&BI_DM;
1159 /* BEGIN LOOP */
1160 for(i = m; i < this.t; ++i) r_array[i] = op(this_array[i],f);
1161 /* END LOOP */
1162 r.t = this.t;
1163 }
1164 else {
1165 f = this.s&BI_DM;
1166 /* BEGIN LOOP */
1167 for(i = m; i < a.t; ++i) r_array[i] = op(f,a_array[i]);
1168 /* END LOOP */
1169 r.t = a.t;
1170 }
1171 r.s = op(this.s,a.s);
1172 r.clamp();
1173 }
1174
1175 // (public) this & a
1176 function op_and(x,y) { return x&y; }
1177 function bnAnd(a) { var r = nbi(); this.bitwiseTo(a,op_and,r); return r; }
1178
1179 // (public) this | a
1180 function op_or(x,y) { return x|y; }
1181 function bnOr(a) { var r = nbi(); this.bitwiseTo(a,op_or,r); return r; }
1182
1183 // (public) this ^ a
1184 function op_xor(x,y) { return x^y; }
1185 function bnXor(a) { var r = nbi(); this.bitwiseTo(a,op_xor,r); return r; }
1186
1187 // (public) this & ~a
1188 function op_andnot(x,y) { return x&~y; }
1189 function bnAndNot(a) { var r = nbi(); this.bitwiseTo(a,op_andnot,r); return r; }
1190
1191 // (public) ~this
1192 function bnNot() {
1193 var this_array = this.array;
1194 var r = nbi();
1195 var r_array = r.array;
1196
1197 /* BEGIN LOOP */
1198 for(var i = 0; i < this.t; ++i) r_array[i] = BI_DM&~this_array[i];
1199 /* END LOOP */
1200 r.t = this.t;
1201 r.s = ~this.s;
1202 return r;
1203 }
1204
1205 // (public) this << n
1206 function bnShiftLeft(n) {
1207 var r = nbi();
1208 if(n < 0) this.rShiftTo(-n,r); else this.lShiftTo(n,r);
1209 return r;
1210 }
1211
1212 // (public) this >> n
1213 function bnShiftRight(n) {
1214 var r = nbi();
1215 if(n < 0) this.lShiftTo(-n,r); else this.rShiftTo(n,r);
1216 return r;
1217 }
1218
1219 // return index of lowest 1-bit in x, x < 2^31
1220 function lbit(x) {
1221 if(x == 0) return -1;
1222 var r = 0;
1223 if((x&0xffff) == 0) { x >>= 16; r += 16; }
1224 if((x&0xff) == 0) { x >>= 8; r += 8; }
1225 if((x&0xf) == 0) { x >>= 4; r += 4; }
1226 if((x&3) == 0) { x >>= 2; r += 2; }
1227 if((x&1) == 0) ++r;
1228 return r;
1229 }
1230
1231 // (public) returns index of lowest 1-bit (or -1 if none)
1232 function bnGetLowestSetBit() {
1233 var this_array = this.array;
1234 /* BEGIN LOOP */
1235 for(var i = 0; i < this.t; ++i)
1236 if(this_array[i] != 0) return i*BI_DB+lbit(this_array[i]);
1237 /* END LOOP */
1238 if(this.s < 0) return this.t*BI_DB;
1239 return -1;
1240 }
1241
1242 // return number of 1 bits in x
1243 function cbit(x) {
1244 var r = 0;
1245 /* BEGIN LOOP */
1246 while(x != 0) { x &= x-1; ++r; }
1247 /* END LOOP */
1248 return r;
1249 }
1250
1251 // (public) return number of set bits
1252 function bnBitCount() {
1253 var r = 0, x = this.s&BI_DM;
1254 /* BEGIN LOOP */
1255 for(var i = 0; i < this.t; ++i) r += cbit(this_array[i]^x);
1256 /* END LOOP */
1257 return r;
1258 }
1259
1260 // (public) true iff nth bit is set
1261 function bnTestBit(n) {
1262 var this_array = this.array;
1263 var j = Math.floor(n/BI_DB);
1264 if(j >= this.t) return(this.s!=0);
1265 return((this_array[j]&(1<<(n%BI_DB)))!=0);
1266 }
1267
1268 // (protected) this op (1<<n)
1269 function bnpChangeBit(n,op) {
1270 var r = BigInteger.ONE.shiftLeft(n);
1271 this.bitwiseTo(r,op,r);
1272 return r;
1273 }
1274
1275 // (public) this | (1<<n)
1276 function bnSetBit(n) { return this.changeBit(n,op_or); }
1277
1278 // (public) this & ~(1<<n)
1279 function bnClearBit(n) { return this.changeBit(n,op_andnot); }
1280
1281 // (public) this ^ (1<<n)
1282 function bnFlipBit(n) { return this.changeBit(n,op_xor); }
1283
1284 // (protected) r = this + a
1285 function bnpAddTo(a,r) {
1286 var this_array = this.array;
1287 var a_array = a.array;
1288 var r_array = r.array;
1289 var i = 0, c = 0, m = Math.min(a.t,this.t);
1290 /* BEGIN LOOP */
1291 while(i < m) {
1292 c += this_array[i]+a_array[i];
1293 r_array[i++] = c&BI_DM;
1294 c >>= BI_DB;
1295 }
1296 /* END LOOP */
1297 if(a.t < this.t) {
1298 c += a.s;
1299 /* BEGIN LOOP */
1300 while(i < this.t) {
1301 c += this_array[i];
1302 r_array[i++] = c&BI_DM;
1303 c >>= BI_DB;
1304 }
1305 /* END LOOP */
1306 c += this.s;
1307 }
1308 else {
1309 c += this.s;
1310 /* BEGIN LOOP */
1311 while(i < a.t) {
1312 c += a_array[i];
1313 r_array[i++] = c&BI_DM;
1314 c >>= BI_DB;
1315 }
1316 /* END LOOP */
1317 c += a.s;
1318 }
1319 r.s = (c<0)?-1:0;
1320 if(c > 0) r_array[i++] = c;
1321 else if(c < -1) r_array[i++] = BI_DV+c;
1322 r.t = i;
1323 r.clamp();
1324 }
1325
1326 // (public) this + a
1327 function bnAdd(a) { var r = nbi(); this.addTo(a,r); return r; }
1328
1329 // (public) this - a
1330 function bnSubtract(a) { var r = nbi(); this.subTo(a,r); return r; }
1331
1332 // (public) this * a
1333 function bnMultiply(a) { var r = nbi(); this.multiplyTo(a,r); return r; }
1334
1335 // (public) this / a
1336 function bnDivide(a) { var r = nbi(); this.divRemTo(a,r,null); return r; }
1337
1338 // (public) this % a
1339 function bnRemainder(a) { var r = nbi(); this.divRemTo(a,null,r); return r; }
1340
1341 // (public) [this/a,this%a]
1342 function bnDivideAndRemainder(a) {
1343 var q = nbi(), r = nbi();
1344 this.divRemTo(a,q,r);
1345 return new Array(q,r);
1346 }
1347
1348 // (protected) this *= n, this >= 0, 1 < n < DV
1349 function bnpDMultiply(n) {
1350 var this_array = this.array;
1351 this_array[this.t] = this.am(0,n-1,this,0,0,this.t);
1352 ++this.t;
1353 this.clamp();
1354 }
1355
1356 // (protected) this += n << w words, this >= 0
1357 function bnpDAddOffset(n,w) {
1358 var this_array = this.array;
1359 /* BEGIN LOOP */
1360 while(this.t <= w) this_array[this.t++] = 0;
1361 /* END LOOP */
1362 this_array[w] += n;
1363 /* BEGIN LOOP */
1364 while(this_array[w] >= BI_DV) {
1365 this_array[w] -= BI_DV;
1366 if(++w >= this.t) this_array[this.t++] = 0;
1367 ++this_array[w];
1368 }
1369 /* END LOOP */
1370 }
1371
1372 // A "null" reducer
1373 function NullExp() {}
1374 function nNop(x) { return x; }
1375 function nMulTo(x,y,r) { x.multiplyTo(y,r); }
1376 function nSqrTo(x,r) { x.squareTo(r); }
1377
1378 NullExp.prototype.convert = nNop;
1379 NullExp.prototype.revert = nNop;
1380 NullExp.prototype.mulTo = nMulTo;
1381 NullExp.prototype.sqrTo = nSqrTo;
1382
1383 // (public) this^e
1384 function bnPow(e) { return this.exp(e,new NullExp()); }
1385
1386 // (protected) r = lower n words of "this * a", a.t <= n
1387 // "this" should be the larger one if appropriate.
1388 function bnpMultiplyLowerTo(a,n,r) {
1389 var r_array = r.array;
1390 var a_array = a.array;
1391 var i = Math.min(this.t+a.t,n);
1392 r.s = 0; // assumes a,this >= 0
1393 r.t = i;
1394 /* BEGIN LOOP */
1395 while(i > 0) r_array[--i] = 0;
1396 /* END LOOP */
1397 var j;
1398 /* BEGIN LOOP */
1399 for(j = r.t-this.t; i < j; ++i) r_array[i+this.t] = this.am(0,a_array[i],r,i,0,this.t);
1400 /* END LOOP */
1401 /* BEGIN LOOP */
1402 for(j = Math.min(a.t,n); i < j; ++i) this.am(0,a_array[i],r,i,0,n-i);
1403 /* END LOOP */
1404 r.clamp();
1405 }
1406
1407 // (protected) r = "this * a" without lower n words, n > 0
1408 // "this" should be the larger one if appropriate.
1409 function bnpMultiplyUpperTo(a,n,r) {
1410 var r_array = r.array;
1411 var a_array = a.array;
1412 --n;
1413 var i = r.t = this.t+a.t-n;
1414 r.s = 0; // assumes a,this >= 0
1415 /* BEGIN LOOP */
1416 while(--i >= 0) r_array[i] = 0;
1417 /* END LOOP */
1418 /* BEGIN LOOP */
1419 for(i = Math.max(n-this.t,0); i < a.t; ++i)
1420 r_array[this.t+i-n] = this.am(n-i,a_array[i],r,0,0,this.t+i-n);
1421 /* END LOOP */
1422 r.clamp();
1423 r.drShiftTo(1,r);
1424 }
1425
1426 // Barrett modular reduction
1427 function Barrett(m) {
1428 // setup Barrett
1429 this.r2 = nbi();
1430 this.q3 = nbi();
1431 BigInteger.ONE.dlShiftTo(2*m.t,this.r2);
1432 this.mu = this.r2.divide(m);
1433 this.m = m;
1434 }
1435
1436 function barrettConvert(x) {
1437 if(x.s < 0 || x.t > 2*this.m.t) return x.mod(this.m);
1438 else if(x.compareTo(this.m) < 0) return x;
1439 else { var r = nbi(); x.copyTo(r); this.reduce(r); return r; }
1440 }
1441
1442 function barrettRevert(x) { return x; }
1443
1444 // x = x mod m (HAC 14.42)
1445 function barrettReduce(x) {
1446 x.drShiftTo(this.m.t-1,this.r2);
1447 if(x.t > this.m.t+1) { x.t = this.m.t+1; x.clamp(); }
1448 this.mu.multiplyUpperTo(this.r2,this.m.t+1,this.q3);
1449 this.m.multiplyLowerTo(this.q3,this.m.t+1,this.r2);
1450 /* BEGIN LOOP */
1451 while(x.compareTo(this.r2) < 0) x.dAddOffset(1,this.m.t+1);
1452 /* END LOOP */
1453 x.subTo(this.r2,x);
1454 /* BEGIN LOOP */
1455 while(x.compareTo(this.m) >= 0) x.subTo(this.m,x);
1456 /* END LOOP */
1457 }
1458
1459 // r = x^2 mod m; x != r
1460 function barrettSqrTo(x,r) { x.squareTo(r); this.reduce(r); }
1461
1462 // r = x*y mod m; x,y != r
1463 function barrettMulTo(x,y,r) { x.multiplyTo(y,r); this.reduce(r); }
1464
1465 Barrett.prototype.convert = barrettConvert;
1466 Barrett.prototype.revert = barrettRevert;
1467 Barrett.prototype.reduce = barrettReduce;
1468 Barrett.prototype.mulTo = barrettMulTo;
1469 Barrett.prototype.sqrTo = barrettSqrTo;
1470
1471 // (public) this^e % m (HAC 14.85)
1472 function bnModPow(e,m) {
1473 var e_array = e.array;
1474 var i = e.bitLength(), k, r = nbv(1), z;
1475 if(i <= 0) return r;
1476 else if(i < 18) k = 1;
1477 else if(i < 48) k = 3;
1478 else if(i < 144) k = 4;
1479 else if(i < 768) k = 5;
1480 else k = 6;
1481 if(i < 8)
1482 z = new Classic(m);
1483 else if(m.isEven())
1484 z = new Barrett(m);
1485 else
1486 z = new Montgomery(m);
1487
1488 // precomputation
1489 var g = new Array(), n = 3, k1 = k-1, km = (1<<k)-1;
1490 g[1] = z.convert(this);
1491 if(k > 1) {
1492 var g2 = nbi();
1493 z.sqrTo(g[1],g2);
1494 /* BEGIN LOOP */
1495 while(n <= km) {
1496 g[n] = nbi();
1497 z.mulTo(g2,g[n-2],g[n]);
1498 n += 2;
1499 }
1500 /* END LOOP */
1501 }
1502
1503 var j = e.t-1, w, is1 = true, r2 = nbi(), t;
1504 i = nbits(e_array[j])-1;
1505 /* BEGIN LOOP */
1506 while(j >= 0) {
1507 if(i >= k1) w = (e_array[j]>>(i-k1))&km;
1508 else {
1509 w = (e_array[j]&((1<<(i+1))-1))<<(k1-i);
1510 if(j > 0) w |= e_array[j-1]>>(BI_DB+i-k1);
1511 }
1512
1513 n = k;
1514 /* BEGIN LOOP */
1515 while((w&1) == 0) { w >>= 1; --n; }
1516 /* END LOOP */
1517 if((i -= n) < 0) { i += BI_DB; --j; }
1518 if(is1) { // ret == 1, don't bother squaring or multiplying it
1519 g[w].copyTo(r);
1520 is1 = false;
1521 }
1522 else {
1523 /* BEGIN LOOP */
1524 while(n > 1) { z.sqrTo(r,r2); z.sqrTo(r2,r); n -= 2; }
1525 /* END LOOP */
1526 if(n > 0) z.sqrTo(r,r2); else { t = r; r = r2; r2 = t; }
1527 z.mulTo(r2,g[w],r);
1528 }
1529
1530 /* BEGIN LOOP */
1531 while(j >= 0 && (e_array[j]&(1<<i)) == 0) {
1532 z.sqrTo(r,r2); t = r; r = r2; r2 = t;
1533 if(--i < 0) { i = BI_DB-1; --j; }
1534 }
1535 /* END LOOP */
1536 }
1537 /* END LOOP */
1538 return z.revert(r);
1539 }
1540
1541 // (public) gcd(this,a) (HAC 14.54)
1542 function bnGCD(a) {
1543 var x = (this.s<0)?this.negate():this.clone();
1544 var y = (a.s<0)?a.negate():a.clone();
1545 if(x.compareTo(y) < 0) { var t = x; x = y; y = t; }
1546 var i = x.getLowestSetBit(), g = y.getLowestSetBit();
1547 if(g < 0) return x;
1548 if(i < g) g = i;
1549 if(g > 0) {
1550 x.rShiftTo(g,x);
1551 y.rShiftTo(g,y);
1552 }
1553 /* BEGIN LOOP */
1554 while(x.signum() > 0) {
1555 if((i = x.getLowestSetBit()) > 0) x.rShiftTo(i,x);
1556 if((i = y.getLowestSetBit()) > 0) y.rShiftTo(i,y);
1557 if(x.compareTo(y) >= 0) {
1558 x.subTo(y,x);
1559 x.rShiftTo(1,x);
1560 }
1561 else {
1562 y.subTo(x,y);
1563 y.rShiftTo(1,y);
1564 }
1565 }
1566 /* END LOOP */
1567 if(g > 0) y.lShiftTo(g,y);
1568 return y;
1569 }
1570
1571 // (protected) this % n, n < 2^26
1572 function bnpModInt(n) {
1573 var this_array = this.array;
1574 if(n <= 0) return 0;
1575 var d = BI_DV%n, r = (this.s<0)?n-1:0;
1576 if(this.t > 0)
1577 if(d == 0) r = this_array[0]%n;
1578 else for(var i = this.t-1; i >= 0; --i) r = (d*r+this_array[i])%n;
1579 return r;
1580 }
1581
1582 // (public) 1/this % m (HAC 14.61)
1583 function bnModInverse(m) {
1584 var ac = m.isEven();
1585 if((this.isEven() && ac) || m.signum() == 0) return BigInteger.ZERO;
1586 var u = m.clone(), v = this.clone();
1587 var a = nbv(1), b = nbv(0), c = nbv(0), d = nbv(1);
1588 /* BEGIN LOOP */
1589 while(u.signum() != 0) {
1590 /* BEGIN LOOP */
1591 while(u.isEven()) {
1592 u.rShiftTo(1,u);
1593 if(ac) {
1594 if(!a.isEven() || !b.isEven()) { a.addTo(this,a); b.subTo(m,b); }
1595 a.rShiftTo(1,a);
1596 }
1597 else if(!b.isEven()) b.subTo(m,b);
1598 b.rShiftTo(1,b);
1599 }
1600 /* END LOOP */
1601 /* BEGIN LOOP */
1602 while(v.isEven()) {
1603 v.rShiftTo(1,v);
1604 if(ac) {
1605 if(!c.isEven() || !d.isEven()) { c.addTo(this,c); d.subTo(m,d); }
1606 c.rShiftTo(1,c);
1607 }
1608 else if(!d.isEven()) d.subTo(m,d);
1609 d.rShiftTo(1,d);
1610 }
1611 /* END LOOP */
1612 if(u.compareTo(v) >= 0) {
1613 u.subTo(v,u);
1614 if(ac) a.subTo(c,a);
1615 b.subTo(d,b);
1616 }
1617 else {
1618 v.subTo(u,v);
1619 if(ac) c.subTo(a,c);
1620 d.subTo(b,d);
1621 }
1622 }
1623 /* END LOOP */
1624 if(v.compareTo(BigInteger.ONE) != 0) return BigInteger.ZERO;
1625 if(d.compareTo(m) >= 0) return d.subtract(m);
1626 if(d.signum() < 0) d.addTo(m,d); else return d;
1627 if(d.signum() < 0) return d.add(m); else return d;
1628 }
1629
1630 var lowprimes = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509];
1631 var lplim = (1<<26)/lowprimes[lowprimes.length-1];
1632
1633 // (public) test primality with certainty >= 1-.5^t
1634 function bnIsProbablePrime(t) {
1635 var i, x = this.abs();
1636 var x_array = x.array;
1637 if(x.t == 1 && x_array[0] <= lowprimes[lowprimes.length-1]) {
1638 for(i = 0; i < lowprimes.length; ++i)
1639 if(x_array[0] == lowprimes[i]) return true;
1640 return false;
1641 }
1642 if(x.isEven()) return false;
1643 i = 1;
1644 /* BEGIN LOOP */
1645 while(i < lowprimes.length) {
1646 var m = lowprimes[i], j = i+1;
1647 /* BEGIN LOOP */
1648 while(j < lowprimes.length && m < lplim) m *= lowprimes[j++];
1649 /* END LOOP */
1650 m = x.modInt(m);
1651 /* BEGIN LOOP */
1652 while(i < j) if(m%lowprimes[i++] == 0) return false;
1653 /* END LOOP */
1654 }
1655 /* END LOOP */
1656 return x.millerRabin(t);
1657 }
1658
1659 // (protected) true if probably prime (HAC 4.24, Miller-Rabin)
1660 function bnpMillerRabin(t) {
1661 var n1 = this.subtract(BigInteger.ONE);
1662 var k = n1.getLowestSetBit();
1663 if(k <= 0) return false;
1664 var r = n1.shiftRight(k);
1665 t = (t+1)>>1;
1666 if(t > lowprimes.length) t = lowprimes.length;
1667 var a = nbi();
1668 /* BEGIN LOOP */
1669 for(var i = 0; i < t; ++i) {
1670 a.fromInt(lowprimes[i]);
1671 var y = a.modPow(r,this);
1672 if(y.compareTo(BigInteger.ONE) != 0 && y.compareTo(n1) != 0) {
1673 var j = 1;
1674 /* BEGIN LOOP */
1675 while(j++ < k && y.compareTo(n1) != 0) {
1676 y = y.modPowInt(2,this);
1677 if(y.compareTo(BigInteger.ONE) == 0) return false;
1678 }
1679 /* END LOOP */
1680 if(y.compareTo(n1) != 0) return false;
1681 }
1682 }
1683 /* END LOOP */
1684 return true;
1685 }
1686
1687 // protected
1688 BigInteger.prototype.chunkSize = bnpChunkSize;
1689 BigInteger.prototype.toRadix = bnpToRadix;
1690 BigInteger.prototype.fromRadix = bnpFromRadix;
1691 BigInteger.prototype.fromNumber = bnpFromNumber;
1692 BigInteger.prototype.bitwiseTo = bnpBitwiseTo;
1693 BigInteger.prototype.changeBit = bnpChangeBit;
1694 BigInteger.prototype.addTo = bnpAddTo;
1695 BigInteger.prototype.dMultiply = bnpDMultiply;
1696 BigInteger.prototype.dAddOffset = bnpDAddOffset;
1697 BigInteger.prototype.multiplyLowerTo = bnpMultiplyLowerTo;
1698 BigInteger.prototype.multiplyUpperTo = bnpMultiplyUpperTo;
1699 BigInteger.prototype.modInt = bnpModInt;
1700 BigInteger.prototype.millerRabin = bnpMillerRabin;
1701
1702 // public
1703 BigInteger.prototype.clone = bnClone;
1704 BigInteger.prototype.intValue = bnIntValue;
1705 BigInteger.prototype.byteValue = bnByteValue;
1706 BigInteger.prototype.shortValue = bnShortValue;
1707 BigInteger.prototype.signum = bnSigNum;
1708 BigInteger.prototype.toByteArray = bnToByteArray;
1709 BigInteger.prototype.equals = bnEquals;
1710 BigInteger.prototype.min = bnMin;
1711 BigInteger.prototype.max = bnMax;
1712 BigInteger.prototype.and = bnAnd;
1713 BigInteger.prototype.or = bnOr;
1714 BigInteger.prototype.xor = bnXor;
1715 BigInteger.prototype.andNot = bnAndNot;
1716 BigInteger.prototype.not = bnNot;
1717 BigInteger.prototype.shiftLeft = bnShiftLeft;
1718 BigInteger.prototype.shiftRight = bnShiftRight;
1719 BigInteger.prototype.getLowestSetBit = bnGetLowestSetBit;
1720 BigInteger.prototype.bitCount = bnBitCount;
1721 BigInteger.prototype.testBit = bnTestBit;
1722 BigInteger.prototype.setBit = bnSetBit;
1723 BigInteger.prototype.clearBit = bnClearBit;
1724 BigInteger.prototype.flipBit = bnFlipBit;
1725 BigInteger.prototype.add = bnAdd;
1726 BigInteger.prototype.subtract = bnSubtract;
1727 BigInteger.prototype.multiply = bnMultiply;
1728 BigInteger.prototype.divide = bnDivide;
1729 BigInteger.prototype.remainder = bnRemainder;
1730 BigInteger.prototype.divideAndRemainder = bnDivideAndRemainder;
1731 BigInteger.prototype.modPow = bnModPow;
1732 BigInteger.prototype.modInverse = bnModInverse;
1733 BigInteger.prototype.pow = bnPow;
1734 BigInteger.prototype.gcd = bnGCD;
1735 BigInteger.prototype.isProbablePrime = bnIsProbablePrime;
1736
1737 // BigInteger interfaces not implemented in jsbn:
1738
1739 // BigInteger(int signum, byte[] magnitude)
1740 // double doubleValue()
1741 // float floatValue()
1742 // int hashCode()
1743 // long longValue()
1744 // static BigInteger valueOf(long val)
1745 // prng4.js - uses Arcfour as a PRNG
1746
1747 function Arcfour() {
1748 this.i = 0;
1749 this.j = 0;
1750 this.S = new Array();
1751 }
1752
1753 // Initialize arcfour context from key, an array of ints, each from [0..255]
1754 function ARC4init(key) {
1755 var i, j, t;
1756 /* BEGIN LOOP */
1757 for(i = 0; i < 256; ++i)
1758 this.S[i] = i;
1759 /* END LOOP */
1760 j = 0;
1761 /* BEGIN LOOP */
1762 for(i = 0; i < 256; ++i) {
1763 j = (j + this.S[i] + key[i % key.length]) & 255;
1764 t = this.S[i];
1765 this.S[i] = this.S[j];
1766 this.S[j] = t;
1767 }
1768 /* END LOOP */
1769 this.i = 0;
1770 this.j = 0;
1771 }
1772
1773 function ARC4next() {
1774 var t;
1775 this.i = (this.i + 1) & 255;
1776 this.j = (this.j + this.S[this.i]) & 255;
1777 t = this.S[this.i];
1778 this.S[this.i] = this.S[this.j];
1779 this.S[this.j] = t;
1780 return this.S[(t + this.S[this.i]) & 255];
1781 }
1782
1783 Arcfour.prototype.init = ARC4init;
1784 Arcfour.prototype.next = ARC4next;
1785
1786 // Plug in your RNG constructor here
1787 function prng_newstate() {
1788 return new Arcfour();
1789 }
1790
1791 // Pool size must be a multiple of 4 and greater than 32.
1792 // An array of bytes the size of the pool will be passed to init()
1793 var rng_psize = 256;
1794 // Random number generator - requires a PRNG backend, e.g. prng4.js
1795
1796 // For best results, put code like
1797 // <body onClick='rng_seed_time();' onKeyPress='rng_seed_time();'>
1798 // in your main HTML document.
1799
1800 var rng_state;
1801 var rng_pool;
1802 var rng_pptr;
1803
1804 // Mix in a 32-bit integer into the pool
1805 function rng_seed_int(x) {
1806 rng_pool[rng_pptr++] ^= x & 255;
1807 rng_pool[rng_pptr++] ^= (x >> 8) & 255;
1808 rng_pool[rng_pptr++] ^= (x >> 16) & 255;
1809 rng_pool[rng_pptr++] ^= (x >> 24) & 255;
1810 if(rng_pptr >= rng_psize) rng_pptr -= rng_psize;
1811 }
1812
1813 // Mix in the current time (w/milliseconds) into the pool
1814 function rng_seed_time() {
1815 rng_seed_int(new Date().getTime());
1816 }
1817
1818 // Initialize the pool with junk if needed.
1819 if(rng_pool == null) {
1820 rng_pool = new Array();
1821 rng_pptr = 0;
1822 var t;
1823 /* BEGIN LOOP */
1824 while(rng_pptr < rng_psize) { // extract some randomness from Math.random()
1825 t = Math.floor(65536 * Math.random());
1826 rng_pool[rng_pptr++] = t >>> 8;
1827 rng_pool[rng_pptr++] = t & 255;
1828 }
1829 /* END LOOP */
1830 rng_pptr = 0;
1831 rng_seed_time();
1832 //rng_seed_int(window.screenX);
1833 //rng_seed_int(window.screenY);
1834 }
1835
1836 function rng_get_byte() {
1837 if(rng_state == null) {
1838 rng_seed_time();
1839 rng_state = prng_newstate();
1840 rng_state.init(rng_pool);
1841 /* BEGIN LOOP */
1842 for(rng_pptr = 0; rng_pptr < rng_pool.length; ++rng_pptr)
1843 rng_pool[rng_pptr] = 0;
1844 /* END LOOP */
1845 rng_pptr = 0;
1846 //rng_pool = null;
1847 }
1848 // TODO: allow reseeding after first request
1849 return rng_state.next();
1850 }
1851
1852 function rng_get_bytes(ba) {
1853 var i;
1854 /* BEGIN LOOP */
1855 for(i = 0; i < ba.length; ++i) ba[i] = rng_get_byte();
1856 /* END LOOP */
1857 }
1858
1859 function SecureRandom() {}
1860
1861 SecureRandom.prototype.nextBytes = rng_get_bytes;
1862 // Depends on jsbn.js and rng.js
1863
1864 // convert a (hex) string to a bignum object
1865 function parseBigInt(str,r) {
1866 return new BigInteger(str,r);
1867 }
1868
1869 function linebrk(s,n) {
1870 var ret = "";
1871 var i = 0;
1872 /* BEGIN LOOP */
1873 while(i + n < s.length) {
1874 ret += s.substring(i,i+n) + "\n";
1875 i += n;
1876 }
1877 /* END LOOP */
1878 return ret + s.substring(i,s.length);
1879 }
1880
1881 function byte2Hex(b) {
1882 if(b < 0x10)
1883 return "0" + b.toString(16);
1884 else
1885 return b.toString(16);
1886 }
1887
1888 // PKCS#1 (type 2, random) pad input string s to n bytes, and return a bigint
1889 function pkcs1pad2(s,n) {
1890 if(n < s.length + 11) {
1891 alert("Message too long for RSA");
1892 return null;
1893 }
1894 var ba = new Array();
1895 var i = s.length - 1;
1896 /* BEGIN LOOP */
1897 while(i >= 0 && n > 0) ba[--n] = s.charCodeAt(i--);
1898 /* END LOOP */
1899 ba[--n] = 0;
1900 var rng = new SecureRandom();
1901 var x = new Array();
1902 /* BEGIN LOOP */
1903 while(n > 2) { // random non-zero pad
1904 x[0] = 0;
1905 /* BEGIN LOOP */
1906 while(x[0] == 0) rng.nextBytes(x);
1907 /* END LOOP */
1908 ba[--n] = x[0];
1909 }
1910 /* END LOOP */
1911 ba[--n] = 2;
1912 ba[--n] = 0;
1913 return new BigInteger(ba);
1914 }
1915
1916 // "empty" RSA key constructor
1917 function RSAKey() {
1918 this.n = null;
1919 this.e = 0;
1920 this.d = null;
1921 this.p = null;
1922 this.q = null;
1923 this.dmp1 = null;
1924 this.dmq1 = null;
1925 this.coeff = null;
1926 }
1927
1928 // Set the public key fields N and e from hex strings
1929 function RSASetPublic(N,E) {
1930 if(N != null && E != null && N.length > 0 && E.length > 0) {
1931 this.n = parseBigInt(N,16);
1932 this.e = parseInt(E,16);
1933 }
1934 else
1935 alert("Invalid RSA public key");
1936 }
1937
1938 // Perform raw public operation on "x": return x^e (mod n)
1939 function RSADoPublic(x) {
1940 return x.modPowInt(this.e, this.n);
1941 }
1942
1943 // Return the PKCS#1 RSA encryption of "text" as an even-length hex string
1944 function RSAEncrypt(text) {
1945 var m = pkcs1pad2(text,(this.n.bitLength()+7)>>3);
1946 if(m == null) return null;
1947 var c = this.doPublic(m);
1948 if(c == null) return null;
1949 var h = c.toString(16);
1950 if((h.length & 1) == 0) return h; else return "0" + h;
1951 }
1952
1953 // Return the PKCS#1 RSA encryption of "text" as a Base64-encoded string
1954 //function RSAEncryptB64(text) {
1955 // var h = this.encrypt(text);
1956 // if(h) return hex2b64(h); else return null;
1957 //}
1958
1959 // protected
1960 RSAKey.prototype.doPublic = RSADoPublic;
1961
1962 // public
1963 RSAKey.prototype.setPublic = RSASetPublic;
1964 RSAKey.prototype.encrypt = RSAEncrypt;
1965 //RSAKey.prototype.encrypt_b64 = RSAEncryptB64;
1966 // Depends on rsa.js and jsbn2.js
1967
1968 // Undo PKCS#1 (type 2, random) padding and, if valid, return the plaintext
1969 function pkcs1unpad2(d,n) {
1970 var b = d.toByteArray();
1971 var i = 0;
1972 /* BEGIN LOOP */
1973 while(i < b.length && b[i] == 0) ++i;
1974 /* END LOOP */
1975 if(b.length-i != n-1 || b[i] != 2)
1976 return null;
1977 ++i;
1978 /* BEGIN LOOP */
1979 while(b[i] != 0)
1980 if(++i >= b.length) return null;
1981 /* END LOOP */
1982 var ret = "";
1983 /* BEGIN LOOP */
1984 while(++i < b.length)
1985 ret += String.fromCharCode(b[i]);
1986 /* END LOOP */
1987 return ret;
1988 }
1989
1990 // Set the private key fields N, e, and d from hex strings
1991 function RSASetPrivate(N,E,D) {
1992 if(N != null && E != null && N.length > 0 && E.length > 0) {
1993 this.n = parseBigInt(N,16);
1994 this.e = parseInt(E,16);
1995 this.d = parseBigInt(D,16);
1996 }
1997 else
1998 alert("Invalid RSA private key");
1999 }
2000
2001 // Set the private key fields N, e, d and CRT params from hex strings
2002 function RSASetPrivateEx(N,E,D,P,Q,DP,DQ,C) {
2003 if(N != null && E != null && N.length > 0 && E.length > 0) {
2004 this.n = parseBigInt(N,16);
2005 this.e = parseInt(E,16);
2006 this.d = parseBigInt(D,16);
2007 this.p = parseBigInt(P,16);
2008 this.q = parseBigInt(Q,16);
2009 this.dmp1 = parseBigInt(DP,16);
2010 this.dmq1 = parseBigInt(DQ,16);
2011 this.coeff = parseBigInt(C,16);
2012 }
2013 else
2014 alert("Invalid RSA private key");
2015 }
2016
2017 // Generate a new random private key B bits long, using public expt E
2018 function RSAGenerate(B,E) {
2019 var rng = new SecureRandom();
2020 var qs = B>>1;
2021 this.e = parseInt(E,16);
2022 var ee = new BigInteger(E,16);
2023 /* BEGIN LOOP */
2024 for(;;) {
2025 /* BEGIN LOOP */
2026 for(;;) {
2027 this.p = new BigInteger(B-qs,1,rng);
2028 if(this.p.subtract(BigInteger.ONE).gcd(ee).compareTo(BigInteger.ONE) == 0 && this.p.isProbablePrime(10)) break;
2029 }
2030 /* END LOOP */
2031 /* BEGIN LOOP */
2032 for(;;) {
2033 this.q = new BigInteger(qs,1,rng);
2034 if(this.q.subtract(BigInteger.ONE).gcd(ee).compareTo(BigInteger.ONE) == 0 && this.q.isProbablePrime(10)) break;
2035 }
2036 /* END LOOP */
2037 if(this.p.compareTo(this.q) <= 0) {
2038 var t = this.p;
2039 this.p = this.q;
2040 this.q = t;
2041 }
2042 var p1 = this.p.subtract(BigInteger.ONE);
2043 var q1 = this.q.subtract(BigInteger.ONE);
2044 var phi = p1.multiply(q1);
2045 if(phi.gcd(ee).compareTo(BigInteger.ONE) == 0) {
2046 this.n = this.p.multiply(this.q);
2047 this.d = ee.modInverse(phi);
2048 this.dmp1 = this.d.mod(p1);
2049 this.dmq1 = this.d.mod(q1);
2050 this.coeff = this.q.modInverse(this.p);
2051 break;
2052 }
2053 }
2054 /* END LOOP */
2055 }
2056
2057 // Perform raw private operation on "x": return x^d (mod n)
2058 function RSADoPrivate(x) {
2059 if(this.p == null || this.q == null)
2060 return x.modPow(this.d, this.n);
2061
2062 // TODO: re-calculate any missing CRT params
2063 var xp = x.mod(this.p).modPow(this.dmp1, this.p);
2064 var xq = x.mod(this.q).modPow(this.dmq1, this.q);
2065
2066 /* BEGIN LOOP */
2067 while(xp.compareTo(xq) < 0)
2068 xp = xp.add(this.p);
2069 /* END LOOP */
2070 return xp.subtract(xq).multiply(this.coeff).mod(this.p).multiply(this.q).add(xq);
2071 }
2072
2073 // Return the PKCS#1 RSA decryption of "ctext".
2074 // "ctext" is an even-length hex string and the output is a plain string.
2075 function RSADecrypt(ctext) {
2076 var c = parseBigInt(ctext, 16);
2077 var m = this.doPrivate(c);
2078 if(m == null) return null;
2079 return pkcs1unpad2(m, (this.n.bitLength()+7)>>3);
2080 }
2081
2082 // Return the PKCS#1 RSA decryption of "ctext".
2083 // "ctext" is a Base64-encoded string and the output is a plain string.
2084 //function RSAB64Decrypt(ctext) {
2085 // var h = b64tohex(ctext);
2086 // if(h) return this.decrypt(h); else return null;
2087 //}
2088
2089 // protected
2090 RSAKey.prototype.doPrivate = RSADoPrivate;
2091
2092 // public
2093 RSAKey.prototype.setPrivate = RSASetPrivate;
2094 RSAKey.prototype.setPrivateEx = RSASetPrivateEx;
2095 RSAKey.prototype.generate = RSAGenerate;
2096 RSAKey.prototype.decrypt = RSADecrypt;
2097 //RSAKey.prototype.b64_decrypt = RSAB64Decrypt;
2098
2099
2100 nValue="a5261939975948bb7a58dffe5ff54e65f0498f9175f5a09288810b8975871e99af3b5dd94057b0fc07535f5f97444504fa35169d461d0d30cf0192e307727c065168c788771c561a9400fb49175e9e6aa4e23fe11af69e9412dd23b0cb6684c4c2429bce139e848ab26d0829073351f4acd36074eafd036a5eb83359d2a698d3";
2101 eValue="10001";
2102 dValue="8e9912f6d3645894e8d38cb58c0db81ff516cf4c7e5a14c7f1eddb1459d2cded4d8d293fc97aee6aefb861859c8b6a3d1dfe710463e1f9ddc72048c09751971c4a580aa51eb523357a3cc48d31cfad1d4a165066ed92d4748fb6571211da5cb14bc11b6e2df7c1a559e6d5ac1cd5c94703a22891464fba23d0d965086277a161";
2103 pValue="d090ce58a92c75233a6486cb0a9209bf3583b64f540c76f5294bb97d285eed33aec220bde14b2417951178ac152ceab6da7090905b478195498b352048f15e7d";
2104 qValue="cab575dc652bb66df15a0359609d51d1db184750c00c6698b90ef3465c99655103edbf0d54c56aec0ce3c4d22592338092a126a0cc49f65a4a30d222b411e58f";
2105 dmp1Value="1a24bca8e273df2f0e47c199bbf678604e7df7215480c77c8db39f49b000ce2cf7500038acfff5433b7d582a01f1826e6f4d42e1c57f5e1fef7b12aabc59fd25";
2106 dmq1Value="3d06982efbbe47339e1f6d36b1216b8a741d410b0c662f54f7118b27b9a4ec9d914337eb39841d8666f3034408cf94f5b62f11c402fc994fe15a05493150d9fd";
2107 coeffValue="3a3e731acd8960b7ff9eb81a7ff93bd1cfa74cbd56987db58b4594fb09c09084db1734c8143f98b602b981aaa9243ca28deb69b5b280ee8dcee0fd2625e53250";
2108
2109 setupEngine(am3, 28);
2110
2111 var RSA = new RSAKey();
2112 var TEXT = "The quick brown fox jumped over the extremely lazy frogs!";
2113
2114 RSA.setPublic(nValue, eValue);
2115 RSA.setPrivateEx(nValue, eValue, dValue, pValue, qValue, dmp1Value, dmq1Value, coeffValue);
2116
2117 function encrypt() {
2118 return RSA.encrypt(TEXT);
2119 }
2120
2121 function decrypt() {
2122 return RSA.decrypt(TEXT);
2123 }
2124
2125 function PrintResult(name, result) {
2126 }
2127
2128
2129 function PrintScore(score) {
2130 // print(score);
2131 }
2132
2133
2134 BenchmarkSuite.RunSuites({ NotifyResult: PrintResult,
2135 NotifyScore: PrintScore });

Mercurial Repository: The Tor Browser

Europalab SCM Repository Server

mercurial