CODEWITHSUNDEEP
c#.netcrsachinese-remainder-theorem
AaA
AaA

Reputation: 3694

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

Upvotes: 6

Views: 2985

Answers (3)

HuiLin Xiong
HuiLin Xiong

Reputation: 51

Extended Euclidean algorithm can be used to compute the modular inverse, in this case D will be calculated, use this link: http://www.di-mgt.com.au/euclidean.html#extendedeuclidean to get the detail, I tested the source code in C# as below, and the result is matching,

public static BigInteger modinv(BigInteger u, BigInteger v)
{
   BigInteger inv, u1, u3, v1, v3, t1, t3, q;
   BigInteger iter;
   /* Step X1. Initialise */
   u1 = 1;
   u3 = u;
   v1 = 0;
   v3 = v;
   /* Remember odd/even iterations */
   iter = 1;
   /* Step X2. Loop while v3 != 0 */
   while (v3 != 0)
   {
       /* Step X3. Divide and "Subtract" */
       q = u3 / v3;
       t3 = u3 % v3;
       t1 = u1 + q * v1;
       /* Swap */
       u1 = v1; v1 = t1; u3 = v3; v3 = t3;
       iter = -iter;
   }
   /* Make sure u3 = gcd(u,v) == 1 */
   if (u3 != 1)
       return 0;   /* Error: No inverse exists */
       /* Ensure a positive result */
       if (iter < 0)
           inv = v - u1;
       else
           inv = u1;
       return inv;
}

Upvotes: 2

DividedByZero
DividedByZero

Reputation: 4391

D can be calculated like this:

    var qq = BigInteger.Multiply(phi, n);
    var qw = BigInteger.Multiply(phi, qq);
    BigInteger D = BigInteger.ModPow(e, (qw - 1), phi);

Upvotes: 0

President James K. Polk
President James K. Polk

Reputation: 42009

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.

Upvotes: 6

Related Questions