Generate private RSA key in C#

Question

I have the values for p, q, n and e and would like to calculate the private key d. How can I do this, could someone give me the example C# code ? I am using a BigInteger class to represent the values for p, q, n and e so I assume d will be a BigInteger as well.

Answer 1

From Wikipedia:

Determine d (using modular arithmetic) which satisfies the congruence relation

• Stated differently, ed − 1 can be evenly divided by the totient (p − 1)(q − 1).
• This is often computed using the extended Euclidean algorithm.
• d is kept as the private key exponent.

---

The extended Euclidean algorithm allows you to find integers such that the following holds:

The extended Euclidean algorithm is particularly useful when a and b are coprime, since x is the modular multiplicative inverse of a modulo b.

In this formula set a to e, b to (p-1)(q-1) and gcd(a, b) to 1 (because e and φ(pq) are required to be coprime in the RSA algorithm) and solve for x which gives you your d. The Wikipedia page on extended Euclidean algorithm has more details on how to write the algorithm to solve for x and y. For example you can use this recursive function (in pseudo-code):

function extended_gcd(a, b)
    if a mod b = 0
        return {0, 1}
    else
        {x, y} := extended_gcd(b, a mod b)
        return {y, x-(y*(a div b))}

In .NET if you just want to generate some RSA keys you don't have to implement the RSA algorithm yourself. There already is an implementation of RSA in the .NET framework that you can use.

• Generating Keys for Encryption and Decryption

Answer 2

The short way is to compute the inverse of e modulo (p-1)*(q-1). Actually you only need the least common multiple of p-1 and q-1, but this will not buy you much (yes, there are several possible values for d, this is normal, they are all equivalent).

If your BigInteger class has a modular inverse method, then this will be easy: just call it. Otherwise, you will have to compute it yourself, using the extended Euclidean algorithm (this is what BigInteger classes tend to use to compute modular inverses).

Answer 3

This is how I did it.

primes p=7 and q=17

Calculate n = p*q = 119

Calculate f(n) = (p-1)*(q-1) = 96

Calculate d = e^-1 mod f(n), e.g., d = 77