title: RSA Implementation in C#
body: <p>I am trying to implement the RSA Algorithm in C#. The code below works when p and q are small, but not when trying to replicate RSA-100 or greater where p and q are very large.</p>
  
  <p>For example when:</p>
  
  <pre><code>p = 61, q = 53, n = 3233, phi(n) = 3120, e = 17, d = 2753
  </code></pre>
  
  <p>Once decrypted, I get the correct original messsage. I got these values from the <a href="http://en.wikipedia.org/wiki/RSA_%28algorithm%29#A_working_example" rel="nofollow">RSA Wikipedia page</a>. The code also works for other small values of p and q.</p>
  
  <p>However, when using <a href="http://en.wikipedia.org/wiki/RSA_numbers#RSA-100" rel="nofollow">RSA-100</a> or greater, I do not get back my original message. I have tried using different values for the exponent (e) and made sure it is coprime with phi(n) but I cannot get the correct result. Am I missing something simple/obvious? </p>
  
  <p>Thank you in advance for your help!</p>
  
  <pre><code>//p and q for RSA-100
  //string p = "37975227936943673922808872755445627854565536638199";
  //string q = "40094690950920881030683735292761468389214899724061";
  
  string p = "61";
  string q = "53";
  
  //Convert string to BigInteger
  BigInteger rsa_p = BigInteger.Parse(p);
  BigInteger rsa_q = BigInteger.Parse(q);
  
  //n = p * q
  BigInteger rsa_n = BigInteger.Multiply(rsa_p, rsa_q);
  
  //phi(n) = (p-1)*(q-1)
  BigInteger rsa_fn = BigInteger.Multiply((rsa_p - 1), (rsa_q - 1));
  
  BigInteger rsa_e = 17;
  
  //Compute d
  BigInteger rsa_d = BigInteger.ModPow(rsa_e, (rsa_fn - 1), rsa_fn);
  
  //Encrypt the message, in this case 3007
  //C = (3007^rsa_e) mod rsa_n
  BigInteger C = BigInteger.ModPow(3007, rsa_e, rsa_n);
  
  //Decrypt the message, M should equal 3007
  //M = (3007^rsa_d) mod rsa_n
  BigInteger M = BigInteger.ModPow(C, rsa_d, rsa_n);
  </code></pre>