pureperl.html
4587d9016ab96dff78799def788bcd7ba7d21f5b2921ad10a5c901b34fdcd355
<HTML>
<HEAD>
<TITLE>RSA in 5 lines of perl</TITLE>
</HEAD>
<BODY>
<H1>RSA in 5 lines of perl</H1>
The <A HREF="http://www.dcs.ex.ac.uk/~aba/rsa/rsa-details.html">RSA
.sig</A> actually is implemented part in perl and part in
<A HREF="http://www.dcs.ex.ac.uk/~aba/rsa/dc.html">dc</A>, an arbitrary
precision calculater which ships with most unix systems.
<P>
Some people view this as cheating (shelling to another language), and
I concede the point slightly, but offer the counter-point that dc is
available on a *lot* of unix systems. A happy solution to this
argument has been provided though...
<P>
Clifford Adams mailed me this RSA implementation in pure perl, using
the perl bigint library.
<HR>
<XMP>
#!/usr/local/bin/perl -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}
</XMP>
<HR>
Cliff also submitted a modified version of this (heavily obfuscated,
and including ROT-N functionality also) to the obfuscated perl contest
and
<A HREF="http://www.tpj.com/tpj/obfusc-3-writeup">won first prize</A>.
<H3>Annotated version</H3>
And Clifford's commented version explaining how it works:
<XMP>
#!/usr/local/bin/perl -s
#Above: full path for perl (may need to be changed on local system).
# -s switch enables simple switch processing, which sets $d to 1
# if "-d" is on the command line (it also removes the switch from ARGV).
# if -d is not given $d is undefined (acts like 0)
#Load the standard bigint library. Unlike require, do will not complain if
#the library is not present. The space between do and the quotes is required
#(ha ha) in 4.036.
do 'bigint.pl';
#Set $_ to the key (e or d), and $n to n.
($_,$n)=@ARGV;
#For $_ (the key), if there are an odd number of characters,
#then add a leading zero. This is needed for the pack below.
s/^.(..)*$/0$&/;
#pack hex digits to 8-bit binary, then unpack to ASCII binary, store in $k
#The outer parens are needed for precedence.
($k=unpack('B*',pack('H*',$_)))
#remove any leading zeros from $k
=~s/^0*//;
#Extract $x (bigint version of $n).
# $x=0; Initialize bigint (needed?)
# $z= result of search/replace--the number of characters
# (hex digits) in $n
# $n=~s/./ for each character in $n...
# $x=&badd(&bmul($x,16),hex$&) ...mult old total and add digit ($&)
# /ge;
$x=0;$z=$n=~s/./$x=&badd(&bmul($x,16),hex$&)/ge;
#Reading from standard input into $_ until exhausted.
while(read(STDIN,$_
#...$w characters of STDIN ($w set for later use).
#...don't completely understand formula and reasoning yet.
#This might be able to be shortened, but be careful w/ precendence!
,$w=((2*$d-1+$z)&~1)/2))
{
#result of calculations (output)
$r=1;
#Make $_ contain trailing NUL/zero characters up to $w total length.
#The $_ string is only changed when encrypting and the final block is short.
#we save a couple chars by set $c clear/cypher (input) here.
$_=substr($_."\0"x$w,$c=0,$w);
#Set the clear/cypher text bigint.
# s/.|\n/ for each character in $_ (need .|\n for 8-bit match)...
# $c=&badd(&bmul($c,256),ord$&) ...mult old total, add unsigned char.
# /ge;
s/.|\n/$c=&badd(&bmul($c,256),ord$&)/ge;
#Set $_ to copy of $k (key--ascii binary) for big calculation below
$_=$k;
#Do that RSA thang:
# s/./
# $r=&bmod(&bmul($r,$r),$x),
# $&?
# $r=&bmod(&bmul($r,$c),$x)
# :0
# ,""
# /ge;
#Note: this empties $_, saving a few chars below.
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
}
</XMP>
<HR>
<EM>
Comments, html bugs to me
(<A HREF="http://www.dcs.ex.ac.uk/~aba/">Adam Back</A>) at
<A HREF="mailto:aba@dcs.ex.ac.uk"><aba@dcs.ex.ac.uk></A>
</BODY>
</HTML>