Path: hks.net!news-mail-gateway!toad.com!owner-cypherpunks
From: hfinney@shell.portal.com (Hal)
Newsgroups: hks.lists.cypherpunks
Subject: Re: perl hackery, export-a-crypt-system
Date: 9 Mar 1995 12:41:47 -0500
Lines: 68
Sender: root@bb.hks.net
References: <13359.9503090852@exe.dcs.exeter.ac.uk>
NNTP-Posting-Host: bb.hks.net

aba@dcs.exeter.ac.uk writes:

>Heres a bit of perl code which implements RSA encryption and
>decryption and is small enough to use for a signature:

This is incredible!  What a beautiful hack.  I am absolutely blown away.
I have split your code up and added some spaces, then some comments to
try to understand how it works.  It is very clean and handles many
subtleties nicely.

# $s is -d or -e, $k is exponent, $n is modulus; $k and $n in hex
	($s,$k,$n)=@ARGV
# $w is number of hex digits in $n
	$w=length $n
# Add a leading 0 to make length of $k and $n be even so they will fill
# Bytes when packed as 2 digits per byte
	$k="0$k"if length($k)&1
	$n="0$n", $w++ if $w&1
# Print usage message if $s is not -d or -e or too few arguments
	die "$0 -d|-e key mod <in >out\n" if $s!~/^-[de]$/ || $#ARGV<2
# $v will be the digits of output per block, $w the digits of input per block.
# If encrypting need to reduce $w so input is guaranteed to be less than
# modulus; for decrypting reduce $v to match.
	$v=$w
	$s=~/d/?$v-=2:$w-=2
# Make $_ be the exponent $k as a binary bit string
	$_=unpack('B*',pack('H*',$k))
# Strip leading 0's from $_
	s/^0*//g
# Turn every 0 into "d*ln%", every 1 into "d*ln%lm*ln%".  These are dc codes
# which construct an exponentiation algorithm for that exponent.
# "d*ln%" is duplicate, square, load n, modulus; e.g. square the number
# on the stack, mod n.  "d*ln%lm*ln%" does this then, load m, multiply,
# load n, modulus; e.g. then multiply by m mod n.  This is the square and
# multiply algorithm for modular exponentiation.
	s/0/d*ln%/g
	s/1/d*ln%lm*ln%/g
# Put 1 at front, p at end of constructed string, put into $c
# The 1 will feed the square-and-multiply, the p will print the result.
	$c="1${_}p"
# Encryption/decryption loop.  Read $w/2 bytes of data to $m.
	while(read(STDIN,$m,$w/2)){
# Turn data into equivalent hex digits in $m
	  $m=unpack("H$w",$m)
# Run dc: 16 bit radix for input and output; $m into dc register "m";
# $n into dc register "n"; execute $c, the exponentiation program above.
# "\U...\E" forces upper case on the hex digits as dc requires.
# Put the result into $a.
	  chop($a=`echo 16o16i\U$m\Esm\U$n\Esn$c|dc`)
# Pad the result with leading 0's to $v digits, pack to raw data and output.
	  print pack('H*','0'x($v-length $a).$a)
	}

There is a cryptographic problem with this kind of algorithm is a
certain weakness against guessing plaintext.  This is a "pure RSA"
encryption so if the plaintext in one block is guessed it can be
encrypted and compared against the cyphertext.  Particularly in the last
block which may be short this might be feasible.  (Maybe it has a sig,
making it easy to guess.) This is not a major security hole but people
should be aware of it.

Still I think this is a tour de force.  Unfortunately I don't know perl
well enough to suggest improvements.  That is amazing how you are able to
turn the exponent into a program to do the exponentiation just by textual
manipulations.  I do think this would make an excellent .sig and I hope
people adopt it.

Hal