/*********************************************************************
 *   baby_pgp.cc -- Sample program to show how the PGP encrypt/decrypt 
 *   algorithm works.  Requires a large integer library (such as GMP) 
 *   and a class named "Integer" that supports it in the <Integer.h> file.
 *
 * Compile:
 *    g++ -o baby_pgp baby_pgp.cc libgmp.a
 * Invoke:
 *    ./baby_pgp [DesiredModulus]
 * Changelog:
 *   970904: Created - Paul Herman <a540pau@pslc.ucla.edu>
 ******************************************************************/

/*******************************************************
			BRIGHT IDEA

Say you want to encrypt a number, say, A.  (You can always
convert text to a number.)  Choose a number N, that is
greater than all the numbers you want to excrypt.  Be sure
that N = PQ, where both P and Q are prime.  This gives you
the most amout of security.

Here's what we wanna do:
    A					- the plaintext
    A^E (mod N)				- the cyphertext (is pretty random)
    (A^E)^D  =  A^(E*D)  (mod N)	- decode the cyphertext

    This works, because:
	A^(E*D) = A  (mod N)  iff  E*D = 1 (mod J(N))

where J(N) is *easily* calculable *IF* you know the factors of N.  In 
this case J(N) = (P-1)*(Q-1).  Just choose a random E (so long as E and 
J(N) have no common factors), and compute D to be the inverse of E.

So, when you give somebody your public key, just give them N, and E.  
That is all they need to encrypt the text.  To decrypt the text, you need 
the D number (keep it secret!)

Why is this secure?
    ATTACK 1)	Reverse the encryption by computing the "Eth root" of A^E  
		(mod N). This isn't easy.  From what I can tell this is
		equivalent to factoring N, but don't quote me on that.

    ATTACK 2)	Decrypt by computing D.  This is also difficult, because 
		to find the inverse of E (mod J(N)) you need J(N).  J(N) 
		can be computed many ways, but without knowing P and Q, 
		it takes a long time (the larger the N, the better)

Other than that, I assume :-P that other attack methods take a while as 
well.  OK, here is the code.

********************* BEGIN CODE *********************************/

#include <Integer.h>		// This is important

void do_pgp(Integer n, Integer e, Integer d) {
	Integer a, encrypted, decrypted;

	for (;;) {
		cout << "Enter a number to encode (0 to exit): " << flush;
		cin >> a;	// MUST be less that n
		if (a == 0) break;

		// ENCRYPT NUMBER
		encrypted = PowModN(a, e, n);
		cout << a << " ==> " << encrypted << " ==> " << flush;

		// DECRYPT NUMBER
		decrypted = PowModN(encrypted, d, n);
		cout << decrypted << endl;
		}
	return;
}

int main(int argc, char **argv) {
	Integer n, p, q, pub, sec, jn;
	char *c;
	int opt_count = 0, ccount;

	// PARSE ARGUMENTS
	if (argc > 2) {
		cerr << "Usage: " << argv[0] << " [desired modulus]" << endl;
		return -1; }
	if (argc < 2) {
		cout << "Enter any positive number, n: " << flush;
		cin >> n; }
	else n = argv[1];

	// NOW, CHOOSE A NUMBER SLIGHTLY BIGGER THAN YOURS
	// THAT IS ONLY A PRODUCT OF 2 PRIMES
	p = nextprime( sqrt(n) ); cout << "..." << flush;
	q = nextprime(p);
	n = p*q;

	// CALCULATE J(n)
//	jn = euler(n);		// the very LONG way
	jn = (p-1)*(q-1);	// faster because I know p and q

	cout << "Hang on... choosing exponents..." << flush;

	// CALCULATE E AND D, THE TWO EXPONENTS
	do {
		pub = random(jn);
		if (pub == 0) continue;
		} while (gcd(pub, jn) != 1);	// must have an inverse

	sec = InvModN(pub, jn);	// calculate d, the inverse of e mod J(n)

	// REPORT WHAT I FOUND
	cout << endl << "N = " << n << " = " << p << " * " << q << endl;
	cout << "J(N) = " << jn << endl;
	cout << "E = " << pub << ",  D = " << sec << endl;

	do_pgp(n, pub, sec);

	return 0;
}