The CrackRSAWorkFactorDemo Example Program

The CrackRSAWorkFactorDemo example shows the exponential growth in time required to crack RSA. Figure B-1 shows the output from this program. These results are from a 900 MHz PC.

Figure B-1. Cracking RSA work factor demo.

If you want to compare these results on your own machine, and you want to know your machine's clock speed, see the following using Regedt32.exe .

 HKEY_LOCAL_MACHINE/HARDWARE/DESCRIPTION/System/CentralProcessor/0 

For numbers up to 13 bits, less than one millisecond is required. When 22 bits are used, it takes almost one second; 28 bits takes an hour ; and if you had the patience, you would see that 38 bits takes more than a day. How many bits would take a human lifetime? Assume that you would live 2^15 = 32768 days, which is 89 years and about 9 months, just a few years higher than average life expectancy in most of the developed world. If 38 bits takes more than one day, then 53 = 38 + 15 (multiplying is done by adding exponents) will take considerably more than a human lifetime.

Here is the source code for this example program.

 unsafe static void Main(string[] args) {   //initialize prime p   mpz_struct p;   GmpWrapper.__gmpz_init(&p);   //initialize prime q   mpz_struct q;   GmpWrapper.__gmpz_init(&q);   //initialize pq   mpz_struct pq;   GmpWrapper.__gmpz_init(&pq);   //string representation of n-bit binary number   String strBits = "1";   Console.WriteLine(     "bits    hh:mm:ss.msec                 loops");   Console.WriteLine(     "----    -------------                 -----");   //iterate over n-bit binary numbers 2^1 to 2^256   for (ulong n= 1; n<=256; n++)   {     //get p = next prime after 2^n     GmpWrapper.__gmpz_set_str(&p, strBits, 2);     GmpWrapper.__gmpz_nextprime(&p, &p);     //get q = next prime after p     GmpWrapper.__gmpz_nextprime(&q, &p);     //get product of primes pq = p*q     GmpWrapper.__gmpz_mul(&pq, &p, &q);     //display number of bits n     Console.Write("{0,4}    ", n);     //do the factoring work and show loop count     WorkFactor(&pq);     //one more bit next time around     strBits = strBits + "0";   } } unsafe static void WorkFactor(mpz_struct* pq) {   //initialize candidate   mpz_struct candidate;   GmpWrapper.__gmpz_init(&candidate);   GmpWrapper.__gmpz_set_ui(&candidate, 2);   DateTime dtStart = DateTime.Now;   //brute force search   while (true)   {     if (GmpWrapper.__gmpz_divisible_p(       pq, &candidate) != 0)       break; //factor found     GmpWrapper.__gmpz_add_ui (       &candidate, &candidate, 1L);   }   DateTime dtEnd = DateTime.Now;   TimeSpan ts = dtEnd-dtStart;   Console.Write(     "{0,2:d2}:{1,2:d2}:{2,2:d2}.{3,2:d4}    ",     ts.Hours,     ts.Minutes,     ts.Seconds,     ts.Milliseconds);      GmpWrapper.__gmpz_sub_ui(     &candidate, &candidate, 1);   String str = GmpWrapper.__gmpz_get_str(     null, 10, &candidate);   Console.WriteLine("{0,18}", str); }