Search code examples
c#.netcrsachinese-remainder-theorem

Mapping RSA Encryption Parameters from CRT (Chinese remainder theorem) to .NET format

I need to implement RSA encryption/decryption using C#

I have a private key with following parameters:

mod n, exponent, p, q, dP, dQ, and (p-1mod q)

Above parameters are explained in Chinese remainder algorithm

However C#.NET implementation of the RSA has different parameter set as following:

Modulus, Exponent, P, Q, DP, DQ, D, InverseQ

When I'm trying to map the data from CRT to DOTNET, I get error Bad Data

For p,q, dP and dQ the mapping is obvious but about the rest of parameters I'm not sure.

It would be great if I can get help mapping these paramters

Solution

  • mod n maps to Modulus, p-1mod q maps to InverseQ, the encryption exponent maps to Exponent and the decryption exponent maps to D.

    The encryption exponent e and the decryption exponent d are related by e*d = 1 mod (p-1)(q-1). Thus if you have one them you can easily derive the other use a few methods from the System.Numerics.BigInteger class.

    var Pminus1 = BigInteger.Subtract(P, BigInteger.One);
var Qminus1 = BigInteger.Subtract(Q, BigInteger.One);
var Phi = BigInteger.Multiply(Pminus1, Qminus1);
var PhiMinus1 = BigInteger.Subtract(Phi, BigInteger.One);
// var D = BigInteger.ModPow(E, PhiMinus1, Phi);

    Note that care must be taken when constructing a .NET BigInteger, especially if you are used to Java's BigInteger class. See this question for more information.

    EDIT :

    As CodeInChaos points out that last line is WRONG!

    WRONG! WRONG! WRONG!

    I am embarrassed. In a bow to the forces of evil the BigInteger class does not have a modular inverse method nor an extended euclidean algorithm method. You can nevertheless google for 'c # extended euclidean algorithm' you can find many implementations. The extended euclidean algorithm will give you integers x and y such that 1 = e*x + phi * y. x is the inverse of e mod phi, so setting D = x mod phi is what is needed.