The previous version (as featured on many
T-shirts, and one
tattoo), and its explanation have been retained
here
Hall of fame:
- Ken Pizzini
<ken@halcyon.com>
lopped a cool 20 bytes off + 4 + 2 +2 = 28!
- using dc to convert $k to binary
- +4 for skipping one of the modulus ops in the new dc code
- +2 for some clever juggling to eliminate spaces
- plus contribution of beautiful -e redundancy stuff for
new usage string
- movement of usage string to length$n||die...
- I kind of lost track of byte count accounting in shortening
my last re-write (last shortenings were a joint effort - me & Ken)
but suffice it to say, as far as perl & dc (he *wrote*
GNU dc
you know?) hacking goes: Ken rules!
- Ken also contributed some bytes in the last rewrite started
by Jay Lorch
- Jay Lorch
<lorch@cs.berkeley.edu>
just blew away the works after many months of stagnation...
- found 5 bytes by making use of x^0 = 1 to replace a conditional
in the dc code
- then (major contrib this one) another 4 bytes by changing the
way that the program splits up stdin into blocks just less
than N, the RSA modulus. He uses base-N (ie base RSA
modulus) instead of expanding to nearest whole byte as the
previous version did. This allows the splitting into blocks
to be done in dc. It also enabled a whole string of further
optimisations which Jay, Ken (Pizzini) and myself spent a few
enjoyable days discovering.
- Joey Hess
<joey@kitenet.net>
greatly improved the accuracy of the three lines of perl claim
- with his contribution of using -i and the string $^I within the
program. This enabled the move to a true 3 lines including the
#!/bin/perl!!
- Travis Kuhn
<trav@clark.edu>
knocked off another 14 bytes
- by eliminating ($k,$n)=@ARGV;
- months after every one else had run out of steam, and when I had
long given up hope of finding more savings!
- Chris Barker
<barker@ling.rochester.edu> shaved off 8 bytes
- with a fiendishly clever improvment over hal's s///
improvement
- Chris was winning for the greatest dc code until the last twist
with another 4 byte optimisation of mine which worked out better
on Ken's version. Chris's was previously one byte short than Kens's
-
<jfriedl@omron.co.jp> shaved off 8 bytes
- use of -s and cunning $w-=2*$d parts
- Adam Roach
<exuadam@exu.ericsson.se>
shaved off 4 more!
- with a clever manipulation of the $v and $w
calcuations
- plus some clever dc stuff which led to his discovery of a
compatibility problem
- Hal Finney
<hal@rain.org> shaved off 4 bytes
- clever optimisation of s/// expressions
- Tom Phoenix
<rootbeer@teleport.com> shaved off another 2 bytes
- replacement of "H$v" with H.$v in
2 occurences
- Dov Grobgeld
<dov@orbotech.co.il>
- shaved off another byte '0'x becomes 0 x
- Volker Hetzer
<volker.hetzer@informatik.tu-chemnitz.de> found a related
HTML bug.
If you see any way to shorten the above please contact me:
Adam Back <adam@cypherspace.org>
Please note
compatibility problems with dc command P.
(If you are wondering how the above savings add up and why the script
doesn't have negative size by now it's because I have rewritten it
(yet again) and a couple of them are no longer used. The new code
uses dc to do just about everything except packing/unpacking the file,
and converting to hex. The re-write saved another 7 bytes, as well as
making the code about 4 times faster for old versions of dc and about
the same speed for the newest GNU dc-1.03). Ken Pizzini, Chris Barker
and Adam Roach all found some more optimisations on top of this. And
then I found another 4 and Ken another 2, and so it goes on. Since
that I re-wrote part of it again to fix a bug, which made it over 3
lines, slowly shortened that back to 3 lines (joint effort with Ken).
Some months later, Jay Lorch found a 5 byte saving, and then a
different way of blocking and unblocking to less than N the RSA
modulus. The reorganisation and further compression with Jay's new
RSA blocking method lead to a whole string of further optimisations by
Jay, Ken and myself. Joey Hess's suggestion of using -i was also
adopted which greatly improved the appearance, allowing perl (well dc)
code to be placed after the #!/bin/perl.
#!/bin/perl -sp0777i
The commented version
This used to be based on
Hal Finney's reply to
my original post
on the
cypherpunks list.
However it has undergone so many revisions that little remains of the
original.
Enjoy:-)
#!/bin/perl -sp0777i msg.rsa
# rsa -d -k=private-key -n=rsa-modulus < msg.rsa > msg.out
#
# some time ago Ken made -e redundant, by altering some perl
# expressions (and saving some bytes at the same time) which made -e
# (encrypt) the default behaviour:
#
# rsa -k=public-key -n=rsa-modulus < msg > msg.rsa
# rsa -d -k=private-key -n=rsa-modulus < msg.rsa > msg.out
#
# now, both -d and -e are redundant! Encrypt and decrypt are the
# same operation just with a different key with Jay's blocking method,
# so the usage is now:
#
# rsa -k=public-key -n=rsa-modulus < msg > msg.rsa
# rsa -k=private-key -n=rsa-modulus < msg.rsa > msg.out
#
# amusingly both versions have backwards compatible usage! (Earlier versions
# did not use Travis Kuhn's hack (of omitting @ARGV=($k,$n), and using -x=exp
# trick instead), and backwards compatibility was lost at that stage with
# those old versions)
#
# also note that Jay's blocking method even though the usage is
# backwards compatible, the encryted code is not, and they can not be
# used to decrypt files encrypted with the other.
#
#!/bin/perl -sp0777i
# (where <> is a synonym for which means read from pseudo file ARGV,
# the file after the flags or if there is no file, standard input.) because
# the -p does this automatically
$/=unpack('H*',$_);
# you will recall that we have given the -p flag, and the -0777 flag;
# those two flags in combination ensure that $_ holds the whole of
# standard input at this point. The above statement therefore
# converts standard input into hex, and stores this in the variable
# $/. The (re)use of $/ rather than using a normal, variable such as
# $m (for message) was a nifty hack to save one byte by Jay! (Note
# that the re-use is safe, the perl meaning for $/ is no longer
# required as the program has already done all the input it is going
# to: it has read the entire standard input into $_) The reason that
# this saves a byte is that you can place $/ next to an alphanumeric
# in a perl expression without the following alphanumeric being
# considered part of the variable name. This saves a space here:
#
# ...16dio\U$k"SK$m SM$n...
# ^
# ...16dio\U$k"SK$/SM$n...
#
# because $mSM makes perl interpret that as a variable named mSM,
# ie as ${mSM}!
$_=`echo 16dio\U$k"SK$/SM$n\EsN0p[lN*1
lK[d2%Sa2/d0$^Ixp"|dc`;
# next a string is piped to dc (the string $^I is replaced with the
# string of dc commands coming after the -i on the #! line as
# explained above.
#
# expanding the $^I, the string passed in to dc is in full:
#
# 16dio\U$k"SK$/SM$n\EsN0p[lN*1
# lK[d2%Sa2/d0
Comments, html bugs to me
(Adam Back) at
<adam@cypherspace.org>