Diffie-Helman example in g++

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

Earlier, Douglas Barnes wrote:

> // Demo of mathematics for Diffie-Hellman type key exchange
[..]
> // Does anyone have a clue what good values of 'a' are in this
> // algorithm?
> 
> a = 127;

The only restriction placed on /a/ is that it be a primitive root of
/p/. To do this, you choose /a/ at random until you find the condition
(/a/, /p/-1) == 1 is satisfied. Since there are lots of primitive roots,
this shouldn't take long. I wonder though, are there any strengths in
choosing higher values of /a/?

Feel free to correct me if I'm wrong, my engineering background means
my number theory isn't as strong as it could be (but I'm working on it
:-).

Matthew.
-- 
Matthew Gream, M.Gream@uts.edu.au. "... encryption is the ultimate means of
Consent Technologies, 02-821-2043.  protection against an Orwellian state."

> The only restriction placed on /a/ is that it be a primitive root of
> /p/. To do this, you choose /a/ at random until you find the condition
> (/a/, /p/-1) == 1 is satisfied. Since there are lots of primitive roots,
> this shouldn't take long. I wonder though, are there any strengths in
> choosing higher values of /a/?
> 
> Feel free to correct me if I'm wrong, my engineering background means
> my number theory isn't as strong as it could be (but I'm working on it
> :-).
> 

a is a constant, known to all (especially to both A and B).

Doug

-- 
----------------                                             /\ 
Douglas Barnes            cman@illuminati.io.com            /  \ 
Chief Wizard         (512) 448-8950 (d), 447-7866 (v)      / () \
Illuminati Online          metaverse.io.com 7777          /______\

Earlier, Douglas Barnes wrote:

> a is a constant, known to all (especially to both A and B).

Yes, that is true, but it still must be a primitive root w.r.t p. 
Unfortunately I am not well versed enough to explain the mathematical
reasoning behind this, but in the texts I have read, they all stated
this fact.

In an implementation of D-H I did for a project once, I ensured that
these conditions were met. Some probablistic analysis showed that approx
37-38% of numbers < p are primitive roots (done by sampling primes and
testing all n < p to see if n was primitive root), so finding a primitive
root was trivial.

Matthew.
-- 
Matthew Gream, M.Gream@uts.edu.au. "... encryption is the ultimate means of
Consent Technologies, 02-821-2043.  protection against an Orwellian state."

>Earlier, Douglas Barnes wrote:

>> // Demo of mathematics for Diffie-Hellman type key exchange
>[..]
>> // Does anyone have a clue what good values of 'a' are in this
>> // algorithm?
>> 
>> a = 127;

Notation: here 'a' is the base of the D-H exponentials.

>Feel free to correct me if I'm wrong, [...]

Certainly.  ;-)

>The only restriction placed on /a/ is that it be a primitive root of
>/p/. 

D-H works, i.e. a key is agreed upon, even if 'a' is not a primitive
root mod p, but the security may be adversely affected if it is not.

If 'a' is not a primitive root, then size of the search space which
the exponentials may take will be less than maximal.  In fact, the
order of the element 'a' gives the number of such possibilities.  (The
order is the smallest power of an element that is equal to the
identity.)

>To do this, you choose /a/ at random until you find the condition
>(/a/, /p/-1) == 1 is satisfied. 

Nope.  Being relatively prime to p-1 is not even involved.  Here is
the actual condition for primitivity:

   For every prime q which divides p-1, a^((p-1)/q) != 1 (mod p)

By Fermat's Little Theorem, x^(p-1) == 1 (mod p), for all 'x'.  Now
'a' is primitive if p-1 is the smallest such number.  Since the order
of an element much divide the order of the group, if no divisor d of
p-1 is such that x^d == 1 (mod p), then p-1 must be the smallest.

Burt Kaliski, of RSA Labs, told be he picked a D-H modulus p such that
p = 2q+1, where both p and q are prime.  It took a long time to find
such a pair.  The advantage is that almost half the elements of such
a field are primitive roots.

Eric