RSAThreads.java

import java.io.UnsupportedEncodingException;
import java.math.BigInteger;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.util.Arrays;
import java.util.Random;

import javax.crypto.BadPaddingException;
import javax.crypto.Cipher;
import javax.crypto.IllegalBlockSizeException;
import javax.crypto.spec.SecretKeySpec;

/* Author:     Aaron Parks
 * Assignment: Assignment 2-RSA
 * Course:     CSS 527 - Cryptography
 * Term:       Autumn 2014
 * Version:    v1.1
 * 
 * Description:
 * Creates two threads -- Alice and Bob -- and a common RSACommunication object for the threads to synchronize their
 * sent / get requests.
 * Functionality of Alice
 * =======================
 * -> RSA encryption / decryption
 * -> AES decryption
 * -> Random generation of session key and nonce
 *
 * Functionality of Bob
 * =====================
 * -> RSA encryption / decryption
 * -> AES encryption
 *
 * Functionality of 'main'
 * ========================
 * -> generate RSA keys
 * -> primality testing
 */
class RSACommunication {
	//local holder for messages sent between Alice and Bob threads
	private BigInteger[] message = new BigInteger[2];
	//signaling flag for threads
	boolean flag = false;
	
	/* method "sendMessage()"
	 * Will copy value from parameter 'msg' to local BigInteger array.  Provides
	 * synchronized communication between threads by requiring a thread to wait
	 * if another thread is in 'getMessage' method.  */
	public synchronized void sendMessage(String thread_id, BigInteger[] msg) {
		if (flag) {
			try {
				wait();
			}
			catch (InterruptedException sm_err) {
				sm_err.printStackTrace();
			}
		}
		System.out.println("--> " + thread_id + " sending message");
		//assign to local variable
		for (int i = 0; i < msg.length; i++ ) {
			message[i] = msg[i];
		}
		flag = true;
		notify();
	}
	/* method "getMessage()"
	 * Will copy value from local BigInteger array to parameter 'msg'. Provides
	 * synchronized communication between threadsd by requiring a thread to wait
	 * if another thread is in 'sendMessage' method.  */
	public synchronized void getMessage(String thread_id, BigInteger[] msg) {
		if (!flag) {
			try {
				wait();
			}
			catch (InterruptedException gm_err) {
				gm_err.printStackTrace();
			}
		}
		System.out.println("<-- " + thread_id + " getting message");
		//read from local variable
		for (int i = 0; i < msg.length; i++ ) {
			msg[i] = message[i];
		}
		Arrays.fill(message, null);
		flag = false;
		notify();
	}
}

class Alice implements Runnable {
	RSACommunication local;
	
	private String t_name = "Alice";                 		//thread name
		
	private BigInteger[] privateKey = new BigInteger[2];	//alice's private key
	private BigInteger[] alicesKey  = new BigInteger[2];	//alice's public key
	private BigInteger[] bobsKey    = new BigInteger[2];	//bob's public key
	private String sessionKey       = null;					//random session key generated by Alice
	
	private String nonce          = null;               	//random nonce generated by Alice
	private BigInteger message    = null;					//session key + nonce
	private BigInteger signature  = null;					//signed (session key + nonce)
	private BigInteger[] cipher   = new BigInteger[2];		//encrypted msg to be sent (index[0]= message, index[1]= signature)
	
	//for aes encryption / decryption
	private String keyHash 					= null;
	private BigInteger[] encryptedMessage 	= new BigInteger[1];
	private BigInteger finalresult			= null;
	
	//Alice constructor
	public Alice(RSACommunication shared, BigInteger[] keys) {
		//assign key values (public key= (n, e) , private key= (n, d)
		alicesKey[0] = privateKey[0] = keys[0];		//n
		alicesKey[1] = keys[1];						//e
		privateKey[1] = keys[2];					//d
		this.local = shared;						//common RSACommunication object between Alice and Bob
		new Thread(this, t_name).start();
	}
	
	public void run() {
		//STEP 1 -> Alice sends public key to Bob
		local.sendMessage(t_name, alicesKey);
		//put Alice to sleep //will ensure Bob will have lock for next step
		try {
			Thread.sleep(64);
		}
		catch (InterruptedException ar0_err) {
			ar0_err.printStackTrace();
		}
		//STEP 2 -> Alice reads in Bob's public key
		local.getMessage(t_name, bobsKey);
		//STEP 3 -> Alice generates session key between 10 and 99 (inclusive)
		sessionKey = generateRandom(89, 10);
		//STEP 4 -> Alice generates random nonce between 0 and 8 (inclusive)
		nonce = generateRandom(8, 0);
		//create left side of message (session key + nonce)
		message = new BigInteger(sessionKey.concat(nonce));
		//STEP 4 -> create right side of message ( signed [session key + nonce] )
		signature = encrypt(message, privateKey);
		//STEP 4 -> encrypt 'message' and 'signature' with Bob's public key
		cipher[0] = encrypt(message, bobsKey);
		cipher[1] = encrypt(signature, bobsKey);
		//STEP 4 -> send message to Bob
		local.sendMessage(t_name, cipher);
		//put Alice to sleep //will ensure Bob will have lock for next step
		//increased sleep time due to decrpytion and AES encryption being performed by Bob
		try {
			Thread.sleep(128);
		}
		catch (InterruptedException ar1_err) {
			ar1_err.printStackTrace();
		}
		//STEP 6 -> Alice reads message from Bob
		local.getMessage(t_name, encryptedMessage);
		//STEP 6 -> Alice decrypts message with session key
		try {
			keyHash = generateHash(Integer.parseInt(sessionKey));
			finalresult = aesDecrypt(encryptedMessage[0].toByteArray(), keyHash.getBytes("UTF-8"));
		}
		catch (NumberFormatException |
				NoSuchAlgorithmException |
				IllegalBlockSizeException |
				BadPaddingException |
				UnsupportedEncodingException e) {
			e.printStackTrace();
		}
		//STEP 6 -> Output result
		System.out.println("Final Result");
		System.out.println("Original nonce= (" + nonce + ") +1 = (" + finalresult.toString() + ")");
		//-- Alice thread terminates
	}
	/* method "encrypt()"
	 * NOTE: this method and 'decrypt()' are identical //declared as separate functions for clarity
	 * Will perform an RSA encryption on parameter BigInteger with the parameter key array.  The
	 * key array contains two BigInteger values which are members of either a public (n, e) or
	 * private (n, d) key.
	 * Encryption uses the following formula:
	 *    Ciphertext = p^e mod n */
	private BigInteger encrypt(BigInteger msg, BigInteger[] key) {
		return msg.modPow(key[1], key[0]);
	}
	/* method "generateRandom()"
	 * Will generate a random integer between MIN_VALUE and MAX_VALUE (inclusive). Used to generate a random
	 * session key and random nonce value. Because of the size of the numbers used for RSA encryption, numbers
	 * generated will generally be smaller than 100. */
	private String generateRandom(int MAX_VALUE, int MIN_VALUE) {
		Random rObject = new Random();
		return Integer.toString(rObject.nextInt(MAX_VALUE) + MIN_VALUE);
	}
	/* method "aesDecrypt()"
	 * Will decrypted parameter byte array with parameter key.  Assumes resulting message will be an integer. */
	private static BigInteger aesDecrypt(byte[] encrypted, byte[] key) throws IllegalBlockSizeException, BadPaddingException {
		//generate secret key
		SecretKeySpec secretKey = new SecretKeySpec(key, "AES");
		Cipher aesCipher = null;
		try {
			aesCipher = Cipher.getInstance("AES/ECB/PKCS5PADDING");
			aesCipher.init(Cipher.DECRYPT_MODE, secretKey);
		}
		catch (Exception e) {
			System.out.println("Decryption error: " + e.toString());
		}
		String decoded = new String(aesCipher.doFinal(encrypted));
		return new BigInteger(decoded);
	}
	/* method "generateHash()"
	 * Will hash the parameter integer into a 16 hex-character (128-bit) string.  Hashing scheme
	 * used is SHA-1.  Will be used as the AES key for encryption and decryption. */
	private static String generateHash(int param) throws NoSuchAlgorithmException {
		String digestChars;
		MessageDigest md;
		md = MessageDigest.getInstance("SHA1");
		md.update(Integer.toString(param).substring(0, 1).getBytes());
		byte[] digestBytes = md.digest();
		
		//convert byte array from decimal to hex
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < digestBytes.length; i++)
			sb.append(Integer.toString((digestBytes[i] & 0xff) + 0x100, 16).substring(1));
		
		//only need first 16 characters
		digestChars = sb.toString().substring(0, 16);
		return digestChars;
	}
}

class Bob implements Runnable {
	RSACommunication local;
	
	private String t_name = "Bob";                   		//thread name
	
	private BigInteger[] privateKey = new BigInteger[2];	//Bob's private key
	private BigInteger[] alicesKey  = new BigInteger[2];	//Bob's public key
	private BigInteger[] bobsKey    = new BigInteger[2];	//Alice's public key
	
	private BigInteger[] cipher  = new BigInteger[2];		//encrypted message from Alice
	private BigInteger message   = null;					//cipher[0] = session key + nonce
	private BigInteger signature = null;					//cipher[1] = Alice's signed (session key + nonce)
	
	//for AES encryption / decryption
	private String keyHash = null;
	private BigInteger[] encryptedMessage = new BigInteger[1];
	
	//Bob constructor
	public Bob(RSACommunication shared, BigInteger[] keys) {
		//assign keys (public key= (n, e) , private key= (n, d)
		bobsKey[0] = privateKey[0] = keys[0];   //n
		bobsKey[1] = keys[1];					//e
		privateKey[1] = keys[2];				//d
		this.local = shared;					//common RSACommunication object between Alice and Bob
		new Thread(this, t_name).start();
	}
	
	public void run() {
		//STEP 0 -> Bob waits for Alice's public key
		//STEP 1 -> Bob reads in Alice's public key
		local.getMessage(t_name,alicesKey);
		//STEP 2 -> Bob sends public key to Alice
		local.sendMessage(t_name, bobsKey);
		//put Bob to sleep //ensures Alice will get lock for next step
		try {
			Thread.sleep(128);
		}
		catch (InterruptedException br0_err) {
			br0_err.printStackTrace();
		}
		//Bob gets encrypted message from Alice
		local.getMessage(t_name, cipher);
		//STEP 5 -> Bob decrypts message and signature with private key
		message = decrypt(cipher[0], privateKey);
		signature = decrypt(cipher[1], privateKey);
		//STEP 5 -> Bob verifies Alice's signature with Alice's public key and increments nonce
		if (verifySignature(message, signature, alicesKey)) {
			System.out.println("<=> SIGNATURE VERIFIED");
			//nonce will always be between 0 and 8 (inclusive)
			message = message.add(BigInteger.ONE);
		}
		else
			System.out.println(" ! SIGNATURE MISMATCH !");
		
		//STEP 5 -> generate hash from key, encrypt nonce with hash
		try {
			//param is first two digits of the message (session key)
			keyHash = generateHash(Integer.parseInt(message.toString().substring(0, 1)));
			//param is last digit of the message (nonce)
			encryptedMessage[0] = aesEncrypt(message.toString().substring(2), keyHash.getBytes("UTF-8"));

		}
		catch (NumberFormatException |
				NoSuchAlgorithmException |
				UnsupportedEncodingException |
				IllegalBlockSizeException |
				BadPaddingException e) {
			e.printStackTrace();
		}
		//STEP 5 -> Bob sends Alice encrypted message (byte array) of nonce++
		local.sendMessage(t_name, encryptedMessage);
		//-- Bob thread terminates
	}
	
	/* method "aesEncrypt()"
	 * Will perform AES encrpytion on parameter String with paramater key (key is 128-bits long).  Result will
	 * be numeric and output as a BitInteger (this is done for communication over the "sendMessage()" RSACommunication method. */
	private static BigInteger aesEncrypt(String plain, byte[] key) throws UnsupportedEncodingException, IllegalBlockSizeException, BadPaddingException {
		//generate secret key
		SecretKeySpec secretKey = new SecretKeySpec(key, "AES");
		Cipher aesCipher = null;
		try {
			aesCipher = Cipher.getInstance("AES/ECB/PKCS5Padding");
			aesCipher.init(Cipher.ENCRYPT_MODE, secretKey);
		}
		catch (Exception e) {
			System.out.println("AES Encryption error: " + e.toString());
		}
		return new BigInteger(aesCipher.doFinal(plain.getBytes("UTF-8")));
	}
	/* method "generateHash()"
	 * Will generate a 16 hex-character hash (128-bit) from the parameter integer. Hash will be 
	 * used as the key for an AES encryption.  */
	private static String generateHash(int param) throws NoSuchAlgorithmException {
		String digestChars;
		MessageDigest md;
		md = MessageDigest.getInstance("SHA1");
		md.update(Integer.toString(param).substring(0, 1).getBytes());
		byte[] digestBytes = md.digest();
		
		//convert byte array from decimal to hex
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < digestBytes.length; i++)
			sb.append(Integer.toString((digestBytes[i] & 0xff) + 0x100, 16).substring(1));
		
		//only need first 16 characters
		digestChars = sb.toString().substring(0, 16);
		return digestChars;
	}
	/* method "decrypt()"
	 * NOTE: this method and 'encrypt()' are identical //declared as separate functions for clarity
	 * Will perform an RSA decryption on parameter BigInteger with the parameter key array.  The
	 * key array contains two BigInteger values which are members of either a public (n, e) or
	 * private (n, d) key.
	 * Encryption uses the following formula:
	 *    Plaintext = c^d mod n */
	private BigInteger decrypt(BigInteger msg, BigInteger[] key) {
		return msg.modPow(key[1], key[0]);
	}
	/* method "verifySignature()"
	 * Will decrypt parameter 'right' with Alice's public key.  The resulting value will
	 * be compared with parameter 'left' with a potential result of 1, 0, or -1.  Returns
	 * 'true' if values the same (compare result 0) and false for any other value.  */ 
	private boolean verifySignature(BigInteger left, BigInteger right, BigInteger[] key) {
		BigInteger result = decrypt(right, key);
		return (left.compareTo(result) == 0);
	}
}

public class RSAThreads {
	/* method "generateKeys()"
	 * Will generate the public key (n, e) and private key (n, d) for the calling object.  Will call a private
	 * helper method to generate unique primes (p and q).  The totient of n (n = p * q) will be compared to an
	 * e value (17) for gcd of 1.  If the test fails, another set of primes will be generated until the gcd
	 * test is passed.
	 * Returns an array of length 3.  Index values will be:
	 *   index[0] = n;
	 *   index[1] = e;
	 *   index[2] = d;
	 * Public and private keys can be derived from those values. */
	private static BigInteger[] generateKeys() {
		BigInteger[] keys = new BigInteger[3];
		int[] primes = null;
		
		BigInteger e = new BigInteger("17");		//coprime value (could probably also use 65537)
		BigInteger p = null;						//first prime
		BigInteger q = null;						//second prime
		BigInteger n = null;						//p * q
		BigInteger d = null;						//d*e = 1 mod totn
		BigInteger totn = null;						//totient of n [ (p - 1)*(q - 1) ]
		
		while (true) {
			//generate two unique primes
			primes = generatePrimes();
		
			//convert primes to BigIntegers
			p = new BigInteger(Integer.toString(primes[0]));
			q = new BigInteger(Integer.toString(primes[1]));
			//n = p * q
			n = new BigInteger(p.multiply(q).toString());
			//totn = (p - 1)*(q - 1)
			totn = (p.subtract(BigInteger.ONE)).multiply((q.subtract(BigInteger.ONE)));
		
			//gcd test
			if (e.gcd(totn).intValue() == 1) {
				break;
			}
		}
		//calculate mod inverse
		// d  = e^(-1) mod (n)
		d = e.modInverse(totn);
		//assign values
		keys[0] = n;
		keys[1] = e;
		keys[2] = d;
		
		return keys;
	}
	/* method "generatePrimes()"
	 * Will generate two random prime values between 19 and 101 (inclusive).  Values generated
	 * will be checked with the 'isPrime' primality test before being assigned to one of the
	 * two elements of the 'pArray'.  The second prime generated will be compared to the prime
	 * stored in pArray[0] to ensure unique primes are generated. Could probably generate larger
	 * values, but small values used to prevent overflow. */
	private static int[] generatePrimes() {		
		int[] pArray = {0,0};
		Random rObject = new Random();
		int temp = rObject.nextInt(82) + 19;
		
		while (true) {
			//continually generates a number until a prime is generated
			while (!isPrime(temp))
				temp = rObject.nextInt(82) + 19;

			if (pArray[0] <= 0) //assign value to p
				pArray[0] = temp;
			else {
				//check if new prime is equal to the first prime stored				
				if (temp != pArray[0] && temp > 1) {
					pArray[1] = temp;
					break;
				}
			}
			temp = 0;
		}
		return pArray;
	}
	/* method "isPrime()"
	 * Primality helper method for "generatePrimes" method. Will check if parameter integer is
	 * prime or not and will return a boolean result. */
	private static boolean isPrime(int param) {
		if (param <= 3 || param % 2 == 0) 
			return param == 2 || param == 3; //returns 'false' if param is <= 1 and 'true' if param is 2 or 3
	    int divisor = 3;
	    while ((divisor <= Math.sqrt(param)) && (param % divisor != 0)) 
	    	divisor += 2; //iterates through all possible divisors
	    return param % divisor != 0;
	}
	
	public static void main(String[] args) {
		//instantiate a RSACommunication object though which Alice and Bob will synchronize their communication
		RSACommunication commObject = new RSACommunication();
		
		new Alice(commObject, generateKeys());
		new Bob(commObject, generateKeys());
	}
}