Here is a little demo using the big Integer routines from libg++ illustrating how Diffie-Hellman key exchange works. Basically, I wanted to prove to myself that it works, and thought others might appreciate it. Doug =============================================================== // Demo of mathematics for Diffie-Hellman type key exchange // // Useful to convince oneself that it really does work and that // a patent on it is pretty silly. // // Douglas Barnes (cman@io.com) // // Based on algorithm from Cryptography and Data Security, by Dorothy E. // Denning, 1983, Addison-Wesley. // // Note: you will need to have GNU libg++, or hack it to use big integer // math you do have. #include <stdlib.h> #include <time.h> #include <sys/types.h> #include "Integer.h" Integer& RandBigInt(int bits); Integer& FastExp(Integer& A, Integer& B, Integer& p); #define keysize 644 main() { Integer p; Integer a; Integer XA, XB, K1, KA, KB, YA, YB, T; char state[256]; pow(2, keysize, p); p = p - 1; // Does anyone have a clue what good values of 'a' are in this // algorithm? a = 127; // Set up random stuff initstate(time(0), state, 256); cout << "A and B pick random numbers in the Galois field [0, p - 1]\n"; cout << "where p is (2^" << keysize << ") - 1:\n" << p << "\n"; XA = RandBigInt(keysize); cout << "\nA picks a random secret XA: \n" << XA << "\n"; XB = RandBigInt(keysize); cout << "\nB picks a random secret XB: \n" << XB << "\n"; YA = FastExp(a, XA, p); YB = FastExp(a, XB, p); cout << "\nA gives B a message YA (a^XA mod p): \n" << YA << "\n"; cout << "\nB gives A a message YB (a^XB mod p): \n" << YB << "\n"; KA = FastExp(YB, XA, p); cout << "\nA now knows the key is (YB^XA mod p): \n" << KA << "\n"; KB = FastExp(YA, XB, p); cout << "\nB now knows the key is (YA^XB mod p): \n" << KB << "\n"; cout << "\nComputing the key (which is a^XA^XB mod p) from (a^XA mod p) and\n"; cout << "(a^XB mod p) is equivalent to performing two discrete log calculations;\n"; cout << "the number of steps to perform discrete logs grows exponentially\n"; cout << "in proportion to the # of bits in the field. For a 'p' of 644 bits,\n"; cout << "Denning estimates 1.2 x 10^23 steps.\n"; } // Calculate a^z mod n // // Based on the fact that (a^3 mod n) is the same thing // as: (((a * a) mod n) * a) mod n // // Gets its speed from the fact that, for example, n^18 is the // same as (n^2)^9 Integer& FastExp(Integer& a, Integer& z, Integer& n) { Integer a1, z1, two; static Integer x; a1 = a; z1 = z; x = 1; two = 2; while(z1 != 0) { while((z1 % 2) == 0) { div(z1, two, z1); a1 = (a1 * a1) % n; } z1 = z1 - 1; x = (x * a1) % n; } return x; } // Yes, I know the random stuff is lame. This is a demo. Integer& RandBigInt(int bits) { int i; int randval; static Integer retval; retval = 0; for(i = 0; i<bits; i++) { retval |= (random()&01); lshift(retval, 1, retval); } return retval; }