Using an RSA Public key to decrypt a string that was encrypted using an RSA private key

Question

This is a duplicate of an unanswered question here: Using an RSA Public Key to decrypt a string that was encrypted using RSA Private Key

You can see the author found a solution using some code from here: http://www.codeproject.com/KB/security/PrivateEncryption.aspx

Using code from that link looks very promising. The only thing missing is the padding. I typically use PKCS1.5 padding which is the default for OpenSSL RSA.

I know the answer to this question is very close. I know the only thing holding back decryption is the pkcs1.5 padding on the encrypted openssl ciphertext.

I was surprised to see how little information is out there on this subject because there are many situations where you would need a server to encrypt something, sign something, etc, and have a client application verify, decrypt, etc with the public key.

I also extensively tried using the RSACryptoServiceProvider to verify hash's resulting from the encryption using OpenSSL. For example, I would do a private key encryption using a SHA256 hash of the plaintext, then try to do a RSACryptoServiceProvider verify on that signature, and it does not work. I think the way MS does this is non standard and there are perhaps special customization at work with that.

So, the alternative is this question, which is simply taking private key encrypted ciphertext and using C# to decrypt it, thus, verifying it's authenticity. Hashes can be incorporated to make a simple signature verification system for data objects signed by the server and verified on the client.

I've looked through the PKCS1 RFC's, OpenSSL rsa source code, and other projects, I cannot get a solid answer on how to account for PKCS1 padding when doing my RSA Decrypt. I cannot locate where in the OpenSSL source code they handle the PKCS1 padding, otherwise, I might have an answer by now.

Also, this is my first question, I know it's a duplicate of an unanswered question, so, what to do? I googled that too, and found nothing.

The other thing I don't understand is why my decrypt method doesn't work. Since padding is removed after decryption, my decrypted data should resemble plaintext, and it's not even close. So, I'm almost sure that pkcs1 padding means that other things are happening, specifically, to the ciphertext which means that the ciphertext must be preprocessed prior to decryption to remove padding elements.

Perhaps simply filtering the ciphertext to remove padding elements is the simplest solution here...

Here is my Decrypt method:

    public static byte[] PublicDecryption(this RSACryptoServiceProvider rsa, byte[] cipherData)
    {
        if (cipherData == null)
            throw new ArgumentNullException("cipherData");

        BigInteger numEncData = new BigInteger(cipherData);

        RSAParameters rsaParams = rsa.ExportParameters(false);
        BigInteger Exponent = GetBig(rsaParams.Exponent);
        BigInteger Modulus = GetBig(rsaParams.Modulus);

        BigInteger decData = BigInteger.ModPow(numEncData, Exponent, Modulus);

        byte[] data = decData.ToByteArray();
        byte[] result = new byte[data.Length - 1];
        Array.Copy(data, result, result.Length);
        result = RemovePadding(result);
        Array.Reverse(result);
        return result;
    }

    private static byte[] RemovePadding(byte[] data)
    {
        byte[] results = new byte[data.Length - 4];
        Array.Copy(data, results, results.Length);
        return results;
    }

Solution

The problem isn't with the padding. In fact, removing padding values from decrypted ciphertext is actually very simple. The problem was with the software at this location: You can see the author found a solution using some code from here: http://www.codeproject.com/KB/security/PrivateEncryption.aspx

And with Microsoft's implementation of System.Numeric which simply cannot handle larger integers...

To fix the issue, I looked at previous releases of code on the codeproject site and ended up with this PublicDecrypt method.

    public static byte[] PublicDecryption(this RSACryptoServiceProvider rsa, byte[] cipherData)
    {
        if (cipherData == null)
            throw new ArgumentNullException("cipherData");

        BigInteger numEncData = new BigInteger(cipherData);
        RSAParameters rsaParams = rsa.ExportParameters(false);
        BigInteger Exponent = new BigInteger(rsaParams.Exponent);
        BigInteger Modulus = new BigInteger(rsaParams.Modulus);

        BigInteger decData2 = numEncData.modPow(Exponent, Modulus);
        byte[] data = decData2.getBytes();
        bool first = false;
        List<byte> bl = new List<byte>();
        for (int i = 0; i < data.Length; ++i)
        {
            if (!first && data[i] == 0x00)
            {
                first = true;
            }
            else if (first)
            {
                if (data[i] == 0x00)
                {
                    return bl.ToArray();
                }
                bl.Add(data[i]);
            }
        }
        if (bl.Count > 0)
            return bl.ToArray();
        return new byte[0];
    }

That will perfectly decrypt ciphertext created by openssl using the rsautl utility, or the Perl Crypt::OpenSSL::RSA private_encrypt method.

The other big change was dropping the Microsoft BitInteger library which simply didn't work. I ended up using the one mentioned in the Code Project article , and found here: http://www.codeproject.com/Articles/2728/C-BigInteger-Class

The key here is to set the maxintsize in the library to a value which is larger based on how big of a key size you are using. For 4096 bit, a value of 500 worked fine (approx length of the modulus).

Here is the calling method:

            var encmsg3 = "JIA7qtOrbBthptILxnurAeiQM3JzSoi5WiPCpZrIIqURKfVQMN1BrondF9kyNzbjTs1DaEKEuMBVwKExZe22yCvXXpm8pwcEGc9EHcVK2MPqNo89tIF8LJcaDqBMwLvxdaa/QgebtpmOVN/TIWfuiV8KR+Wn07KwsgV+3SALbNgbOIR3RtCx3IiQ3tZzybJb08+ZKwJEOT011uwvvGmtJskQgq9PC8kr1RPXMgaP6xMX7PHFJ8ORhkuWOFfCh+R4NhY1cItVhnRewKpIC2qVlpzUYRAgKIKdCXuZDqUQdIponR29eTovvLb0DvKQCLTf9WI1SzUm6pKRn0vLsQL7L3UYHWl43ISrTpDdp+3oclhgRF3uITR4WCvoljephbGc6Gelk5z3Vi6lN0oQaazJ7zIen+a/Ts7ZX3KKlwPl4/lAFRjdjoqu7u4IAK7O7u1Jf2xDiGw18C/eGt8UHl09zU4qQf9/u+7gtJ+10z2NERlLSaCDjVqslwmmxu81pG2gCv8LfpR4JlPaFfBZMGfGBihyGryWhJwizUXXo8wgdoYbHRXe8/gL19qro0ea5pA9aAhDjTpX1Zzbwu2rUU7j6wtwQtUDJOGXXCw1VOHsx6WXeW196RkqG72ucVIaSAlx5TFJv8cnj6werEx1Ung5456gth3gj19zHc8E/Mwcpsk=";
            byte[] enc = Convert.FromBase64String(encmsg3);
            var dec = rsa2.PublicDecryption(enc);
            Debug.Print("PLAINTEXT: " + Encoding.UTF8.GetString(dec));

The only last thing someone would need to completely replicate this would be getting the private key into openssl format so that they could pass the private and public keys back and forth between openssl and C#.

I used openssl.net, and created an RSA instance, and set all the variables using bignumbers. Here's the code for that:

        RSACryptoServiceProvider rsa = new RSACryptoServiceProvider();
        rsa.FromXmlString(Properties.Resources.RSAParameters);

        RSAParameters par = rsa.ExportParameters(true); // export the private key


        using (OpenSSL.Crypto.RSA rsaos = new OpenSSL.Crypto.RSA())
        using (BigNumber bnmod = BigNumber.FromArray(par.Modulus))
        using (BigNumber bnexp = BigNumber.FromArray(par.Exponent))
        using (BigNumber bnD = BigNumber.FromArray(par.D))
        using (BigNumber bnP = BigNumber.FromArray(par.P))
        using (BigNumber bnQ = BigNumber.FromArray(par.Q))
        using (BigNumber bnDmodP = BigNumber.FromArray(par.DP))
        using (BigNumber bnDmodQ = BigNumber.FromArray(par.DQ))
        using (BigNumber bnInverse = BigNumber.FromArray(par.InverseQ))
        {
            rsaos.PublicExponent = bnexp;
            rsaos.PublicModulus = bnmod;

            rsaos.IQmodP = bnInverse;
            rsaos.DmodP1 = bnDmodP;
            rsaos.DmodQ1 = bnDmodQ;
            rsaos.SecretPrimeFactorP = bnP;
            rsaos.SecretPrimeFactorQ = bnQ;
            rsaos.PrivateExponent = bnD;
            string privatekey = rsaos.PrivateKeyAsPEM;   
            string publickey = rsaos.PublicKeyAsPEM
        }

With that you can easily create an RSA key, export everything to OpenSSL, and encrypt/decrypt anything you want within reason. It is enough to handle private key encryption followed by public key decryption.

Cool.

Comments

[President James K. Polk]

Where's the encrypt code? There are two kinds of PKCS #1 version 1.5 padding: block type (BT) 1 and block type 2 padding. BT 1 is used for RSA signatures which is what you are doing, BT 2 is for RSA encryption.