// Arup Guha
// 6/26/06
// This program illustrates the steps in the Diffie-Hellman Key Exchange
import java.util.*;

public class DiffieHellman {
		
	public static void main(String args[]) {
		
		Scanner stdin = new Scanner(System.in);
		int p=2;
		
		// Get a prime number from the user.
		boolean done = false;
		while (!done) {
		
			System.out.println("Enter a number you want to use for p in the Diffie-Hellman key exchange.");
			p = stdin.nextInt();
			if (prime(p)) {
				System.out.println("Great, your choice "+p+" is prime and will be your p.");
				done = true;
			}
			else
				System.out.println("Sorry that number isn't prime.");
		}
		
		// Get the base for exponentiation from the user.
		System.out.println("Now, enter a number in between 2 and p-1.");
		int g = stdin.nextInt();
		
		// Get A's secret number.
		System.out.println("Person A: enter your secret number now.");
		int a = stdin.nextInt();
		
		// Make A's calculation.
		int resulta = modPow(g,a,p);
		
		// This is the value that will get sent from A to B.
		// This value does NOT compromise the value of a easily.
		System.out.println("Person A sends to person B "+resulta+".");
		
		// Get B's secret number.
		System.out.println("Person B: enter your secret number now.");
		int b = stdin.nextInt();
		
		// Make B's calculation.
		int resultb = modPow(g,b,p);
		
		// This is the value that will get sent from B to A.
		// This value does NOT compromise the value of b easily.
		System.out.println("Person B sends to person A "+resultb+".");
		
		// Once A and B receive their values, they make their new calculations.
		// This involved getting their new numbers and raising them to the 
		// same power as before, their secret number.
		int KeyACalculates = modPow(resultb,a,p);
		int KeyBCalculates = modPow(resulta,b,p);
		
		// Print out the Key A calculates.
		System.out.println("A takes "+resultb+" raises it to the power "+a+" mod "+p);
		System.out.println("The Key A calculates is "+KeyACalculates+".");
		
		// Print out the Key B calculates.
		System.out.println("B takes "+resulta+" raises it to the power "+b+" mod "+p);
		System.out.println("The Key B calculates is "+KeyBCalculates+".");
		
	}
	
	// A relatively slow way to determine if p is prime or not.
	public static boolean prime(int p) {
		
		for (int i=2; i<=Math.sqrt(p)+1; i++)
			if (p%i == 0)
				return false;
		return true;
	}
	
	
	// A relatively slow way to do modular exponentiation.	
	public static int modPow(int base, int exponent, int modulus) {
		
		int ans = 1;
		for (int i=0; i<exponent; i++)
			ans = (ans*base)%modulus;
		return ans;
	}
	
	// A faster way to do modular exponentiation
	public static int modPowRec(int base, int exponent, int modulus) {
		
		if (exponent == 0)
			return 1;
		if (exponent == 1)
			return base%modulus;
		if (exponent%2 == 0) {
			int temp = modPow(base, exponent/2, modulus);
			return (temp*temp)%modulus;
		}
		else
			return (base*modPow(base, exponent-1, modulus))%modulus;
	}
}