RSA in 5 lines of perl

The RSA .sig actually is implemented part in perl and part in dc, an arbitrary precision calculater which ships with most unix systems.

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...

Clifford Adams mailed me this RSA implementation in pure perl, using the perl bigint library.


#!/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}
Cliff also submitted a modified version of this (heavily obfuscated, and including ROT-N functionality also) to the obfuscated perl contest and won first prize.

Annotated version

And Clifford's commented version explaining how it works: #!/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 }
Comments, html bugs to me (Adam Back) at <adam@cypherspace.org>