/*
This is an implementation of Diffie-Hellman-Merkle key exchange.

http://en.wikipedia.org/wiki/Diffie-Hellman#Description

This is just a demonstration. A bignum library would be needed to make the
numbers large enough for this to be secure.
*/

#include <cmath>
#include <iostream>

class person
{
public:
	//g^s % p
	int g;
	int p; //needs to be prime, should generally be at least 300 digits long
	int s; //secret exponent, should generally be at least 100 digits long

	/*
	The result of when someone else does g^s % p and sends
	use their result. We do not know what s they used.
	*/
	int result_other;

	//calculates the result to send to someone else
	int calc()
	{
		//long long is big enough to hold this example only
		return (long long)pow(g, s) % p;
	}

	/*
	The key calculated by doing (result_other)^s % p, where result
	other is the result of the other person who did g^s % p with
	their secret exponent.
	*/
	int secret_key;

	//calculates the secret key
	void calc_secret()
	{
		//long long is big enough to hold this example only
		secret_key = (long long)pow(result_other, s) % p;
	}
};

int main(int argc, char * argv[])
{
	//person A wants to negotiate secure communication to B
	person A, B;


	/*
	Initial negotiation of the key exhange.
	Note: Anyone could know the agreed upon base and number to mod by.
	Public Knowledge: g, p
	*/
	A.g = 5; B.g = 5;   //both A and B decide to use the base 5
	A.p = 23; B.p = 23; //both A and B decide to mod by 23


	/*
	A and B both generate secret exponents.
	Note: No one but A knows A's secret exponent, same for B.
	*/
	A.s = 6;  //A picks 6 as its secret exponent
	B.s = 15; //B picks 15 as it's secret exponent
	

	/*
	A and B exchange info used to generate the private key
	Note: The result sent could be the result of the secret exponent being any
         one of a billion billion numbers.
	*/
	B.result_other = A.calc(); //A sends g^s % p to B
	A.result_other = B.calc(); //B sends g^s % p to A


	/*
	A and B now each calculate the secret_key they can use to encrypt their
	communications. They can both generate the same key because:
	(g^s1 % p)^s2 % p = g^(s1s2) % p = (g^s2 % p)^s1 % p
	*/
	A.calc_secret();
	B.calc_secret();


	//lets now take a peek to make sure they actually have the same secret keys
	std::cout << "A's secret key: " << A.secret_key << "\n";
	std::cout << "B's secret key: " << B.secret_key << "\n";


	/*
	This is secure because g^(s1s2) is hard for a third party to solve.
	see http://en.wikipedia.org/wiki/Discrete_logarithm_problem .
	Basically there are fast algorithms for exponentiation but no known fast
	algorithms for solving exponents with logarithms.
	*/

	return 0;
}