From: cman@IO.COM (Douglas Barnes)
Date: Fri, 8 Oct 93 12:56:09 PDT
To: cypherpunks@toad.com
Subject: Diffie-Helman example in g++
Message-ID: <9310081951.AA12236@illuminati.IO.COM>
MIME-Version: 1.0
Content-Type: text/plain



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;
}