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.
<![CDATA[
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://www.cypherspace.org/~adam/ 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.
<![CDATA[
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
<adam@cypherspace.org>