RSA Implementation in C#

Question

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.

For example when:

p = 61, q = 53, n = 3233, phi(n) = 3120, e = 17, d = 2753

Once decrypted, I get the correct original messsage. I got these values from the RSA Wikipedia page. The code also works for other small values of p and q.

However, when using RSA-100 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?

Thank you in advance for your help!

//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);

possible duplicate of [How to calculate D for RSA encryption from P,Q and E](http://stackoverflow.com/questions/14229040/how-to-calculate-d-for-rsa-encryption-from-p-q-and-e) — CodesInChaos, Apr 17 '13 at 22:34

score 3 · Accepted Answer · answered Apr 17 '13 at 22:32

3

d=e^(phi(n)-1) mod phi(n) looks wrong to me. You either need d=e^(phi(phi(n))-1) mod phi(n), or you could use extended euclid.

answered Apr 17 '13 at 22:32

CodesInChaos

106,488
23
218
262

1

I ended up implementing the Extended Euclidean algorithm from the pseudo code on the Wikipedia page to compute d and it worked correctly. Thank you! – Ivan Stalev Apr 18 '13 at 01:46

score 2 · Answer 2 · answered Apr 19 '13 at 21:53

2

I see that you already accepted the solution. However, I would like to point you to the article that shows a more complex example on RSA encryption in C#. Check this post (There is also source code available): http://xmight.blogspot.com/2011/07/multithreaded-rsa-encryption-with-keys.html

answered Apr 19 '13 at 21:53

XMight

1,991
2
20
36

XMight === Andrei??? I for one am very grateful for the / your article especially since after reading about RSA I can then trace through a COMPLETE working example. Very helpful reinforcement. – GPGVM Nov 03 '14 at 15:49
Glad to hear that, this was its purpose. And yes, you are right :) – XMight Nov 12 '14 at 12:56
@XMight Your link to source code is broken now. Please, create a new link. – AlexMelw Sep 18 '17 at 05:53

RSA Implementation in C#

2 Answers2

Linked