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

	This pile of characters loosely called a Perl script
implements the following in 100% Pure(no tm) (200 Proof?) Perl:

	Rot-13+ (patent pending).  This enhanced encryption algorithm
allows the user to choose the number of rotatations used in encryption.
Billions of distinct keys are available.

	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.

	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 you are wearing a white hat.)

Code walkthrough:

NOTE: The full commented explanation will *not* work with cut-and-
      paste, as the original script is sensitive to comments
      and (some) newlines.

#####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, 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.
$k=~s=^.(..)*$=0$&=;
# If the key ($k) has an odd number of characters, add a leading 0.
# This is required for the pack below.  Could be deleted if users could
# be trusted to type the leading 0 for odd-length keys.
($k=unpack("B*",pack("H*",$k)))=~s$^0*$$;
# 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.
$*=0;
# Unfortunately, the bigint library doesn't treat undefines as 0
do 'bigint.pl';
# Speaking of bigints...
$"=$n=~s-.|\n-;$*=&badd(&bmul($*,16),hex$&)-ge;
# Translate the hex modulus into a decimal bigint
# $" is the number of hex characters, needed below
;$;=6x(1-$d*2+($:=($d*2-1+$")>>1));
# Set the input block size ($:) and output block size ($;)
# We'll take the output size as an n-character string.
# This is where you 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
$_=<>."\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.
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($,,$"),$*):0,""-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 *****
Encrypt:
gak [-r=<N>] -k=<KEY> -n=<MODULUS>

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

#Sample usages (tcsh aliases):
alias zt 'ze gak | zd"
alias ze "time ./gak -k=62a03c0df0b96335047a12923a7d20bc2b7bb07c59aba2c4b094fc7d54392e8a2e7606cb5d574407640f4bb4e0ea6aeb7fff0000ffff0000ffff0000ffff0001 -n=12004001208404a43f00502200b204602600c00001da894922433e4601a2c85024024001418004602404240109301008140000000142404002010000000000001"
alias zd "time ./gak -d -k=10001 -n=12004001208404a43f00502200b204602600c00001da894922433e4601a2c85024024001418004602404240109301008140000000142404002010000000000001"
alias ze "./gak -k=10001 -n=1967cb529"
alias zd "./gak -d -k=ac363601 -n=1967cb529"
alias ze "./gak -n=ca1 -k=11"
alias zd "./gak -n=ca1 -k=ac1 -d"
alias ze "./gak -k=1925d31f005a0c0e1165ccf0c5d14adb -n=1bab373c0002013b41f1a05a16b65161"
alias zd "./gak -d -k=2d15b41e97d0b5431efc7a734d59f53 -n=1bab373c0002013b41f1a05a16b65161"


	***** 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.
Factoring can take a long time for large keys, so please be patient.
Once you have the proper RSA keys, use the -g switch with -d to use
the escrowed Rot-13+ key.


     ***** HISTORY *****
March 95: Adam Back writes first RSA-in-perl (DC wrapper)
Dec 95: I write first pure-RSA-in-perl, send it to Adam Back.
Now: The above entry.

[Hmmm...  5 minutes left to tarball and upload this entry...]
