[Summary view] [Print] [Text view]

   1  /* The following functions are (c) 2000 by John M Hanna and are
   2   * released under the terms of the Gnu Public License.
   3   * You must freely redistribute them with their source -- see the
   4   * GPL for details.
   5   *  -- Latest version found at http://sourceforge.net/projects/shop-js
   6   */
   7  
   8  // ---------------------- Arbitrary Precision Math
   9  // badd(a,b), bsub(a,b), bmul(a,b), bdiv(a,b), bmod(a,b),
  10  // brshift(a), beq(a,b)
  11  
  12  // set the base... 32bit cpu -> bs=16, 64bit -> bs=32
  13  // bm is the mask, bs is the shift
  14  //bm=0xf; bs=4;  // low base useful for testing if digits handled ok
  15  bs=28;
  16  bx2=1<<bs; bm=bx2-1; bx=bx2>>1; bd=bs>>1; bdm=(1 << bd) -1
  17  log2=Math.log(2)
  18  
  19  
  20  function badd(a,b) { // binary add
  21   var al=a.length, bl=b.length
  22   if(al < bl) return badd(b,a)
  23   var c=0, r=[], n=0
  24   for(; n<bl; n++) {
  25    c+=a[n]+b[n]
  26    r[n]=c & bm
  27    c>>>=bs
  28   }
  29   for(; n<al; n++) {
  30    c+=a[n]
  31    r[n]=c & bm
  32    c>>>=bs
  33   }
  34   if(c) r[n]=c
  35   return r
  36  }
  37  function beq(a,b) { // returns 1 if a == b
  38   if(a.length != b.length) return 0
  39   for(var n=a.length-1; n>=0; n--)
  40    if(a[n] != b[n]) return 0
  41   return 1
  42  }
  43  function bsub(a,b) { // binary subtract
  44   var al=a.length, bl=b.length, c=0, r=[]
  45   if(bl > al) {return []}
  46   if(bl == al) {
  47    if(b[bl-1] > a[bl-1]) return []
  48    if(bl==1) return [a[0]-b[0]]
  49   }
  50   for(var n=0; n<bl; n++) {
  51    c+=a[n]-b[n]
  52    r[n]=c & bm
  53    c>>=bs
  54   }
  55   for(;n<al; n++) {
  56    c+=a[n]
  57    r[n]=c & bm
  58    c>>=bs
  59   }
  60   if(c) {return []}
  61   if(r[n-1]) return r
  62   while(n>1 && r[n-1]==0) n--;
  63   return r.slice(0,n)
  64  }
  65  function bmul(a,b) { // binary multiply
  66   b=b.concat([0])
  67   var al=a.length, bl=b.length, r=[], n,nn,aa, c, m
  68   var g,gg,h,hh, ghhb
  69  
  70   for(n=al+bl; n>=0; n--) r[n]=0
  71   for(n=0; n<al; n++) {
  72    if(aa=a[n]) {
  73     c=0
  74     hh=aa>>bd; h=aa & bdm
  75     m=n
  76     for(nn=0; nn<bl; nn++, m++) {
  77      g = b[nn]; gg=g>>bd; g=g & bdm
  78      //(gg*2^15 + g) * (hh*2^15 + h) = (gghh*2^30 + (ghh+hgg)*2^15 +hg)
  79      ghh = g * hh + h * gg
  80      ghhb= ghh >> bd; ghh &= bdm
  81      c += r[m] + h * g + (ghh << bd)
  82      r[m] = c & bm
  83      c = (c >> bs) + gg * hh + ghhb
  84     }
  85    }
  86   }
  87   n=r.length
  88   if(r[n-1]) return r
  89   while(n>1 && r[n-1]==0) n--;
  90   return r.slice(0,n)
  91  }
  92  
  93  function blshift(a,b) {
  94   var n, c=0, r=[]
  95   for(n=0; n<a.length; n++) {
  96    c|= (a[n]<<b) 
  97    r[n]= c & bm
  98    c>>=bs
  99   }
 100   if(c) r[n]=c
 101   return r
 102  }
 103  function brshift(a) {
 104   var c=0,n,cc, r=[]
 105   for(n=a.length-1; n>=0; n--) {
 106    cc=a[n]; c<<=bs
 107    r[n]=(cc | c)>>1
 108    c=cc & 1
 109   }
 110   while(r.length > 1 && r[r.length-1]==0) {
 111    r=r.slice(0,-1)
 112   }
 113   this.a=r; this.c=c
 114   return this
 115  }
 116  function zeros(n) {var r=[]; while(n-->0) r[n]=0; return r}
 117  function toppart(x,start,len) { var n=0
 118   while(start >= 0 && len-->0) n=n*bx2+x[start--]
 119   return n
 120  }
 121  //14.20 Algorithm Multiple-precision division from HAC
 122  function bdiv(x,y) {
 123   var n=x.length-1, t=y.length-1, nmt=n-t
 124   // trivial cases; x < y
 125   if(n < t || n==t && (x[n]<y[n] || n>0 && x[n]==y[n] && x[n-1]<y[n-1])) {
 126    this.q=[0]; this.mod=x; return this
 127   }
 128   // trivial cases; q < 4
 129   if(n==t && toppart(x,t,2)/toppart(y,t,2) <4) {
 130    var q=0, xx
 131    for(;;) {
 132     xx=bsub(x,y)
 133     if(xx.length==0) break
 134     x=xx; q++
 135    }
 136    this.q=[q]; this.mod=x; return this
 137   }
 138   var shift, shift2
 139   // normalize
 140   shift2=Math.floor(Math.log(y[t])/log2)+1
 141   shift=bs-shift2
 142   if(shift) {
 143    x=x.concat(); y=y.concat()
 144    for(i=t; i>0; i--) y[i]=((y[i]<<shift) & bm) | (y[i-1] >> shift2); y[0]=(y[0]<<shift) & bm
 145    if(x[n] & ((bm <<shift2) & bm)) { x[++n]=0; nmt++; }
 146    for(i=n; i>0; i--) x[i]=((x[i]<<shift) & bm) | (x[i-1] >> shift2); x[0]=(x[0]<<shift) & bm
 147   }
 148   var i, j, x2, y2,q=zeros(nmt+1)
 149  
 150   y2=zeros(nmt).concat(y)
 151   for(;;) {
 152    x2=bsub(x,y2)
 153    if(x2.length==0) break
 154    q[nmt]++
 155    x=x2
 156   }
 157   var yt=y[t], top=toppart(y,t,2)
 158   for(i=n; i>t; i--) {
 159    m=i-t-1
 160    if(i >= x.length)
 161     q[m]=1
 162    else if(x[i] == yt)
 163     q[m]=bm
 164    else
 165     q[m]=Math.floor(toppart(x,i,2)/yt)
 166  
 167    topx=toppart(x,i,3)
 168    while(q[m] * top > topx)
 169     q[m]--
 170    //x-=q[m]*y*b^m
 171    y2=y2.slice(1)
 172    x2=bsub(x,bmul([q[m]],y2))
 173    if(x2.length==0) {
 174     q[m]--
 175     x2=bsub(x,bmul([q[m]],y2))
 176    }
 177    x=x2
 178   }
 179   // de-normalize
 180   if(shift) {
 181    for(i=0; i<x.length-1; i++) x[i]=(x[i]>>shift) | ((x[i+1] << shift2) & bm); x[x.length-1]>>=shift
 182   }
 183   while(q.length > 1 && q[q.length-1]==0) q=q.slice(0,q.length-1)
 184   while(x.length > 1 && x[x.length-1]==0) x=x.slice(0,x.length-1)
 185   this.mod=x
 186   this.q=q
 187   return this
 188  }
 189  
 190  function bmod(p,m) { // binary modulo
 191   if(m.length==1) {
 192    if(p.length==1) return [p[0] % m[0]]
 193    if(m[0] < bdm) return [simplemod(p,m[0])]
 194   }
 195  
 196   var r=bdiv(p,m)
 197   return r.mod
 198  }
 199  function simplemod(i,m) {
 200   // returns the mod where m < 2^bd
 201   if(m>bdm)
 202    return mod(i,[m])
 203   var c=0, v
 204   for(var n=i.length-1; n>=0; n--) {
 205    v=i[n]
 206    c=((v >> bd) + (c<<bd)) % m
 207    c=((v & bdm) + (c<<bd)) % m
 208   }
 209   return c
 210  }
 211  function bmodexp(xx,y,m) { // binary modular exponentiation
 212   var r=[1], n, an,a, x=xx.concat()
 213   var mu=[]
 214   n=m.length*2;  mu[n--]=1;  for(; n>=0; n--) mu[n]=0; mu=bdiv(mu,m).q
 215  
 216   for(n=0; n<y.length; n++) {
 217    for(a=1, an=0; an<bs; an++, a<<=1) {
 218     if(y[n] & a) r=bmod2(bmul(r,x),m,mu)
 219     x=bmod2(bmul(x,x),m,mu)
 220    }
 221   }
 222   return r
 223  }
 224  function bmod2(x,m,mu) { // Barrett's modular reduction from HAC, 14.42, CRC Press
 225   var xl=x.length - (m.length << 1)
 226   if(xl > 0) {
 227    return bmod2(x.slice(0,xl).concat(bmod2(x.slice(xl),m,mu)),m,mu)
 228   }
 229   var ml1=m.length+1, ml2=m.length-1,rr
 230   //var q1=x.slice(ml2)
 231   //var q2=bmul(q1,mu)
 232   var q3=bmul(x.slice(ml2),mu).slice(ml1)
 233   var r1=x.slice(0,ml1)
 234   var r2=bmul(q3,m).slice(0,ml1)
 235   var r=bsub(r1,r2)
 236   //var s=('x='+x+'\nm='+m+'\nmu='+mu+'\nq1='+q1+'\nq2='+q2+'\nq3='+q3+'\nr1='+r1+'\nr2='+r2+'\nr='+r); 
 237   if(r.length==0) {
 238    r1[ml1]=1
 239    r=bsub(r1,r2)
 240   }
 241   for(var n=0;;n++) {
 242    rr=bsub(r,m)
 243    if(rr.length==0) break
 244    r=rr
 245    if(n>=3) return bmod2(r,m,mu)
 246   }
 247   return r
 248  }
 249  
 250  function sub2(a,b) {
 251   var r=bsub(a,b)
 252   if(r.length==0) {
 253    this.a=bsub(b,a)
 254    this.sign=1
 255   } else {
 256    this.a=r
 257    this.sign=0
 258   }
 259   return this
 260  }
 261  function signedsub(a,b) {
 262   if(a.sign) {
 263    if(b.sign) {
 264     return sub2(b,a)
 265    } else {
 266     this.a=badd(a,b)
 267     this.sign=1
 268    }
 269   } else {
 270    if(b.sign) {
 271     this.a=badd(a,b)
 272     this.sign=0
 273    } else {
 274     return sub2(a,b)
 275    }
 276   }
 277   return this
 278  }
 279  
 280  function modinverse(x,n) { // returns x^-1 mod n
 281  // from  Bryan Olson <bryanolson@my-deja.com> 
 282   var y=n.concat(), t, r, bq, a=[1], b=[0], ts
 283   a.sign=0; b.sign=0
 284   while( y.length > 1 || y[0]) {
 285    t=y.concat()
 286    r=bdiv(x,y)
 287    y=r.mod
 288    q=r.q
 289    x=t
 290    t=b.concat(); ts=b.sign
 291    bq=bmul(b,q)
 292    bq.sign=b.sign
 293    r=signedsub(a,bq)
 294    b=r.a; b.sign=r.sign
 295    a=t; a.sign=ts
 296   }
 297   if(beq(x,[1])==0) return [0] // No inverse; GCD is x
 298   if(a.sign) {
 299    a=bsub(n,a)
 300   }
 301   return a
 302  }
 303  
 304  function crt_RSA(m, d, p, q) {
 305   // Compute m**d mod p*q for RSA private key operations. -- Bryan Olson via deja.com
 306   var xp = bmodexp(bmod(m,p), bmod(d,bsub(p,[1])), p)
 307   var xq = bmodexp(bmod(m,q), bmod(d,bsub(q,[1])), q)
 308   var t=bsub(xq,xp);
 309   if(t.length==0) {
 310    t=bsub(xp,xq)
 311    t = bmod(bmul(t, modinverse(p, q)), q);
 312    t=bsub(q,t)
 313   } else {
 314    t = bmod(bmul(t, modinverse(p, q)), q);
 315   } 
 316   return badd(bmul(t,p), xp)
 317  }
 318  
 319  // conversion functions:
 320  // text to binary and binary to text, text to base64 and base64 to text
 321  // OK, so this isn't exactly base64 -- fix it if you care
 322  
 323  function t2b(s) {
 324   var bits=s.length*8, bn=1, r=[0], rn=0, sn=0, sb=1;
 325   var c=s.charCodeAt(0)
 326   for(var n=0; n<bits; n++) {
 327    if(bn > bm) {bn=1; r[++rn]=0; }
 328    if(c & sb)  r[rn]|=bn;
 329    bn<<=1
 330    if((sb<<=1) > 255) {sb=1; c=s.charCodeAt(++sn); }
 331   }
 332   return r;
 333  }
 334  function b2t(b) {
 335   var bits=b.length*bs, bn=1, bc=0, r=[0], rb=1, rn=0
 336   for(var n=0; n<bits; n++) {
 337    if(b[bc] & bn) r[rn]|=rb;
 338    if((rb<<=1) > 255) {rb=1; r[++rn]=0; }
 339    if((bn<<=1) > bm) {bn=1; bc++; }
 340   }
 341   while(r[rn]==0) {rn--;}
 342   var rr=''
 343   for(var n=0; n<=rn; n++) rr+=String.fromCharCode(r[n]);
 344   return rr;
 345  }
 346  b64s='abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789_"'
 347  function textToBase64(t) {
 348   var r=''; var m=0; var a=0; var tl=t.length-1; var c
 349   for(n=0; n<=tl; n++) {
 350    c=t.charCodeAt(n)
 351    r+=b64s.charAt((c << m | a) & 63)
 352    a = c >> (6-m)
 353    m+=2
 354    if(m==6 || n==tl) {
 355     r+=b64s.charAt(a)
 356     if((n%45)==44) {r+="\n"}
 357     m=0
 358     a=0
 359    }
 360   }
 361   return r
 362  }
 363  function base64ToText(t) {
 364   var r=''; var m=0; var a=0; var c
 365   for(n=0; n<t.length; n++) {
 366    c=b64s.indexOf(t.charAt(n))
 367    if(c >= 0) {
 368     if(m) {
 369      r+=String.fromCharCode((c << (8-m))&255 | a)
 370     }
 371     a = c >> m
 372     m+=2
 373     if(m==8) { m=0 }
 374    }
 375   }
 376   return r
 377  }
 378  
 379  // RC4 stream encryption
 380  // adapted from www.cpan.org crypt::rc4 -- thanks!
 381  function rc4(key, text) {
 382   var i, x, y, t, x2, kl=key.length;
 383   s=[];
 384  
 385   for (i=0; i<256; i++) s[i]=i
 386   y=0
 387   for(j=0; j<2; j++) {
 388    for(x=0; x<256; x++) {
 389     y=(key.charCodeAt(x%kl) + s[x] + y) % 256
 390     t=s[x]; s[x]=s[y]; s[y]=t
 391    }
 392   }
 393   var z=""
 394   for (x=0; x<text.length; x++) {
 395    x2=x & 255
 396    y=( s[x2] + y) & 255
 397    t=s[x2]; s[x2]=s[y]; s[y]=t
 398    z+= String.fromCharCode((text.charCodeAt(x) ^ s[(s[x2] + s[y]) % 256]))
 399   }
 400   return z
 401  }
 402  
 403  function ror(a,n) {n&=7; return n?((a>>n) | ((a<<(8-n))&255)):a;}
 404  function hash(s,l) {
 405   var sl=s.length,r=[],rr='',v=1,lr=4;
 406   for(var n=0; n<l; n++) r[n]=(v=((v*v*5081+n) & 255));
 407   while(sl--) {
 408    lr = r[sl % l] ^= ror(s.charCodeAt(sl),lr) ^ r[r[(sl * 5081) % l] % l];
 409   }
 410   for(var n=0; n<l; n++)
 411    rr+=String.fromCharCode(r[n] ^
 412     ror(r[r[(n * 171) % l] % l],r[n]));
 413   return rr
 414  }
 415  
 416  // tie it all together with rsa encrypt and decrypt
 417  function rsaEncode(key,mod,text) {
 418   // create a good random session key
 419   var keylen=Math.floor((mod.length+1)*bs/8)
 420   var sessionkey=hash(text+Date()+Math.random(),keylen)
 421  
 422   // sessionkey must be less than modulo
 423   sessionkey=bmod(t2b(sessionkey),mod)
 424  
 425   // convert it from arbitrary precision representation into text for RC4
 426   var sk2=b2t(sessionkey)
 427  
 428   // rsa encrypt the key
 429   var ske=bmodexp(sessionkey,key,mod)
 430  
 431   // to pack it in with the text we need its length
 432   var skeText=b2t(ske)
 433  
 434    // return the rsa encoded key and the encrypted text
 435   // pack up the completed encoded package with base64
 436   return textToBase64(
 437    String.fromCharCode(skeText.length)+skeText+
 438    rc4(sk2,text))
 439  }
 440  function rsaDecode(key,text) {
 441   // separate the session key from the text
 442   text=base64ToText(text)
 443   var sessionKeyLength=text.charCodeAt(0)
 444   var sessionKeyEncryptedText=text.substr(1,sessionKeyLength)
 445   text=text.substr(sessionKeyLength+1)
 446   var sessionKeyEncrypted=t2b(sessionKeyEncryptedText)
 447  
 448   // un-rsa the session key
 449   sessionkey=crt_RSA(sessionKeyEncrypted,key[0],key[1],key[2])
 450   sessionkey=b2t(sessionkey)
 451  
 452   text=rc4(sessionkey,text)
 453   return text
 454  }
 455