<?php

/************************************************************************
 Code to be Executed
 You should include your code below. The subsequent sections contain the 
 set of functions. Some of these functions are already written for you,
 others you need to complete.
 ************************************************************************/


/************************************************************************
 EXAMPLE CODE
 The following code illustrates the use of BCMath and serialize, both of 
 which should be used in your assignment.
 THIS CODE MUST NOT BE INCLUDED WHEN YOU SUBMIT YOUR ASSIGNMENT
 ************************************************************************/

/* Create an array of integers and strings */
/* Note there are different ways to create arrays - this is just 2 examples */
$arr_of_int = array(1,2,3);
$arr_of_str = array();
$arr_of_str[0] = "hello";
$arr_of_str[1] = "world";

/* Print an array */
print_r($arr_of_str);

/* Output some text */
echo "This is a test\n";
echo $arr_of_str[0] . " " . $arr_of_str[1] . "\n";

/* Convert a data type into a string and vice versa */
/* The serial form is useful for sending a data structure over the network */
$serial_arr_of_str = serialize($arr_of_str);
echo $serial_arr_of_str;
echo "\n"; 
print_r(unserialize($serial_arr_of_str));
echo "\n";

/* BC Math */
/* You must use special BC Math functions in the RSA Encrypt and Decrypt, 
 * so that large calculations (exponentials) can be performed. You do so using 
 * the functions with integers input as strings */
echo "5 + 3 = " . bcadd('5','3') . "\n";
echo "6 x 5 = " . bcmul('6','5') . "\n";
echo "2 to the power of 3 = " . bcpow('2','3') . "\n";
/* Note there is also a function bcpowmod */

/* You can explicitly convert between data types using settype */
$i = 5; /* $i is an integer */
settype($i,"string"); /* $i is now a string */


/************************************************************************
 Diffie Hellman
 ************************************************************************/
/**
 * Generates public value Y for Diffie-Hellman Key Exchange
 * @param String $q Global DH parameter, prime number
 * @param String $a Global DH parameter, primitive root of q
 * @param String $X Private value X selected by user
 * @return String $Y Public value Y to be exchanged with other user
 */
function DH_GeneratePublic($q,$a,$X) {
	/* ====== START YOUR CODE HERE ====== */

	/* ====== END YOUR CODE HERE ====== */
}
	
/**
 * Generates secret value K for Diffie-Hellman Key Exchange
 * @param String $q Global DH parameter, prime number
 * @param String $X Private value X selected by user
 * @param String $Y Public value Y received from other user
 * @return String $K Secret value K shared between users
 */
function DH_GenerateSecret($q,$X,$Y) {
	/* ====== START YOUR CODE HERE ====== */

	/* ====== END YOUR CODE HERE ====== */
}

/************************************************************************
 RC4
 ************************************************************************/

/**
 * Encrypt using RC4
 * @param String $plaintext Plaintext
 * @param String $key Key (array of integers)
 * @return String Ciphertext as Hex string
 */
function RC4_Encrypt($plaintext,$key) {
	/* ====== START YOUR CODE HERE ====== */

 	/* ====== END YOUR CODE HERE ====== */
}

/**
 * Decrypt using RC4
 * @param String $ciphertext Ciphertext as Hex string
 * @param String $key Key (array of integers)
 * @return String Plaintext
 */
function RC4_Decrypt($ciphertext,$key) {
	/* ====== START YOUR CODE HERE ====== */

	/* ====== END YOUR CODE HERE ====== */
}

/**
 * Generated RC4 key stream
 * @param String $key Key (array of integers)
 * @param Integer $length Number of bits in plaintext
 * @return String Binary key stream as string
 */
function RC4_GenerateStream($key,$length) {
	/* ====== START YOUR CODE HERE ====== */

	/* ====== END YOUR CODE HERE ====== */
}


/************************************************************************
 RSA
 ************************************************************************/

/** 
 * Performs RSA encryption
 * @param String $plaintext the message to be encrypted. This should be an integer 
 *        represented as string (so BC math can be used)
 * @param Array of Strings $key the RSA key to perform the encryption. This should be 
 *        an array indicating appropriate RSA key
 * @return String $ciphertext the encrypted message
 */
function RSA_Encrypt($plaintext,$key) {
	/* ====== START YOUR CODE HERE ====== */

	/* ====== END YOUR CODE HERE ====== */
	return $ciphertext;
}

/** 
 * Performs RSA decryption
 * @param String $ciphertext the message to be decrypted. This should be an integer 
 *        represented as string (so BC math can be used)
 * @param Array of Strings $key the RSA key to perform the encryption. This should be 
 *        an array indicating appropriate RSA key
 * @return String $plaintext the original message
 */
function RSA_Decrypt($ciphertext,$key) {
	/* ====== START YOUR CODE HERE ====== */

	/* ====== END YOUR CODE HERE ====== */
	return $plaintext;
}

/** 
 * Generates an RSA Public/Private key pair
 * @param Integer $p Prime p
 * @param Integer $q Prime q
 * @return Array RSA keys (pu, pr, p and q)
 */
function RSA_GenerateKeys($p=-1, $q=-1) {
	/* ====== START YOUR CODE HERE ====== */

	/* ====== END YOUR CODE HERE ====== */
	/* Put the keys into the appropriate data structures */
	$publickey[0] = $e; /* e is a string */
	$privatekey[0] = $d; /* d is a string */
	$publickey[1] = $n; /* n is a string */
	$privatekey[1] = $n;

	$rsakeys['pu'] = $publickey;
	$rsakeys['pr'] = $privatekey;
	$rsakeys['p'] = $p; /* p is a string */
	$rsakeys['q'] = $q; /* q is a string */

	return $rsakeys;
}

/**
 * Prints the RSA key in a user friendly manner
 * @param Array of Array of Strings $rsakeys pair of RSA keys and primes p, q
 */
function RSA_PrintKeys($rsakeys) {
	echo "RSA key information\n";
	echo "   Primes: (p=" . $rsakeys['p'] . ",q=" . $rsakeys['q'] . ")\n";
	echo "   Public key: (e=" . $rsakeys['pu'][0] . ",n=" . $rsakeys['pu'][1] . ")\n";
	echo "   Private key: (d=" . $rsakeys['pr'][0] . ",n=" . $rsakeys['pr'][1] . ")\n";
}

/**
 * Calculate the hash of a message
 * @param String $message the data to be hashed
 * @return Integer $hash the hash value
 */
function Hash_Simple($message) {
	$i = 0;
	$n = 0;
	while ($i < strlen($message)) {
		$n = $n + ord($message[$i])*($i+1);
		$i++;
	}
	$hash = ($n % 1048576); 
	return $hash;
}


/************************************************************************
 General functions
 These function are provided for you to use. They may not be the best 
 or most efficient implementations, but that are suitable for this 
 assignment. You should not need to modify this code.
 ************************************************************************/

/** 
 * Convert Secret key generated by Diffie Hellman into format used by RC4 
 * @param String $secret Secret key from Diffie Hellman, integer stored as string
 * @return Array of Integers Key to be used by RC4 algorithm
 */
function Crypto_Secret2RC4Key ($secret) {
	$rc4key = array();
	for ($i=0; $i<strlen($secret); $i=$i+2) {
		$rc4key[$i/2] = substr($secret,$i,2);
	}
	return $rc4key;
}

/**
 * Permutate the input 
 * @param Array of binary $input
 * @param Array of binary $permutation
 * @return Array of binary 
 */
function Crypto_Permutate ($input, $permutation)
{
        $out = array();
        foreach($permutation as $i => $p) {
		        $out[$i] = $input[$p-1];
        }
        return $out;
}

/**
 * Exclusive OR two arrays
 * @param
 * @param
 * @return
 */
function Crypto_XOR ($a, $b) {
        foreach ($a as $i => $x) {
                $out[$i] = abs($a[$i] - $b[$i]);
        }

        return $out;
}

/**
 * Convert a binary number it its decimal value
 * @param Array of Integer $a Binary value as array
 * @return Integer Decimal value
 */
function Crypto_BinArr2Dec($a) {
	$i = 0;
	$b = 0;
	foreach (array_reverse($a) as $x) {
		$b = $b + ($x * pow(2,$i));
		$i++;
	}	
	return $b;
}

/**
 * Convert decimal number into its n bit binary value stored in an Array
 * @param Integer $a Decimal integer
 * @param Integer $n Number of bits 
 * @return Array of Integer Binary value
 */
function Crypto_Dec2BinArr($a,$n) {
	if ($a >= pow(2,$n)) {
		echo 'Error in Crypto_Dec2BinArr(): $a must be less than 2^$n.';
		return array();
	}
	$b = array();
	$i = 0;
	if ($a == 0) {
		$b = array_pad($b,$n,0);
	}
	while ($a != 0 && $i < $n) {
		$b[] = $a % 2;
		$a = $a / 2;
		$i++;
	}
	return array_reverse($b);
}

/**
 * Converts an ASCII string into its binary equivalent, that is
 * 7-bits for each character
 * @param String $ascii text or words
 * @param Integer $bits Number of bits the character is converted to (Default: 7)
 * @return String binary representation of input text or words
 */
function Crypto_ASCII2BinString ($ascii,$bits=7) {
	$l = strlen($ascii);
	$bin = '';
	for ($i = 0; $i < $l; $i++) {
		$bin_arr = Crypto_Dec2BinArr(ord($ascii[$i]),$bits);
		$bin = $bin . implode("",$bin_arr);
	}
	return $bin;
}

/**
 * Converts binary data into string of Hexadecimal digits
 * @param String $bin binary representation of text
 * @return String text 
 */
function Crypto_BinString2Hex ($bin) {
	$l = floor(strlen($bin) / 4);
	$hex = '';
	for ($i = 0; $i < $l; $i++) {
		$hex = $hex . base_convert(substr($bin,$i*4,4),2,16);
	} 
	return $hex;
}

/**
 * Converts an Hex string into its binary equivalent
 * @param String $hex Hex
 * @return String binary representation of input hex
 */
function Crypto_Hex2BinString ($hex) {
	$l = strlen($hex);
	$bin = '';
	for ($i = 0; $i < $l; $i++) {
		$bin = $bin . str_pad(base_convert(substr($hex,$i,1),16,2),4,"0",STR_PAD_LEFT);
	}
	return $bin;
}

/**
 * Converts binary data into ASCII (7-bit) text
 * @param String $bin binary representation of text
 * @param Integer $bits Number of bits to convert to character (Default: 7)
 * @return String text 
 */
function Crypto_BinString2ASCII ($bin,$bits=7) {
	$l = floor(strlen($bin) / $bits);
	$ascii = '';
	for ($i = 0; $i < $l; $i++) {
		$bin_arr = str_split(substr($bin,$i*$bits,$bits));
		$dec = Crypto_BinArr2Dec($bin_arr);
//		if ($dec < 32 || $dec > 122) {
		if ($dec < 0 || $dec > 127) {
			$ascii = $ascii . "~";
		} else {
			$ascii = $ascii . chr($dec);
		}
	} 
	return $ascii;
}

function Sec_IsPrime($n) {
/* Returns true of $n is a prime number
 * Code from http://www.phpmath.com/
 */
	$sqrtn = sqrt($n);
	for($i=2; $i <= $sqrtn; $i++ )
		if ($n % $i == 0) return false;
	return true ;
}

function Sec_ListPrimes($upTo) {
/* Return the prime numbers up to the parameter $upTo
 * Code from http://www.phpmath.com/
 */
	if ($upTo > 0) {
		$size   = $upTo + 1;
		$flags  = array();
		$primes = array();
		$limit  = sqrt($size);
  
		// Set flags
		for ($i=2; $i < $size; $i++) 
			$flags[$i] = true;
  
		// Cross out multiples of 2
		$j = 2;
		for ($i=$j+$j; $i < $size; $i=$i+$j) 
			$flags[$i] = false;
  
		// Cross out multiples of odd numbers
		for ($j=3; $j <= $limit; $j=$j+2) {
			if ($flags[$j]) {
				for ($i=$j+$j; $i < $size; $i=$i+$j) 
					$flags[$i] = false;
			}
		}
  
		// Build list of primes from what is left
		for ($i=2; $i < $size; $i++) {
			if ($flags[$i]) 
				$primes[] = $i;
		}
  
		return $primes;
	} else     
		die("n must be greater than 0.");
}

function Sec_GetPrimeFactors($n,$max=500000) {
/* Return the prime factors of $n
 * $max is an optional parameter, limiting the search
 *  If $max is not given as an input, then the default is used 
 * Code from http://www.phpmath.com/
 */
   
	$sqrtn = (int)ceil(sqrt($max));
	$trialDivisors = Sec_ListPrimes($sqrtn);    
	$trialDivisors[] = $sqrtn;

	$factors = array();
	if ($n > 0) {
		if ($n > $max) 
			die("Illegal arguments: ".$n." > ".$max);
      
		$k = 0;
		while ($n > 1) {
			$divisor   = $trialDivisors[$k];
			$quotient  = $n / $divisor;
			$remainder = $n % $divisor;
			if ($remainder == 0) {
				$factors[] = $divisor;
				$n         = $quotient;
			} else {
				if ($quotient > $divisor) 
					$k++;
				else {          
					$factors[]=$n;
					break;
				}
			}
		}
		return $factors;
	} else 
		die("n must be greater than 0.");      
}
  
function Sec_Gcd($a,$b) {
/* Returns an array with the first entry $x[0] containing the GCD of $a and $b
 * and the second entry $x[1] containing the multiplicative inverse of $b in mod $a
 * Uses the function Sec_EuclidGcd to peform the main calculation
 */
	$x = Sec_EuclidGcd($a,$b);
	if ($x[1] < 0) {
		if ($a > $b)
			$x[1] = $a + $x[1];
		else
			$x[1] = $b + $x[1];
	}
	return $x;
} 

function Sec_EuclidGcd($a,$b,$x=0,$y=1) {
/* 
 * Calculates the GCD and Multiplicative Inverse (if exists)
 * Code from http://www.ultimatespin.com/e_art_example.php
 * Modified to simplify the input parameters
 */

	// ensure that a > b, we can do this because the same two numbers always
	// have the same gcd.
	if($a < $b) {
		Sec_Swap($x,$y);
		Sec_Swap($a,$b);
	}

	//get the m of a/b = mb+r
	if($a != 0 && $b != 0) {
		$q = (int)($a/$b);
	} else {
		$q = 0;
	}

	//if there is no multiplicative inverse
	if(0 == $b) 
		return array($a,'no inverse');
	//if there is a multiplicative invers
	elseif(1 == $b) 
		return array($b,$y);
	//otherwise we are not at the gcd so we keep going
	else 
		return Sec_EuclidGcd($b,($a - ($q * $b)),$y,($x - ($q * $y)));

}

function Sec_Swap(&$a,&$b) {
/* Swaps the two values $a and $b */
	$temp = $a;
	$a = $b;
	$b = $temp;
}

function Sec_RelativelyPrime($a,$limit=100000) {
/* Returns a list of numbers relatively prime to $a
 * The list is limited to $limit numbers
 */
	$relprime = array(1);
	$i = 2;
	$n = 1;
	while ($n < $limit and $i < $a) {
		$x = Sec_Gcd($a,$i);
		if ($x[0] == 1) {
			$relprime[] = $i;
			$n++;
		}
		$i++;
	}
	return $relprime;
}


function Sec_Totient($a) {
/* Returns Eulers Totient of $a (if it is known) */
	$limit = 100000;
	if (Sec_IsPrime($a)) 
		return $a-1;
	else {
		$relprime = Sec_RelativelyPrime($a,$limit);
		if (count($relprime) < $limit) 
			return count($relprime);
		else
			return 'unknown';
	}
}
		

?>