Original version

The original post to the cypherpunks list, followed by Hal Finney's reply where he picks the program apart and explains how it works.
Date: 9 Mar 1995 04:06:20 -0500 From: aba@atlas.ex.ac.uk To: cypherpunks@toad.com Subject: perl hackery, export-a-crypt-system Heres a bit of perl code which implements RSA encryption and decryption and is small enough to use for a signature: -------------------------------------8<------------------------------------- #!/usr/local/bin/perl -- export-a-crypto-system sig, RSA in 5 lines of PERL: ($s,$k,$n)=@ARGV;$w=length$n;$k="0$k"if length($k)&1;$n="0$n",$w++if$w&1;die "$0 -d|-e key mod <in >out\n"if$s!~/^-[de]$/||$#ARGV<2;$v=$w;$s=~/d/?$v-=2: $w-=2;$_=unpack('B*',pack('H*',$k));s/^0*//g;s/0/d*ln%/g;s/1/d*ln%lm*ln%/g; $c="1${_}p";while(read(STDIN,$m,$w/2)){$m=unpack("H$w",$m);chop($a= `echo 16o16i\U$m\Esm\U$n\Esn$c|dc`);print pack('H*','0'x($v-length$a).$a);} -------------------------------------8<------------------------------------- It has usable speed even for 512 bit keys, though its not as fast as PGP. It uses repeated modulus on exponentiation to achieve usable performance, you could probably make it a line shorter without this optimisation. It uses dc for bignums (you should be able to spot the `echo blah|dc` on the last line). Heres a few keys you can try out 8bits: e=11 d=ac1 n=ca1 32 bits: e=10001 d=ac363601 n=1967cb529 128 bits: e=10001 d=135b03530e94874283f0f0000ffff0001 n=24000c6c9620886831124848640044901 512 bits: e=10001 d=62a03c0df0b96335047a12923a7d20bc2b7bb07c59aba2c4b094fc7d54392e8a2e7606cb5d574407640f4bb4e0ea6aeb7fff0000ffff0000ffff0000ffff0001 n=12004001208404a43f00502200b204602600c00001da894922433e4601a2c85024024001418004602404240109301008140000000142404002010000000000001 To test, just save it as file "rsa", then do: % chmod 700 rsa % echo "squeamish ossifrage" | rsa -e 11 ca1 > msg.rsa % rsa -d ac1 ca1 < msg.rsa I wonder how good your chances of getting prosecuted under ITAR for having the above as a signature as an Amerikan citizen are :-) If challenged for exporting it you could defend yourself by saying you could have written it down on a piece of paper and snail mailed it which would presumably be legal? Or read it over the phone? Another use I thought of is an auto-reply block, ie the rsa code with your public key hard-coded into it: -------------------------------------8<------------------------------------- #!/usr/local/bin/perl -- auto-encrypt-reply sig, RSA in 5 lines of perl: $n="012004001208404a43f00502200b204602600c00001da894922433e4601a2c8502402400". "1418004602404240109301008140000000142404002010000000000001";$/=0;$f=<STDIN>; $_="10000000000000001";s/0/d*ln%/g;s/1/d*ln%lm*ln%/g;$c="${_}p"; for(;$i<length$f;$i+=64){$m=unpack("H128",substr($f,$i,128));chop($a= `echo 16o16i\U$m\Esm\U$n\Esn1$c|dc`);print pack('H*','0'x(130-length$a).$a);} -------------------------------------8<------------------------------------- Any body can then encrypt a reply to you by saving and running the perl code, without needing PGP installed on their system. Suggestions on any perl hackery to further shorten the code gratefully accepted. Adam _________________________________________________________________________ email:aba@dcs.ex.ac.uk http://dcs.ex.ac.uk/~aba/ pgp-key:556A4A67

Hal Finney's reply

This post where Hal Finney picked the dense perl and dc apart and added comments explaining how it works is useful for understanding what is going on.
Date: 9 Mar 1995 12:41:47 -0500 From: hfinney@shell.portal.com (Hal) To: cypherpunks@toad.com Subject: Re: perl hackery, export-a-crypt-system aba@dcs.exeter.ac.uk writes: >Heres a bit of perl code which implements RSA encryption and >decryption and is small enough to use for a signature: This is incredible! What a beautiful hack. I am absolutely blown away. I have split your code up and added some spaces, then some comments to try to understand how it works. It is very clean and handles many subtleties nicely. # $s is -d or -e, $k is exponent, $n is modulus; $k and $n in hex ($s,$k,$n)=@ARGV # $w is number of hex digits in $n $w=length $n # Add a leading 0 to make length of $k and $n be even so they will fill # Bytes when packed as 2 digits per byte $k="0$k"if length($k)&1 $n="0$n", $w++ if $w&1 # Print usage message if $s is not -d or -e or too few arguments die "$0 -d|-e key mod <in >out\n" if $s!~/^-[de]$/ || $#ARGV<2 # $v will be the digits of output per block, $w the digits of input per block. # If encrypting need to reduce $w so input is guaranteed to be less than # modulus; for decrypting reduce $v to match. $v=$w $s=~/d/?$v-=2:$w-=2 # Make $_ be the exponent $k as a binary bit string $_=unpack('B*',pack('H*',$k)) # Strip leading 0's from $_ s/^0*//g # Turn every 0 into "d*ln%", every 1 into "d*ln%lm*ln%". These are dc codes # which construct an exponentiation algorithm for that exponent. # "d*ln%" is duplicate, square, load n, modulus; e.g. square the number # on the stack, mod n. "d*ln%lm*ln%" does this then, load m, multiply, # load n, modulus; e.g. then multiply by m mod n. This is the square and # multiply algorithm for modular exponentiation. s/0/d*ln%/g s/1/d*ln%lm*ln%/g # Put 1 at front, p at end of constructed string, put into $c # The 1 will feed the square-and-multiply, the p will print the result. $c="1${_}p" # Encryption/decryption loop. Read $w/2 bytes of data to $m. while(read(STDIN,$m,$w/2)){ # Turn data into equivalent hex digits in $m $m=unpack("H$w",$m) # Run dc: 16 bit radix for input and output; $m into dc register "m"; # $n into dc register "n"; execute $c, the exponentiation program above. # "\U...\E" forces upper case on the hex digits as dc requires. # Put the result into $a. chop($a=`echo 16o16i\U$m\Esm\U$n\Esn$c|dc`) # Pad the result with leading 0's to $v digits, pack to raw data and output. print pack('H*','0'x($v-length $a).$a) } There is a cryptographic problem with this kind of algorithm is a certain weakness against guessing plaintext. This is a "pure RSA" encryption so if the plaintext in one block is guessed it can be encrypted and compared against the cyphertext. Particularly in the last block which may be short this might be feasible. (Maybe it has a sig, making it easy to guess.) This is not a major security hole but people should be aware of it. Still I think this is a tour de force. Unfortunately I don't know perl well enough to suggest improvements. That is amazing how you are able to turn the exponent into a program to do the exponentiation just by textual manipulations. I do think this would make an excellent .sig and I hope people adopt it. Hal
Comments, html bugs to me (Adam Back) at <aba@dcs.ex.ac.uk>