The BigRSA Example Program

If you have read Chapter 4, you may recall the basic algorithmic steps involved in RSA. In the example program BigRSA , you will see similarities to the implementation shown in the TinyRSA example program provided in Chapter 4. The main difference you will see in the BigRSA example program is that we are using the GnuMP multiprecision math library. For details on installing and using this library, see Appendix C.

Note that in the BigRSA example program, the value of e is selected randomly . This was done just to prove that any value of e, such that e < phi and GCD( e , phi) = 1 are true, will work. However, the values of e that are most frequently used in practice are 3, 17, and 65535 (or 0xFFFF).

 unsafe static void Main(string[] args) {   //initialize random state with default algorithm   gmp_randstate_struct state =     new gmp_randstate_struct();   GmpWrapper.__gmp_randinit_default(&state);   //set seed to current time   DateTime dt = DateTime.Now; //current date and time   GmpWrapper.__gmp_randseed_ui(     &state, (ulong)dt.Ticks);   //get 256 bit uniformly distributed random prime p   mpz_struct p;   GmpWrapper.__gmpz_init(&p);   GmpWrapper.__gmpz_urandomb(&p, &state, 256);   GmpWrapper.__gmpz_nextprime(&p, &p);   //display random prime p   Console.WriteLine(     "p: " +     GmpWrapper.__gmpz_get_str(null, 10, &p));   //get 256 bit uniformly distributed random prime q   //in theory, we should ensure that p != q   //but we don't bother here ...   //i.e. have you won the lottery lately?   mpz_struct q;   GmpWrapper.__gmpz_init(&q);   GmpWrapper.__gmpz_urandomb(&q, &state, 256);   GmpWrapper.__gmpz_nextprime(&q, &q);   //display random prime q   Console.WriteLine(     "q: " +     GmpWrapper.__gmpz_get_str(null, 10, &q));   //pq = p*q   mpz_struct pq;   GmpWrapper.__gmpz_init(&pq);   GmpWrapper.__gmpz_mul(&pq, &p, &q);   //display product pq   Console.WriteLine(     "\npq:  " +     GmpWrapper.__gmpz_get_str(null, 10, &pq));   //initialize euler totient phi = (p-1)*(q-1)   mpz_struct phi;   GmpWrapper.__gmpz_init(&phi);   mpz_struct one;   GmpWrapper.__gmpz_init(&one);   GmpWrapper.__gmpz_set_str(&one, "1", 10);   mpz_struct pminusone;   GmpWrapper.__gmpz_init(&pminusone);   GmpWrapper.__gmpz_sub(&pminusone, &p, &one);   mpz_struct qminusone;   GmpWrapper.__gmpz_init(&qminusone);   GmpWrapper.__gmpz_sub(&qminusone, &q, &one);   GmpWrapper.__gmpz_mul(&phi, &pminusone, &qminusone);   //display phi   Console.WriteLine(     "phi: " +     GmpWrapper.__gmpz_get_str(null, 10, &phi));   //get value for e rel prime to phi and < phi   mpz_struct e;   GmpWrapper.__gmpz_init(&e);   while(true)   {     //get random number as candidate for e     GmpWrapper.__gmpz_urandomb(&e, &state, 256);     //is e < phi?     bool goodsize =       GmpWrapper.__gmpz_cmp(&e, &phi) < 0;     //is gcd of e and phi = 1?     mpz_struct gcd;     GmpWrapper.__gmpz_init(&gcd);     GmpWrapper.__gmpz_gcd(&gcd, &e, &phi);     bool relprime =       GmpWrapper.__gmpz_cmp(&gcd, &one) == 0;     //bail out if we have what we want     if (goodsize && relprime)       break;   }   //display random rel prime e   Console.WriteLine(     "\ne: " +     GmpWrapper.__gmpz_get_str(null, 10, &e));   //calculate d = e^-1 mod phi   mpz_struct d;   GmpWrapper.__gmpz_init(&d);   GmpWrapper.__gmpz_invert(&d, &e, &phi);   //display d   Console.WriteLine(     "d: " +     GmpWrapper.__gmpz_get_str(null, 10, &d));   //initialize plaintext message m   mpz_struct m;   GmpWrapper.__gmpz_init(&m);   while (true)   {     //get 256 bit uniformly dist random message m     GmpWrapper.__gmpz_urandomb(&m, &state, 256);     //must ensure that m < pq, or algebra fails     if (GmpWrapper.__gmpz_cmp(&m, &pq) < 0)       break;   }   //display plaintext message m   Console.WriteLine(     "\nm: " +     GmpWrapper.__gmpz_get_str(null, 10, &m));   //calculate ciphertext c = m^e mod pq   mpz_struct c;   GmpWrapper.__gmpz_init(&c);   GmpWrapper.__gmpz_powm(&c, &m, &e, &pq);   //display ciphertext message c   Console.WriteLine(     "c: " +     GmpWrapper.__gmpz_get_str(null, 10, &c));   //calculate deciphered  x = c^d mod pq   mpz_struct x;   GmpWrapper.__gmpz_init(&x);   GmpWrapper.__gmpz_powm(&x, &c, &d, &pq);   //display deciphered message x   Console.WriteLine(     "x: " +     GmpWrapper.__gmpz_get_str(null, 10, &x)); }