includes/clientside/static/libbigint.js
author Dan
Sun, 04 May 2008 21:57:48 -0400
changeset 541 acb7e23b6ffa
parent 436 242353360e37
permissions -rw-r--r--
Massive commit with various changes. Added user ranks system (no admin interface yet) and ability for users to have custom user titles. Made cron framework accept fractions of hours through floating-point intervals. Modifed ACL editor to use miniPrompt framework for close confirmation box. Made avatar system use a special page as opposed to fetching the files directly for caching reasons.
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
436
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
     1
////////////////////////////////////////////////////////////////////////////////////////
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
     2
// Big Integer Library v. 5.1
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
     3
// Created 2000, last modified 2007
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
     4
// Leemon Baird
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
     5
// www.leemon.com
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
     6
//
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
     7
// Version history:
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
     8
//
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
     9
// v 5.1  8 Oct 2007 
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
    10
//   - renamed inverseModInt_ to inverseModInt since it doesn't change its parameters
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
    11
//   - added functions GCD and randBigInt, which call GCD_ and randBigInt_
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
    12
//   - fixed a bug found by Rob Visser (see comment with his name below)
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
    13
//   - improved comments
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
    14
//
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
    15
// This file is public domain.   You can use it for any purpose without restriction.
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
    16
// I do not guarantee that it is correct, so use it at your own risk.  If you use 
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
    17
// it for something interesting, I'd appreciate hearing about it.  If you find 
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
    18
// any bugs or make any improvements, I'd appreciate hearing about those too.
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
    19
// It would also be nice if my name and address were left in the comments.
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
    20
// But none of that is required.
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
    21
//
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
    22
// This code defines a bigInt library for arbitrary-precision integers.
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
    23
// A bigInt is an array of integers storing the value in chunks of bpe bits, 
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
    24
// little endian (buff[0] is the least significant word).
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
    25
// Negative bigInts are stored two's complement.
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
    26
// Some functions assume their parameters have at least one leading zero element.
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
    27
// Functions with an underscore at the end of the name have unpredictable behavior in case of overflow, 
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
    28
// so the caller must make sure the arrays must be big enough to hold the answer.
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
    29
// For each function where a parameter is modified, that same 
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
    30
// variable must not be used as another argument too.
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
    31
// So, you cannot square x by doing multMod_(x,x,n).  
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
    32
// You must use squareMod_(x,n) instead, or do y=dup(x); multMod_(x,y,n).
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
    33
//
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
    34
// These functions are designed to avoid frequent dynamic memory allocation in the inner loop.
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
    35
// For most functions, if it needs a BigInt as a local variable it will actually use
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
    36
// a global, and will only allocate to it only when it's not the right size.  This ensures
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
    37
// that when a function is called repeatedly with same-sized parameters, it only allocates
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
    38
// memory on the first call.
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
    39
//
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
    40
// Note that for cryptographic purposes, the calls to Math.random() must 
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
    41
// be replaced with calls to a better pseudorandom number generator.
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
    42
//
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
    43
// In the following, "bigInt" means a bigInt with at least one leading zero element,
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
    44
// and "integer" means a nonnegative integer less than radix.  In some cases, integer 
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
    45
// can be negative.  Negative bigInts are 2s complement.
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
    46
// 
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
    47
// The following functions do not modify their inputs.
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
    48
// Those returning a bigInt, string, or Array will dynamically allocate memory for that value.
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
    49
// Those returning a boolean will return the integer 0 (false) or 1 (true).
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
    50
// Those returning boolean or int will not allocate memory except possibly on the first time they're called with a given parameter size.
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
    51
// 
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
    52
// bigInt  add(x,y)               //return (x+y) for bigInts x and y.  
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
    53
// bigInt  addInt(x,n)            //return (x+n) where x is a bigInt and n is an integer.
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
    54
// string  bigInt2str(x,base)     //return a string form of bigInt x in a given base, with 2 <= base <= 95
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
    55
// int     bitSize(x)             //return how many bits long the bigInt x is, not counting leading zeros
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
    56
// bigInt  dup(x)                 //return a copy of bigInt x
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
    57
// boolean equals(x,y)            //is the bigInt x equal to the bigint y?
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
    58
// boolean equalsInt(x,y)         //is bigint x equal to integer y?
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
    59
// bigInt  expand(x,n)            //return a copy of x with at least n elements, adding leading zeros if needed
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
    60
// Array   findPrimes(n)          //return array of all primes less than integer n
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
    61
// bigInt  GCD(x,y)               //return greatest common divisor of bigInts x and y (each with same number of elements).
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
    62
// boolean greater(x,y)           //is x>y?  (x and y are nonnegative bigInts)
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
    63
// boolean greaterShift(x,y,shift)//is (x <<(shift*bpe)) > y?
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
    64
// bigInt  int2bigInt(t,n,m)      //return a bigInt equal to integer t, with at least n bits and m array elements
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
    65
// bigInt  inverseMod(x,n)        //return (x**(-1) mod n) for bigInts x and n.  If no inverse exists, it returns null
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
    66
// int     inverseModInt(x,n)     //return x**(-1) mod n, for integers x and n.  Return 0 if there is no inverse
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
    67
// boolean isZero(x)              //is the bigInt x equal to zero?
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
    68
// boolean millerRabin(x,b)       //does one round of Miller-Rabin base integer b say that bigInt x is possibly prime (as opposed to definitely composite)?
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
    69
// bigInt  mod(x,n)               //return a new bigInt equal to (x mod n) for bigInts x and n.
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
    70
// int     modInt(x,n)            //return x mod n for bigInt x and integer n.
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
    71
// bigInt  mult(x,y)              //return x*y for bigInts x and y. This is faster when y<x.
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
    72
// bigInt  multMod(x,y,n)         //return (x*y mod n) for bigInts x,y,n.  For greater speed, let y<x.
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
    73
// boolean negative(x)            //is bigInt x negative?
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
    74
// bigInt  powMod(x,y,n)          //return (x**y mod n) where x,y,n are bigInts and ** is exponentiation.  0**0=1. Faster for odd n.
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
    75
// bigInt  randBigInt(n,s)        //return an n-bit random BigInt (n>=1).  If s=1, then the most significant of those n bits is set to 1.
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
    76
// bigInt  randTruePrime(k)       //return a new, random, k-bit, true prime bigInt using Maurer's algorithm.
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
    77
// bigInt  str2bigInt(s,b,n,m)    //return a bigInt for number represented in string s in base b with at least n bits and m array elements
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
    78
// bigInt  sub(x,y)               //return (x-y) for bigInts x and y.  Negative answers will be 2s complement
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
    79
// bigInt  bigint_trim(x,k)              //return a copy of x with exactly k leading zero elements
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
    80
//
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
    81
//
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
    82
// The following functions each have a non-underscored version, which most users should call instead.
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
    83
// These functions each write to a single parameter, and the caller is responsible for ensuring the array 
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
    84
// passed in is large enough to hold the result. 
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
    85
//
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
    86
// void    addInt_(x,n)          //do x=x+n where x is a bigInt and n is an integer
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
    87
// void    add_(x,y)             //do x=x+y for bigInts x and y
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
    88
// void    copy_(x,y)            //do x=y on bigInts x and y
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
    89
// void    copyInt_(x,n)         //do x=n on bigInt x and integer n
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
    90
// void    GCD_(x,y)             //set x to the greatest common divisor of bigInts x and y, (y is destroyed).  (This never overflows its array).
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
    91
// boolean inverseMod_(x,n)      //do x=x**(-1) mod n, for bigInts x and n. Returns 1 (0) if inverse does (doesn't) exist
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
    92
// void    mod_(x,n)             //do x=x mod n for bigInts x and n. (This never overflows its array).
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
    93
// void    mult_(x,y)            //do x=x*y for bigInts x and y.
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
    94
// void    multMod_(x,y,n)       //do x=x*y  mod n for bigInts x,y,n.
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
    95
// void    powMod_(x,y,n)        //do x=x**y mod n, where x,y,n are bigInts (n is odd) and ** is exponentiation.  0**0=1.
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
    96
// void    randBigInt_(b,n,s)    //do b = an n-bit random BigInt. if s=1, then nth bit (most significant bit) is set to 1. n>=1.
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
    97
// void    randTruePrime_(ans,k) //do ans = a random k-bit true random prime (not just probable prime) with 1 in the msb.
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
    98
// void    sub_(x,y)             //do x=x-y for bigInts x and y. Negative answers will be 2s complement.
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
    99
//
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   100
// The following functions do NOT have a non-underscored version. 
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   101
// They each write a bigInt result to one or more parameters.  The caller is responsible for
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   102
// ensuring the arrays passed in are large enough to hold the results. 
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   103
//
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   104
// void addShift_(x,y,ys)       //do x=x+(y<<(ys*bpe))
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   105
// void carry_(x)               //do carries and borrows so each element of the bigInt x fits in bpe bits.
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   106
// void divide_(x,y,q,r)        //divide x by y giving quotient q and remainder r
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   107
// int  divInt_(x,n)            //do x=floor(x/n) for bigInt x and integer n, and return the remainder. (This never overflows its array).
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   108
// int  eGCD_(x,y,d,a,b)        //sets a,b,d to positive bigInts such that d = GCD_(x,y) = a*x-b*y
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   109
// void halve_(x)               //do x=floor(|x|/2)*sgn(x) for bigInt x in 2's complement.  (This never overflows its array).
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   110
// void leftShift_(x,n)         //left shift bigInt x by n bits.  n<bpe.
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   111
// void linComb_(x,y,a,b)       //do x=a*x+b*y for bigInts x and y and integers a and b
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   112
// void linCombShift_(x,y,b,ys) //do x=x+b*(y<<(ys*bpe)) for bigInts x and y, and integers b and ys
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   113
// void mont_(x,y,n,np)         //Montgomery multiplication (see comments where the function is defined)
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   114
// void multInt_(x,n)           //do x=x*n where x is a bigInt and n is an integer.
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   115
// void rightShift_(x,n)        //right shift bigInt x by n bits.  0 <= n < bpe. (This never overflows its array).
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   116
// void squareMod_(x,n)         //do x=x*x  mod n for bigInts x,n
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   117
// void subShift_(x,y,ys)       //do x=x-(y<<(ys*bpe)). Negative answers will be 2s complement.
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   118
//
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   119
// The following functions are based on algorithms from the _Handbook of Applied Cryptography_
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   120
//    powMod_()           = algorithm 14.94, Montgomery exponentiation
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   121
//    eGCD_,inverseMod_() = algorithm 14.61, Binary extended GCD_
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   122
//    GCD_()              = algorothm 14.57, Lehmer's algorithm
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   123
//    mont_()             = algorithm 14.36, Montgomery multiplication
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   124
//    divide_()           = algorithm 14.20  Multiple-precision division
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   125
//    squareMod_()        = algorithm 14.16  Multiple-precision squaring
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   126
//    randTruePrime_()    = algorithm  4.62, Maurer's algorithm
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   127
//    millerRabin()       = algorithm  4.24, Miller-Rabin algorithm
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   128
//
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   129
// Profiling shows:
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   130
//     randTruePrime_() spends:
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   131
//         10% of its time in calls to powMod_()
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   132
//         85% of its time in calls to millerRabin()
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   133
//     millerRabin() spends:
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   134
//         99% of its time in calls to powMod_()   (always with a base of 2)
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   135
//     powMod_() spends:
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   136
//         94% of its time in calls to mont_()  (almost always with x==y)
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   137
//
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   138
// This suggests there are several ways to speed up this library slightly:
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   139
//     - convert powMod_ to use a Montgomery form of k-ary window (or maybe a Montgomery form of sliding window)
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   140
//         -- this should especially focus on being fast when raising 2 to a power mod n
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   141
//     - convert randTruePrime_() to use a minimum r of 1/3 instead of 1/2 with the appropriate change to the test
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   142
//     - tune the parameters in randTruePrime_(), including c, m, and recLimit
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   143
//     - speed up the single loop in mont_() that takes 95% of the runtime, perhaps by reducing checking
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   144
//       within the loop when all the parameters are the same length.
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   145
//
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   146
// There are several ideas that look like they wouldn't help much at all:
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   147
//     - replacing trial division in randTruePrime_() with a sieve (that speeds up something taking almost no time anyway)
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   148
//     - increase bpe from 15 to 30 (that would help if we had a 32*32->64 multiplier, but not with JavaScript's 32*32->32)
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   149
//     - speeding up mont_(x,y,n,np) when x==y by doing a non-modular, non-Montgomery square
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   150
//       followed by a Montgomery reduction.  The intermediate answer will be twice as long as x, so that
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   151
//       method would be slower.  This is unfortunate because the code currently spends almost all of its time
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   152
//       doing mont_(x,x,...), both for randTruePrime_() and powMod_().  A faster method for Montgomery squaring
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   153
//       would have a large impact on the speed of randTruePrime_() and powMod_().  HAC has a couple of poorly-worded
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   154
//       sentences that seem to imply it's faster to do a non-modular square followed by a single
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   155
//       Montgomery reduction, but that's obviously wrong.
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   156
////////////////////////////////////////////////////////////////////////////////////////
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   157
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   158
//globals
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   159
bpe=0;         //bits stored per array element
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   160
mask=0;        //AND this with an array element to chop it down to bpe bits
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   161
radix=mask+1;  //equals 2^bpe.  A single 1 bit to the left of the last bit of mask.
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   162
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   163
//the digits for converting to different bases
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   164
digitsStr='0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz_=!@#$%^&*()[]{}|;:,.<>/?`~ \\\'\"+-';
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   165
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   166
//initialize the global variables
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   167
for (bpe=0; (1<<(bpe+1)) > (1<<bpe); bpe++);  //bpe=number of bits in the mantissa on this platform
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   168
bpe>>=1;                   //bpe=number of bits in one element of the array representing the bigInt
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   169
mask=(1<<bpe)-1;           //AND the mask with an integer to get its bpe least significant bits
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   170
radix=mask+1;              //2^bpe.  a single 1 bit to the left of the first bit of mask
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   171
one=int2bigInt(1,1,1);     //constant used in powMod_()
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   172
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   173
//the following global variables are scratchpad memory to 
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   174
//reduce dynamic memory allocation in the inner loop
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   175
t=new Array(0);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   176
ss=t;       //used in mult_()
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   177
s0=t;       //used in multMod_(), squareMod_() 
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   178
s1=t;       //used in powMod_(), multMod_(), squareMod_() 
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   179
s2=t;       //used in powMod_(), multMod_()
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   180
s3=t;       //used in powMod_()
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   181
s4=t; s5=t; //used in mod_()
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   182
s6=t;       //used in bigInt2str()
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   183
s7=t;       //used in powMod_()
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   184
T=t;        //used in GCD_()
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   185
sa=t;       //used in mont_()
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   186
mr_x1=t; mr_r=t; mr_a=t;                                      //used in millerRabin()
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   187
eg_v=t; eg_u=t; eg_A=t; eg_B=t; eg_C=t; eg_D=t;               //used in eGCD_(), inverseMod_()
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   188
md_q1=t; md_q2=t; md_q3=t; md_r=t; md_r1=t; md_r2=t; md_tt=t; //used in mod_()
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   189
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   190
primes=t; pows=t; s_i=t; s_i2=t; s_R=t; s_rm=t; s_q=t; s_n1=t; 
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   191
  s_a=t; s_r2=t; s_n=t; s_b=t; s_d=t; s_x1=t; s_x2=t, s_aa=t; //used in randTruePrime_()
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   192
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   193
////////////////////////////////////////////////////////////////////////////////////////
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   194
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   195
//return array of all primes less than integer n
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   196
function findPrimes(n) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   197
  var i,s,p,ans;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   198
  s=new Array(n);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   199
  for (i=0;i<n;i++)
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   200
    s[i]=0;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   201
  s[0]=2;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   202
  p=0;    //first p elements of s are primes, the rest are a sieve
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   203
  for(;s[p]<n;) {                  //s[p] is the pth prime
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   204
    for(i=s[p]*s[p]; i<n; i+=s[p]) //mark multiples of s[p]
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   205
      s[i]=1;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   206
    p++;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   207
    s[p]=s[p-1]+1;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   208
    for(; s[p]<n && s[s[p]]; s[p]++); //find next prime (where s[p]==0)
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   209
  }
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   210
  ans=new Array(p);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   211
  for(i=0;i<p;i++)
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   212
    ans[i]=s[i];
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   213
  return ans;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   214
}
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   215
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   216
//does a single round of Miller-Rabin base b consider x to be a possible prime?
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   217
//x is a bigInt, and b is an integer
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   218
function millerRabin(x,b) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   219
  var i,j,k,s;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   220
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   221
  if (mr_x1.length!=x.length) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   222
    mr_x1=dup(x);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   223
    mr_r=dup(x);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   224
    mr_a=dup(x);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   225
  }
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   226
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   227
  copyInt_(mr_a,b);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   228
  copy_(mr_r,x);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   229
  copy_(mr_x1,x);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   230
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   231
  addInt_(mr_r,-1);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   232
  addInt_(mr_x1,-1);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   233
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   234
  //s=the highest power of two that divides mr_r
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   235
  k=0;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   236
  for (i=0;i<mr_r.length;i++)
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   237
    for (j=1;j<mask;j<<=1)
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   238
      if (x[i] & j) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   239
        s=(k<mr_r.length+bpe ? k : 0); 
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   240
         i=mr_r.length;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   241
         j=mask;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   242
      } else
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   243
        k++;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   244
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   245
  if (s)                
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   246
    rightShift_(mr_r,s);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   247
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   248
  powMod_(mr_a,mr_r,x);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   249
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   250
  if (!equalsInt(mr_a,1) && !equals(mr_a,mr_x1)) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   251
    j=1;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   252
    while (j<=s-1 && !equals(mr_a,mr_x1)) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   253
      squareMod_(mr_a,x);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   254
      if (equalsInt(mr_a,1)) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   255
        return 0;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   256
      }
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   257
      j++;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   258
    }
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   259
    if (!equals(mr_a,mr_x1)) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   260
      return 0;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   261
    }
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   262
  }
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   263
  return 1;  
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   264
}
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   265
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   266
//returns how many bits long the bigInt is, not counting leading zeros.
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   267
function bitSize(x) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   268
  var j,z,w;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   269
  for (j=x.length-1; (x[j]==0) && (j>0); j--);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   270
  for (z=0,w=x[j]; w; (w>>=1),z++);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   271
  z+=bpe*j;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   272
  return z;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   273
}
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   274
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   275
//return a copy of x with at least n elements, adding leading zeros if needed
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   276
function expand(x,n) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   277
  var ans=int2bigInt(0,(x.length>n ? x.length : n)*bpe,0);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   278
  copy_(ans,x);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   279
  return ans;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   280
}
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   281
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   282
//return a k-bit true random prime using Maurer's algorithm.
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   283
function randTruePrime(k) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   284
  var ans=int2bigInt(0,k,0);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   285
  randTruePrime_(ans,k);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   286
  return bigint_trim(ans,1);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   287
}
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   288
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   289
//return a new bigInt equal to (x mod n) for bigInts x and n.
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   290
function mod(x,n) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   291
  var ans=dup(x);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   292
  mod_(ans,n);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   293
  return bigint_trim(ans,1);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   294
}
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   295
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   296
//return (x+n) where x is a bigInt and n is an integer.
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   297
function addInt(x,n) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   298
  var ans=expand(x,x.length+1);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   299
  addInt_(ans,n);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   300
  return bigint_trim(ans,1);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   301
}
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   302
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   303
//return x*y for bigInts x and y. This is faster when y<x.
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   304
function mult(x,y) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   305
  var ans=expand(x,x.length+y.length);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   306
  mult_(ans,y);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   307
  return bigint_trim(ans,1);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   308
}
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   309
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   310
//return (x**y mod n) where x,y,n are bigInts and ** is exponentiation.  0**0=1. Faster for odd n.
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   311
function powMod(x,y,n) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   312
  var ans=expand(x,n.length);  
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   313
  powMod_(ans,bigint_trim(y,2),bigint_trim(n,2),0);  //this should work without the trim, but doesn't
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   314
  return bigint_trim(ans,1);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   315
}
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   316
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   317
//return (x-y) for bigInts x and y.  Negative answers will be 2s complement
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   318
function sub(x,y) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   319
  var ans=expand(x,(x.length>y.length ? x.length+1 : y.length+1)); 
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   320
  sub_(ans,y);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   321
  return bigint_trim(ans,1);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   322
}
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   323
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   324
//return (x+y) for bigInts x and y.  
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   325
function add(x,y) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   326
  var ans=expand(x,(x.length>y.length ? x.length+1 : y.length+1)); 
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   327
  add_(ans,y);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   328
  return bigint_trim(ans,1);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   329
}
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   330
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   331
//return (x**(-1) mod n) for bigInts x and n.  If no inverse exists, it returns null
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   332
function inverseMod(x,n) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   333
  var ans=expand(x,n.length); 
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   334
  var s;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   335
  s=inverseMod_(ans,n);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   336
  return s ? bigint_trim(ans,1) : null;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   337
}
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   338
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   339
//return (x*y mod n) for bigInts x,y,n.  For greater speed, let y<x.
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   340
function multMod(x,y,n) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   341
  var ans=expand(x,n.length);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   342
  multMod_(ans,y,n);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   343
  return bigint_trim(ans,1);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   344
}
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   345
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   346
//generate a k-bit true random prime using Maurer's algorithm,
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   347
//and put it into ans.  The bigInt ans must be large enough to hold it.
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   348
function randTruePrime_(ans,k) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   349
  var c,m,pm,dd,j,r,B,divisible,z,zz,recSize;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   350
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   351
  if (primes.length==0)
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   352
    primes=findPrimes(30000);  //check for divisibility by primes <=30000
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   353
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   354
  if (pows.length==0) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   355
    pows=new Array(512);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   356
    for (j=0;j<512;j++) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   357
      pows[j]=Math.pow(2,j/511.-1.);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   358
    }
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   359
  }
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   360
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   361
  //c and m should be tuned for a particular machine and value of k, to maximize speed
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   362
  c=0.1;  //c=0.1 in HAC
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   363
  m=20;   //generate this k-bit number by first recursively generating a number that has between k/2 and k-m bits
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   364
  recLimit=20; //stop recursion when k <=recLimit.  Must have recLimit >= 2
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   365
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   366
  if (s_i2.length!=ans.length) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   367
    s_i2=dup(ans);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   368
    s_R =dup(ans);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   369
    s_n1=dup(ans);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   370
    s_r2=dup(ans);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   371
    s_d =dup(ans);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   372
    s_x1=dup(ans);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   373
    s_x2=dup(ans);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   374
    s_b =dup(ans);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   375
    s_n =dup(ans);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   376
    s_i =dup(ans);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   377
    s_rm=dup(ans);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   378
    s_q =dup(ans);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   379
    s_a =dup(ans);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   380
    s_aa=dup(ans);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   381
  }
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   382
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   383
  if (k <= recLimit) {  //generate small random primes by trial division up to its square root
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   384
    pm=(1<<((k+2)>>1))-1; //pm is binary number with all ones, just over sqrt(2^k)
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   385
    copyInt_(ans,0);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   386
    for (dd=1;dd;) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   387
      dd=0;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   388
      ans[0]= 1 | (1<<(k-1)) | Math.floor(Math.random()*(1<<k));  //random, k-bit, odd integer, with msb 1
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   389
      for (j=1;(j<primes.length) && ((primes[j]&pm)==primes[j]);j++) { //trial division by all primes 3...sqrt(2^k)
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   390
        if (0==(ans[0]%primes[j])) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   391
          dd=1;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   392
          break;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   393
        }
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   394
      }
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   395
    }
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   396
    carry_(ans);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   397
    return;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   398
  }
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   399
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   400
  B=c*k*k;    //try small primes up to B (or all the primes[] array if the largest is less than B).
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   401
  if (k>2*m)  //generate this k-bit number by first recursively generating a number that has between k/2 and k-m bits
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   402
    for (r=1; k-k*r<=m; )
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   403
      r=pows[Math.floor(Math.random()*512)];   //r=Math.pow(2,Math.random()-1);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   404
  else
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   405
    r=.5;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   406
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   407
  //simulation suggests the more complex algorithm using r=.333 is only slightly faster.
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   408
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   409
  recSize=Math.floor(r*k)+1;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   410
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   411
  randTruePrime_(s_q,recSize);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   412
  copyInt_(s_i2,0);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   413
  s_i2[Math.floor((k-2)/bpe)] |= (1<<((k-2)%bpe));   //s_i2=2^(k-2)
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   414
  divide_(s_i2,s_q,s_i,s_rm);                        //s_i=floor((2^(k-1))/(2q))
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   415
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   416
  z=bitSize(s_i);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   417
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   418
  for (;;) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   419
    for (;;) {  //generate z-bit numbers until one falls in the range [0,s_i-1]
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   420
      randBigInt_(s_R,z,0);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   421
      if (greater(s_i,s_R))
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   422
        break;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   423
    }                //now s_R is in the range [0,s_i-1]
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   424
    addInt_(s_R,1);  //now s_R is in the range [1,s_i]
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   425
    add_(s_R,s_i);   //now s_R is in the range [s_i+1,2*s_i]
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   426
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   427
    copy_(s_n,s_q);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   428
    mult_(s_n,s_R); 
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   429
    multInt_(s_n,2);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   430
    addInt_(s_n,1);    //s_n=2*s_R*s_q+1
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   431
    
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   432
    copy_(s_r2,s_R);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   433
    multInt_(s_r2,2);  //s_r2=2*s_R
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   434
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   435
    //check s_n for divisibility by small primes up to B
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   436
    for (divisible=0,j=0; (j<primes.length) && (primes[j]<B); j++)
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   437
      if (modInt(s_n,primes[j])==0) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   438
        divisible=1;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   439
        break;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   440
      }      
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   441
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   442
    if (!divisible)    //if it passes small primes check, then try a single Miller-Rabin base 2
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   443
      if (!millerRabin(s_n,2)) //this line represents 75% of the total runtime for randTruePrime_ 
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   444
        divisible=1;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   445
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   446
    if (!divisible) {  //if it passes that test, continue checking s_n
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   447
      addInt_(s_n,-3);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   448
      for (j=s_n.length-1;(s_n[j]==0) && (j>0); j--);  //strip leading zeros
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   449
      for (zz=0,w=s_n[j]; w; (w>>=1),zz++);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   450
      zz+=bpe*j;                             //zz=number of bits in s_n, ignoring leading zeros
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   451
      for (;;) {  //generate z-bit numbers until one falls in the range [0,s_n-1]
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   452
        randBigInt_(s_a,zz,0);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   453
        if (greater(s_n,s_a))
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   454
          break;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   455
      }                //now s_a is in the range [0,s_n-1]
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   456
      addInt_(s_n,3);  //now s_a is in the range [0,s_n-4]
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   457
      addInt_(s_a,2);  //now s_a is in the range [2,s_n-2]
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   458
      copy_(s_b,s_a);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   459
      copy_(s_n1,s_n);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   460
      addInt_(s_n1,-1);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   461
      powMod_(s_b,s_n1,s_n);   //s_b=s_a^(s_n-1) modulo s_n
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   462
      addInt_(s_b,-1);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   463
      if (isZero(s_b)) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   464
        copy_(s_b,s_a);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   465
        powMod_(s_b,s_r2,s_n);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   466
        addInt_(s_b,-1);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   467
        copy_(s_aa,s_n);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   468
        copy_(s_d,s_b);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   469
        GCD_(s_d,s_n);  //if s_b and s_n are relatively prime, then s_n is a prime
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   470
        if (equalsInt(s_d,1)) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   471
          copy_(ans,s_aa);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   472
          return;     //if we've made it this far, then s_n is absolutely guaranteed to be prime
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   473
        }
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   474
      }
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   475
    }
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   476
  }
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   477
}
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   478
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   479
//Return an n-bit random BigInt (n>=1).  If s=1, then the most significant of those n bits is set to 1.
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   480
function randBigInt(n,s) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   481
  var a,b;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   482
  a=Math.floor((n-1)/bpe)+2; //# array elements to hold the BigInt with a leading 0 element
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   483
  b=int2bigInt(0,0,a);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   484
  randBigInt_(b,n,s);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   485
  return b;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   486
}
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   487
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   488
//Set b to an n-bit random BigInt.  If s=1, then the most significant of those n bits is set to 1.
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   489
//Array b must be big enough to hold the result. Must have n>=1
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   490
function randBigInt_(b,n,s) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   491
  var i,a;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   492
  for (i=0;i<b.length;i++)
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   493
    b[i]=0;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   494
  a=Math.floor((n-1)/bpe)+1; //# array elements to hold the BigInt
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   495
  for (i=0;i<a;i++) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   496
    b[i]=Math.floor(Math.random()*(1<<(bpe-1)));
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   497
  }
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   498
  b[a-1] &= (2<<((n-1)%bpe))-1;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   499
  if (s==1)
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   500
    b[a-1] |= (1<<((n-1)%bpe));
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   501
}
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   502
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   503
//Return the greatest common divisor of bigInts x and y (each with same number of elements).
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   504
function GCD(x,y) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   505
  var xc,yc;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   506
  xc=dup(x);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   507
  yc=dup(y);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   508
  GCD_(xc,yc);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   509
  return xc;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   510
}
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   511
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   512
//set x to the greatest common divisor of bigInts x and y (each with same number of elements).
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   513
//y is destroyed.
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   514
function GCD_(x,y) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   515
  var i,xp,yp,A,B,C,D,q,sing;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   516
  if (T.length!=x.length)
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   517
    T=dup(x);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   518
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   519
  sing=1;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   520
  while (sing) { //while y has nonzero elements other than y[0]
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   521
    sing=0;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   522
    for (i=1;i<y.length;i++) //check if y has nonzero elements other than 0
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   523
      if (y[i]) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   524
        sing=1;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   525
        break;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   526
      }
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   527
    if (!sing) break; //quit when y all zero elements except possibly y[0]
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   528
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   529
    for (i=x.length;!x[i] && i>=0;i--);  //find most significant element of x
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   530
    xp=x[i];
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   531
    yp=y[i];
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   532
    A=1; B=0; C=0; D=1;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   533
    while ((yp+C) && (yp+D)) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   534
      q =Math.floor((xp+A)/(yp+C));
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   535
      qp=Math.floor((xp+B)/(yp+D));
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   536
      if (q!=qp)
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   537
        break;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   538
      t= A-q*C;   A=C;   C=t;    //  do (A,B,xp, C,D,yp) = (C,D,yp, A,B,xp) - q*(0,0,0, C,D,yp)      
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   539
      t= B-q*D;   B=D;   D=t;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   540
      t=xp-q*yp; xp=yp; yp=t;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   541
    }
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   542
    if (B) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   543
      copy_(T,x);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   544
      linComb_(x,y,A,B); //x=A*x+B*y
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   545
      linComb_(y,T,D,C); //y=D*y+C*T
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   546
    } else {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   547
      mod_(x,y);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   548
      copy_(T,x);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   549
      copy_(x,y);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   550
      copy_(y,T);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   551
    } 
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   552
  }
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   553
  if (y[0]==0)
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   554
    return;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   555
  t=modInt(x,y[0]);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   556
  copyInt_(x,y[0]);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   557
  y[0]=t;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   558
  while (y[0]) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   559
    x[0]%=y[0];
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   560
    t=x[0]; x[0]=y[0]; y[0]=t;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   561
  }
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   562
}
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   563
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   564
//do x=x**(-1) mod n, for bigInts x and n.
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   565
//If no inverse exists, it sets x to zero and returns 0, else it returns 1.
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   566
//The x array must be at least as large as the n array.
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   567
function inverseMod_(x,n) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   568
  var k=1+2*Math.max(x.length,n.length);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   569
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   570
  if(!(x[0]&1)  && !(n[0]&1)) {  //if both inputs are even, then inverse doesn't exist
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   571
    copyInt_(x,0);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   572
    return 0;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   573
  }
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   574
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   575
  if (eg_u.length!=k) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   576
    eg_u=new Array(k);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   577
    eg_v=new Array(k);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   578
    eg_A=new Array(k);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   579
    eg_B=new Array(k);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   580
    eg_C=new Array(k);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   581
    eg_D=new Array(k);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   582
  }
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   583
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   584
  copy_(eg_u,x);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   585
  copy_(eg_v,n);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   586
  copyInt_(eg_A,1);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   587
  copyInt_(eg_B,0);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   588
  copyInt_(eg_C,0);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   589
  copyInt_(eg_D,1);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   590
  for (;;) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   591
    while(!(eg_u[0]&1)) {  //while eg_u is even
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   592
      halve_(eg_u);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   593
      if (!(eg_A[0]&1) && !(eg_B[0]&1)) { //if eg_A==eg_B==0 mod 2
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   594
        halve_(eg_A);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   595
        halve_(eg_B);      
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   596
      } else {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   597
        add_(eg_A,n);  halve_(eg_A);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   598
        sub_(eg_B,x);  halve_(eg_B);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   599
      }
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   600
    }
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   601
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   602
    while (!(eg_v[0]&1)) {  //while eg_v is even
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   603
      halve_(eg_v);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   604
      if (!(eg_C[0]&1) && !(eg_D[0]&1)) { //if eg_C==eg_D==0 mod 2
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   605
        halve_(eg_C);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   606
        halve_(eg_D);      
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   607
      } else {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   608
        add_(eg_C,n);  halve_(eg_C);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   609
        sub_(eg_D,x);  halve_(eg_D);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   610
      }
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   611
    }
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   612
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   613
    if (!greater(eg_v,eg_u)) { //eg_v <= eg_u
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   614
      sub_(eg_u,eg_v);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   615
      sub_(eg_A,eg_C);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   616
      sub_(eg_B,eg_D);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   617
    } else {                   //eg_v > eg_u
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   618
      sub_(eg_v,eg_u);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   619
      sub_(eg_C,eg_A);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   620
      sub_(eg_D,eg_B);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   621
    }
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   622
  
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   623
    if (equalsInt(eg_u,0)) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   624
      if (negative(eg_C)) //make sure answer is nonnegative
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   625
        add_(eg_C,n);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   626
      copy_(x,eg_C);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   627
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   628
      if (!equalsInt(eg_v,1)) { //if GCD_(x,n)!=1, then there is no inverse
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   629
        copyInt_(x,0);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   630
        return 0;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   631
      }
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   632
      return 1;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   633
    }
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   634
  }
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   635
}
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   636
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   637
//return x**(-1) mod n, for integers x and n.  Return 0 if there is no inverse
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   638
function inverseModInt(x,n) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   639
  var a=1,b=0,t;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   640
  for (;;) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   641
    if (x==1) return a;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   642
    if (x==0) return 0;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   643
    b-=a*Math.floor(n/x);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   644
    n%=x;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   645
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   646
    if (n==1) return b; //to avoid negatives, change this b to n-b, and each -= to +=
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   647
    if (n==0) return 0;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   648
    a-=b*Math.floor(x/n);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   649
    x%=n;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   650
  }
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   651
}
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   652
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   653
//this deprecated function is for backward compatibility only. 
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   654
function inverseModInt_(x,n) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   655
   return inverseModInt(x,n);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   656
}
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   657
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   658
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   659
//Given positive bigInts x and y, change the bigints v, a, and b to positive bigInts such that:
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   660
//     v = GCD_(x,y) = a*x-b*y
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   661
//The bigInts v, a, b, must have exactly as many elements as the larger of x and y.
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   662
function eGCD_(x,y,v,a,b) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   663
  var g=0;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   664
  var k=Math.max(x.length,y.length);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   665
  if (eg_u.length!=k) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   666
    eg_u=new Array(k);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   667
    eg_A=new Array(k);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   668
    eg_B=new Array(k);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   669
    eg_C=new Array(k);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   670
    eg_D=new Array(k);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   671
  }
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   672
  while(!(x[0]&1)  && !(y[0]&1)) {  //while x and y both even
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   673
    halve_(x);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   674
    halve_(y);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   675
    g++;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   676
  }
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   677
  copy_(eg_u,x);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   678
  copy_(v,y);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   679
  copyInt_(eg_A,1);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   680
  copyInt_(eg_B,0);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   681
  copyInt_(eg_C,0);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   682
  copyInt_(eg_D,1);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   683
  for (;;) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   684
    while(!(eg_u[0]&1)) {  //while u is even
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   685
      halve_(eg_u);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   686
      if (!(eg_A[0]&1) && !(eg_B[0]&1)) { //if A==B==0 mod 2
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   687
        halve_(eg_A);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   688
        halve_(eg_B);      
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   689
      } else {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   690
        add_(eg_A,y);  halve_(eg_A);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   691
        sub_(eg_B,x);  halve_(eg_B);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   692
      }
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   693
    }
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   694
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   695
    while (!(v[0]&1)) {  //while v is even
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   696
      halve_(v);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   697
      if (!(eg_C[0]&1) && !(eg_D[0]&1)) { //if C==D==0 mod 2
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   698
        halve_(eg_C);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   699
        halve_(eg_D);      
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   700
      } else {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   701
        add_(eg_C,y);  halve_(eg_C);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   702
        sub_(eg_D,x);  halve_(eg_D);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   703
      }
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   704
    }
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   705
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   706
    if (!greater(v,eg_u)) { //v<=u
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   707
      sub_(eg_u,v);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   708
      sub_(eg_A,eg_C);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   709
      sub_(eg_B,eg_D);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   710
    } else {                //v>u
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   711
      sub_(v,eg_u);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   712
      sub_(eg_C,eg_A);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   713
      sub_(eg_D,eg_B);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   714
    }
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   715
    if (equalsInt(eg_u,0)) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   716
      if (negative(eg_C)) {   //make sure a (C)is nonnegative
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   717
        add_(eg_C,y);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   718
        sub_(eg_D,x);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   719
      }
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   720
      multInt_(eg_D,-1);  ///make sure b (D) is nonnegative
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   721
      copy_(a,eg_C);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   722
      copy_(b,eg_D);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   723
      leftShift_(v,g);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   724
      return;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   725
    }
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   726
  }
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   727
}
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   728
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   729
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   730
//is bigInt x negative?
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   731
function negative(x) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   732
  return ((x[x.length-1]>>(bpe-1))&1);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   733
}
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   734
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   735
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   736
//is (x << (shift*bpe)) > y?
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   737
//x and y are nonnegative bigInts
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   738
//shift is a nonnegative integer
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   739
function greaterShift(x,y,shift) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   740
  var kx=x.length, ky=y.length;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   741
  k=((kx+shift)<ky) ? (kx+shift) : ky;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   742
  for (i=ky-1-shift; i<kx && i>=0; i++) 
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   743
    if (x[i]>0)
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   744
      return 1; //if there are nonzeros in x to the left of the first column of y, then x is bigger
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   745
  for (i=kx-1+shift; i<ky; i++)
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   746
    if (y[i]>0)
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   747
      return 0; //if there are nonzeros in y to the left of the first column of x, then x is not bigger
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   748
  for (i=k-1; i>=shift; i--)
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   749
    if      (x[i-shift]>y[i]) return 1;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   750
    else if (x[i-shift]<y[i]) return 0;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   751
  return 0;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   752
}
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   753
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   754
//is x > y? (x and y both nonnegative)
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   755
function greater(x,y) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   756
  var i;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   757
  var k=(x.length<y.length) ? x.length : y.length;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   758
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   759
  for (i=x.length;i<y.length;i++)
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   760
    if (y[i])
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   761
      return 0;  //y has more digits
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   762
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   763
  for (i=y.length;i<x.length;i++)
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   764
    if (x[i])
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   765
      return 1;  //x has more digits
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   766
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   767
  for (i=k-1;i>=0;i--)
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   768
    if (x[i]>y[i])
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   769
      return 1;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   770
    else if (x[i]<y[i])
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   771
      return 0;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   772
  return 0;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   773
}
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   774
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   775
//divide x by y giving quotient q and remainder r.  (q=floor(x/y),  r=x mod y).  All 4 are bigints.
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   776
//x must have at least one leading zero element.
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   777
//y must be nonzero.
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   778
//q and r must be arrays that are exactly the same length as x. (Or q can have more).
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   779
//Must have x.length >= y.length >= 2.
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   780
function divide_(x,y,q,r) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   781
  var kx, ky;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   782
  var i,j,y1,y2,c,a,b;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   783
  copy_(r,x);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   784
  for (ky=y.length;y[ky-1]==0;ky--); //ky is number of elements in y, not including leading zeros
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   785
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   786
  //normalize: ensure the most significant element of y has its highest bit set  
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   787
  b=y[ky-1];
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   788
  for (a=0; b; a++)
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   789
    b>>=1;  
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   790
  a=bpe-a;  //a is how many bits to shift so that the high order bit of y is leftmost in its array element
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   791
  leftShift_(y,a);  //multiply both by 1<<a now, then divide both by that at the end
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   792
  leftShift_(r,a);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   793
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   794
  //Rob Visser discovered a bug: the following line was originally just before the normalization.
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   795
  for (kx=r.length;r[kx-1]==0 && kx>ky;kx--); //kx is number of elements in normalized x, not including leading zeros
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   796
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   797
  copyInt_(q,0);                      // q=0
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   798
  while (!greaterShift(y,r,kx-ky)) {  // while (leftShift_(y,kx-ky) <= r) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   799
    subShift_(r,y,kx-ky);             //   r=r-leftShift_(y,kx-ky)
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   800
    q[kx-ky]++;                       //   q[kx-ky]++;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   801
  }                                   // }
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   802
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   803
  for (i=kx-1; i>=ky; i--) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   804
    if (r[i]==y[ky-1])
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   805
      q[i-ky]=mask;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   806
    else
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   807
      q[i-ky]=Math.floor((r[i]*radix+r[i-1])/y[ky-1]);	
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   808
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   809
    //The following for(;;) loop is equivalent to the commented while loop, 
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   810
    //except that the uncommented version avoids overflow.
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   811
    //The commented loop comes from HAC, which assumes r[-1]==y[-1]==0
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   812
    //  while (q[i-ky]*(y[ky-1]*radix+y[ky-2]) > r[i]*radix*radix+r[i-1]*radix+r[i-2])
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   813
    //    q[i-ky]--;    
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   814
    for (;;) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   815
      y2=(ky>1 ? y[ky-2] : 0)*q[i-ky];
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   816
      c=y2>>bpe;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   817
      y2=y2 & mask;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   818
      y1=c+q[i-ky]*y[ky-1];
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   819
      c=y1>>bpe;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   820
      y1=y1 & mask;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   821
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   822
      if (c==r[i] ? y1==r[i-1] ? y2>(i>1 ? r[i-2] : 0) : y1>r[i-1] : c>r[i]) 
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   823
        q[i-ky]--;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   824
      else
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   825
        break;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   826
    }
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   827
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   828
    linCombShift_(r,y,-q[i-ky],i-ky);    //r=r-q[i-ky]*leftShift_(y,i-ky)
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   829
    if (negative(r)) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   830
      addShift_(r,y,i-ky);         //r=r+leftShift_(y,i-ky)
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   831
      q[i-ky]--;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   832
    }
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   833
  }
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   834
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   835
  rightShift_(y,a);  //undo the normalization step
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   836
  rightShift_(r,a);  //undo the normalization step
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   837
}
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   838
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   839
//do carries and borrows so each element of the bigInt x fits in bpe bits.
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   840
function carry_(x) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   841
  var i,k,c,b;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   842
  k=x.length;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   843
  c=0;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   844
  for (i=0;i<k;i++) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   845
    c+=x[i];
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   846
    b=0;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   847
    if (c<0) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   848
      b=-(c>>bpe);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   849
      c+=b*radix;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   850
    }
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   851
    x[i]=c & mask;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   852
    c=(c>>bpe)-b;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   853
  }
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   854
}
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   855
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   856
//return x mod n for bigInt x and integer n.
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   857
function modInt(x,n) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   858
  var i,c=0;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   859
  for (i=x.length-1; i>=0; i--)
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   860
    c=(c*radix+x[i])%n;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   861
  return c;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   862
}
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   863
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   864
//convert the integer t into a bigInt with at least the given number of bits.
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   865
//the returned array stores the bigInt in bpe-bit chunks, little endian (buff[0] is least significant word)
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   866
//Pad the array with leading zeros so that it has at least minSize elements.
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   867
//There will always be at least one leading 0 element.
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   868
function int2bigInt(t,bits,minSize) {   
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   869
  var i,k;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   870
  k=Math.ceil(bits/bpe)+1;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   871
  k=minSize>k ? minSize : k;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   872
  buff=new Array(k);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   873
  copyInt_(buff,t);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   874
  return buff;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   875
}
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   876
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   877
//return the bigInt given a string representation in a given base.  
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   878
//Pad the array with leading zeros so that it has at least minSize elements.
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   879
//If base=-1, then it reads in a space-separated list of array elements in decimal.
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   880
//The array will always have at least one leading zero, unless base=-1.
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   881
function str2bigInt(s,base,minSize) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   882
  var d, i, j, x, y, kk;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   883
  var k=s.length;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   884
  if (base==-1) { //comma-separated list of array elements in decimal
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   885
    x=new Array(0);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   886
    for (;;) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   887
      y=new Array(x.length+1);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   888
      for (i=0;i<x.length;i++)
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   889
        y[i+1]=x[i];
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   890
      y[0]=parseInt(s,10);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   891
      x=y;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   892
      d=s.indexOf(',',0);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   893
      if (d<1) 
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   894
        break;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   895
      s=s.substring(d+1);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   896
      if (s.length==0)
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   897
        break;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   898
    }
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   899
    if (x.length<minSize) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   900
      y=new Array(minSize);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   901
      copy_(y,x);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   902
      return y;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   903
    }
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   904
    return x;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   905
  }
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   906
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   907
  x=int2bigInt(0,base*k,0);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   908
  for (i=0;i<k;i++) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   909
    d=digitsStr.indexOf(s.substring(i,i+1),0);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   910
    if (base<=36 && d>=36)  //convert lowercase to uppercase if base<=36
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   911
      d-=26;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   912
    if (d<base && d>=0) {   //ignore illegal characters
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   913
      multInt_(x,base);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   914
      addInt_(x,d);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   915
    }
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   916
  }
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   917
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   918
  for (k=x.length;k>0 && !x[k-1];k--); //strip off leading zeros
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   919
  k=minSize>k+1 ? minSize : k+1;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   920
  y=new Array(k);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   921
  kk=k<x.length ? k : x.length;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   922
  for (i=0;i<kk;i++)
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   923
    y[i]=x[i];
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   924
  for (;i<k;i++)
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   925
    y[i]=0;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   926
  return y;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   927
}
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   928
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   929
//is bigint x equal to integer y?
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   930
//y must have less than bpe bits
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   931
function equalsInt(x,y) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   932
  var i;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   933
  if (x[0]!=y)
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   934
    return 0;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   935
  for (i=1;i<x.length;i++)
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   936
    if (x[i])
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   937
      return 0;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   938
  return 1;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   939
}
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   940
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   941
//are bigints x and y equal?
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   942
//this works even if x and y are different lengths and have arbitrarily many leading zeros
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   943
function equals(x,y) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   944
  var i;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   945
  var k=x.length<y.length ? x.length : y.length;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   946
  for (i=0;i<k;i++)
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   947
    if (x[i]!=y[i])
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   948
      return 0;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   949
  if (x.length>y.length) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   950
    for (;i<x.length;i++)
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   951
      if (x[i])
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   952
        return 0;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   953
  } else {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   954
    for (;i<y.length;i++)
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   955
      if (y[i])
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   956
        return 0;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   957
  }
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   958
  return 1;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   959
}
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   960
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   961
//is the bigInt x equal to zero?
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   962
function isZero(x) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   963
  var i;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   964
  for (i=0;i<x.length;i++)
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   965
    if (x[i])
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   966
      return 0;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   967
  return 1;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   968
}
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   969
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   970
//convert a bigInt into a string in a given base, from base 2 up to base 95.
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   971
//Base -1 prints the contents of the array representing the number.
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   972
function bigInt2str(x,base) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   973
  var i,t,s="";
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   974
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   975
  if (s6.length!=x.length) 
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   976
    s6=dup(x);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   977
  else
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   978
    copy_(s6,x);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   979
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   980
  if (base==-1) { //return the list of array contents
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   981
    for (i=x.length-1;i>0;i--)
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   982
      s+=x[i]+',';
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   983
    s+=x[0];
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   984
  }
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   985
  else { //return it in the given base
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   986
    while (!isZero(s6)) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   987
      t=divInt_(s6,base);  //t=s6 % base; s6=floor(s6/base);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   988
      s=digitsStr.substring(t,t+1)+s;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   989
    }
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   990
  }
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   991
  if (s.length==0)
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   992
    s="0";
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   993
  return s;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   994
}
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   995
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   996
//returns a duplicate of bigInt x
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   997
function dup(x) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   998
  var i;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
   999
  buff=new Array(x.length);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1000
  copy_(buff,x);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1001
  return buff;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1002
}
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1003
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1004
//do x=y on bigInts x and y.  x must be an array at least as big as y (not counting the leading zeros in y).
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1005
function copy_(x,y) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1006
  var i;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1007
  var k=x.length<y.length ? x.length : y.length;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1008
  for (i=0;i<k;i++)
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1009
    x[i]=y[i];
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1010
  for (i=k;i<x.length;i++)
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1011
    x[i]=0;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1012
}
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1013
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1014
//do x=y on bigInt x and integer y.  
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1015
function copyInt_(x,n) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1016
  var i,c;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1017
  for (c=n,i=0;i<x.length;i++) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1018
    x[i]=c & mask;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1019
    c>>=bpe;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1020
  }
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1021
}
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1022
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1023
//do x=x+n where x is a bigInt and n is an integer.
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1024
//x must be large enough to hold the result.
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1025
function addInt_(x,n) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1026
  var i,k,c,b;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1027
  x[0]+=n;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1028
  k=x.length;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1029
  c=0;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1030
  for (i=0;i<k;i++) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1031
    c+=x[i];
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1032
    b=0;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1033
    if (c<0) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1034
      b=-(c>>bpe);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1035
      c+=b*radix;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1036
    }
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1037
    x[i]=c & mask;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1038
    c=(c>>bpe)-b;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1039
    if (!c) return; //stop carrying as soon as the carry_ is zero
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1040
  }
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1041
}
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1042
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1043
//right shift bigInt x by n bits.  0 <= n < bpe.
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1044
function rightShift_(x,n) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1045
  var i;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1046
  var k=Math.floor(n/bpe);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1047
  if (k) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1048
    for (i=0;i<x.length-k;i++) //right shift x by k elements
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1049
      x[i]=x[i+k];
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1050
    for (;i<x.length;i++)
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1051
      x[i]=0;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1052
    n%=bpe;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1053
  }
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1054
  for (i=0;i<x.length-1;i++) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1055
    x[i]=mask & ((x[i+1]<<(bpe-n)) | (x[i]>>n));
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1056
  }
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1057
  x[i]>>=n;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1058
}
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1059
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1060
//do x=floor(|x|/2)*sgn(x) for bigInt x in 2's complement
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1061
function halve_(x) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1062
  var i;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1063
  for (i=0;i<x.length-1;i++) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1064
    x[i]=mask & ((x[i+1]<<(bpe-1)) | (x[i]>>1));
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1065
  }
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1066
  x[i]=(x[i]>>1) | (x[i] & (radix>>1));  //most significant bit stays the same
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1067
}
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1068
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1069
//left shift bigInt x by n bits.
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1070
function leftShift_(x,n) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1071
  var i;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1072
  var k=Math.floor(n/bpe);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1073
  if (k) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1074
    for (i=x.length; i>=k; i--) //left shift x by k elements
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1075
      x[i]=x[i-k];
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1076
    for (;i>=0;i--)
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1077
      x[i]=0;  
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1078
    n%=bpe;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1079
  }
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1080
  if (!n)
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1081
    return;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1082
  for (i=x.length-1;i>0;i--) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1083
    x[i]=mask & ((x[i]<<n) | (x[i-1]>>(bpe-n)));
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1084
  }
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1085
  x[i]=mask & (x[i]<<n);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1086
}
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1087
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1088
//do x=x*n where x is a bigInt and n is an integer.
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1089
//x must be large enough to hold the result.
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1090
function multInt_(x,n) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1091
  var i,k,c,b;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1092
  if (!n)
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1093
    return;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1094
  k=x.length;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1095
  c=0;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1096
  for (i=0;i<k;i++) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1097
    c+=x[i]*n;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1098
    b=0;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1099
    if (c<0) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1100
      b=-(c>>bpe);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1101
      c+=b*radix;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1102
    }
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1103
    x[i]=c & mask;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1104
    c=(c>>bpe)-b;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1105
  }
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1106
}
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1107
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1108
//do x=floor(x/n) for bigInt x and integer n, and return the remainder
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1109
function divInt_(x,n) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1110
  var i,r=0,s;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1111
  for (i=x.length-1;i>=0;i--) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1112
    s=r*radix+x[i];
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1113
    x[i]=Math.floor(s/n);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1114
    r=s%n;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1115
  }
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1116
  return r;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1117
}
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1118
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1119
//do the linear combination x=a*x+b*y for bigInts x and y, and integers a and b.
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1120
//x must be large enough to hold the answer.
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1121
function linComb_(x,y,a,b) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1122
  var i,c,k,kk;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1123
  k=x.length<y.length ? x.length : y.length;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1124
  kk=x.length;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1125
  for (c=0,i=0;i<k;i++) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1126
    c+=a*x[i]+b*y[i];
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1127
    x[i]=c & mask;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1128
    c>>=bpe;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1129
  }
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1130
  for (i=k;i<kk;i++) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1131
    c+=a*x[i];
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1132
    x[i]=c & mask;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1133
    c>>=bpe;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1134
  }
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1135
}
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1136
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1137
//do the linear combination x=a*x+b*(y<<(ys*bpe)) for bigInts x and y, and integers a, b and ys.
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1138
//x must be large enough to hold the answer.
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1139
function linCombShift_(x,y,b,ys) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1140
  var i,c,k,kk;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1141
  k=x.length<ys+y.length ? x.length : ys+y.length;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1142
  kk=x.length;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1143
  for (c=0,i=ys;i<k;i++) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1144
    c+=x[i]+b*y[i-ys];
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1145
    x[i]=c & mask;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1146
    c>>=bpe;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1147
  }
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1148
  for (i=k;c && i<kk;i++) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1149
    c+=x[i];
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1150
    x[i]=c & mask;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1151
    c>>=bpe;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1152
  }
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1153
}
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1154
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1155
//do x=x+(y<<(ys*bpe)) for bigInts x and y, and integers a,b and ys.
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1156
//x must be large enough to hold the answer.
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1157
function addShift_(x,y,ys) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1158
  var i,c,k,kk;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1159
  k=x.length<ys+y.length ? x.length : ys+y.length;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1160
  kk=x.length;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1161
  for (c=0,i=ys;i<k;i++) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1162
    c+=x[i]+y[i-ys];
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1163
    x[i]=c & mask;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1164
    c>>=bpe;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1165
  }
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1166
  for (i=k;c && i<kk;i++) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1167
    c+=x[i];
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1168
    x[i]=c & mask;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1169
    c>>=bpe;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1170
  }
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1171
}
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1172
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1173
//do x=x-(y<<(ys*bpe)) for bigInts x and y, and integers a,b and ys.
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1174
//x must be large enough to hold the answer.
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1175
function subShift_(x,y,ys) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1176
  var i,c,k,kk;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1177
  k=x.length<ys+y.length ? x.length : ys+y.length;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1178
  kk=x.length;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1179
  for (c=0,i=ys;i<k;i++) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1180
    c+=x[i]-y[i-ys];
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1181
    x[i]=c & mask;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1182
    c>>=bpe;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1183
  }
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1184
  for (i=k;c && i<kk;i++) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1185
    c+=x[i];
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1186
    x[i]=c & mask;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1187
    c>>=bpe;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1188
  }
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1189
}
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1190
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1191
//do x=x-y for bigInts x and y.
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1192
//x must be large enough to hold the answer.
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1193
//negative answers will be 2s complement
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1194
function sub_(x,y) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1195
  var i,c,k,kk;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1196
  k=x.length<y.length ? x.length : y.length;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1197
  for (c=0,i=0;i<k;i++) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1198
    c+=x[i]-y[i];
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1199
    x[i]=c & mask;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1200
    c>>=bpe;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1201
  }
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1202
  for (i=k;c && i<x.length;i++) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1203
    c+=x[i];
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1204
    x[i]=c & mask;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1205
    c>>=bpe;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1206
  }
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1207
}
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1208
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1209
//do x=x+y for bigInts x and y.
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1210
//x must be large enough to hold the answer.
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1211
function add_(x,y) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1212
  var i,c,k,kk;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1213
  k=x.length<y.length ? x.length : y.length;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1214
  for (c=0,i=0;i<k;i++) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1215
    c+=x[i]+y[i];
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1216
    x[i]=c & mask;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1217
    c>>=bpe;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1218
  }
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1219
  for (i=k;c && i<x.length;i++) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1220
    c+=x[i];
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1221
    x[i]=c & mask;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1222
    c>>=bpe;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1223
  }
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1224
}
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1225
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1226
//do x=x*y for bigInts x and y.  This is faster when y<x.
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1227
function mult_(x,y) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1228
  var i;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1229
  if (ss.length!=2*x.length)
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1230
    ss=new Array(2*x.length);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1231
  copyInt_(ss,0);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1232
  for (i=0;i<y.length;i++)
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1233
    if (y[i])
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1234
      linCombShift_(ss,x,y[i],i);   //ss=1*ss+y[i]*(x<<(i*bpe))
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1235
  copy_(x,ss);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1236
}
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1237
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1238
//do x=x mod n for bigInts x and n.
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1239
function mod_(x,n) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1240
  if (s4.length!=x.length)
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1241
    s4=dup(x);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1242
  else
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1243
    copy_(s4,x);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1244
  if (s5.length!=x.length)
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1245
    s5=dup(x);  
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1246
  divide_(s4,n,s5,x);  //x = remainder of s4 / n
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1247
}
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1248
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1249
//do x=x*y mod n for bigInts x,y,n.
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1250
//for greater speed, let y<x.
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1251
function multMod_(x,y,n) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1252
  var i;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1253
  if (s0.length!=2*x.length)
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1254
    s0=new Array(2*x.length);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1255
  copyInt_(s0,0);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1256
  for (i=0;i<y.length;i++)
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1257
    if (y[i])
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1258
      linCombShift_(s0,x,y[i],i);   //s0=1*s0+y[i]*(x<<(i*bpe))
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1259
  mod_(s0,n);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1260
  copy_(x,s0);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1261
}
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1262
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1263
//do x=x*x mod n for bigInts x,n.
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1264
function squareMod_(x,n) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1265
  var i,j,d,c,kx,kn,k;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1266
  for (kx=x.length; kx>0 && !x[kx-1]; kx--);  //ignore leading zeros in x
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1267
  k=kx>n.length ? 2*kx : 2*n.length; //k=# elements in the product, which is twice the elements in the larger of x and n
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1268
  if (s0.length!=k) 
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1269
    s0=new Array(k);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1270
  copyInt_(s0,0);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1271
  for (i=0;i<kx;i++) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1272
    c=s0[2*i]+x[i]*x[i];
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1273
    s0[2*i]=c & mask;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1274
    c>>=bpe;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1275
    for (j=i+1;j<kx;j++) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1276
      c=s0[i+j]+2*x[i]*x[j]+c;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1277
      s0[i+j]=(c & mask);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1278
      c>>=bpe;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1279
    }
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1280
    s0[i+kx]=c;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1281
  }
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1282
  mod_(s0,n);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1283
  copy_(x,s0);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1284
}
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1285
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1286
//return x with exactly k leading zero elements
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1287
function bigint_trim(x,k) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1288
  var i,y;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1289
  for (i=x.length; i>0 && !x[i-1]; i--);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1290
  y=new Array(i+k);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1291
  copy_(y,x);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1292
  return y;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1293
}
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1294
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1295
//do x=x**y mod n, where x,y,n are bigInts and ** is exponentiation.  0**0=1.
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1296
//this is faster when n is odd.  x usually needs to have as many elements as n.
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1297
function powMod_(x,y,n) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1298
  var k1,k2,kn,np;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1299
  if(s7.length!=n.length)
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1300
    s7=dup(n);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1301
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1302
  //for even modulus, use a simple square-and-multiply algorithm,
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1303
  //rather than using the more complex Montgomery algorithm.
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1304
  if ((n[0]&1)==0) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1305
    copy_(s7,x);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1306
    copyInt_(x,1);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1307
    while(!equalsInt(y,0)) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1308
      if (y[0]&1)
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1309
        multMod_(x,s7,n);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1310
      divInt_(y,2);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1311
      squareMod_(s7,n); 
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1312
    }
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1313
    return;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1314
  }
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1315
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1316
  //calculate np from n for the Montgomery multiplications
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1317
  copyInt_(s7,0);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1318
  for (kn=n.length;kn>0 && !n[kn-1];kn--);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1319
  np=radix-inverseModInt(modInt(n,radix),radix);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1320
  s7[kn]=1;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1321
  multMod_(x ,s7,n);   // x = x * 2**(kn*bp) mod n
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1322
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1323
  if (s3.length!=x.length)
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1324
    s3=dup(x);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1325
  else
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1326
    copy_(s3,x);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1327
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1328
  for (k1=y.length-1;k1>0 & !y[k1]; k1--);  //k1=first nonzero element of y
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1329
  if (y[k1]==0) {  //anything to the 0th power is 1
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1330
    copyInt_(x,1);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1331
    return;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1332
  }
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1333
  for (k2=1<<(bpe-1);k2 && !(y[k1] & k2); k2>>=1);  //k2=position of first 1 bit in y[k1]
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1334
  for (;;) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1335
    if (!(k2>>=1)) {  //look at next bit of y
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1336
      k1--;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1337
      if (k1<0) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1338
        mont_(x,one,n,np);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1339
        return;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1340
      }
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1341
      k2=1<<(bpe-1);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1342
    }    
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1343
    mont_(x,x,n,np);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1344
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1345
    if (k2 & y[k1]) //if next bit is a 1
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1346
      mont_(x,s3,n,np);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1347
  }
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1348
}    
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1349
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1350
//do x=x*y*Ri mod n for bigInts x,y,n, 
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1351
//  where Ri = 2**(-kn*bpe) mod n, and kn is the 
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1352
//  number of elements in the n array, not 
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1353
//  counting leading zeros.  
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1354
//x must be large enough to hold the answer.
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1355
//It's OK if x and y are the same variable.
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1356
//must have:
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1357
//  x,y < n
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1358
//  n is odd
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1359
//  np = -(n^(-1)) mod radix
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1360
function mont_(x,y,n,np) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1361
  var i,j,c,ui,t;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1362
  var kn=n.length;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1363
  var ky=y.length;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1364
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1365
  if (sa.length!=kn)
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1366
    sa=new Array(kn);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1367
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1368
  for (;kn>0 && n[kn-1]==0;kn--); //ignore leading zeros of n
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1369
  //this function sometimes gives wrong answers when the next line is uncommented
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1370
  //for (;ky>0 && y[ky-1]==0;ky--); //ignore leading zeros of y
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1371
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1372
  copyInt_(sa,0);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1373
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1374
  //the following loop consumes 95% of the runtime for randTruePrime_() and powMod_() for large keys
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1375
  for (i=0; i<kn; i++) {
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1376
    t=sa[0]+x[i]*y[0];
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1377
    ui=((t & mask) * np) & mask;  //the inner "& mask" is needed on Macintosh MSIE, but not windows MSIE
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1378
    c=(t+ui*n[0]) >> bpe;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1379
    t=x[i];
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1380
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1381
    //do sa=(sa+x[i]*y+ui*n)/b   where b=2**bpe
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1382
    for (j=1;j<ky;j++) { 
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1383
      c+=sa[j]+t*y[j]+ui*n[j];
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1384
      sa[j-1]=c & mask;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1385
      c>>=bpe;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1386
    }    
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1387
    for (;j<kn;j++) { 
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1388
      c+=sa[j]+ui*n[j];
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1389
      sa[j-1]=c & mask;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1390
      c>>=bpe;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1391
    }    
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1392
    sa[j-1]=c & mask;
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1393
  }
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1394
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1395
  if (!greater(n,sa))
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1396
    sub_(sa,n);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1397
  copy_(x,sa);
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1398
}
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1399
242353360e37 Added support for Diffie-Hellman key exchange during login. w00t!
Dan
parents:
diff changeset
  1400