Below is the original posting in which I released my perl/dc program for RSA key generation. I have lost the commented version, but this is how I remember it working: 1- Get "random" input from user. 2- Use cheap XOR-and-rotate hash to generate random(?) 256-bit key. 3- Use RC4, seeded with 256-bit key, to generate two pseudo-random numbers for use as starting points in a search for two primes. 4- The two large numbers are passed to dc. All further processing is done by dc. 5- Take one of the large numbers, increment it such that it is always congruent to 2 modulo the public exponent. 6- Run primality test (Lehmann, I think) on the current number. If not prime, goto step 5. 7- Repeat steps 5 and 6 with the other large number to generate the second prime. 8- Print the two primes (p and q), the public modulus (n = pq), the public exponent (usually 10001 (65536 decimal)) and the private exponent (d). I don't remember how I calculated the private exponent, but I did it _without_ the Extended Euclidian algorithm. Search the coderpunks archives for a message from Ron Rivest to me for the details. The above is all from memory. I wrote the code about a year and a half ago, so there might be some inaccuracies. In any case, I could barely read the dc gobbledygook when I wrote it, so after such a long time and losing the commented version it's not likely that I (or anyone else, I think) will ever decipher it. P.S. My old email address is dead. My new address (which is actually older than the dead one) is sreid@sea-to-sky.net. My public PGP key, self-signed with the new address, has been sent to the keyservers. Return-Path: steve@edmweb.com Date: Sun, 1 Dec 1996 14:19:01 -0800 (PST) From: Steve Reid To: coderpunks@toad.com, cypherpunks@toad.com Subject: RSA key generation in 13 lines of Perl Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: RO X-Status: -----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=;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/d0C]sC[LsSrld1-dsd0QQ]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. -----BEGIN PGP SIGNATURE----- Version: 2.6.3ia Charset: noconv iQEVAwUBMqID5dtVWdufMXJpAQE14AgApqOI2MMPe0V74cKI0vc3bDw8hfDW723c QKqVleH0MTIv4F792bf7ItekM81RbQiaB+AhSigFFFb679ZgdCV7XpPOwhkE3SD4 vJy1xU4HdZ6TbSrfzzZn8Peqd5K5zZdY7CpXbxW30TZWFNX5lqdDAAbvM77h36QC h/jwK1nWMzrTDupbhBwemkpZKaFmk5uAms5Y94Ckezh66+sOcWmvf7smyn8RJg4q zad6OVrclso22NBp/Pa0nf2+IdgFnhEfHgHxsI0t+awSokfr6WlZ8WAScxv40kJO KfcdBX1DXg4spl8kXgoQOrrA3VIUJKWXFfpnTt2nAKr/P4XfbpyFQw== =CY5F -----END PGP SIGNATURE-----