-export-a-crypto-system-sig -RSA-3-lines-PERL

#!/bin/perl -sp0777i<X+d*lMLa^*lN%0]dsXx++lMlN/dsM0<j]dsj
$/=unpack('H*',$_);$_=`echo 16dio\U$k"SK$/SM$n\EsN0p[lN*1
lK[d2%Sa2/d0$^Ixp"|dc`;s/\W//g;$_=pack('H*',/((..)*)$/)

NOTE:  The fully commented version is below these instructions.
       I challenge you to make it shorter than it is now, and still
       function properly.


This is a perl program which implements RSA encryption and decryption, and
is small enough to use as a signature file.  To use it, save it as "rsa"
then try: 

% chmod 700 rsa
% echo "squeamish ossifrage" | rsa -k=10001 -n=1967cb529 > msg.rsa
% rsa -d -k=ac363601 -n=1967cb529 < msg.rsa

it will generate keys up to 1024 bits.  to send encrypted email with it,
try this:

% rsa -k=[e] -n=[n] | uuencode "filename" | mail -s "subject" email_addy

ex.

rsa -k=13
-n=b487306fc179f3bd5e55a9e7c5737722dc97ec4326838b67de814638214988cd
90416ff55fee783c32aacc55f2b90c073c69344f5a4d9a6fb3f90770ffe6a78084bbae3f2c
77fe14b70e0db894b063e01f91e169591ec2b5da7bf2a0427b7bd77bfa97129e9cfe10768b
919f05728e7484949bf29de83b6a9fe7f36ea2de58b5 | 
uuencode "perl-rsa-mail" | mail -s "rsa mail" jkwilli2@unity.ncsu.edu

and finally, here is the commented version:

#!/usr/local/bin/perl -s-- -export-a-crypto-system-sig
-RSA-in-3-lines-PERL
#
#         -d (decrypt) 
#      or -e (encrypt) [this is now optional ie rsa k n < in > out will
# assume -e]
#
# $k is exponent, $n is modulus; $k and $n in hex
#
# use of -s (and $w-=$d*2; below) was contributed by Jeff Friedl
# a cool perl hacker
#
# Things have got a bit more obfuscated in that last re-write
# couldn't be helped tho' we wanted the usage string and 3 lines
#
# Ken Pizzini contributed the excellent redundancy of -e, the way it works 
# is that you can still use -e if you want, it is just redundant.  
#
# $v is the digits of output per block (or it would be if I hadn't
# eliminated it to save another couple of bytes), $w is the hex digits
# per input block.
#
# If encrypting need to reduce $w so input is guaranteed to be less than
# modulus; for decrypting reduce $v to match.
#
# Adam Roach contributed a rearrangement of the $v and $w calculation 
# which shaves off 4 bytes!  Its been juggled around a bit by Ken Pizzini 
# (for precedence prob) but no-ones managed to shorten it yet.
#
#     $v=2-4*$d+($w=2*$d-1+length$n&~1);
#
# also, now its been split up into parts for the $v elimination you should
# recognize it in 2 halves scattered around in obfuscated places for
# optimal byte count reduction.  (part of it has now even moved into the
# dc
# string to save another couple of bytes, +2 for Ken)

# Encryption/decryption loop.  Data to encrypt/decrypt in $m
#
# The whole of the next lot is inside a loop, the while appears at the end
# of 4 comma separated cmds like this:
#
#  cmd1,cmd2,cmd3,cmd4 while expr;
#
# which is perfectly legal in perl.
#
# This saves 4 chars over the more conventional while(expr){cmd1;...cmd6;}
#

#
# Travis Kuhn came up with the idea that the arg decoding (used to say
# ($k,$n)=@ARGV;) could be left out entirely, if you used this syntax 
# for calling the program:
#
#   rsa [-d] -k=123 -n=567
#
# This works because, when you do -d perl sets the variable $d, and
# apparently (cool news to me), when you do: -x=exp perl sets the variable
# $x to equal expression exp.
#
# saves a whole 14 bytes!
#

#
# Turn data into equivalent hex digits in $m
#
# The ."\0"x$w is the bug fix, (it adds way too many ascii(0)s but the 
# surplus don't matter as H.$w just takes as many as required, saves space
# to not bother working out how many.
#
# This fixes a bug which manifested itself in the last block of the
# plain text if the file to encrypt was not a whole multiple of $w.
# Also it was not generally noticed as it just put ascii(0)s on the wrong 
# end of the block and most shells eat ascii(0)s silently.
#

$m=unpack(H.$w,$m."\0"x$w),

#
# Did have Ken Pizzini's awesome:
#
#  $_=`echo 16i2o\U$k\Ep|dc`,s/\W//g,
#
# which shaved of a cool 16 chars in one swoop, and enabled
# the move to 3 lines (by chucking the usage string on bad args)
#
# Also I used to have:
#
#   s/1/d*ln%lM*ln%/g,
#   s/0/d*ln%/g,
#
# a cool contribution from Hal Finney shortened this by 4 chars to:
#
#   s/1/0lM*ln%/g,
#   s/0/d*ln%/g,
#
# this was improved on even more by Chris Barker with the fiendishly
# clever:
#
#   s/./d*lM$&^*ln%/g,
#
# However, I've re-written a big chunk in dc, so Ken's, Hal's, and Chris's
# improvements have been replaced, the work of doing the binary conversion
# has been re-written in dc and incorporated into this single dc command 
# which does the binary conversion, and the modular exponentiation in one
# swoop.
#
# Since the re-write Ken, and Chris have found more shortcuts (Ken's
# solution
# was adopted in the final twist as the additional 7 bytes I found
# couldn't be
# applied as well to Chris's initially winning variation)
# 
# There was some very clever juggling (the strange looking 16i1Io and the
# first ") by Ken which finally got the last 4 bytes working.
#
# The lastest dc command:
#       "16do$w
# 2+4Oi0$d*-^1[d2%Sa2/d0<X+d*La1=z\U$n%0]SX$k"[$m*]\EszlXx++p
#
# Firstly the "s, are necessary to protect the < and also for perl5
# the second " is cunningly placed by Ken to protect $k[$m*] from being
# interpreted as an array index of @k (this doesn't happen in perl4)
#
#
# the dc does following (note that "s and \U wont be visible to dc as perl 
# will evaluate these):
#
#       "16do                   - push 16 for later on [1] 
#                               - and ask for hex output
#       $w 2+4Oi0$d*-           - part of Adam Roach's $v calculation as
# moved
#                               - into dc by ken calculates $w+2-4**$d
#                               - 0$d is written as $d can be either "1"
# or ""
#                               - also the iO sets the output base to the
#                               - same as the input base (16)
#       ^                       - calculates 16**$v (use 16 pushed [1]
# above
#                               - and raise that to the power of $v left
# on 
#                               - the stack by the above.)
#                               - this is value left on the stack for
# later [2]
#       1                       - push 1 to seed mod exp later on [3]

[d2%Sa2/d0<X+d*La1=z\U$n%0]SX$k"[$m*]\EszlXx++p

#       [d2%Sa2/d               - convert $k to binary storing the bit
#                               - (0 or 1) on stack a this reverses the
#                               - order of the bits
#
#  ..    0<X                    - if more binary bits left in $k call
#                               - X (this subroutine) recursively to 
#                               - do the next bit
#
#  ..    +                      - junk the left after converting
#                               - $k to binary (I used to have sj to junk
#                               - Ken improved that to + adding 0)
#
#  ..    d*                     - exposing the 1 we pushed [3] near the 
#                               - top to seed this:
#                               - stack = stack * stack
#
#  ..    La1=z                  - pop the next bit of $k off stack a
#                               - if it is a 1 call subroutine z above
#
#  ..    \U$n%                  - modulo $n 
#
#  ..    0                      - unfortunately we need to store a junk 
#       ]                       - digit (0 here) to feed the + required
#                               - above which eats the stack entry left
#                               - by the conversion to binary of $k
#
#  ..    SX                     - save as subroutine X (its stored on a
# stack X
#                               - S = push on stack, but that is just to
# save 
#                               - another byte)
#
#
#       $k"[$m*]\Esz            - store $k for later conversion to binary
#                               - make subroutine z, called when next
#                               - binary digit from $k is 1
#                               - \U...\E ensures all hex digits (a-f) are 
#                               - uppercase
#
#  ..    lXx                    - call the subroutine X to convert $k to
# binary
#                               - and then do the modular exponentiation
# operation
#
#       +                       - junk the extra digit again
#
#       +                       - add the 16^$v calculated as [3] above
#                               - cunning this part this was Ken's hack
# and saves
#                               - 3 bytes over doing the padding to $v*2
# bytes in 
#                               - perl.
#                               - ie if you have result a1 and $v = 2 this
# will
#                               - result in 100a1, the perl below chops
# off the 
#                               - first character (always 1) and then the
# rest
#                               - is automatically padded to $v*2 bytes...
#
#       p                       - and print result
#
# the s/^.|\W//g is necessary for GNU dc 1.00 and above due to the way it 
# outputs long lines
#  
# the ^.| bit chops off the first character as described above in the dc
# part
#
# the \W//g ensures that \ and \n chars are removed from GNU dc's output
#

$_=`echo "16do$w
2+4Oi0$d*-^1[d2%Sa2/d0<X+d*La1=z\U$n%0]SX$k"[$m*]\EszlXx++p|dc`,
s/^.|\W//g,

#
# Pad the result with leading 0's to $v digits, pack to raw data and
# output.
#
# Dov Grobgeld contributed the "0 x" it used to be "'0'x" saves one more
# byte!
#
# Dov's "0 x" is no longer here due to the hack described in the dc part
# by Ken
# which does the padding in dc rather than perl.
#
# $w is the size of the input block
#

print pack('H*',$_)

#
# Encryption/decryption loop.  Read $w/2 bytes of data to $m.
#
# this while applies to the preceding 4 comma separated commands
#
# this has now gotten very obfuscated to shave off the last half dozen
# or so bytes
#
# blocks are based on modulus size in hex digits rounded up to nearest
# even 
# length (1+length$n&~1) so that things will unpack properly
#
# Here it is:
#
#   while read(STDIN,$m,
#          ($w=2*$d-1+length$n&~1)/2)
#
# I'll break it down into parts
#

#
# read $w bytes into $m ($w is input block size and is calculated in
# place)
# 
# this bit calculates $w = 
#
#    2*$d-1
#

while read(STDIN,$m,($w=2*$d-1

#
# then round $n up to nearest multiple of 2
#

+length$n&~1)

#
# $w is in hex nibbles, we want that in bytes when reading so /2
#

/2)