/*********************************************************************
* 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 file.
*
* Compile:
* g++ -o baby_pgp baby_pgp.cc libgmp.a
* Invoke:
* ./baby_pgp [DesiredModulus]
* Changelog:
* 970904: Created - Paul Herman
******************************************************************/
/*******************************************************
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 // 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;
}