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 <postmaster@replay.com> 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 <stdio.h> /* 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<S-1)&&(x[v]==m[v]);)v++;if(x[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>