(thing) by hypocrite Wed Aug 08 2001 at 7:24:41
The following interesting explanation of a Diffie-Hellman key exchange, including a 2-line (!) Perl script to implement it, is from:

http://www.cypherspace.org/~adam/rsa/perl-dh.html


It is by Adam Back. (Munged email: <not eve but her partner ____> at cypherspace dot org).
Please note that I had to fudge a lot of things in it (some <pre> tags wanted to treat < as opening an HTML tag, and some didn't.) So if there's anything weird, lemme' know. (Unless I've just noded this...I have a sneaking suspicion that the Scratch Pad isn't quite WYSIWYG...in which case, I am already busily working to fix it!).

-----Beginquote----

Diffie-Hellman in 2 lines of perl

#!/usr/local/bin/perl -- -export-a-crypto-system-sig Diffie-Hellman-2-lines
($g,$e,$m)=@ARGV,$m||die"$0 gen exp mod\n";print`echo "16dio1[d2%Sa2/d0<X+d
*La1=z\U$m%0]SX$e"[$g*]\EszlXx+p|dc`

Diffie-Hellman key exchange allows two parties who have not met to exchange keys securely on an unsecure communication path. Typically D-H is used to exchange a randomly generated conventional encryption key, the rest of the exchange is then encrypted with the conventional cipher. It has been used with DES, 3DES, IDEA, RC4 though basically the approach of using D-H key exchange can be used for any conventional stream or block cipher.

PGP itself operates in a similar fashion, except that PGP uses RSA for key exchange, and IDEA as the conventional cipher.

The maths for Diffie-Hellman is quite simple.

Here is an example:

We are trying to exchange a random key for communication. Say that we will be using the RC4 stream cipher as our conventional cipher. Here's the stages in the process.

  • You advertise your public generator g, and public prime modulus m as your "public key" in the same way that you would advertise an RSA public key, you give this to anyone you wish to exchange messages with. This is no requirement for these numbers to be kept secret, all knowledge of these numbers gives is the ability to send you messages.

    You do not tell anyone what your secret exponent x is.

    You initiate a key exchange by calculating a: 

    	     x
	a = g  mod m
    and sending me the number a.

    You can use the dh perl program to do this calculation. For the sake of argument we will choose some numbers. Say that your public generator g = 3, your public prime modulus m = 10001 and your secret exponent x = 9a2e (all numbers in hex). Then you would run the perl dh program like this to calculate a: 

    % dh g x m
    You send me the following in email: 
    g = 3, m = 10001, a = c366
  • Now I choose a session key to use for RC4, using D-H key exchange I can send this to you without an eavesdropper being able to get the key.

    I do not choose a session key directly but rather choose a random number y from which I will calculate the session key.

    Say that the random y = 4c20.

    Now I calculate the session key s: 

    	     y
	s = a  mod m
    Or using the perl dh program: 
    % dh c366 4c20 10001
    So the session key s = ded4

  • In order to send you the session s key I need only calculate: 
    	     y
	b = g  mod m
    Again using the perl dh program: 
    % dh 3 4c20 10001
    So b = 6246

    I send the number b to you in email, now you can recover the session key: 

    	     x
	s = b  mod m
    So to obtain the session key, using the perl dh program you do: 
    
% dh 6246 9a2e 10001
    And sure enough out pops the session key as I calculated, s = ded4.

    Now we both have the session key and commence exchanging messages using our agreed key as the key to a symmetric cipher such as rc4.

    So now I can send you (or you can send me) rc4 messages encrypted with our negotiated session key s = ded4: 

    % cat msg | rc4 ded4 | uuencode r r | mail
    A perl (and a C version) of rc4 suitable for the above can be found here. This works because of the mathematical property that: 
    	  y           x
	 x	     y
	g   mod m = g   mod m

and
 	     x			y
	a = g  mod m,      b = g  mod m

	     y	        x
=>	s = a  mod m = b  mod m
    x and y never change hands, and yet s has changed hands. Further you can't discover my y and I can't discover your x, and an eavesdropper has neither x nor y and so cannot discover s.

Real example

You can try sending me some RC4 encrypted email, using a D-H negotiated session key.

For security (the above example is for clarity only 32 bit keys are utterly useless for security purposes) we will use 1024 bits. Here is my Diffie-Helman public key, you can have a go at negotiating a D-H key exchange and sending me some RC4 encrypted email.

I have chosen an x (which I won't be telling you this time for obvious reasons), and calculated the corresponding a as described above. Here are my D-H public key numbers: 

g = 3

m = 
de9b707d4c5a4633c0290c95ff30a605aeb7ae864ff48370f13cf01d49adb9f2
3d19a439f753ee7703cf342d87f431105c843c78ca4df639931f3458fae8a94d
1687e99a76ed99d0ba87189f42fd31ad8262c54a8cf5914ae6c28c540d714a5f
6087a171fb74f4814c6f968d72386ef356a05180c3bec7ddd5ef6fe76b0531c3

a =
56C03667F3B50335AD532D0ADCAA2897A02C0878099D8E3AAB9D80B2B5C83E2F
14C78CEE664BCE7D209E0FD8B73F7F6822FCDF6FFADE5AF2DDBB38FF3D2270CE
BBED172D7C399F47EE9F1067F1B85CCBEC8F43B721B4F9802F3EA51A8ACD1F6F
B526ECF4A56AD62B0AC17551727B6A7C7AADB9362394B410611A21A7711DCDE2
To send me some mail you will need to generate your choice of random y as described above, and then calculate the session key s: 
% dh [a] [y] [m] > s
(where [a] and [m] are the large numbers above cut and pasted in, and [y] is your large random number.) and then calculate key exchange number b: 
% dh [g] [y] [m] > b
% mail adam@cypherspace.org < b
Then you compose your mail message as file "msg" and rc4 encrypt that using s as calculated above: 
% cat msg | rc4 `cat s` | uuencode r r | mail adam@cypherspace.org
Comments, html bugs to me [contact info. as at top of node.]
-----Endquote----

I like it!