1// Copyright (c) 2005  Tom Wu
2// All Rights Reserved.
3// See "LICENSE" for details.
4
5// Basic JavaScript BN library - subset useful for RSA encryption.
6
7// Bits per digit
8var dbits;
9
10// JavaScript engine analysis
11var canary = 0xdeadbeefcafe;
12var j_lm = ((canary & 0xffffff) == 0xefcafe);
13
14// (public) Constructor
15function BigInteger(a, b, c) {
16	if (a != null)
17		if ("number" == typeof a)
18			this.fromNumber(a, b, c);
19		else if (b == null && "string" != typeof a)
20			this.fromString(a, 256);
21		else
22			this.fromString(a, b);
23}
24
25// return new, unset BigInteger
26function nbi() {
27	return new BigInteger(null);
28}
29
30// am: Compute w_j += (x*this_i), propagate carries,
31// c is initial carry, returns final carry.
32// c < 3*dvalue, x < 2*dvalue, this_i < dvalue
33// We need to select the fastest one that works in this environment.
34
35// am1: use a single mult and divide to get the high bits,
36// max digit bits should be 26 because
37// max internal value = 2*dvalue^2-2*dvalue (< 2^53)
38function am1(i, x, w, j, c, n) {
39	while (--n >= 0) {
40		var v = x * this[i++] + w[j] + c;
41		c = Math.floor(v / 0x4000000);
42		w[j++] = v & 0x3ffffff;
43	}
44	return c;
45}
46// am2 avoids a big mult-and-extract completely.
47// Max digit bits should be <= 30 because we do bitwise ops
48// on values up to 2*hdvalue^2-hdvalue-1 (< 2^31)
49function am2(i, x, w, j, c, n) {
50	var xl = x & 0x7fff, xh = x >> 15;
51	while (--n >= 0) {
52		var l = this[i] & 0x7fff;
53		var h = this[i++] >> 15;
54		var m = xh * l + h * xl;
55		l = xl * l + ((m & 0x7fff) << 15) + w[j] + (c & 0x3fffffff);
56		c = (l >>> 30) + (m >>> 15) + xh * h + (c >>> 30);
57		w[j++] = l & 0x3fffffff;
58	}
59	return c;
60}
61// Alternately, set max digit bits to 28 since some
62// browsers slow down when dealing with 32-bit numbers.
63function am3(i, x, w, j, c, n) {
64	var xl = x & 0x3fff, xh = x >> 14;
65	while (--n >= 0) {
66		var l = this[i] & 0x3fff;
67		var h = this[i++] >> 14;
68		var m = xh * l + h * xl;
69		l = xl * l + ((m & 0x3fff) << 14) + w[j] + c;
70		c = (l >> 28) + (m >> 14) + xh * h;
71		w[j++] = l & 0xfffffff;
72	}
73	return c;
74}
75if (j_lm && (navigator.appName == "Microsoft Internet Explorer")) {
76	BigInteger.prototype.am = am2;
77	dbits = 30;
78} else if (j_lm && (navigator.appName != "Netscape")) {
79	BigInteger.prototype.am = am1;
80	dbits = 26;
81} else { // Mozilla/Netscape seems to prefer am3
82	BigInteger.prototype.am = am3;
83	dbits = 28;
84}
85
86BigInteger.prototype.DB = dbits;
87BigInteger.prototype.DM = ((1 << dbits) - 1);
88BigInteger.prototype.DV = (1 << dbits);
89
90var BI_FP = 52;
91BigInteger.prototype.FV = Math.pow(2, BI_FP);
92BigInteger.prototype.F1 = BI_FP - dbits;
93BigInteger.prototype.F2 = 2 * dbits - BI_FP;
94
95// Digit conversions
96var BI_RM = "0123456789abcdefghijklmnopqrstuvwxyz";
97var BI_RC = new Array();
98var rr, vv;
99rr = "0".charCodeAt(0);
100for (vv = 0; vv <= 9; ++vv)
101	BI_RC[rr++] = vv;
102rr = "a".charCodeAt(0);
103for (vv = 10; vv < 36; ++vv)
104	BI_RC[rr++] = vv;
105rr = "A".charCodeAt(0);
106for (vv = 10; vv < 36; ++vv)
107	BI_RC[rr++] = vv;
108
109function int2char(n) {
110	return BI_RM.charAt(n);
111}
112function intAt(s, i) {
113	var c = BI_RC[s.charCodeAt(i)];
114	return (c == null) ? -1 : c;
115}
116
117// (protected) copy this to r
118function bnpCopyTo(r) {
119	for ( var i = this.t - 1; i >= 0; --i)
120		r[i] = this[i];
121	r.t = this.t;
122	r.s = this.s;
123}
124
125// (protected) set from integer value x, -DV <= x < DV
126function bnpFromInt(x) {
127	this.t = 1;
128	this.s = (x < 0) ? -1 : 0;
129	if (x > 0)
130		this[0] = x;
131	else if (x < -1)
132		this[0] = x + DV;
133	else
134		this.t = 0;
135}
136
137// return bigint initialized to value
138function nbv(i) {
139	var r = nbi();
140	r.fromInt(i);
141	return r;
142}
143
144// (protected) set from string and radix
145function bnpFromString(s, b) {
146	var k;
147	if (b == 16)
148		k = 4;
149	else if (b == 8)
150		k = 3;
151	else if (b == 256)
152		k = 8; // byte array
153	else if (b == 2)
154		k = 1;
155	else if (b == 32)
156		k = 5;
157	else if (b == 4)
158		k = 2;
159	else {
160		this.fromRadix(s, b);
161		return;
162	}
163	this.t = 0;
164	this.s = 0;
165	var i = s.length, mi = false, sh = 0;
166	while (--i >= 0) {
167		var x = (k == 8) ? s[i] & 0xff : intAt(s, i);
168		if (x < 0) {
169			if (s.charAt(i) == "-")
170				mi = true;
171			continue;
172		}
173		mi = false;
174		if (sh == 0)
175			this[this.t++] = x;
176		else if (sh + k > this.DB) {
177			this[this.t - 1] |= (x & ((1 << (this.DB - sh)) - 1)) << sh;
178			this[this.t++] = (x >> (this.DB - sh));
179		} else
180			this[this.t - 1] |= x << sh;
181		sh += k;
182		if (sh >= this.DB)
183			sh -= this.DB;
184	}
185	if (k == 8 && (s[0] & 0x80) != 0) {
186		this.s = -1;
187		if (sh > 0)
188			this[this.t - 1] |= ((1 << (this.DB - sh)) - 1) << sh;
189	}
190	this.clamp();
191	if (mi)
192		BigInteger.ZERO.subTo(this, this);
193}
194
195// (protected) clamp off excess high words
196function bnpClamp() {
197	var c = this.s & this.DM;
198	while (this.t > 0 && this[this.t - 1] == c)
199		--this.t;
200}
201
202// (public) return string representation in given radix
203function bnToString(b) {
204	if (this.s < 0)
205		return "-" + this.negate().toString(b);
206	var k;
207	if (b == 16)
208		k = 4;
209	else if (b == 8)
210		k = 3;
211	else if (b == 2)
212		k = 1;
213	else if (b == 32)
214		k = 5;
215	else if (b == 4)
216		k = 2;
217	else
218		return this.toRadix(b);
219	var km = (1 << k) - 1, d, m = false, r = "", i = this.t;
220	var p = this.DB - (i * this.DB) % k;
221	if (i-- > 0) {
222		if (p < this.DB && (d = this[i] >> p) > 0) {
223			m = true;
224			r = int2char(d);
225		}
226		while (i >= 0) {
227			if (p < k) {
228				d = (this[i] & ((1 << p) - 1)) << (k - p);
229				d |= this[--i] >> (p += this.DB - k);
230			} else {
231				d = (this[i] >> (p -= k)) & km;
232				if (p <= 0) {
233					p += this.DB;
234					--i;
235				}
236			}
237			if (d > 0)
238				m = true;
239			if (m)
240				r += int2char(d);
241		}
242	}
243	return m ? r : "0";
244}
245
246// (public) -this
247function bnNegate() {
248	var r = nbi();
249	BigInteger.ZERO.subTo(this, r);
250	return r;
251}
252
253// (public) |this|
254function bnAbs() {
255	return (this.s < 0) ? this.negate() : this;
256}
257
258// (public) return + if this > a, - if this < a, 0 if equal
259function bnCompareTo(a) {
260	var r = this.s - a.s;
261	if (r != 0)
262		return r;
263	var i = this.t;
264	r = i - a.t;
265	if (r != 0)
266		return r;
267	while (--i >= 0)
268		if ((r = this[i] - a[i]) != 0)
269			return r;
270	return 0;
271}
272
273// returns bit length of the integer x
274function nbits(x) {
275	var r = 1, t;
276	if ((t = x >>> 16) != 0) {
277		x = t;
278		r += 16;
279	}
280	if ((t = x >> 8) != 0) {
281		x = t;
282		r += 8;
283	}
284	if ((t = x >> 4) != 0) {
285		x = t;
286		r += 4;
287	}
288	if ((t = x >> 2) != 0) {
289		x = t;
290		r += 2;
291	}
292	if ((t = x >> 1) != 0) {
293		x = t;
294		r += 1;
295	}
296	return r;
297}
298
299// (public) return the number of bits in "this"
300function bnBitLength() {
301	if (this.t <= 0)
302		return 0;
303	return this.DB * (this.t - 1)
304			+ nbits(this[this.t - 1] ^ (this.s & this.DM));
305}
306
307// (protected) r = this << n*DB
308function bnpDLShiftTo(n, r) {
309	var i;
310	for (i = this.t - 1; i >= 0; --i)
311		r[i + n] = this[i];
312	for (i = n - 1; i >= 0; --i)
313		r[i] = 0;
314	r.t = this.t + n;
315	r.s = this.s;
316}
317
318// (protected) r = this >> n*DB
319function bnpDRShiftTo(n, r) {
320	for ( var i = n; i < this.t; ++i)
321		r[i - n] = this[i];
322	r.t = Math.max(this.t - n, 0);
323	r.s = this.s;
324}
325
326// (protected) r = this << n
327function bnpLShiftTo(n, r) {
328	var bs = n % this.DB;
329	var cbs = this.DB - bs;
330	var bm = (1 << cbs) - 1;
331	var ds = Math.floor(n / this.DB), c = (this.s << bs) & this.DM, i;
332	for (i = this.t - 1; i >= 0; --i) {
333		r[i + ds + 1] = (this[i] >> cbs) | c;
334		c = (this[i] & bm) << bs;
335	}
336	for (i = ds - 1; i >= 0; --i)
337		r[i] = 0;
338	r[ds] = c;
339	r.t = this.t + ds + 1;
340	r.s = this.s;
341	r.clamp();
342}
343
344// (protected) r = this >> n
345function bnpRShiftTo(n, r) {
346	r.s = this.s;
347	var ds = Math.floor(n / this.DB);
348	if (ds >= this.t) {
349		r.t = 0;
350		return;
351	}
352	var bs = n % this.DB;
353	var cbs = this.DB - bs;
354	var bm = (1 << bs) - 1;
355	r[0] = this[ds] >> bs;
356	for ( var i = ds + 1; i < this.t; ++i) {
357		r[i - ds - 1] |= (this[i] & bm) << cbs;
358		r[i - ds] = this[i] >> bs;
359	}
360	if (bs > 0)
361		r[this.t - ds - 1] |= (this.s & bm) << cbs;
362	r.t = this.t - ds;
363	r.clamp();
364}
365
366// (protected) r = this - a
367function bnpSubTo(a, r) {
368	var i = 0, c = 0, m = Math.min(a.t, this.t);
369	while (i < m) {
370		c += this[i] - a[i];
371		r[i++] = c & this.DM;
372		c >>= this.DB;
373	}
374	if (a.t < this.t) {
375		c -= a.s;
376		while (i < this.t) {
377			c += this[i];
378			r[i++] = c & this.DM;
379			c >>= this.DB;
380		}
381		c += this.s;
382	} else {
383		c += this.s;
384		while (i < a.t) {
385			c -= a[i];
386			r[i++] = c & this.DM;
387			c >>= this.DB;
388		}
389		c -= a.s;
390	}
391	r.s = (c < 0) ? -1 : 0;
392	if (c < -1)
393		r[i++] = this.DV + c;
394	else if (c > 0)
395		r[i++] = c;
396	r.t = i;
397	r.clamp();
398}
399
400// (protected) r = this * a, r != this,a (HAC 14.12)
401// "this" should be the larger one if appropriate.
402function bnpMultiplyTo(a, r) {
403	var x = this.abs(), y = a.abs();
404	var i = x.t;
405	r.t = i + y.t;
406	while (--i >= 0)
407		r[i] = 0;
408	for (i = 0; i < y.t; ++i)
409		r[i + x.t] = x.am(0, y[i], r, i, 0, x.t);
410	r.s = 0;
411	r.clamp();
412	if (this.s != a.s)
413		BigInteger.ZERO.subTo(r, r);
414}
415
416// (protected) r = this^2, r != this (HAC 14.16)
417function bnpSquareTo(r) {
418	var x = this.abs();
419	var i = r.t = 2 * x.t;
420	while (--i >= 0)
421		r[i] = 0;
422	for (i = 0; i < x.t - 1; ++i) {
423		var c = x.am(i, x[i], r, 2 * i, 0, 1);
424		if ((r[i + x.t] += x.am(i + 1, 2 * x[i], r, 2 * i + 1, c, x.t - i - 1)) >= x.DV) {
425			r[i + x.t] -= x.DV;
426			r[i + x.t + 1] = 1;
427		}
428	}
429	if (r.t > 0)
430		r[r.t - 1] += x.am(i, x[i], r, 2 * i, 0, 1);
431	r.s = 0;
432	r.clamp();
433}
434
435// (protected) divide this by m, quotient and remainder to q, r (HAC 14.20)
436// r != q, this != m. q or r may be null.
437function bnpDivRemTo(m, q, r) {
438	var pm = m.abs();
439	if (pm.t <= 0)
440		return;
441	var pt = this.abs();
442	if (pt.t < pm.t) {
443		if (q != null)
444			q.fromInt(0);
445		if (r != null)
446			this.copyTo(r);
447		return;
448	}
449	if (r == null)
450		r = nbi();
451	var y = nbi(), ts = this.s, ms = m.s;
452	var nsh = this.DB - nbits(pm[pm.t - 1]); // normalize modulus
453	if (nsh > 0) {
454		pm.lShiftTo(nsh, y);
455		pt.lShiftTo(nsh, r);
456	} else {
457		pm.copyTo(y);
458		pt.copyTo(r);
459	}
460	var ys = y.t;
461	var y0 = y[ys - 1];
462	if (y0 == 0)
463		return;
464	var yt = y0 * (1 << this.F1) + ((ys > 1) ? y[ys - 2] >> this.F2 : 0);
465	var d1 = this.FV / yt, d2 = (1 << this.F1) / yt, e = 1 << this.F2;
466	var i = r.t, j = i - ys, t = (q == null) ? nbi() : q;
467	y.dlShiftTo(j, t);
468	if (r.compareTo(t) >= 0) {
469		r[r.t++] = 1;
470		r.subTo(t, r);
471	}
472	BigInteger.ONE.dlShiftTo(ys, t);
473	t.subTo(y, y); // "negative" y so we can replace sub with am later
474	while (y.t < ys)
475		y[y.t++] = 0;
476	while (--j >= 0) {
477		// Estimate quotient digit
478		var qd = (r[--i] == y0) ? this.DM : Math.floor(r[i] * d1
479				+ (r[i - 1] + e) * d2);
480		if ((r[i] += y.am(0, qd, r, j, 0, ys)) < qd) { // Try it out
481			y.dlShiftTo(j, t);
482			r.subTo(t, r);
483			while (r[i] < --qd)
484				r.subTo(t, r);
485		}
486	}
487	if (q != null) {
488		r.drShiftTo(ys, q);
489		if (ts != ms)
490			BigInteger.ZERO.subTo(q, q);
491	}
492	r.t = ys;
493	r.clamp();
494	if (nsh > 0)
495		r.rShiftTo(nsh, r); // Denormalize remainder
496	if (ts < 0)
497		BigInteger.ZERO.subTo(r, r);
498}
499
500// (public) this mod a
501function bnMod(a) {
502	var r = nbi();
503	this.abs().divRemTo(a, null, r);
504	if (this.s < 0 && r.compareTo(BigInteger.ZERO) > 0)
505		a.subTo(r, r);
506	return r;
507}
508
509// Modular reduction using "classic" algorithm
510function Classic(m) {
511	this.m = m;
512}
513function cConvert(x) {
514	if (x.s < 0 || x.compareTo(this.m) >= 0)
515		return x.mod(this.m);
516	else
517		return x;
518}
519function cRevert(x) {
520	return x;
521}
522function cReduce(x) {
523	x.divRemTo(this.m, null, x);
524}
525function cMulTo(x, y, r) {
526	x.multiplyTo(y, r);
527	this.reduce(r);
528}
529function cSqrTo(x, r) {
530	x.squareTo(r);
531	this.reduce(r);
532}
533
534Classic.prototype.convert = cConvert;
535Classic.prototype.revert = cRevert;
536Classic.prototype.reduce = cReduce;
537Classic.prototype.mulTo = cMulTo;
538Classic.prototype.sqrTo = cSqrTo;
539
540// (protected) return "-1/this % 2^DB"; useful for Mont. reduction
541// justification:
542// xy == 1 (mod m)
543// xy = 1+km
544// xy(2-xy) = (1+km)(1-km)
545// x[y(2-xy)] = 1-k^2m^2
546// x[y(2-xy)] == 1 (mod m^2)
547// if y is 1/x mod m, then y(2-xy) is 1/x mod m^2
548// should reduce x and y(2-xy) by m^2 at each step to keep size bounded.
549// JS multiply "overflows" differently from C/C++, so care is needed here.
550function bnpInvDigit() {
551	if (this.t < 1)
552		return 0;
553	var x = this[0];
554	if ((x & 1) == 0)
555		return 0;
556	var y = x & 3; // y == 1/x mod 2^2
557	y = (y * (2 - (x & 0xf) * y)) & 0xf; // y == 1/x mod 2^4
558	y = (y * (2 - (x & 0xff) * y)) & 0xff; // y == 1/x mod 2^8
559	y = (y * (2 - (((x & 0xffff) * y) & 0xffff))) & 0xffff; // y == 1/x mod 2^16
560	// last step - calculate inverse mod DV directly;
561	// assumes 16 < DB <= 32 and assumes ability to handle 48-bit ints
562	y = (y * (2 - x * y % this.DV)) % this.DV; // y == 1/x mod 2^dbits
563	// we really want the negative inverse, and -DV < y < DV
564	return (y > 0) ? this.DV - y : -y;
565}
566
567// Montgomery reduction
568function Montgomery(m) {
569	this.m = m;
570	this.mp = m.invDigit();
571	this.mpl = this.mp & 0x7fff;
572	this.mph = this.mp >> 15;
573	this.um = (1 << (m.DB - 15)) - 1;
574	this.mt2 = 2 * m.t;
575}
576
577// xR mod m
578function montConvert(x) {
579	var r = nbi();
580	x.abs().dlShiftTo(this.m.t, r);
581	r.divRemTo(this.m, null, r);
582	if (x.s < 0 && r.compareTo(BigInteger.ZERO) > 0)
583		this.m.subTo(r, r);
584	return r;
585}
586
587// x/R mod m
588function montRevert(x) {
589	var r = nbi();
590	x.copyTo(r);
591	this.reduce(r);
592	return r;
593}
594
595// x = x/R mod m (HAC 14.32)
596function montReduce(x) {
597	while (x.t <= this.mt2)
598		// pad x so am has enough room later
599		x[x.t++] = 0;
600	for ( var i = 0; i < this.m.t; ++i) {
601		// faster way of calculating u0 = x[i]*mp mod DV
602		var j = x[i] & 0x7fff;
603		var u0 = (j * this.mpl + (((j * this.mph + (x[i] >> 15) * this.mpl) & this.um) << 15))
604				& x.DM;
605		// use am to combine the multiply-shift-add into one call
606		j = i + this.m.t;
607		x[j] += this.m.am(0, u0, x, i, 0, this.m.t);
608		// propagate carry
609		while (x[j] >= x.DV) {
610			x[j] -= x.DV;
611			x[++j]++;
612		}
613	}
614	x.clamp();
615	x.drShiftTo(this.m.t, x);
616	if (x.compareTo(this.m) >= 0)
617		x.subTo(this.m, x);
618}
619
620// r = "x^2/R mod m"; x != r
621function montSqrTo(x, r) {
622	x.squareTo(r);
623	this.reduce(r);
624}
625
626// r = "xy/R mod m"; x,y != r
627function montMulTo(x, y, r) {
628	x.multiplyTo(y, r);
629	this.reduce(r);
630}
631
632Montgomery.prototype.convert = montConvert;
633Montgomery.prototype.revert = montRevert;
634Montgomery.prototype.reduce = montReduce;
635Montgomery.prototype.mulTo = montMulTo;
636Montgomery.prototype.sqrTo = montSqrTo;
637
638// (protected) true iff this is even
639function bnpIsEven() {
640	return ((this.t > 0) ? (this[0] & 1) : this.s) == 0;
641}
642
643// (protected) this^e, e < 2^32, doing sqr and mul with "r" (HAC 14.79)
644function bnpExp(e, z) {
645	if (e > 0xffffffff || e < 1)
646		return BigInteger.ONE;
647	var r = nbi(), r2 = nbi(), g = z.convert(this), i = nbits(e) - 1;
648	g.copyTo(r);
649	while (--i >= 0) {
650		z.sqrTo(r, r2);
651		if ((e & (1 << i)) > 0)
652			z.mulTo(r2, g, r);
653		else {
654			var t = r;
655			r = r2;
656			r2 = t;
657		}
658	}
659	return z.revert(r);
660}
661
662// (public) this^e % m, 0 <= e < 2^32
663function bnModPowInt(e, m) {
664	var z;
665	if (e < 256 || m.isEven())
666		z = new Classic(m);
667	else
668		z = new Montgomery(m);
669	return this.exp(e, z);
670}
671
672// protected
673BigInteger.prototype.copyTo = bnpCopyTo;
674BigInteger.prototype.fromInt = bnpFromInt;
675BigInteger.prototype.fromString = bnpFromString;
676BigInteger.prototype.clamp = bnpClamp;
677BigInteger.prototype.dlShiftTo = bnpDLShiftTo;
678BigInteger.prototype.drShiftTo = bnpDRShiftTo;
679BigInteger.prototype.lShiftTo = bnpLShiftTo;
680BigInteger.prototype.rShiftTo = bnpRShiftTo;
681BigInteger.prototype.subTo = bnpSubTo;
682BigInteger.prototype.multiplyTo = bnpMultiplyTo;
683BigInteger.prototype.squareTo = bnpSquareTo;
684BigInteger.prototype.divRemTo = bnpDivRemTo;
685BigInteger.prototype.invDigit = bnpInvDigit;
686BigInteger.prototype.isEven = bnpIsEven;
687BigInteger.prototype.exp = bnpExp;
688
689// public
690BigInteger.prototype.toString = bnToString;
691BigInteger.prototype.negate = bnNegate;
692BigInteger.prototype.abs = bnAbs;
693BigInteger.prototype.compareTo = bnCompareTo;
694BigInteger.prototype.bitLength = bnBitLength;
695BigInteger.prototype.mod = bnMod;
696BigInteger.prototype.modPowInt = bnModPowInt;
697
698// "constants"
699BigInteger.ZERO = nbv(0);
700BigInteger.ONE = nbv(1);
701// prng4.js - uses Arcfour as a PRNG
702
703function Arcfour() {
704	this.i = 0;
705	this.j = 0;
706	this.S = new Array();
707}
708
709// Initialize arcfour context from key, an array of ints, each from [0..255]
710function ARC4init(key) {
711	var i, j, t;
712	for (i = 0; i < 256; ++i)
713		this.S[i] = i;
714	j = 0;
715	for (i = 0; i < 256; ++i) {
716		j = (j + this.S[i] + key[i % key.length]) & 255;
717		t = this.S[i];
718		this.S[i] = this.S[j];
719		this.S[j] = t;
720	}
721	this.i = 0;
722	this.j = 0;
723}
724
725function ARC4next() {
726	var t;
727	this.i = (this.i + 1) & 255;
728	this.j = (this.j + this.S[this.i]) & 255;
729	t = this.S[this.i];
730	this.S[this.i] = this.S[this.j];
731	this.S[this.j] = t;
732	return this.S[(t + this.S[this.i]) & 255];
733}
734
735Arcfour.prototype.init = ARC4init;
736Arcfour.prototype.next = ARC4next;
737
738// Plug in your RNG constructor here
739function prng_newstate() {
740	return new Arcfour();
741}
742
743// Pool size must be a multiple of 4 and greater than 32.
744// An array of bytes the size of the pool will be passed to init()
745var rng_psize = 256;
746// Random number generator - requires a PRNG backend, e.g. prng4.js
747
748// For best results, put code like
749// <body onClick='rng_seed_time();' onKeyPress='rng_seed_time();'>
750// in your main HTML document.
751
752var rng_state;
753var rng_pool;
754var rng_pptr;
755
756// Mix in a 32-bit integer into the pool
757function rng_seed_int(x) {
758	rng_pool[rng_pptr++] ^= x & 255;
759	rng_pool[rng_pptr++] ^= (x >> 8) & 255;
760	rng_pool[rng_pptr++] ^= (x >> 16) & 255;
761	rng_pool[rng_pptr++] ^= (x >> 24) & 255;
762	if (rng_pptr >= rng_psize)
763		rng_pptr -= rng_psize;
764}
765
766// Mix in the current time (w/milliseconds) into the pool
767function rng_seed_time() {
768	rng_seed_int(new Date().getTime());
769}
770
771// Initialize the pool with junk if needed.
772if (rng_pool == null) {
773	rng_pool = new Array();
774	rng_pptr = 0;
775	var t;
776	if (navigator.appName == "Netscape" && navigator.appVersion < "5"
777			&& window.crypto) {
778		// Extract entropy (256 bits) from NS4 RNG if available
779		var z = window.crypto.random(32);
780		for (t = 0; t < z.length; ++t)
781			rng_pool[rng_pptr++] = z.charCodeAt(t) & 255;
782	}
783	while (rng_pptr < rng_psize) { // extract some randomness from Math.random()
784		t = Math.floor(65536 * Math.random());
785		rng_pool[rng_pptr++] = t >>> 8;
786		rng_pool[rng_pptr++] = t & 255;
787	}
788	rng_pptr = 0;
789	rng_seed_time();
790	// rng_seed_int(window.screenX);
791	// rng_seed_int(window.screenY);
792}
793
794function rng_get_byte() {
795	if (rng_state == null) {
796		rng_seed_time();
797		rng_state = prng_newstate();
798		rng_state.init(rng_pool);
799		for (rng_pptr = 0; rng_pptr < rng_pool.length; ++rng_pptr)
800			rng_pool[rng_pptr] = 0;
801		rng_pptr = 0;
802		// rng_pool = null;
803	}
804	// TODO: allow reseeding after first request
805	return rng_state.next();
806}
807
808function rng_get_bytes(ba) {
809	var i;
810	for (i = 0; i < ba.length; ++i)
811		ba[i] = rng_get_byte();
812}
813
814function SecureRandom() {
815}
816
817SecureRandom.prototype.nextBytes = rng_get_bytes;
818// Depends on jsbn.js and rng.js
819
820// convert a (hex) string to a bignum object
821function parseBigInt(str, r) {
822	return new BigInteger(str, r);
823}
824
825function linebrk(s, n) {
826	var ret = "";
827	var i = 0;
828	while (i + n < s.length) {
829		ret += s.substring(i, i + n) + "\n";
830		i += n;
831	}
832	return ret + s.substring(i, s.length);
833}
834
835function byte2Hex(b) {
836	if (b < 0x10)
837		return "0" + b.toString(16);
838	else
839		return b.toString(16);
840}
841
842// PKCS#1 (type 2, random) pad input string s to n bytes, and return a bigint
843function pkcs1pad2(s, n) {
844	if (n < s.length + 11) {
845		alert("Message too long for RSA");
846		return null;
847	}
848	var ba = new Array();
849	var i = s.length - 1;
850	while (i >= 0 && n > 0)
851		ba[--n] = s.charCodeAt(i--);
852	ba[--n] = 0;
853	var rng = new SecureRandom();
854	var x = new Array();
855	while (n > 2) { // random non-zero pad
856		x[0] = 0;
857		while (x[0] == 0)
858			rng.nextBytes(x);
859		ba[--n] = x[0];
860	}
861	ba[--n] = 2;
862	ba[--n] = 0;
863	return new BigInteger(ba);
864}
865
866// "empty" RSA key constructor
867function RSAKey() {
868	this.n = null;
869	this.e = 0;
870	this.d = null;
871	this.p = null;
872	this.q = null;
873	this.dmp1 = null;
874	this.dmq1 = null;
875	this.coeff = null;
876}
877
878// Set the public key fields N and e from hex strings
879function RSASetPublic(N, E) {
880	if (N != null && E != null && N.length > 0 && E.length > 0) {
881		this.n = parseBigInt(N, 16);
882		this.e = parseInt(E, 16);
883	} else
884		alert("Invalid RSA public key");
885}
886
887// Perform raw public operation on "x": return x^e (mod n)
888function RSADoPublic(x) {
889	return x.modPowInt(this.e, this.n);
890}
891
892// Return the PKCS#1 RSA encryption of "text" as an even-length hex string
893function RSAEncrypt(text) {
894	var m = pkcs1pad2(text, (this.n.bitLength() + 7) >> 3);
895	if (m == null)
896		return null;
897	var c = this.doPublic(m);
898	if (c == null)
899		return null;
900	var h = c.toString(16);
901	if ((h.length & 1) == 0)
902		return h;
903	else
904		return "0" + h;
905}
906
907// Return the PKCS#1 RSA encryption of "text" as a Base64-encoded string
908// function RSAEncryptB64(text) {
909// var h = this.encrypt(text);
910// if(h) return hex2b64(h); else return null;
911// }
912
913// protected
914RSAKey.prototype.doPublic = RSADoPublic;
915
916// public
917RSAKey.prototype.setPublic = RSASetPublic;
918RSAKey.prototype.encrypt = RSAEncrypt;
919// RSAKey.prototype.encrypt_b64 = RSAEncryptB64;
920var b64map = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
921var b64pad = "=";
922
923function hex2b64(h) {
924	var i;
925	var c;
926	var ret = "";
927	for (i = 0; i + 3 <= h.length; i += 3) {
928		c = parseInt(h.substring(i, i + 3), 16);
929		ret += b64map.charAt(c >> 6) + b64map.charAt(c & 63);
930	}
931	if (i + 1 == h.length) {
932		c = parseInt(h.substring(i, i + 1), 16);
933		ret += b64map.charAt(c << 2);
934	} else if (i + 2 == h.length) {
935		c = parseInt(h.substring(i, i + 2), 16);
936		ret += b64map.charAt(c >> 2) + b64map.charAt((c & 3) << 4);
937	}
938	while ((ret.length & 3) > 0)
939		ret += b64pad;
940	return ret;
941}
942
943// convert a base64 string to hex
944function b64tohex(s) {
945	var ret = ""
946	var i;
947	var k = 0; // b64 state, 0-3
948	var slop;
949	for (i = 0; i < s.length; ++i) {
950		if (s.charAt(i) == b64pad)
951			break;
952		v = b64map.indexOf(s.charAt(i));
953		if (v < 0)
954			continue;
955		if (k == 0) {
956			ret += int2char(v >> 2);
957			slop = v & 3;
958			k = 1;
959		} else if (k == 1) {
960			ret += int2char((slop << 2) | (v >> 4));
961			slop = v & 0xf;
962			k = 2;
963		} else if (k == 2) {
964			ret += int2char(slop);
965			ret += int2char(v >> 2);
966			slop = v & 3;
967			k = 3;
968		} else {
969			ret += int2char((slop << 2) | (v >> 4));
970			ret += int2char(v & 0xf);
971			k = 0;
972		}
973	}
974	if (k == 1)
975		ret += int2char(slop << 2);
976	return ret;
977}
978
979// convert a base64 string to a byte/number array
980function b64toBA(s) {
981	//piggyback on b64tohex for now, optimize later
982	var h = b64tohex(s);
983	var i;
984	var a = new Array();
985	for (i = 0; 2 * i < h.length; ++i) {
986		a[i] = parseInt(h.substring(2 * i, 2 * i + 2), 16);
987	}
988	return a;
989}
990