Reply to nobody's D-H in 10 lines of C

An anonymous person posting to sci.crypt via a cypherpunks anonymous remailmer, posted a beautifully compacted Diffie-Hellman key exchange program in 10 lines of C.

Here is my followup to sci.crypt.

Note that I have modified the post shown below to fix a bug in the perl RC4 code which was in this message when I posted it originally.

Details on using my perl version of RC4.

Details on perl version (now shorter): perl diffie-hellman.

My followup:

In-reply-to:'s message of Sun, 2 Apr 1995 02:25:08 +0000 Newsgroups: sci.crypt,talk.politics.crypto,alt.anonymous.messages Subject: Re: Export-a-crypto-system: Diffie-Hellman References: <> Distribution: --text follows this line-- Name withheld by request <> writes: > Inspired by Adam Back's RSA code... > > The export-a-crypto-system sig II - Diffie-Hellman in 10 lines of C: > > #include &lt;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&lt;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&lt;S;){d|=x[v];x[v++]=d/2;d=(d&1)&lt;&lt;8;}}M(u *x,u *y){u X[1024],Y[1024];bc\ > opy(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&lt;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);} Excellent! My RSA program has the problem that it can not generate keys, as RSA keys are more difficult to generate. I haven't got around to writing an RSA key generation program yet, I suspect it would be a fairly lengthy program. Your program nicely allows secure key exchange for conventional ciphers. A while ago I converted RSA's RC4 stream cipher which somebody reverse-engineered / leaked into perl from the original C, heres the code: -------------------------------------8&lt;------------------------------------- #!/usr/local/bin/perl -- -export-a-crypto-system-sig -RC4-in-4-lines-of-PERL (@k=unpack('C*',pack('H*',$ARGV[0])))||die"$0 key &lt;in >out\n";for(@t=0..255) {$s[$_]=$_;}for(@t){$y=($k[$i]+$s[$_]+$y)%256;$x=$_;&S;$i++;$i%=$#k+1;}$/=$x =$y=0;sub S{($s[$x],$s[$y])=($s[$y],$s[$x]);}for(unpack('C*',&lt;STDIN>)){$x++; $x%=256;$y=($s[$x]+$y)%256;&S;print pack('C',$_^=$s[($s[$x]+$s[$y])%256]);} -------------------------------------8&lt;------------------------------------- This provides a nice small convential key cipher to use with your diffie-helman key exchange program. It can usefully use keys up to 2048 bits (512 hex digits, or 256 bytes), as RC4 uses an internal table of 256 bytes for encryption which is seeded by the key you give. I also took the liberty of converting your excellent diffie-hellman program into perl and dc (this is cheating of course as dc does all the hard stuff for me, but it allows me to shorten the code by avoiding your cleverly compacted big integer code). -------------------------------------8&lt;------------------------------------- #!/usr/local/bin/perl --#export-a-crypto-system sig, Diffie-Hellman 2 lines: ($g,$e,$m)=@ARGV;$_=unpack('B*',pack('H*',1&length$e?"0$e":$e));s/^0+//; s/1/0lG*lm%/g;s/0/d*lm%/g;print `echo 16i\U$g"\nSG$m\Esm1Io$_"p|dc` -------------------------------------8&lt;------------------------------------- This is ripped straight out of perl-rsa, as you pointed out modular exponentiation is the key to both diffie-helman and rsa. We'll give this a go shall we: I've generated a 1024-bit random number, and used your DH keys to generate this (took 4 mins, 45 seconds on a 100Mhz R4600 Indy using the perl dh above): y=C8574634C0F5C36FFA746B894A917C3468E2D726453E84CAD43F5AC64EE792591F75839B8172 D4CA11F1CCE0E8D7DFBCEEA0DB9FA6AA9A27AD20B6A6DF7F531C9B3E8E32C680E51A45BA15631D 65E3B7186E71B3C0FF90894FD99785704D704E6136BD88ABD2A9C5653F40C869EE07095B04A725 5A0BBCCD636AD7B8FFA12896 (generating the session key took 6 mins 44 seconds) You can generate the RC4 session key, and then use that to decyrpt the following uuencoded message: % dh y secret m % rc4 session &lt; msg begin 600 msg MXD858'5:CQ>_5BY`8/`2EP*(D*\%KQ.3&9J0M(^J3ZGRD&FEX!2]5N@`)J6X M0V]M:&lt;50Z!G]!$J0IN0$U4"90Q44ST1-':8"RM#D$YO"X2S3G2G^3HC_/X&" MD=&lt;6W'BC$G&,32@V;&W):6-JECXV\7Y-7Q$5&lt;(%HI#9N`QI4'G4HS63QMS"% @/Y`6'%\PU>"M?5V!U1(;6U^:[_&lt;PL?Q&U2BD'S`G80IN ` end (Nobody: message is for amusement only, dont worry if the message doesnt decode its quite possible that I made a mistake cutting and pasting all of those huge integers, one slip is all it takes) The rc4 is blazing fast (0.06 secs), as compared to DH key stuff and RSA. Heres my DH key (same modulus): g=3 x=56C03667F3B50335AD532D0ADCAA2897A02C0878099D8E3AAB9D80B2B5C83E2F14C78CEE664B CE7D209E0FD8B73F7F6822FCDF6FFADE5AF2DDBB38FF3D2270CEBBED172D7C399F47EE9F1067F1 B85CCBEC8F43B721B4F9802F3EA51A8ACD1F6FB526ECF4A56AD62B0AC17551727B6A7C7AADB936 2394B410611A21A7711DCDE2 m=DE9B707D4C5A4633C0290C95FF30A605AEB7AE864FF48370F13CF01D49ADB9F23D19A439F753 EE7703CF342D87F431105C843C78CA4DF639931F3458FAE8A94D1687E99A76ED99D0BA87189F42 FD31AD8262C54A8CF5914AE6C28C540D714A5F6087A171FB74F4814C6F968D72386EF356A05180 C3BEC7DDD5EF6FE76B0531C3 This has provided me with several hours worth of amusement, as well as allowing me to brush up on my DH key-exchange, excellent stuff! Adam
Comments, html bugs to me (Adam Back) at <>