/*
 
 My javascript implementation of the RSA algorithm, ported (partially)
 from the PHP implementation found at http://www.edsko.net/. Using the
 Big Integers library from http://www.ohdave.com/rsa/ (see BigInt.js
 for details).

 Send any question, suggestion or remark to: jay.bertrand@free.fr
 
  ----------------------------------------------------------------------------

 This software is provided as-is, without express or implied warranty.  
 Permission to use, copy, modify, distribute or sell this software, with or
 without fee, for any purpose and by any individual or organization, is hereby
 granted, provided that the above copyright notice and this paragraph appear 
 in all copies. Distribution as a part of an application or binary must
 include the above copyright notice in the documentation and/or other materials
 provided with the application or distribution.

  ----------------------------------------------------------------------------

 Exemple of usage:

  // first set up the bigint library
  // 76 is a good value for a 512 bits key
  // (use 19 digits per 128 bits)
  setMaxDigits(76);

  // prepare modulus and public exponent in hexa string format
  // (i.e. each byte represented as hexa decimal digit)
  var modulus = "0099d74e67d039f75654aea8d19fb199...16d";
  var publicKey = "10001";

  // message holds data to encrypt, length must be 
  // maxi (key length in bits / 8 - 3)

  // convert the "string" into a "byte array"
  var array = new Array();
  for(var k=0; k<message.length; k++)
    array.push(message.charCodeAt(k));

  array = rsa_encrypt(array, publicKey, modulus, 512);
  alert("Crypted data (byte array): " + array + "(" + array.length + ")");


*/

//--
// The function to encrypt data
//--
function rsa_encrypt(message, public_key_hex, modulus_hex, keylength) {

	var public_key = biFromHex(public_key_hex);
	var modulus = biFromHex(modulus_hex);

	var padded = add_PKCS1_padding(message, keylength / 8);
	var number = binary_to_number(padded);
	var encrypted = pow_mod(number, public_key, modulus);
	var result = number_to_binary(encrypted, keylength / 8);
	
	return result;
}

// -------------------------------- Implementation details below

//--
// Computes (in a clever way ;-)) pow(p,q) mod r
//--
function pow_mod(p, q, r)
{
	// Extract powers of 2 from $q
	var factors = new Array();
	var power_of_two = 0;

	var TWO = biFromNumber(2);
	var div = biCopy(q);
		
	while(biCompare(div, bigZero) == 1) {
		rem = biModulo(div, TWO);
		div = biDivide(div, TWO);

		if(biCompare(rem,bigOne)==0)
			factors.push(power_of_two);
		power_of_two++;
	}

	// Calculate partial results for each factor, using each partial result as a
	// starting point for the next. This depends of the factors of two being
	// generated in increasing order.
	partial_results = new Array();
	part_res = biCopy(p);
	idx = 0;

	for(k=0; k<factors.length; k++) {
		factor = factors[k];
		while(idx < factor)
		{
			part_res = biPow(part_res, 2);
			part_res = biModulo(part_res, r);
			idx++;
		}
		
		partial_results.push(part_res);
	}
	
	// Calculate final result
	result = bigOne;
	for(k=0; k<partial_results.length; k++) {
		part_res = partial_results[k];
		result = biMultiply(result, part_res);
		result = biModulo(result, r);
	}
	
	return result;
}

//--
// Function to add padding to a decrypted string
// We need to know if this is a private or a public key operation [4]
//--
function add_PKCS1_padding(data, blocksize)
{
	var pad_length = blocksize - 3 - data.length;

	var result = new Array();
	result.push(0);
	result.push(2); // block type
	for(i = 0; i < pad_length; i++)
		result.push( Math.round(Math.random()*255) );
	result.push(0);
	result = result.concat(data);
	return result;
}

function binary_to_number(data)
{
	base = biFromNumber(256);
	result = biFromNumber(0);
	radix = biFromNumber(1);
	
	for(i = data.length-1; i >= 0; i--) {
		digit = biFromNumber(data[i]);
		part_res = biMultiply(digit, radix);
		result = biAdd(result, part_res);
		radix = biMultiply(radix, base); 
	}
	
	return result;
}

function number_to_binary(number, blocksize) {

	var base = biFromNumber(256);
	var result = new Array();
	var div = biCopy(number);
	var idx = blocksize-1;
	
	for(k=0; k<blocksize; k++)
		result.push(0);
	
	while(biCompare(div, bigZero) > 0)
	{
		mod = biModulo(div, base);
		div = biDivide(div, base);
		
		// /!\ mod is a big integer
		result[idx--] = parseInt(biToString(mod, 10));
	}
	
	return result;
}

/* EOF */