#!/bin/perl -s-- -export-a-crypto-system-sig -RSA-3-lines-PERL $m=unpack(H.$w,$m."\0"x$w),$_=`echo "16do$w 2+4Oi0$d*-^1[d2%Sa 2/d0<X+d*La1=z\U$n%0]SX$k"[$m*]\EszlXx++p|dc`,s/^.|\W//g,print pack('H*',$_)while read(STDIN,$m,($w=2*$d-1+length$n&~1)/2)
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) to what we have now:
#!/bin/perl -s-- -export-a-crypto-system-sig -RSA-3-lines-PERL $m=unpack(H.$w,$m."\0"x$w),$_=`echo "16do$w 2+4Oi0$d*-^1[d2%Sa 2/d0<X+d*La1=z\U$n%0]SX$k"[$m*]\EszlXx++p|dc`,s/^.|\W//g,print pack('H*',$_)while read(STDIN,$m,($w=2*$d-1+length$n&~1)/2)
Enjoy:-)
#!/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)