Converting Python RSA Decryption Script to C#, Output is only last 16B instead of 128B

Question

I come to you today, hat in hand, after pounding my head against the brick wall that is encryption.

Here's the premise: I have a python script that generates a ASN.1 encoded DER key. I then have another python script that takes that DER private key and uses it to decrypt a base64 encoded string. I'm currently attempting to convert that second script into its C# alternative, and I've got it working--to a point.

When using the original python scripts, the decrypted output is 127 bytes long, while the C# code I have is 16 bytes long. At this point I thought the C# code I had was completely wrong, until I noticed that the last 16 bytes of both the python output and the C# output are the exact same. WAT?

Here's the code I have for prosterity (obv no error checking, etc.)

Input DER Private Key (Base64 encoded for web)

MIICXAIBAAKBgQDMJQczcaoGepZIPcTGJB5AfSBFqhCt5B+HRpaUosZzAhooljxKrlRd3oLww2pqyjyGl9bqrKhaRuCPaEg/RHYvqT3gEjtW9XrF3absMP2ihp+SgOTnRaQLlK7Wyh2QU4XKTd0Pyjv+nYTM3R1LRveN2YEg+dWUeGqGJuNs9NArqwIDAQABAoGBAMT0kI78gbrAeM938Knt3NYBIqqzmmX6qsR7wPnkVaxOAejYkZDHwpPSAujA0KH5Pg3o3qwJKl/2897IELQhnBdCfb1AvL87ENj0Kh1+SP5Y2LeqQVRE3HT1fGXlbBDdXDiCNiBcgnIT7nsVKA+KmKUjJI/MvefM9p2sVJudVfdxAkEA+6GtJqjOF4Ver/O+J8LJF5O0/fh6MRvdHKqPNehm+NygtAxsygu1MTpZFJVAHsfdQnL+rRJi9vbqiwHfNbsVmQJBAM+wTmCHhJ7g3RAGswhbgAqg3LfM8dre03b4fwHkp4+S6j5tcYazrN8dqifiL83Hyo0522BQsRt+YADIk7f1TeMCQFhEXWW7Pxf3G8Di4mg2Jq4TjSCtocdKO+TLW5MQY9aWJfUiiqLROoz7J7ZVqHljqJSfnAB/+6Ef+iQq0u6ZIrkCQGDELZBuM81uybD43hurvjm1f4EnvRwULATHfS2dorCTbA6QIY/4UThXcvtIOKuxRd+NMHhswEgmFobm7WSNp68CQEMn75sLC874hitiqVVu6bNyDsOG4X6Cyc8uLKA58BeIg8eG590ehrFHYR0JsawgePsAVXb/RCPuYgONi5TRHBk=

Input Encypted String (Base64 encoded)

e1algxNK5vfiLQmN42bQf9CHJnRGH06w13P+ObHx5U7XJWbCsh9HKclXX88b2peEG4U3K4WC+dSNGLEPe8d3bPwxlBOYXVgsAHKLrgD7gXJDOG+gMawUsUlVx+hWPESITHXDscbcM6zASUuIWGtPkJw3r00MwJy9ZzYqfr2OiJg=

Python RSA Script using (PyCrypt) to decode Encrypted String

//removed python code to convert base64 encoded DER key to ASN.1 and then to RSA key tuple for pycrypto, the following is the hex data within the tuple:
key = ['0x0:0xcc:0x25:0x7:0x33:0x71:0xaa:0x6:0x7a:0x96:0x48:0x3d:0xc4:0xc6:0x24:0x1e:0x40:0x7d:0x20:0x45:0xaa:0x10:0xad:0xe4:0x1f:0x87:0x46:0x96:0x94:0xa2:0xc6:0x73:0x2:0x1a:0x28:0x96:0x3c:0x4a:0xae:0x54:0x5d:0xde:0x82:0xf0:0xc3:0x6a:0x6a:0xca:0x3c:0x86:0x97:0xd6:0xea:0xac:0xa8:0x5a:0x46:0xe0:0x8f:0x68:0x48:0x3f:0x44:0x76:0x2f:0xa9:0x3d:0xe0:0x12:0x3b:0x56:0xf5:0x7a:0xc5:0xdd:0xa6:0xec:0x30:0xfd:0xa2:0x86:0x9f:0x92:0x80:0xe4:0xe7:0x45:0xa4:0xb:0x94:0xae:0xd6:0xca:0x1d:0x90:0x53:0x85:0xca:0x4d:0xdd:0xf:0xca:0x3b:0xfe:0x9d:0x84:0xcc:0xdd:0x1d:0x4b:0x46:0xf7:0x8d:0xd9:0x81:0x20:0xf9:0xd5:0x94:0x78:0x6a:0x86:0x26:0xe3:0x6c:0xf4:0xd0:0x2b:0xab',
'0x1:0x0:0x1',
'0x0:0xc4:0xf4:0x90:0x8e:0xfc:0x81:0xba:0xc0:0x78:0xcf:0x77:0xf0:0xa9:0xed:0xdc:0xd6:0x1:0x22:0xaa:0xb3:0x9a:0x65:0xfa:0xaa:0xc4:0x7b:0xc0:0xf9:0xe4:0x55:0xac:0x4e:0x1:0xe8:0xd8:0x91:0x90:0xc7:0xc2:0x93:0xd2:0x2:0xe8:0xc0:0xd0:0xa1:0xf9:0x3e:0xd:0xe8:0xde:0xac:0x9:0x2a:0x5f:0xf6:0xf3:0xde:0xc8:0x10:0xb4:0x21:0x9c:0x17:0x42:0x7d:0xbd:0x40:0xbc:0xbf:0x3b:0x10:0xd8:0xf4:0x2a:0x1d:0x7e:0x48:0xfe:0x58:0xd8:0xb7:0xaa:0x41:0x54:0x44:0xdc:0x74:0xf5:0x7c:0x65:0xe5:0x6c:0x10:0xdd:0x5c:0x38:0x82:0x36:0x20:0x5c:0x82:0x72:0x13:0xee:0x7b:0x15:0x28:0xf:0x8a:0x98:0xa5:0x23:0x24:0x8f:0xcc:0xbd:0xe7:0xcc:0xf6:0x9d:0xac:0x54:0x9b:0x9d:0x55:0xf7:0x71']

// from https://www.dlitz.net/software/pycrypto/api/current/Crypto.PublicKey.RSA-module.html
// from Crypto.PublicKey import RSA

rsa = RSA.construct(key)
plain_text = RSA.decrypt(cipher_text.decode('base64'))

Python Script Output

0x02:0x96:0xd3:0x80:0xeb:0xcc:0x89:0xa1:0xff:0x0f:0x97:0x64:0x21:0x6b:0xf1:0x69:0xe3:0xa9:0xb7:0x5a:0x7e:0xd8:0xe8:0x2d:0xa9:0x27:0x78:0x90:0x8a:0x56:0x58:0xcd:0x4a:0x08:0x24:0x22:0xdd:0x88:0xa0:0x58:0xe1:0x18:0xd2:0xe4:0xca:0xa3:0xba:0x70:0xa7:0x6d:0x07:0x40:0x9e:0x2a:0x23:0x05:0x73:0x5e:0x23:0xb3:0x0c:0xa8:0xb4:0x43:0xf8:0xee:0xa6:0x67:0xfb:0x56:0xb0:0xcc:0x59:0xe3:0x59:0x9b:0xe5:0x9c:0xae:0xca:0x3f:0x17:0x73:0xf8:0x69:0x1b:0x73:0x20:0xfe:0x2a:0x0d:0x91:0x8f:0x94:0x26:0xde:0x3c:0xdb:0xa2:0x3e:0xf9:0x8f:0x0d:0x8c:0xd2:0x7b:0xfb:0xd6:0x92:0x8c:0x00:0x11:0x5c:0x31:0x5e:0xee:0x76:0xfe:0xf5:0x4a:0x9e:0x04:0x51:0x8a:0x3d:0x93:0xec

C# RSA Decryption Script

static void Main(string[] args)
{
    var derContent = Convert.FromBase64String(base64DerContent); //base64DerContent is the "Input DER Private Key" above
    var rsa = DecodeRSAPrivateKey(derContent);
    Byte[] cipher_text_data = Convert.FromBase64String("e1algxNK5vfiLQmN42bQf9CHJnRGH06w13P+ObHx5U7XJWbCsh9HKclXX88b2peEG4U3K4WC+dSNGLEPe8d3bPwxlBOYXVgsAHKLrgD7gXJDOG+gMawUsUlVx+hWPESITHXDscbcM6zASUuIWGtPkJw3r00MwJy9ZzYqfr2OiJg=");

    Byte[] raw = rsa.Decrypt(cipher_text_data, false);
        string hex = BitConverter.ToString(raw);
        System.Console.WriteLine("Decrypted: " + hex);
}
//the following code taken from http://www.jensign.com/opensslkey/opensslkey.cs
//------- Parses binary ans.1 RSA private key; returns RSACryptoServiceProvider  ---
    public static RSACryptoServiceProvider DecodeRSAPrivateKey(byte[] privkey)
    {
        byte[] MODULUS, E, D, P, Q, DP, DQ, IQ;

        // ---------  Set up stream to decode the asn.1 encoded RSA private key  ------
        MemoryStream mem = new MemoryStream(privkey);
        BinaryReader binr = new BinaryReader(mem);    //wrap Memory Stream with BinaryReader for easy reading
        byte bt = 0;
        ushort twobytes = 0;
        int elems = 0;
        try
        {
            twobytes = binr.ReadUInt16();
            if (twobytes == 0x8130) //data read as little endian order (actual data order for Sequence is 30 81)
                binr.ReadByte();        //advance 1 byte
            else if (twobytes == 0x8230)
                binr.ReadInt16();       //advance 2 bytes
            else
                return null;

            twobytes = binr.ReadUInt16();
            if (twobytes != 0x0102) //version number
                return null;
            bt = binr.ReadByte();
            if (bt != 0x00)
                return null;


            //------  all private key components are Integer sequences ----
            elems = GetIntegerSize(binr);
            MODULUS = binr.ReadBytes(elems);

            elems = GetIntegerSize(binr);
            E = binr.ReadBytes(elems);

            elems = GetIntegerSize(binr);
            D = binr.ReadBytes(elems);

            elems = GetIntegerSize(binr);
            P = binr.ReadBytes(elems);

            elems = GetIntegerSize(binr);
            Q = binr.ReadBytes(elems);

            elems = GetIntegerSize(binr);
            DP = binr.ReadBytes(elems);

            elems = GetIntegerSize(binr);
            DQ = binr.ReadBytes(elems);

            elems = GetIntegerSize(binr);
            IQ = binr.ReadBytes(elems);

            System.Console.WriteLine("showing components ..");
            if (true)
            {
                System.Console.WriteLine("\nModulus", MODULUS);
                System.Console.WriteLine("\nExponent", E);
                System.Console.WriteLine("\nD", D);
                System.Console.WriteLine("\nP", P);
                System.Console.WriteLine("\nQ", Q);
                System.Console.WriteLine("\nDP", DP);
                System.Console.WriteLine("\nDQ", DQ);
                System.Console.WriteLine("\nIQ", IQ);
            }

            // ------- create RSACryptoServiceProvider instance and initialize with public key -----
            RSACryptoServiceProvider RSA = new RSACryptoServiceProvider();
            RSAParameters RSAparams = new RSAParameters();
            RSAparams.Modulus = MODULUS;
            RSAparams.Exponent = E;
            RSAparams.D = D;
            RSAparams.P = P;
            RSAparams.Q = Q;
            RSAparams.DP = DP;
            RSAparams.DQ = DQ;
            RSAparams.InverseQ = IQ;
            RSA.ImportParameters(RSAparams);
            return RSA;
        }
        catch (Exception)
        {
            return null;
        }
        finally
        {
            binr.Close();
        }
    }
    private static int GetIntegerSize(BinaryReader binr)
    {
        byte bt = 0;
        byte lowbyte = 0x00;
        byte highbyte = 0x00;
        int count = 0;
        bt = binr.ReadByte();
        if (bt != 0x02)     //expect integer
            return 0;
        bt = binr.ReadByte();

        if (bt == 0x81)
            count = binr.ReadByte();    // data size in next byte
        else
            if (bt == 0x82)
            {
                highbyte = binr.ReadByte(); // data size in next 2 bytes
                lowbyte = binr.ReadByte();
                byte[] modint = { lowbyte, highbyte, 0x00, 0x00 };
                count = BitConverter.ToInt32(modint, 0);
            }
            else
            {
                count = bt;     // we already have the data size
            }



        while (binr.ReadByte() == 0x00)
        {   //remove high order zeros in data
            count -= 1;
        }
        binr.BaseStream.Seek(-1, SeekOrigin.Current);       //last ReadByte wasn't a removed zero, so back up a byte
        return count;
    }

C# Script Output

11-5C-31-5E-EE-76-FE-F5-4A-9E-04-51-8A-3D-93-EC

As you can see the output of the C# code is only 16 bytes long, however it directly matches the last 16 bytes of the python script. I'm not sure exactly what is going on, and my (basic) understanding of RSA tells me it should be an all or nothing function--the whole text gets decrypted, or I get gibberish.

Answer 1

The issue here is padding. RSA operations require that the message be padded with a secure padding scheme before encryption. Otherwise, certain attacks exist that could recover the private key. Here's a good article explaining why.

For some reason, the Python crypto library is not removing the padding for you, but the C# library is. So you'll have to remove the padding manually in the Python code.

Lucky for you, from the data you give, it looks like the padding scheme being used here is PKCS#1.5. That's a relatively simple padding scheme that will be easy to handle. The full specs are in RFC 3447, but it boils down to this:

EM = 0x00 || 0x02 || PS || 0x00 || M.

where EM is the padded message before encryption, PS is the padding, and M is the original, unpadded message.

Here's a Python function that should do the job for you:

def RemovePKCS15Padding( padded_msg ):
    if len(padded_msg) < 2 or padded_msg[0]!='\x02':
        raise PaddingError # or whatever
    p = padded_msg.find('\x00')
    if p < 0:
        raise PaddingError # or whatever
    return padded_msg[p+1:]