RSA key generation in 13 lines of Perl

17 Dec 2003

      -----BEGIN PGP SIGNED MESSAGE-----

I've completed my Perl/dc RSA key generation program. The compacted
13-line version is below. A commented version can be found at
http://www.edmweb.com/steve/rsagen.txt

#!/usr/local/bin/perl
$k=768;$e=sprintf'%X',65537;print"Please enter a LOT of random junk.\n"
;$a=<STDIN>;print"Working. This may take a while.\n";for(1..(length($a)-
1)){$b[$_&31]^=unpack('C',substr($a,$_,1));$b[$_&31]=(($b[$_&31]<<5)|($b
[$_&31]>>3))&255;}for(0..255){$c[$_]=$_;}$a=$d=$f=0;for(0..255){$a=($a+
$c[$_]+$b[$a&31])&255;($c[$_],$c[$a])=($c[$a],$c[$_]);}open(F,'|dc');
select F;print"16dio[$e+]sa";for(1..50){for(1..$k/32){printf'%02X',&g;}
print"Sr";}for(1,2){printf'%02X',&g|128;for(2..$k/16){printf'%02X',&g;}
print"d$e%-2+d2%0=aSP";}print"[d2%SA2/d0<X+d*LA1=ZlP%0]sX[lR*]sZ[1+Q]sQ[
la1+sa0sc]sA[lAxlb1+sb]sB[ld1+sdLrddSssR1lP1-2/lXx+1+lP%99scd0=A2=Bclcla
+32>C]sC[LsSrld1-dsd0<D]sD[le1+se0ddsasbsdlCxlDxlP2 $e*+sPlc99=Elb32=ElP
2 $e*-led1>QQ]sE_1selExsq_1seLPlExsp[p=]Plpp[q=]Plqp[n=]P*p[e=]P$e p1-lp
1-lq1-**1+$e/[d=]Pp\n";close(F);sub g{$d=($d+1)&255;$f=($f+$c[$d])&255;(
$c[$d],$c[$f])=($c[$f],$c[$d]);return($c[($c[$d]+$c[$f])&255]);}

I'm sure this can be compacted further. I haven't put a lot of work into
compacting it; I really just want to get it out. 

Run the program, type in a LOT of random gibberish (several lines at
least) and press enter. Then wait. Eventually it will output your p, q, n,
e and d in hexadecimal. 

p and q: Prime numbers, congruent to 2 mod e. They can usually be
discarded, but they should never be revealed. 

n: Your public modulus

e: Your public encryption exponent (usually 10001 hex)

d: Your private decryption exponent

By default the program generates a 768-bit public modulus and a public
exponent of 10001 hex (65537 decimal). These can be changed by adjusting
the numbers in the first line. A 1024-bit modulus would be better, but for
some reason generation takes a LOT longer than a 768-bit modulus.
Fortunately key generation doesn't need to be done very often. 

Timings on a 100 MHz Pentium running FreeBSD:

Size of n  Time
512-bit:   4-5 minutes
768-bit:   8-9 minutes
1024-bit:  35-80 minutes (ack!)

I've had some difficulty generating 1024-bit keys, but it seems to be
working now. Let me know if you see any problems generating large keys
other than the obvious problem with the time spent. 

Disclaimer: This program seems to work, but your milage may vary. 

RSA key generation in 13 lines of Perl

Steve Reid