/* ***************************************************************
This is a JavaScript Library that contains a variety of functions
that support encryption efforts.  Everything from data obfuscation
functions, to Pseudo Random Number Generators, to hash functions.

There is a major effort to create alternatives to Cryptographically
Secure pseudo-random number Generators (CSGs).  I have several
examples of alternate techniques.
*************************************************************** */

                      /* GLOBAL CONSTANTS */
       /* ***** First, we have true global constants ***** */
var Hex = new Array (  // for doing hex I/O to an HTML page
'0','1','2','3','4','5','6','7','8','9','a','b','c','d','e','f');
B64 =                  // for doing base 64 I/O to a page
"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";


/* This next part contains global constants that the user may change to
affect the way the RASCAL system works.  Changing any of these values
will alter the encrypted output given the same keys and plain-text
input.

A good idea is to set these to your unique values before using the
RASCAL system, and then modifying them periodically. Changing a single
character will produce an entirely different output from the system.
*/

/* ***************************************************************
This is a "hidden" key value that makes your encryptions unique
to you.  It makes your encryptions different from those of other
users when they use the same keyboard values against similar text.

It should have a length of about 60 characters (480 bit encryption.)
Of course, everyone you send encrypted msgs to must also have this
exact same hidden key.  A good idea is to change it periodically
by doing something like I did here by including the date.  This
also protects you from accidently using the same regular keys - if
you change it every month, then you only have to be unique for a
month at a time.
****************************************************************** */
var SubGenKey = "January 2010 - This is my special key string...";

/* ******************************************************************
In many parts of the code a starting point within an array is
calculated which is usually not the first location of the array, but is
based on some Pseudo Random value.  IN is an index that modifies this
value by adding to it.  Because of the keys given to an encryption, we
may calculate that we shall begin with the 10th element of an array. 
If IN is 2 this will be modified by starting with the 12th element of
that array instead.

The longer your message is, or your keys are, the more obfuscation
these values will perform.
****************************************************************** */
var IN = 13;   // value used to modify index into an array.
               //  used in Hash2 & shuffle1.  Can be any + value.
var FR = 0.53; // .25 < FR < .75, in rascal.js encryption rule.

/* *****************************************************************
In JavaScript, all numeric values are 16 decimal-digit values.  To
help in the conversion to other languages I specify the range of
values that variables may take (as coded).
  (b) = byte. (8-bits).  Usually a numeric value.
  (c) = JavaScript character value (UTF may convert to u32).
  (i..) = signed integer that requires some number of places.
          (i16 means a 16-bit signed integer.)
  (u..) = unsigned integer requiring some number of places.
  (fp) = floating point value.  8 byte IEEE standard.

In compiled languages it is more efficient to specify smaller values.
For example, with just minor changes all (fp) values can be changed
to u64 values, which would execute much faster, and require less
space for the object.
*************************************************************** */

                          /* THE CODE */
/* *****************************************************************
Within normal text data there may appear special UTF codes with a
value beyond 8-bits.  Because the encryption code works only with 8-bit
values, we must convert these special UTF codes into a series of 8-bit
groups, and then convert back to UTF after decryption.  We use special
marker-bytes to mark these converted strings of bytes.
This is probably unique to JavaScript which cannot address file content
as untyped bytes.
***************************************************************** */
function FixUTF (s) {  /* fix UTF data in s - string in, array out
  1 = 1 byte special marker storage
  2 = 2 bytes stored
  3 = 3 bytes
  4 = 4 bytes
*/
var i,j=0,t,la=s.length;         // (i32)
var a2 = new Array();            // (b)
  for (i=0; i<la; i++) {         // scan data for weird values
    t = s.charCodeAt(i);         // get an ordinal value
    if (t < 5) {                 // special char to protect
      a2[j++]=1;  // special marker char to be protected follows
      a2[j++]=t;  // marker char
    } 
    else if (t < 0x100)
      a2[j++] = t;               // normal text data, all done
    else if (t < 0x10000) {      // small UTF stuff (most codes)
      a2[j++] = 2;               // marker
      a2[j++] = (t & 0xff00) >> 8;
      a2[j++] =  t & 0xff;
    }
    else if (t < 0x1000000) {    // this is for UTF-16 stuff...
      a2[j++] = 3;               // marker
      a2[j++] = (t & 0xff0000) >>16;
      a2[j++] = (t & 0xff00) >> 8;
      a2[j++] =  t & 0xff;
    }
    else {                       // big UTF-16 stuff
      a2[j++] = 4;               // marker
      a2[j++] = (t & 0xff000000) >>> 24;
      a2[j++] = (t & 0xff0000) >> 16;
      a2[j++] = (t & 0xff00) >> 8;
      a2[j++] =  t & 0xff;
    }
  }
  return a2;              // return an array of bytes
}

function RstUTF (a) {  // restore UTF codes - numbers in, chars out
var i=0,j=0,k,c,t,la=a.length;
var a1=new Array();    // output array
  do {                 // run the array
    t = a[i++];        // current value
    if (t < 5) {       // special marker present?
        c = t;         // bytes to follow
        t = a[i++];    // running total
        for (k=1; k<c; k++)
          t=(t << 8) | a[i++]; // rebuild unicode values
    }
    a1[j++] = String.fromCharCode(t); // put UTF back into data
  } while (i<la);
  return a1.join("");  // return string
}

/* ******************************************************************
THIS IS A BYTE SHUFFLE!
This will shuffle a byte array based on generated random numbers.
It is a complete shuffle.
****************************************************************** */
function Shuffle (aray,seed,r) {  // shuffle an entire byte array
/* aray = the array of ordinal data to shuffle. (b)
   seed = some numeric array used to seed the shuffle keys (b)
   r    - if not zero, then init PRNG to new value. (b) */
var i,k,la=aray.length;           // (i32)
var t;                            // (b)
  if (r != 0) Rand1(seed);        // init PRNG
  for (i=la-1; i>0; i--) {        // run backwards
    k=Math.floor(Rand1()*(i+1));  // randomly select a location
    t=aray[i]; aray[i]=aray[k]; aray[k]=t; // swap with end loc
  }
  return aray;                    // aray is now in random order
}

function UnShuffle (aray,seed,r) {// undo array shuffle
var ary1 = new Array ();          // output array (b)
var a = new Array ();             // (u32)
var i,k,la=aray.length;           // (i32)
var t;                            // (b)
  if (r != 0) Rand1(seed);        // init PRNG
  for (i=0; i<la; i++)            // create original key data
    a[i] = i;                     // location index
  for (i=la-1; i>0; i--) {        // run backwards
    k=Math.floor(Rand1()*(i+1));  // randomly select a location
    t=a[i]; a[i]=a[k]; a[k]=t;    // swap with end loc
  }
  for (i=0; i<la; i++)            // put bytes back where they were
    ary1[a[i]] = aray[i];
  return ary1;                    // return original order
}

/* ***************************************************************
This will randomly shuffle the bits within an array of bytes.
This can be very time-comsuming for large amounts of data -
In C this is more simple than in JS.
*************************************************************** */
function BitShuffle (a,seed,r) {  // shuffle some bits in array
var i,j,l=0,la=a.length,m,n=0;    // (i32)
var b  = new Array ();            // bit array
  for (i=0; i<la; i++) {          // run the array for bits
    m = a[i];                     // an 8-bit byte
    for (j=7; j>=0; j--)          // process the byte
      b[l++] = (m >> j) & 1;      // change it into bits
  }
  b = Shuffle(b,seed,r);          // shuffle the bits
  for (i=0; i<la; i++) {          // reconstruct the array
    m = b[n++];                   // rebuild bytes
    for (j=1; j<8; j++)
      m = (m << 1) | b[n++];
    a[i] = m;
  }
  return a;
}

function UnBitShuffle (a,seed,r) {// Undo what BitShuffle did
var i,j,l=0,la=a.length,m,n=0;    // (i32)
var b  = new Array ();            // bit array
  for (i=0; i<la; i++) {          // run the array for bits
    m = a[i];                     // an 8-bit byte
    for (j=7; j>=0; j--)          // process the byte
      b[l++] = (m >> j) & 1;
  }
  b = UnShuffle(b,seed,r);        // unmix the bits
  for (i=0; i<la; i++) {          // reconstruct the array
    m = b[n++];
    for (j=1; j<8; j++)
      m = (m << 1) | b[n++];
    a[i] = m;
  }
 return a;
}

/* ****************************************************************
Normal text is only 7-bit data which leaves the high-order bit of
the key exposed.  These two functions work with a substitution array
to make it full 8-bit data.
   aray = the array of ordinal data to have substitution applied
   seed = some numeric byte array used to build the substitution table
   r    = whether or not to init the RNG - if zero, then do not init.
 This function will build a substitution array to be used to force
 the data to be encrypted into a full 8-bit version.

 Best fed with a 256-byte hashed seed.
****************************************************************** */
function SubGen (aray,seed,r) {        // substitute char set gen
var ary1 = new Array (256);            // temp working array (b)
var i,k,la=aray.length;                // (i32)
  if (r != 0) Rand14(seed);            // prime the PRNG
  for (i=0; i<256; i++)                // base index
    ary1[i]=255 - i;
  ary1 = Shuffle(ary1,seed,0);         // mess up sub array
  for (i=0; i<la; i++) {               // replace characters
    k = Rand14();                      // random index into sub array
    aray[i] = ary1[(aray[i]+k)&255];   // sub value
  }
  return aray;
}

function UnSubGen (aray,seed,r) {      // undo substitute chars
var ary1 = new Array (256);            // temp working arrays (b)
var ary3 = new Array (256);            // (b)
var i,k,la=aray.length;                // (i32)
  if (r != 0) Rand14(seed);
  for (i=0; i<256; i++)
    ary3[i]=255 - i;
  ary3 = Shuffle(ary3,seed,0);         // mess up sub array
  for (i=0; i<256; i++)                // form unsub array vector
    ary1[ary3[i]] = i;
  for (i=0; i<la; i++) {               // remove substitution
    k = Rand14();                      // random index into sub array
    aray[i] = (ary1[aray[i]]-k)&255;   // original value back
  }
  return aray;
}

/* ******************************************************************
This is a special sort that just puts data into buckets no larger
than x. The buckets are ordered (every element within bucket 1 is
equal to or less than every element within bucket 2), but the data
within the buckets may not be ordered (unless x was zero).

Used as irreversible mixer of data in Hash2, but also a pretty
good stand-alone sort (setting x to zero).
Watch out for the mixed mode arithmetic involving the c value...
You can do that in JavaScript but not C++, for example.
PS - ALL numbers are FP in JS...   There are no integers in JS
 (although certain logicals truncate to 32-bit integer-like values
   - but they are really still FP values - watch out!)
NOTE - JavaScript is not subject to array subscript range-errors
       like C is. (Subscripts outside defined range - In JS, arrays
       have no defined range [no dimension statement], and array
       elements that have not been filled are undefined so
       comparisons turn out false which stops the while's.)
****************************************************************** */
function QuickSort (a,left,right,x) { // recursive quicksort
var t;                                       // (b, fp - ALL THE SAME!)
var l=left,r=right;                          // local values (i32)
var c=(a[l]+a[l+1]+a[(l+r)>>1]+a[r-1]+a[r])/5; // central value (fp)
  do {
    while (a[l] < c) l++;                    // find val above center
    while (c < a[r]) r--;                    // find val below center
    if (l <= r) {                            // still in current box?
      t=a[l]; a[l++]=a[r]; a[r--]=t;         // swap, adjust indexes
    }
  } while (l <= r);                          // until we're thru
  if (left < (r-x)) {                        // only go to bucket size
    if ((r-left)>21) QuickSort(a,left,r,x);  // recursive call
    else ShellSort(a,left,r,x);              // save stack overhead
  }
  if (l < (right-x)) {
    if ((right-l)>21) QuickSort(a,l,right,x);
    else ShellSort(a,l,right,x);
  }
  return a;
}

/* ******************************************************************
This is a Shell sort that is not recursive, but works on just one
portion of an array delimited by l and r.  Not as fast as Qsort,
but available to those languages that do not support recursion.
****************************************************************** */
function ShellSort (a, l, r, x) { // sort until inc smaller than x
var i,j,t,ipl,jmi;
var inc = (r-l+1) >> 1;           // initial increment
  while (inc > 0) {               // decreasing inc loop
    ipl = inc + l;                // inc plus left
    for (i=ipl; i<=r; i++) {
      j = i;
      while ((j>=ipl) && (a[j-inc]>a[j])) {  // move low value back
        t=a[j]; a[j]=a[j-inc]; a[j-inc]=t;
        j -= inc;
      }
    }
    if (inc <= x) return a;       // no need to go on
    inc = Prime(inc >> 1);        // new increment
  }
  return a;
}

/* ******************************************************************
This will echo a prime, or return the next LOWER prime value.
****************************************************************** */
function Prime (tst) {
var i=3,tp;
  tst = Math.floor (tst);    // must be integer...
  if (tst < 4) return tst;   // 0,1,2,3 are just returned...
  if ((tst & 1) == 0) tst--; // force the rest to lower-odd
  if (tst < 8) return tst;   // already prime (3,5,7)
  tp = Math.sqrt(tst+1);     // no need to go beyond this value
  while (i < tp) {
    if ((tst % i) == 0) {    // oops, divisible
      tst -= 2;
      i = 3;
      continue;              // start loop over
    }
    i += 2;                  // test next value
  }
  return tst;                // this is a prime
}

/* *****************************************************************
This routine gives Rand3 a seed integer somewhere between 0 and
dmod3 from a string of bytes.  The order of the array values is very
important to the calculating of that value.

If we want 12345 to give a different result from 12435, we must
figure out how to give weight to the position of a value within an
array of values.  Just straight addition, or a checksum, does not
give any weight to the order of values, and gives the same results
for both of those strings.

If we accumulate a sum by multiplying the values in an array by an
ever-increasing multiplier, then we have positional weight.  So the
problem is to derive a formula to produce an increment given the
nature of the values (mean and range), and the number (count) of the
values.

Such a formula is  ->  inc = 2.0*tot/(cnt*cnt*ave)
  (I dink with it a little because that is an AVERAGE increment, 
   and I have to deal with the real world.)
***************************************************************** */
function Hash1 (aray) {  // get a seed value from an array
var i;
var sum = 0;                         // the value going to Rand3
var cnt = aray.length;               // the number of items in aray
var tot = dmod3;                     // the value sum cannot exceed
var ave = 127.5;                     // average (mean) of the data
var mul = 1;                         // the current multiplier
var inc=tot/(cnt*cnt*ave*0.6);       // increment
  for (i=0; i<cnt; i++) {            // run the array
    sum += aray[i] * mul;            // accumulate the weighted sum
    mul += inc;                      // bump multiplier by inc
  }
  return Math.floor(sum);            // hand out the seed
}

/* *******************************************************************
This hash function is quite a bit more sophisticated than it may
appear.  The initial encryption value contains the length of the input
array, bits are shifted around within and among bytes, a sort is used
as an irreversible component, and the hashed value is thoroughly
shuffled.

Of particular interest is that the shifting and shuffling are not the
same for any two values to be hashed - it is based on a stream of
random numbers generated from the array being hashed. This ain't a toy!
******************************************************************* */
function Hash2 (aray,len,flg) {  // secure hash function
/* len is length of output, and not the length of the input array */
var ary1 = new Array ();         // internal place for data hash (b)
var i,j,k,m,la=aray.length;      // (i32)
                          /* initialization */
  if (len == 0) len = la;             // for unknown lengths
  if (len > 4096) len = 4096;         // for internal protection
  if (len < 12) len = 12;             // at least 12 long (96 bits)
  k = Math.floor(Rand1(aray)*la)+IN;  // 1st data loc from aray
  for (i=0; i<len; i++)               // set the encryption bytes
    ary1[i]=(k+Rand7()*512)&255;      // - Rand1 init'ed Rand7
  QuickSort(ary1,0,len-1,len>>1);     // irreversible byte mixer
  ary1[len>>1]^=((la>>8)&255);        // insert input data length
  ary1[len>>2]^=(la&255);
  BitShuffle(ary1,0,0);               // mix up encryption bits
                       /* actual hash function */
// do it len values at a time, and force to multiple of len
  m = Math.floor((la+len-1)/len);     // groups of len chars
  for (i=0; i<m; i++) {               // run input array
// now operate on a group of len characters (a block, if you like)
    for (j=0; j<len; j++) {
      ary1[j]^=aray[++k % la];        // xor-in next values
      if (Rand1()<FR)
        ary1[Math.floor(Rand7()*len)]^=Math.floor(Rand1()*256);
    }
    QuickSort(ary1,0,len-1,len>>1);   // irreversible byte mixer
    BitShuffle(ary1,0,0);             // mix up the bits
  }
  QuickSort(ary1,0,len-1,len>>1);     // irreversible byte mixer
  BitShuffle(ary1,0,0);               // shuffle them bits
                              /* output */
  if (flg == 0) return ary1;          // 0-255 numeric output
var ary3 = new Array ();              // output array (b)
  j = 0;                              // output array index
  for (i=0; i<len; i++) {             // hex format
    k = ary1[i];
    ary3[j++]=Hex[k>>4]+Hex[k&15];    // get hex chars from string
  }
  return ary3.join("");               // len-char hash of aray
}


/* **************************************************************** 
An assortment of pseudo random number generators.

I use different generators that are not mathematically related, as
much as possible, to be certain of generating non-related sequences.

LCGs produce a base run for the LFGs upon which the actual seed is
impressed.  Rand3 is the LCG.  1 is a special cascade LCG of my
design that gives more deference to the seed.  14 and 15 are
versions of the old RC4 system tightened up just a bit, and 7 
is the LFG.

Do not ignore the lite encryptors of Shuffle and SubGen,
above.  They are not toys.  And Hash2 deals very well with hiding
keys.  This library provides a wealth of tools for encrypting data.
***************************************************************** */

/* ****************************************************************
This gets close to a Cryptographically Secure (CS) generator.
This is a work in progress.  I think it is "secure" because there
is no way to tell which of the 521+ generators produce output.
**************************************************************** */
var d1    = new Array (); // place for digits
var r1    = 0;            // place for remaindering
var dcnt1 = 521;          // min number of generators
var dmod1 = 2147483647;   // max value (prime)
var dmul1 =     412567;   // prime

function Rand1 (seed) {
var i,j,t,m;
  if (arguments.length > 0) {        // seed present?
var ls = seed.length;
    dcnt1 = Math.max(521,ls);
    j = Math.floor(Rand7(seed) * dcnt1); // mess up index into seed
    r1 = j;
    for (i=dcnt1-1; i>=0; i--)       // base key
      d1[i] = Rand7() * dmod1 +
        seed[j++ % ls] * (1048576 + 1);
  }
  j =  Math.floor(Rand7()*dcnt1);    // which generator to use
  t =  d1[j] * dmul1 + r1;           // Do the LCG math
  m =  t % dmod1;                    // new digit in state array
  r1 = (t / dmod1) & (0x7 | 1);      // get the remainder feedback
  d1[j] = m;                         // store value off
  return m / dmod1;                  // the return fp number...
}

/* ******************************************************************
 The idea for this comes from an Alternating Step Generator, and it
 is quite a bit more robust than a simple Linear Congruential Gen.
 (It is 3 LCGs in one!)
******************************************************************* */

var d3,d4,d5;                 // internal seed values < dmod3
var dmod3 = 2147483647;       // prime
var dmul3 =     412463;       // prime
var dmul4 =     412343;
var dmul5 =     393287;

function Rand3 (seed) {       // simple PRNG
var i;
  if (seed > 0) {             // seed present?
    d3=d4=d5=seed;            // load the seeds
    d4+=21;
    d5+=33;
    for (i=0; i<11; i++)      // let 'em settle down
      Rand3();                //  recursive discard of 1st values
  }
  d3=(d3*dmul3+1)%dmod3;      // clock d3
  if (d3 < 1073741750)        // clock d4 about 1/2 the time
    d4=(d4*dmul4+1)%dmod3;
  else
    d5=(d5*dmul5+3)%dmod3;    //  else, clock d5
  return (d4 ^ d5) / dmod3;   // positive, less than 1
}

/* **************************************************************** */
var d7    = new Array ();    // place for digits
var cntr7 = 0;               // times called
var dcnt7 = 521;             // minimum number of digits
var dmod7 = 2251799813685248;// max size (power of 2)

function Rand7 (seed) {      // Additive lagged fibonacci generator
var m,n,t;
  if (arguments.length > 0) {       // seed present?
var ls=seed.length,i,j;
    dcnt7 = Math.max(521,ls);
    j = Math.floor(Rand3(Hash1(seed)) * dcnt7); // random value 
    cntr7 = j + dmod7;
    for (i=dcnt7-1; i>=0; i--)      // stuff seed on random digits
      d7[i]=Rand3()*dmod7+(seed[j++ % ls]*
        (274877906944 + 134217728 + 32768 + 1));
    for (i=0; i<(dcnt7<<1)+j; i++) Rand7(); // recursive init
  }
  n = cntr7--;                      // set index, then rotate
  t = (n+520)%dcnt7;                // for efficiency
  m = (d7[(n+362)%dcnt7]+d7[t])%dmod7; // new calculation
  d7[t] = m;                        // feedback
  return m / dmod7;
}

/* ************************************************************
This is a base version of RC4 (almost).  It is as described,
but with a few exceptions.  Once you understand this
simple algorithm, it is very easy to modify.

For maximum effectiveness you should hash keys to a length of
256 characters.  That makes it very effective for keys smaller
than about 500 keyboard characters.  The hash ensures a max key.
************************************************************* */
var d14 = new Array ();        // main key array
var i14,j14;                   // indexes into d14 array

function Rand14 (seed) {       // RC4 stream cypher
var tmp;
  if (arguments.length > 0) {  // args present?
var i,j;
    for (i=0; i<256; i++)      // init the key schedule
      d14[i] = i;
    d14 = Shuffle(d14,seed,1); // mix keys
    i14 = d14[1];              // indexes into array
    j14 = d14[0];
    j   = i14;                 // prevent problem with globals
    for (i=0; i<500+j; i++) Rand14();  // initialize
  }

  i14 = (i14 + 1) & 255;       // generate indexes
  tmp = d14[i14];              // remember for swap, coming up
  j14 = (j14 + tmp) & 255;
  d14[i14] = d14[j14];         // swap
  d14[j14] = tmp;
  return d14[(d14[i14] + tmp) & 255];  // value from 0 to 255
}

/* ***********************************************************
  This is a stronger version of RC4. Mod 512 vs fixed 256.
*********************************************************** */
var d15 = new Array ();        // main key array
var dcnt15 = 512;              // min length of d15 array
var i15,j15;                   // indexes into d15 array

function Rand15 (seed) {       // Super RC4-like cipher
var t;
  if (arguments.length > 0) {  // args present?
var i,j,ls=seed.length;
    dcnt15 = Math.floor((ls+511)/512)*512; // mod 512
    for (i=0; i<dcnt15; i++)   // init key schedule
      d15[i] = i;
    d15 = Shuffle(d15,seed,1); // mix of keys using seed
    i15 = d15[0];              // indexes into array
    j15 = d15[1];
    j   = i15;                 // prevent problem with globals
    for (i=0; i<(dcnt15<<1)+j; i++) Rand15(); // initialize
  }

  i15 = (i15 + 1) % dcnt15;    // generate first index
  t = d15[i15];                // set for swap
  j15 = (j15 + t) % dcnt15;    //  second index
  d15[i15] = d15[j15];         // swap them suckers
  d15[j15] = t;
  return d15[(d15[i15] + t) % dcnt15] & 255;  // value from 0 to 255
}