// Arup Guha
// 12/6/07

// Code for CIS 3362 Homework #8 problem #11 from page 265 of the Spillman text.
import java.util.*;
import java.math.*;

public class Homework8 {
	
	public static void main(String[] args) {
	
		// Here is the setup for the problem.
		BigInteger p = new BigInteger("3061");	
		BigInteger g = new BigInteger("17");
		
		// Here is where a problem occurs. The problem asks us to
		// compute K, and that means calculating A*B, which is
		// 113*211 = 23843 in the problem.
		
		// However, this leads to the value K = 345, which is a problem
		// later because gcd(345, 3061-1) is not 1. (p=3061 for the problem.)
		
		/*** Put this back in if you want the original A times B. ***/
		BigInteger AB = new BigInteger("23843");
		
		// In order to get this scheme to work, I changed A and B so that
		// K became relatively prime to p-1. I set A=47, B=127. This was just
		// the first thing that happened to work.
		//BigInteger AB = new BigInteger("5969"); 
		
		// Now I print out K, which for this example is relatively prime to
		// p-1 = 3060.
		BigInteger K = g.modPow(AB,p);
		System.out.println("Original K = "+K);
		
		// Calculate what Alice sends to Bob.
		BigInteger a = new BigInteger("91");
		BigInteger AliceToBob = g.modPow(a.multiply(K),p);
		System.out.println("Alice sends to Bob "+AliceToBob);
		
		// And what Bob sends to Alice.
		BigInteger b = new BigInteger("11");
		BigInteger BobToAlice = g.modPow(b.multiply(K),p);
		System.out.println("Bob sends to Alice "+BobToAlice);
		
		// This is just a gut check, it's what we know ought to be the final
		// key exchanged between the two.
		System.out.println("Key should be "+g.modPow(a.multiply(b), p));
		
		// Now here is where the problem lies. In the book, they NEVER
		// specify which inverse of K should be calculated. Most would probably
		// assume mod p. But mathematically, this just doesn't make sense.
		// You want the EXPONENT to be equivalent to ab mod (p-1), NOT p.
		// Thus, to nullify the effect of K, you'd need K^(-1) mod (p-1). More
		// generally, we want K^(-1) mod (phi(p)). 
		
		// If you try mod p instead, what you'll find is that Alice and Bob
		// WILL always agree, since their exponents are equal, BUT, they won't
		// usually get g^(ab) mod p, they'll just get something else.
		// BigInteger Kinv = K.modInverse(p.subtract(BigInteger.ONE));
		
		/*** Put this back in if you want mod p instead. ***/
		BigInteger Kinv = K.modInverse(p);
		
		// Bob can calculate g^(ab) mod p now.
		BigInteger Bobexp = Kinv.multiply(b);
		System.out.println("Kinv = "+Kinv+" Bobexp = "+Bobexp);
		BigInteger ans = AliceToBob.modPow(Bobexp, p);
		System.out.println("Here is what bob gets: "+ans);
		
		// So can Alice.
		BigInteger Aliceexp = Kinv.multiply(a);
		System.out.println("Aliceexp = "+Aliceexp);
		BigInteger ans2 = BobToAlice.modPow(Aliceexp, p);
		System.out.println("Here is what alice gets: "+ans2);
	}
}