
"Perl.  The only language that looks the same before and after RSA
encryption."[*1]
	(Credited to Richard Stallman)
	Cypherpunks mailing list, 5 Oct 94

	TPJ is going to need an export-controlled FTP area...

	This pile of characters loosely called a Perl script
implements the following in 100% Pure Perl[*2]:

1.  Rot-13+ (patent pending, as soon as I can find the forms).
    This enhanced encryption algorithm features:
    * User-chosen number of encryption rounds used as the key.
      Billions of distinct keys are available.  If your Perl uses 64-bit
      integers, you can actually have more keys than DES!
    * Punctuation translation.  You've seen what it does to this script.
    * CLEAR CHANNEL option: for those times you don't want to encrypt.
      You can use this option if the recipient is unable or unwilling
      to use Rot-13+ encryption.  You can also use it to confuse spies
      who might intercept your Rot-13+ messages.  (For instance,
      the following message: "LETS ALL BE FRIENDS (attack at dawn!)"
      becomes: "LETS ALL BE FRIENDS $nggnpx ng qnja!&".  Hopefully
      any spies will dismiss the real message as line noise.)

2.  GAK (Government (or other Good Guy) Access to Keys).  The
    Rot-13+ key is escrowed in any encrypted messages so as not to
    infringe on the legitimate interests of law enforcement.

3.  RSA encryption/decryption with arbitrary-length keys, just in
    case you don't *completely* trust the new Rot-13+ algorithm.  Since it
    is possible to break RSA given either the private or public key, we do
    not feel it is necessary to escrow the RSA keys.  (See the GoodGuy
    section below if your hat color is correct.)

	***** History *****

	In March 1995, Adam Back wrote the first "RSA-Perl" program:

#!/usr/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);}

	You can see the current script (a bit shorter), and the story
behind it, at Adam Back's homepage: http://dcs.ex.ac.uk/~aba

	In December 1995, I wrote the first Pure-Perl conversion:

#!/usr/local/bin/perl5.000 -s
do 'bigint.pl';($_,$n)=@ARGV;s/^.(..)*$/0$&/;($k=unpack('B*',pack('H*',$_)))=~
s/^0*//;$x=0;$z=$n=~s/./$x=&badd(&bmul($x,16),hex$&)/ge;while(read(STDIN,$_,$w
=((2*$d-1+$z)&~1)/2)){$r=1;$_=substr($_."\0"x$w,$c=0,$w);s/.|\n/$c=&badd(&bmul
($c,256),ord$&)/ge;$_=$k;s/./$r=&bmod(&bmul($r,$r),$x),$&?$r=&bmod(&bmul($r,$c
),$x):0,""/ge;($r,$t)=&bdiv($r,256),$_=pack(C,$t).$_ while$w--+1-2*$d;print}

...and sent it to Adam Back.  (I did not want my name on the script at
the time, and requested that he remove my name from any repostings.)
In the email to Adam I also said: "I *might* be able to cut about 5
characters from the version above, but only at a huge readability cost."

	Consider this script "a huge readability cost".

	***** Code Walkthrough[*3] *****

#####Line 0 (script line):
#!/usr/bin/perl -s0777
# Use -s for switch processing, 0777 is same as undef $/; (save 4 chars)

#####Line 1:
$_=<<'',
# The solution to Backslash Hell.  Far better than regular $_='....';
# No quoting problems, and interesting control flow.  Also, it makes
# this script a 1-line program (with a few lines of data).
s'3'(q))(e))l]'g,
# When run through rot-13+, this gives $d&&$r&&y4
# This saves 3 chars directly, and must be done before the next subst.
s']'|a-mn-z($)&|n-za-m$(&)|;'g,
# The translation table for rot-13+.  Placed into code 3 times.
# Why not a-z?  Short answer: because n-m is not an interesting range.
s'`'/g,s/'g,
# Above is the unnamable ritual which saved this code.  (It also makes
# a neat sequence of g,s chars.)  Replace the backtick with the common
# sequence between a series of subsitutions.  Costs 12 chars, but it
# pays for itself with 3 uses.  (saved 12 chars.)
# Using / makes other code seem normal until you match the / chars...
s/./$'/ee
# Eval $_, except for the first character.  Pure obfuscation, costing
# a few chars.  (I could just eval, and remove the comment on line 2).
# The newline after ee is the last character in the script (control-flow),
# so we don't need a semicolon.

#####Line 2:
#y]
# Translate $_ using the translation table (which includes the ;)
s/\n#/
# One nice(?) thing about the unnamable ritual is that it makes it hard
# to split statements.  The line above removes all but the first
# newline/comment character pair.  ($_ becomes one long line)
`#/d(&bmul(\$
# A big saver: used 4 times, yielding 19 chars savings.
`%/s-.|\\n-
# Save some on substitutions.  Most uses don't require |\\n, but tolerate it.
# The extra backslash makes sure the debugger will get the payload as
# one big line.
`\//-ge;
# As above, but for end of substitutions.  Semicolon elimination also.
`@(.)/;\$$1=
# Replace all @v with ;$v= which makes many variables seem like arrays.
# Several places tolerate the semicolon (saving only one character)
`4/pack("
# Saves 4 characters, and eliminates a warning from -w
# Note: there was one more sequence which would save 3 chars, but it would
# have required either a long line (over 80 chars), or a newline.
`$"/$'/ee 
# Replace the first $" (space) with the result of the payload's execution.
# The payload starts after the space at the end of *this* line.
# After this substitution, the rest of the the current eval is just
# a series of rot-13+ encoded comments.

#####Lines 3-7:
# The payload (a suitable name for a munitions component),
# after rot-13+ decryption and decompression.
# If you copy line 0 (the script line), and the lines below to a file,
# the resulting script has all the functionality of the submitted script.
$r&=1;
# Optimize n-round rot-13+ (r=num of rounds).
# Don't tell Marketing--they would only get upset.
$_="0$k";
# Copy key, need 0 in front for search below (to deal with
# an odd number of hex digits in the key)
# This could be changed to $_=$k if users could be trusted to type a
# leading 0 for odd-length keys.
$*=0;
# Unfortunately, the bigint library doesn't treat undefines as 0
($k=unpack("B*",pack("H*",m,((..)*$),)))=~s-^0*--ge;
# Pack the key into an 8-bit string, then unpack the 8-bit to an ASCII
# binary representation ("101001"), then remove all leading zeros, and
# finally assign back to $k.  Yes, I need all these parenthesis.
# The m, wastes a character, but lets me use the / wrapper subst.
# The final "ge" is tolerated, but the real reason is to let me use the
# search-ending substitution, which saves 1 character (the ;)
do 'bigint.pl';
# Just a little help from the standard library.
# The space is required for perl 4.036.
# (Perl 4 *almost* runs this script.  Perl 4 seems to work better under
#  the debugger--I've managed to get 1 block en/decrypted.)
$"=$n=~s-.|\n-;$*=&badd(&bmul($*,16),hex$&)-ge;
# Translate the hex modulus into a decimal bigint
# $" is the number of hex characters, needed below
;$:=($d*2-1+$")>>1;$;=7x(1-$d*2+$:);
# Set the input block size ($:) and output block size ($;)
# We'll take the output size as an n-character string (of "7" chars)
# This is where you (might) crash when you don't use arguments, since it
# tries to get 2,000,000,000 (and a few) bytes if $" is less than 1
# (On my Linux box I get a Segmentation Fault and a core dump.)
$_=<>."\0"x($:-1);
# Add padding to the input, just enough for no padding-only blocks
!$d&&$r&&y|n-za-m$(&)|a-mn-z($)&|;
# If not decrypting (thus encrypting), apply the powerful Rot-13+ algorithm
$d?s-.|\n-$g?$r=$&:0,""-e:print$r;
# Don't look at the above line unless you are wearing the white hat.
# Even if you are a good guy, you don't need to know how this works.
# Trust us.  We're the Good Guys.
s!(.|\n){$:}!
# The main loop. For all $: size blocks...
  ;$_=$&;$,=1;$"=0;
# Save the block (too bad we can't modify $& :-)
# init result ($,) and cypher-or-clear text ($")
  s-.|\n-;$"=&badd(&bmul($",256),ord$&)-ge;
# Set cypher-or-clear bigint to representation of input.
  ;$_=$k;
# Copy the key for the next step
  s-.|\n-;$,=&bmod(&bmul($,,$,),$*),$&?$,=&bmod(&bmul($,,$"),$*):9,""-ge;
# Do RSA.  (Modular exponentiation)  Also clears $_
  ;$;=~s-.|\n-($,,$")=&bdiv($,,256);$_=pack("C",$").$_,5-ge;
# Pack result ($,) back into characters for output
  $d&&$r&&y|n-za-m$(&)|a-mn-z($)&|;
# If not encrypting (thus decrypting), apply the powerful Rot-13+ algorithm
  print
# Output the result for the world to see
!ge
# end of loop, and end of payload, but not end of code...

#####Line 8:

#Not too exciting, but the blank line above is required by the wrapper.

	***** USAGE *****

	Usage is the same as the modern 3-line Perl-DC-RSA script,
with the addition of the -r switch.

Encrypt:
gak [-r[=<N>]] -k=<KEY> -n=<MODULUS>
Decrypt:
gak [-r[=<N>]] -d -k=<KEY> -n=<MODULUS>

   <N>: number of Rot-13+ encryption rounds.  Defaults to 1 if -r is used.
   <KEY>: Encryption Key
   <MODULUS>: Encryption Modulus

#Sample usages:

# 8-bit RSA key, with Rot-13+ key of 37
#Encrypt:
gak -r=37 -n=ca1 -k=11 gak > gak.enc
#Decrypt:
gak -r=37 -n=ca1 -k=ac1 -d < gak.enc > gak.orig

#Larger key, Rot-13+ key of 1004
gak -r=1004 -k=10001 -n=1967cb529 gak > gak.enc
gak -r=1004 -d -k=ac363601 -n=1967cb529 < gak.enc > gak.orig

#Sample large RSA keys:
-k=1925d31f005a0c0e1165ccf0c5d14adb
-n=1bab373c0002013b41f1a05a16b65161
-d -k=2d15b41e97d0b5431efc7a734d59f53
#(the modulus (-n) is always the same for encrypt/decrypt)

#512-bit key.  (line-wrapped for legibility)
-k=62a03c0df0b96335047a12923a7d20bc2b7bb07c59aba2c4b094fc7d54392e8a2e7606
   cb5d574407640f4bb4e0ea6aeb7fff0000ffff0000ffff0000ffff0001
-n=12004001208404a43f00502200b204602600c00001da894922433e4601a2c850240240
   01418004602404240109301008140000000142404002010000000000001
-d -k=10001

	***** Government (or Good Guys) ONLY! *****

	To retrieve messages, you will need the correct RSA key.  You
can get this by factoring the modulus which is in both the private and
public keys (it is the -n argument to gak).  Factoring can take a long
time for large keys, so please be patient.  Once you have factored the
modulus, see the RSA home page at www.rsa.com for how to obtain both
the secret and public keys.  Once you have the proper RSA keys, use
the -g switch with -d to use the escrowed Rot-13+ key.  For instance:

gak -g -n=ca1 -k=ac1 -d < gak.enc > gak.orig

...would use the proper Rot-13+ key to decrypt the message in the first
example.  In the future it is possible that someone could defeat the
escrow code.  To guard against this possibility, we are building a
hardware brute-force decryptor: "DEEP ROT".  We are currently experiencing
problems with our Perfectly-Portable-Parallel-Perl hardware, but we should
have it working soon.

	***** Notes *****

[*1]  The gak script is actually *more* readable if it is decrypted
      *INCORRECTLY*, using:
      "gak -r -n=ca1 -k=11 gak |gak -n=ca1 -k=ac1 -d"

[*2]  This might upset the J*v* lawyers.  I propose a new name:
      The "200 Proof Perl" certification program.
      Perl: for those who can handle more than coffee.

[*3]  The full commented explanation will *not* work with cut-and-
      paste, as the script wrapper is sensitive to comments
      and (some) newlines.

