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:
<![CDATA[
In-reply-to: nobody@replay.com'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: <199504020216.AA00564@xs1.xs4all.nl>
Distribution:
--text follows this line--
Name withheld by request <nobody@replay.com> writes:
> 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];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<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<-------------------------------------
#!/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 <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*',<STDIN>)){$x++;
$x%=256;$y=($s[$x]+$y)%256;&S;print pack('C',$_^=$s[($s[$x]+$s[$y])%256]);}
-------------------------------------8<-------------------------------------
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<-------------------------------------
#!/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<-------------------------------------
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 < msg
begin 600 msg
MXD858'5:CQ>_5BY`8/`2EP*(D*\%KQ.3&9J0M(^J3ZGRD&FEX!2]5N@`)J6X
M0V]M:<50Z!G]!$J0IN0$U4"90Q44ST1-':8"RM#D$YO"X2S3G2G^3HC_/X&"
MD=<6W'BC$G&,32@V;&W):6-JECXV\7Y-7Q$5<(%HI#9N`QI4'G4HS63QMS"%
@/Y`6'%\PU>"M?5V!U1(;6U^:[_<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
<adam@cypherspace.org>