Decrypt a mesage using RSA in .NET - m**d mod p*q not working

Question

I am experimenting with Mega encryption API, and I am stuck with the RSA decryption part.

The JavaScript used is this:

// Compute m**d mod p*q for RSA private key operations.

function RSAdecrypt(m, d, p, q, u)
{    
 var xp = bmodexp(bmod(m,p), bmod(d,bsub(p,[1])), p);
 var xq = bmodexp(bmod(m,q), bmod(d,bsub(q,[1])), q);

 var t=bsub(xq,xp);
 if(t.length==0)
 {
  t=bsub(xp,xq);
  t=bmod(bmul(t, u), q);
  t=bsub(q,t);
 }
 else
 {
  t=bmod(bmul(t, u), q);
 } 
 return badd(bmul(t,p), xp);
}

I am using .NET (4.0 with support for BigInteger) and I am trying to replicate the same behaviour.

The RSA data I have is:

p (1024 bits)
q (1024 bits)
d (2044 bits)
u (1024 bits)
m (2044 bits) (the ciphered data)

I tried with RSACryptoServiceProvider with no luck. In other post another user reported that he managed using the basic RSA decryption algorithm (m**d mod p*q) and avoiding RSACryptoServiceProvider.

I implemented it (the U part is not necessary, I understand), made sure that the input was exact the same as the Javascript input, but still had no luck. The ouput is not the same as the expected by the Javascript code.

This is the function implemented:

Public Shared Function RSA_Decrypt(ByVal P As Numerics.BigInteger, ByVal Q As Numerics.BigInteger, ByVal D As Numerics.BigInteger, ByVal M As Numerics.BigInteger) As Byte()
    Dim N As System.Numerics.BigInteger = Numerics.BigInteger.Multiply(P, Q)
    Dim DecryptedData As System.Numerics.BigInteger = Numerics.BigInteger.ModPow(M, D, N)
    Return DecryptedData.ToByteArray
End Function

The test code:

Dim P As New Numerics.BigInteger(Convert.FromBase64String("gbb1FjTy...s="))
Dim Q As New Numerics.BigInteger(Convert.FromBase64String("o0fGo0v...8="))
Dim D As New Numerics.BigInteger(Convert.FromBase64String("GFVe9C...bQ=="))
Dim Data As New Numerics.BigInteger(Convert.FromBase64String("BnrSc/..Dg=="))

Dim ResultBytes As Byte() = cripto.RSA_Decrypt(P, Q, D, Data)
Dim ResultStr As String = Convert.ToBase64String(ResultBytes)

This code returns:

Vd2jBCzObTx...QW1y+VRSZHAw==

However, the JavaScript function returns

LUyj3pyIyr4g...1aZU=

Do you have an idea what am I doing wrong, and how I can solve this?

Answer 1

@CodesInChaos was right, it was an endianness problem.

I have used a function "OS2IP" taken from here. Just used it to generate the BigInteger from the byte array.

Dim P As Numerics.BigInteger = cripto.OS2IP(Convert.FromBase64String("gbb1FjTyN ... hs="), false)

Then I had to reverse the generated byte array:

Dim ResultBytes As Byte() = cripto.RSA_Decrypt(P, Q, D, Data).Reverse.ToArray

And the function that corrects the endianness:

''' <summary>
''' Converts a byte array to a non-negative integer.
''' </summary>
''' <param name="data">The number in the form of a byte array.</param>
''' <param name="isLittleEndian">Endianness of the byte array.</param>
''' <returns>An non-negative integer from the byte array of the specified endianness.</returns>
Public Shared Function OS2IP(data As Byte(), isLittleEndian As Boolean) As Numerics.BigInteger
    Dim bi As Numerics.BigInteger = 0
    If isLittleEndian Then
        For i As Integer = 0 To data.Length - 1
            bi += Numerics.BigInteger.Pow(256, i) * data(i)
        Next
    Else
        For i As Integer = 1 To data.Length
            bi += Numerics.BigInteger.Pow(256, i - 1) * data(data.Length - i)
        Next
    End If
    Return bi
End Function

With that change, the result is now correct. Now I will look at the timing-attack issue :)