1 /* (original disclaimer from JSBN, on which this file is based)
  2  *
  3  * Copyright (c) 2003-2005  Tom Wu
  4  * All Rights Reserved.
  5  *
  6  * Permission is hereby granted, free of charge, to any person obtaining
  7  * a copy of this software and associated documentation files (the
  8  * "Software"), to deal in the Software without restriction, including
  9  * without limitation the rights to use, copy, modify, merge, publish,
 10  * distribute, sublicense, and/or sell copies of the Software, and to
 11  * permit persons to whom the Software is furnished to do so, subject to
 12  * the following conditions:
 13  *
 14  * The above copyright notice and this permission notice shall be
 15  * included in all copies or substantial portions of the Software.
 16  *
 17  * THE SOFTWARE IS PROVIDED "AS-IS" AND WITHOUT WARRANTY OF ANY KIND, 
 18  * EXPRESS, IMPLIED OR OTHERWISE, INCLUDING WITHOUT LIMITATION, ANY 
 19  * WARRANTY OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.  
 20  *
 21  * IN NO EVENT SHALL TOM WU BE LIABLE FOR ANY SPECIAL, INCIDENTAL,
 22  * INDIRECT OR CONSEQUENTIAL DAMAGES OF ANY KIND, OR ANY DAMAGES WHATSOEVER
 23  * RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER OR NOT ADVISED OF
 24  * THE POSSIBILITY OF DAMAGE, AND ON ANY THEORY OF LIABILITY, ARISING OUT
 25  * OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 26  *
 27  * In addition, the following condition applies:
 28  *
 29  * All redistributions must retain an intact copy of this copyright notice
 30  * and disclaimer.
 31  */
 32 
 33 /**
 34  * @namespace High-precision arithmetic
 35  * @author Tom Wu (original author of JSBN)
 36  * @author Anonymized
 37  * @description
 38  * <p>Minimal set of high precision arithmetic operations
 39  * for RSA encryption and decryption.</p>
 40  * <p>To preserve both defensiveness and performance, this
 41  * is not an arbitrary precision library! Each number is
 42  * represented by a constant length array of 256 elements.
 43  * Because of tagging optimizations, each number stores 28
 44  * bits, hence the maximal precision is 7168 bits. 128 was
 45  * not chosen to allow RSA on a 2048 bit modulus, and it is
 46  * highly preferred to use a power of 2 to use the short
 47  * dynamic accessor notation.</p>
 48  * @requires encoding
 49  */
 50  var BigInteger =
 51  {
 52   BI_DB: 28,
 53   BI_DM: 268435455,
 54   BI_DV: 268435456,
 55   BI_FP: 52,
 56   BI_FV: 4503599627370496,
 57   BI_F1: 24,
 58   BI_F2: 4,
 59 
 60 /** Create a new BigInteger initialized from the given hex value.
 61   * @param {string} v Hex representation of initial value in a string.
 62   * @returns {BigInteger} A BigInteger structure.
 63   */
 64   create: function(v)
 65   {
 66    var neg = false, p = '', b = '', s = v+'', i = s.length, j = 0, a =
 67    [ 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
 68      0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
 69      0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
 70      0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
 71      0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
 72      0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
 73      0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
 74      0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 ],
 75        res = {array:a, t:0, s:0};
 76 
 77    while(--i >= 0)
 78    {
 79     b = s[(i>>>0)%s.length];
 80     if(i==0 && b=='-'){neg = true; continue;}
 81     p = b + p;
 82     if(j++%7==6)
 83     {
 84      a[res.t++&255] = +('0x'+p); p = '';
 85     }
 86    }
 87    if(!!p) a[res.t++&255] = +('0x'+p); p = '';
 88 
 89    if(neg) res = this.negate(res);
 90    this.clamp(res);
 91    return res;
 92   },
 93 
 94   am: function(th,i,x,w,j,c,n)
 95   {
 96    var a = th.array, b = w.array, l = 0, m = 0,
 97       xl = x&0x3fff, xh = x>>14, h = 0;
 98 
 99    while(--n >= 0)
100    {
101     l = a[i&255]&0x3fff;i
102     h = a[i++&255]>>14;
103     m = xh*l+h*xl;
104     l = xl*l+((m&0x3fff)<<14)+b[j&255]+c;
105     c = (l>>28)+(m>>14)+xh*h;
106     b[j++&255] = l&0xfffffff;
107    }
108 
109    return c;
110   },
111 
112 /** Copy the value of a BigInteger to another.
113   * @param {BigInteger} source Integer to copy.
114   * @param {BigInteger} target Target of copy.
115   * @returns {BigInteger} Returns the target of the copy.
116   */
117   copyTo: function(th, r)
118   {
119    var ta = th.array, ra = r.array, i = 0;
120 
121    for(i = th.t-1; i >= 0; --i)
122     ra[i&255] = ta[i&255];
123 
124    r.t = th.t; r.s = th.s;
125    return r;
126   },
127 
128   clamp: function(th)
129   {
130    var a = th.array, c = th.s & this.BI_DM;
131    while(th.t > 0 && a[(th.t-1)&255] == c) --th.t;
132   },
133 
134 /** Convert BigInteger to its hex representation.
135   * @param {BigInteger} n Number to convert
136   * @returns {string} Hex representation of n, as a string.
137   */
138   toString: function(th)
139   {
140    var a = th.array, c = 0, i = 0, j = 0,
141        nz = false, h = '', res = '', i = 0;
142 
143    if(th.s < 0)
144     return "-"+this.toString(this.negate(th));
145 
146    for(i=th.t-1; i>=0; i--)
147    {
148     c = a[i&255];
149     for(j=24; j>=0; j-=4)
150     {
151      if((h=encoding.hex[(c>>j)&15])!='0') nz=true;
152      if(nz) res+=h;
153     }
154    }
155 
156    return !res ? '0' : res;
157   },
158 
159 /** Change sign of number.
160   * @param {BigInteger} n Input number
161   * @returns {BigInteger} A newly allocated BigInteger with opposite value
162   */
163   negate: function(th)
164   {
165    var t = this.create('0'), z = this.create('0');
166    this.subTo(z, th, t);
167    return t;
168   },
169 
170 /** Absolute value.
171   * @param {BigInteger} n Input number
172   * @returns {BigInteger} If n is positive, returns n, otherwise return negate(n)
173   */
174   abs: function(th)
175   {
176    return th.s<0 ? this.negate(th) : th;
177   },
178 
179 /** Exclusive OR of two numbers
180   * @param {BigInteger} n First operand
181   * @param {BigInteger} m Second operand
182   * @returns {BigInteger} n xor m
183   */
184   xor: function(th, a)
185   {
186    var x = th.array, y = a.array,
187        r = this.create('0'), z = r.array,
188        i = (th.t > a.t) ? th.t : a.t;
189    r.t = i;
190    while(--i >= 0) z[i&255] = x[i&255]^y[i&255];
191    return r;
192   },
193 
194 /** Comparison of BigInteger.
195   * @param {BigInteger} n First value
196   * @param {BigInteger} m Second value
197   * @returns {number} A negative value if n<m, 0 if n=m and a positive value otherwise.
198   */
199   compareTo: function(th,a)
200   {
201    var x = th.array, y = a.array, i = th.t,
202        r = th.s-a.s, s = th.t-a.t;
203 
204    if(!!r) return r; if(!!s) return s;
205    while(--i >= 0)
206     if((r = (x[i&255]-y[i&255]))!=0) return r;
207    return 0;
208   },
209 
210 /** Index of the first non-zero bit starting from the least significant bit.
211   * @param {number} n  Input number
212   * @returns {number} the bit length of n. Can behave strangely on negative and float values.
213   */
214   nbits: function(x)
215   {
216    var r = 1, t = 0;
217    if((t=x>>>16) != 0) { x = t; r += 16; }
218    if((t=x>>8) != 0) { x = t; r += 8; }
219    if((t=x>>4) != 0) { x = t; r += 4; }
220    if((t=x>>2) != 0) { x = t; r += 2; }
221    if((t=x>>1) != 0) { x = t; r += 1; }
222    return r;
223   },
224 
225 /** Index of first non-zero bit starting from the LSB of the given BigInteger.
226   * @param {BigInteger} n Input BigInteger
227   * @returns {number} the bit length of n.
228   */
229   bitLength: function(th)
230   {
231    var a = th.array;
232    if(th.t <= 0) return 0;
233    return this.BI_DB*(th.t-1)+this.nbits(a[(th.t-1)&255]^(th.s&this.BI_DM));
234   },
235 
236   DLshiftTo: function(th,n,r)
237   {
238    var a = th.array, b = r.array, i = 0;
239    for(i = th.t-1; i >= 0; --i) b[(i+n)&255] = a[i&255];
240    for(i = n-1; i >= 0; --i) b[i&255] = 0;
241    r.t = th.t+n; r.s = th.s;
242   },
243 
244   DRshiftTo: function(th,n,r)
245   {
246    var a = th.array, b = r.array, i = 0;
247    for(i = n; i < th.t; ++i) b[(i-n)&255] = a[i&255];
248    r.t = th.t>n?th.t-n:0; r.s = th.s;
249   },
250 
251 /** Logical shift to the left
252   * @param {BigInteger} n Input number
253   * @param {number} k Number of positions to shift
254   * @param {BigInteger} r Target number to store the result to
255   */
256   LshiftTo: function(th,n,r)
257   {
258    var a = th.array, b = r.array,
259       bs = n%this.BI_DB, cbs = this.BI_DB-bs,
260       bm = (1<<cbs)-1,  ds = (n/this.BI_DB)|0,
261        c = (th.s<<bs)&this.BI_DM, i = 0;
262 
263    for(i = th.t-1; i >= 0; --i)
264     b[(i+ds+1)&255] = (a[i&255]>>cbs)|c, c = (a[i&255]&bm)<<bs;
265    for(i = ds-1; i >= 0; --i) b[i&255] = 0;
266 
267    b[ds&255] = c; r.t = th.t+ds+1;
268    r.s = th.s; this.clamp(r);
269   },
270 
271 /** Logical shift to the right.
272   * @param {BigInteger} n Input number
273   * @param {number} k Number of positions to shift
274   * @param {BigInteger} r Target number to store the result to
275   */
276   RshiftTo: function(th,n,r)
277   {
278    var a = th.array, b = r.array, i = 0,
279       bs = n%this.BI_DB, cbs = this.BI_DB-bs,
280       bm = (1<<bs)-1,  ds = (n/this.BI_DB)|0;
281 
282    r.s = th.s;
283    if(ds >= th.t) { r.t = 0; return; }
284    b[0] = a[ds&255]>>bs;
285 
286    for(i = ds+1; i < th.t; ++i)
287     b[(i-ds-1)&255] |= (a[i&255]&bm)<<cbs,
288     b[(i-ds)&255] = a[i&255]>>bs;
289    if(bs > 0) b[(th.t-ds-1)&255] |= (th.s&bm)<<cbs;
290 
291    r.t = th.t-ds; this.clamp(r);
292   },
293 
294 /** Subtraction of BigIntegers.
295   * @param {BigInteger} n First operand
296   * @param {BigInteger} m Second operand
297   * @param {BigInteger} r Target number to store the result (n-m) to.
298   */
299   subTo: function(th, y, r)
300   {
301    var a = th.array, z = r.array, b = y.array,
302        i = 0, c = 0, m = y.t<th.t?y.t:th.t;
303 
304    while(i < m)
305    {
306     c += a[i&255]-b[i&255];
307     z[i++&255] = c&this.BI_DM;
308     c >>= this.BI_DB;
309    }
310 
311    if(y.t < th.t)
312    {
313     c -= y.s;
314     while(i < th.t)
315     {
316      c += a[i&255];
317      z[i++&255] = c&this.BI_DM;
318      c >>= this.BI_DB;
319     }
320     c += th.s;
321    }
322    else
323    {
324     c += th.s;
325     while(i < y.t)
326     {
327      c -= b[i&255];
328      z[i++&255] = c&this.BI_DM;
329      c >>= this.BI_DB;
330     }
331     c -= y.s;
332    }
333 
334    r.s = (c<0)?-1:0;
335    if(c < -1) z[i++&255] = this.BI_DV+c;
336    else if(c > 0) z[i++&255] = c;
337    r.t = i; this.clamp(r);
338   },
339 
340 /** Multiplication of BigIntegers.
341   * @param {BigInteger} n First operand
342   * @param {BigInteger} m Second operand
343   * @param {BigInteger} r Target number to store the result (n*m) to.
344   */
345   multiplyTo: function(th,a,r)
346   {
347    var u = th.array, v = r.array,
348        x = this.abs(th), y = this.abs(a),
349        w = y.array, i = x.t;
350 
351    r.t = i+y.t;
352    while(--i >= 0) v[i&255] = 0;
353    for(i = 0; i < y.t; ++i)
354     v[(i+x.t)&255] = this.am(x,0,w[i&255],r,i,0,x.t);
355 
356    r.s = 0; this.clamp(r);
357    if(th.s != a.s) this.subTo(this.create('0'),r,r);
358   },
359 
360 /** Squaring of a BigInteger.
361   * @param {BigInteger} n First operand
362   * @param {BigInteger} r Target number to store the result (n*n) to.
363   */
364   squareTo: function(th, r)
365   {
366    var x = this.abs(th), u = x.array, v = r.array,
367        i = (r.t = 2*x.t), c = 0;
368 
369    while(--i >= 0) v[i&255] = 0;
370    for(i = 0; i < x.t-1; ++i)
371    {
372     c = this.am(x,i,u[i&255],r,2*i,0,1);
373     if((v[(i+x.t)&255] += this.am(x,i+1,2*u[i&255],r,2*i+1,c,x.t-i-1)) >= this.BI_DV)
374      v[(i+x.t)&255] -= this.BI_DV, v[(i+x.t+1)&255] = 1;
375    }
376 
377    if(r.t > 0) v[(r.t-1)&255] += this.am(x,i,u[i&255],r,2*i,0,1);
378    r.s = 0; this.clamp(r);
379   },
380 
381 /** Euclidean division of two BigIntegers.
382   * @param {BigInteger} n First operand
383   * @param {BigInteger} m Second operand
384   * @returns {BigInteger array[2]} Returns an array of two BigIntegers: first element is the quotient, second is the remainder.
385   */
386   divRem: function(th, div)
387   {
388    var m = this.abs(div), t = this.abs(th), ma = m.array, ta = th.array,
389        ts = th.s, ms = m.s, nsh = this.BI_DB-this.nbits(ma[(m.t-1)&255]),
390        q = this.create('0'), r = this.create('0'),
391        qa = q.array, ra = r.array, qd = 0,
392        y = this.create('0'), ya = y.array, ys = 0, y0 = 0,
393        yt = 0, i = 0, j = 0, d1 = 0, d2 = 0, e = 0;
394 
395    if(t.t < m.t) this.copyTo(th,r);
396    if(!m.t || t.t < m.t) return [q,r];
397 
398    if(nsh > 0){ this.LshiftTo(m,nsh,y); this.LshiftTo(t,nsh,r); }
399    else{ this.copyTo(m,y); this.copyTo(m,r); }
400 
401    ys = y.t; y0 = ya[(ys-1)&255];
402    if(y0 == 0) return [q,r];
403 
404    yt = y0*(1<<this.BI_F1)+((ys>1)?ya[(ys-2)&255]>>this.BI_F2:0);
405    d1 = this.BI_FV/yt, d2 = (1<<this.BI_F1)/yt, e = 1<<this.BI_F2;
406    i = r.t, j = i-ys;
407    this.DLshiftTo(y,j,q);
408 
409    if(this.compareTo(r,q) >= 0)
410    {
411     ra[r.t++ & 255] = 1;
412     this.subTo(r,q,r);
413    }
414 
415    this.DLshiftTo(this.create('1'),ys,q);
416    this.subTo(q,y,y);
417    while(y.t < ys) ya[y.t++&255] = 0;
418 
419    while(--j >= 0)
420    {
421     qd = (ra[--i&255]==y0)?this.BI_DM:(ra[i&255]*d1+(ra[(i-1)&255]+e)*d2)|0;
422     if((ra[i&255]+=this.am(y,0,qd,r,j,0,ys)) < qd)
423     {
424      this.DLshiftTo(y,j,q);
425      this.subTo(r,q,r);
426      while(ra[i&255] < --qd) this.subTo(r,q,r);
427     }
428    }
429 
430    this.DRshiftTo(r,ys,q);
431    if(ts != ms) this.subTo(this.create('0'),q,q);
432    r.t = ys; this.clamp(r);
433 
434    if(nsh > 0) this.RshiftTo(r,nsh,r);
435    if(ts < 0) this.subTo(this.create('0'),r,r);
436    return [q,r];
437   },
438 
439 /** Modular remainder of an integer division.
440   * @param {BigInteger} n First operand
441   * @param {BigInteger} m Second operand
442   * @returns {BigInteger} n mod m
443   */
444   mod: function(th, a)
445   {
446    var r = this.divRem(this.abs(th),a)[1];
447    if(th.s < 0 && this.compareTo(r,this.create('0')) > 0) this.subTo(a,r,r);
448    return r;
449   },
450 
451   invDigit: function(th)
452   {
453    var a = th.array, x = a[0], y = x&3;
454    if(th.t < 1 || !(x&1)) return 0;
455    y = (y*(2-(x&0xf)*y))&0xf;
456    y = (y*(2-(x&0xff)*y))&0xff;
457    y = (y*(2-(((x&0xffff)*y)&0xffff)))&0xffff;
458    y = (y*(2-x*y%this.BI_DV))%this.BI_DV;
459    return (y>0)?this.BI_DV-y:-y;
460   },
461 
462 /** Modular exponentiation using Montgomery reduction. 
463   * @param {BigInteger} x Value to exponentiate
464   * @param {BigInteger} e Exponent
465   * @param {BigInteger} n Modulus - must be odd
466   * @returns {BigInteger} x^e mod n
467   */
468   expMod: function(th, e, m)
469   {
470    var r = this.create('1'), r2 = this.create('0'), eb = e.array[(e.t-1)&255],
471        g = this.Mconvert(th,m), i = this.bitLength(e)-1, j = 0, t = r;
472 
473    if(this.compareTo(e,r)<0) return r;
474    this.copyTo(g,r);
475 
476    while(--i >= 0)
477    {
478     j = i%this.BI_DB;
479     this.squareTo(r,r2); this.Mreduce(r2,m);
480     if((eb&(1<<j)) != 0){ this.multiplyTo(r2,g,r); this.Mreduce(r,m); }
481     else { t = r; r = r2; r2 = t; }
482     if(!j) eb = e.array[(i/this.BI_DB-1)&255];
483    }
484 
485    return this.Mrevert(r,m);
486   },
487 
488   Mconvert: function(th, m)
489   {
490    var s = this.create('0'),
491        r = (this.DLshiftTo(this.abs(th),m.t,s),this.divRem(s,m))[1];
492 
493    if(th.s < 0 && this.compareTo(r,this.create('0')) > 0) this.subTo(m,r,r);
494    return r;
495   },
496 
497   Mreduce: function(th, m)
498   {
499    var mp = this.invDigit(m), mpl = mp&0x7fff, mph = mp>>15, a = th.array,
500        um = (1<<(this.BI_DB-15))-1, mt2 = 2*m.t, i = 0, j = 0, u0 = 0;
501 
502    while(th.t <= mt2) a[th.t++&255] = 0;
503    for(i = 0; i < m.t; ++i)
504    {
505     j = a[i&255]&0x7fff;
506     u0 = (j*mpl+(((j*mph+(a[i&255]>>15)*mpl)&um)<<15))&this.BI_DM;
507     j = i+m.t;
508     a[j&255] += this.am(m,0,u0,th,i,0,m.t);
509     while(a[j&255] >= this.BI_DV) { a[j&255] -= this.BI_DV; a[++j&255]++; }
510    }
511 
512    this.clamp(th); this.DRshiftTo(th, m.t, th);
513    if(this.compareTo(th,m) >= 0) this.subTo(th,m,th);
514    return th;
515   },
516 
517   Mrevert: function(th, m)
518   {
519    var c = this.create('0');
520    this.copyTo(th, c);
521    return this.Mreduce(c,m);
522   }
523  };
524 
525