Diffie-Hellman Key Exchange
This 10 line C program was written by an anonymous poster to
sci.crypt. Possibly the poster is located in the US, though there is
no way of telling. Anyway nobody's code includes a beautifully
compacted big num implementation, so all you need is a C compiler.
If you are trying this out with the example nobody gives in his
message you should note that you must change the initialisation of
S=129 on the first line to be S=3 (size of key in bytes + 1) - nobody
says this in the text, it just caught me out first time.
I posted a follow up
to this message to sci.crypt in which I mail dropped nobody a message
using the 1024 bit Diffie-Hellman key exchange he/she initiated. This
message includes the Diffie-Hellman in perl I wrote (it's very similar
to RSA in it's use of modular exponentiation) inspired by nobody's code.
My
perl-diffie-hellman
plus examples of use (inspired by nobody's C code)
Here is nobody's posting to sci.crypt (it was cross posted to
talk.politics.crypto and alt.anonymous.messages also):
Newsgroups: sci.crypt,talk.politics.crypto,alt.anonymous.messages
From: nobody@replay.com (Name withheld by request)
Organization: Replay and Company UnLimited.
X-Warning: This message was forwarded by an Anonymous Remailer.
X-Comment: Replay does not necessarily approve of the contents of this posting.
X-Comment: Please report inappropriate use to
Subject: Export-a-crypto-system: Diffie-Hellman
X-Posting-Host: xs1.xs4all.nl
Date: Sun, 2 Apr 1995 02:25:08 +0000
Sender: usenet@demon.co.uk
Lines: 88
Inspired by Adam Back's RSA code...
The export-a-crypto-system sig II - Diffie-Hellman in 10 lines of C:
#include /* Usage: dh base exponent modulus */
typedef unsigned char u;u m[1024],g[1024],e[1024],b[1024];int n,v,d,z,S=129;a(
u *x,u *y,int o){d=0;for(v=S;v--;){d+=x[v]+y[v]*o;x[v]=d;d=d>>8;}}s(u *x){for(
v=0;(v=m[v])a(x,m,-1);}r(u *x){d=0;for(v=0;v<
S;){d|=x[v];x[v++]=d/2;d=(d&1)<<8;}}M(u *x,u *y){u X[1024],Y[1024];bcopy(x,X,S
);bcopy(y,Y,S);bzero(x,S);for(z=S*8;z--;){if(X[S-1]&1){a(x,Y,1);s(x);}r(X);a(Y
,Y,1);s(Y);}}h(char *x,u *y){bzero(y,S);for(n=0;x[n]>0;n++){for(z=4;z--;)a(y,y
,1);x[n]|=32;y[S-1]|=x[n]-48-(x[n]>96)*39;}}p(u *x){for(n=0;!x[n];)n++;for(;n<
S;n++)printf("%c%c",48+x[n]/16+(x[n]>159)*7,48+(x[n]&15)+7*((x[n]&15)>9));
printf("\n");}main(int c,char **v){h(v[1],g);h(v[2],e);h(v[3],m);bzero(b,S);b[
S-1]=1;for(n=S*8;n--;){if(e[S-1]&1)M(b,g);M(g,g);r(e);}p(b);}
To compile it, type: gcc dh.c -o dh
The program is somewhat slow, but it works, and it's almost small enough to
attach to your posts as a signature. It's set up for 1024-bit numbers, but
you can allow bigger numbers by setting the value of the S variable. To
allow for carry digits, the value set for S must be one greater than the
maximum length in bytes of the modulus that you wish to use. The time to
calculate a modular exponent is roughly proportional to the cube of the
number of bits, so if a 1024-bit number takes 5 minutes, a 2048-bit number
will take 40 minutes, and a 4096-bit number would take about 5 hours.
All numbers are entered and printed in hexadecimal. Because of the minimal
size, the program doesn't check for human error; it may do strange things
if you give it bad data.
For example purposes, the numbers used below are small, any practical
use would require numbers of 512-1024 bits in length.
To generate a key, Joe selects a public generator (3 in this example), a
public prime modulus (10001 hexadecimal), and a secret exponent (9A2E hex).
Joe then calculates the following:
joe% dh 3 9A2E 10001
C366
This is his public key. Joe sends these three numbers (3,10001,C366)
to Alice.
To encrypt a message to Joe, Alice picks a secret random number (4C20 in
this example) and using Joe's generator and modulus, calculates:
alice% dh 3 4C20 10001
6246
She sends this result to Joe. Alice then takes Joe's public key and her
secret random number and calculates:
alice% dh C366 4C20 10001
DED4
She uses this result as a session key to encrypt her message to Joe.
To decrypt the message, Joe uses the number Alice sent him, and his
secret key to calculate:
joe% dh 6246 9A2E 10001
DED4
Joe now has the session key and can decrypt Alice's message.
An eavesdropper sees Joe send Alice three numbers (3,10001,C366), and
sees Alice send Joe '6246'. But the eavesdropper can not use these
numbers to calculate the secret session key (DED4), and thus can not
decrypt the message.
You can use this program to do RSA also, but generating a key is more
difficult.
I wonder if the USA ITAR law covers integer math programs?
Here is my key:
g=2
X=28D4FEFED5CC1ACDBE7D550813A1518DB56812855014EFDDD9E038A15BE52FD524D6FFA9C9E3
1E59DDFEF705EAB75DD031908F10B584F5A2495BC2C1433ACB6FA065FB0850ECCF139993BA4564
B97A289FBCD59524FC30F377060366077378288F93173AC508D1DC5B4D9DAE0AFECFFA9E5494C5
3EED74C4E29DEBAF0C08B720
m=DE9B707D4C5A4633C0290C95FF30A605AEB7AE864FF48370F13CF01D49ADB9F23D19A439F753
EE7703CF342D87F431105C843C78CA4DF639931F3458FAE8A94D1687E99A76ED99D0BA87189F42
FD31AD8262C54A8CF5914AE6C28C540D714A5F6087A171FB74F4814C6F968D72386EF356A05180
C3BEC7DDD5EF6FE76B0531C3
Comments, html bugs to me
(Adam Back) at
<adam@cypherspace.org>