Public key chunked encryption with C# method to decrypt

Question

I have written a method in PHP which breaks up larger than the byte size of the key of the certificate used to encrypt, and a method in c# which will decrypt said chunks using the corresponding private key.

What I would like to be reviewed is the C# decrypt() function to improve the performance of decrypting each chunk.

In my tests using StopWatch this part takes about 3 seconds to decrypt all chunks in the test string, and store them back as a string. If I change the line

decrypted = decrypted + Encoding.UTF8.GetString( rsa.Decrypt( buffer, false ) );

to

byte[] tmp = rsa.Decrypt( buffer, false );

... the performance increases a bit to 2.8 seconds.

Generate private and public key pair (run this code)

GenerateKeyPair(true);

// generate public and private key
function GenerateKeyPair($display = false) {
    $config =  array(
        "digest_alg" => "sha512",
        "private_key_bits" => 4096,
        "private_key_type" => OPENSSL_KEYTYPE_RSA
    );

    $ssl = openssl_pkey_new( $config );
    openssl_pkey_export($ssl, $privKey);
    $pubKey = openssl_pkey_get_details($ssl)['key'];

    if($display == true) {
        // display keys in textareas
        echo '
              <textarea rows="40" cols="80">' . $privKey . '</textarea>
              <textarea rows="20" cols="80">' . $pubKey . '</textarea>
        ';
    }

    // return keys as an array
    return array(
        'private' => $privKey,
        'public'  => $pubKey
    );
}

Save the results to private.txt and public.txt

PHP: Encrypt using Public key (public.txt)

// replace this line with the one from http://pastebin.com/6Q2Zb3j6
$output = '';

echo encrypt($data, 'public.txt');

// encrypt string using public key
function encrypt($string, $publickey, $chunkPadding = 16) {

    $encrypted = '';

    // load public key
    $key = file_get_contents($publickey);

    $pub_key = openssl_pkey_get_public($key); 
    $keyData = openssl_pkey_get_details($pub_key);

    $chunksize = ($keyData['bits'] / 8) - $chunkPadding;

    openssl_free_key( $pub_key );

    // split string into chunks
    $chunks = str_split($string, $chunksize);

    // loop through and encrypt each chunk
    foreach($chunks as $chunk) {
      $chunkEncrypted = '';

      //using for example OPENSSL_PKCS1_PADDING as padding
      $valid = openssl_public_encrypt($chunk, $chunkEncrypted, $key, OPENSSL_PKCS1_PADDING);

      if($valid === false){
          $encrypted = '';
          return "failed to encrypt";
          break; //also you can return and error. If too big this will be false
      } else {
          $encrypted .= $chunkEncrypted;
      }
    }

    return bin2hex($encrypted);

}

C#: Class to load private key and use it to decrypt

using System;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Security.Cryptography;
using System.IO;
using System.Security.Cryptography.X509Certificates;

public class crypt {

    public static string decrypt(string encrypted, string privateKey) {
        string decrypted = "";
        try {
            RSACryptoServiceProvider rsa = DecodePrivateKeyInfo( DecodePkcs8PrivateKey( File.ReadAllText( privateKey ) ) );

            byte[] encryptedBytes = Enumerable.Range( 0, encrypted.Length -1 )
                         .Where( x => x % 2 == 0 )
                         .Select( x => Convert.ToByte( encrypted.Substring( x, 2 ), 16 ) )
                         .ToArray();

            byte[] buffer = new byte[( rsa.KeySize / 8 )]; // the number of bytes to decrypt at a time
            int bytesRead = 0;

            using ( Stream stream = new MemoryStream( encryptedBytes ) ) {
                while ( (bytesRead = stream.Read( buffer, 0, buffer.Length )) > 0 ) {
                    decrypted = decrypted + Encoding.UTF8.GetString( rsa.Decrypt( buffer, false ) );
                }
            }

            return decrypted;
        } catch (CryptographicException ce) {
            return ce.Message;
        } catch (FormatException fe) {
            return fe.Message;
        } catch (IOException ie) {
            return ie.Message;
        } catch (Exception e) {
            return e.Message;
        }
    }

    //--------   Get the binary PKCS #8 PRIVATE key   --------
    private static byte[] DecodePkcs8PrivateKey( string instr ) {
        const string pemp8header = "-----BEGIN PRIVATE KEY-----";
        const string pemp8footer = "-----END PRIVATE KEY-----";
        string pemstr = instr.Trim();
        byte[] binkey;
        if ( !pemstr.StartsWith( pemp8header ) || !pemstr.EndsWith( pemp8footer ) )
            return null;
        StringBuilder sb = new StringBuilder( pemstr );
        sb.Replace( pemp8header, "" );  //remove headers/footers, if present
        sb.Replace( pemp8footer, "" );

        string pubstr = sb.ToString().Trim();   //get string after removing leading/trailing whitespace

        try {
            binkey = Convert.FromBase64String( pubstr );
        } catch ( FormatException ) {        //if can't b64 decode, data is not valid
            return null;
        }
        return binkey;
    }

    //------- Parses binary asn.1 PKCS #8 PrivateKeyInfo; returns RSACryptoServiceProvider ---
    private static RSACryptoServiceProvider DecodePrivateKeyInfo( byte[] pkcs8 ) {
        // encoded OID sequence for  PKCS #1 rsaEncryption szOID_RSA_RSA = "1.2.840.113549.1.1.1"
        // this byte[] includes the sequence byte and terminal encoded null
        byte[] SeqOID = { 0x30, 0x0D, 0x06, 0x09, 0x2A, 0x86, 0x48, 0x86, 0xF7, 0x0D, 0x01, 0x01, 0x01, 0x05, 0x00 };
        byte[] seq = new byte[15];
        // ---------  Set up stream to read the asn.1 encoded SubjectPublicKeyInfo blob  ------
        MemoryStream mem = new MemoryStream( pkcs8 );
        int lenstream = (int)mem.Length;
        BinaryReader binr = new BinaryReader( mem );    //wrap Memory Stream with BinaryReader for easy reading
        byte bt = 0;
        ushort twobytes = 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;


            bt = binr.ReadByte();
            if ( bt != 0x02 )
                return null;

            twobytes = binr.ReadUInt16();

            if ( twobytes != 0x0001 )
                return null;

            seq = binr.ReadBytes( 15 );     //read the Sequence OID
            if ( !CompareBytearrays( seq, SeqOID ) )    //make sure Sequence for OID is correct
                return null;

            bt = binr.ReadByte();
            if ( bt != 0x04 )   //expect an Octet string
                return null;

            bt = binr.ReadByte();       //read next byte, or next 2 bytes is  0x81 or 0x82; otherwise bt is the byte count
            if ( bt == 0x81 )
                binr.ReadByte();
            else
                if ( bt == 0x82 )
                binr.ReadUInt16();
            //------ at this stage, the remaining sequence should be the RSA private key

            byte[] rsaprivkey = binr.ReadBytes( (int)( lenstream - mem.Position ) );
            RSACryptoServiceProvider rsacsp = DecodeRSAPrivateKey( rsaprivkey );
            return rsacsp;
        } catch ( Exception ) {
            return null;
        } finally { binr.Close(); }

    }

    //------- Parses binary ans.1 RSA private key; returns RSACryptoServiceProvider  ---
    private 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 );

            // ------- 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;
    }

    private static bool CompareBytearrays( byte[] a, byte[] b ) {
        if ( a.Length != b.Length )
            return false;
        int i = 0;
        foreach ( byte c in a ) {
            if ( c != b[i] )
                return false;
            i++;
        }
        return true;
    }

    private static async Task<string> DecryptX(string encrypted, string keyFile) {
        string decrypted = "";

        byte[] data = Convert.FromBase64String( encrypted );
        byte[] cert = pem2bytes( File.ReadAllText( keyFile ) );

        RSACryptoServiceProvider rsa = null;


        if(rsa == null) {
            try {
                X509Certificate2 cer = new X509Certificate2( cert );
                if ( cer.HasPrivateKey ) {
                    rsa = (RSACryptoServiceProvider)cer.PrivateKey;
                } else {
                    rsa = (RSACryptoServiceProvider)cer.PublicKey.Key;
                }
            } catch (CryptographicException ce) {
                return ce.Message;
            }
        }

        if (rsa == null) { return "No decoder hack worked"; }

        try {
            byte[] buffer = new byte[100]; // the number of bytes to decrypt at a time
            int bytesReadTotal = 0;
            int bytesRead = 0;
            byte[] decryptedBytes;
            using ( Stream stream = new MemoryStream( data ) ) {
                while ( ( bytesRead = await stream.ReadAsync( buffer, bytesReadTotal, 100 ) ) > 0 ) {
                    decryptedBytes = rsa.Decrypt( buffer, false );
                    bytesReadTotal = bytesReadTotal + bytesRead;
                    decrypted = decrypted + Encoding.UTF8.GetString( decryptedBytes );
                }
            }

        } catch ( CryptographicException ce) {
            return ce.Message;
        } catch ( Exception e) {
            return e.Message;
        }

        return decrypted;

    }

    private static byte[] pem2bytes( string publicKey ) {
        string[] stripstrings = new string[] {
            "PRIVATE KEY",
            "PUBLIC KEY",
            "CERTIFICATE"
        };

        string pemstr = publicKey.Trim();
        StringBuilder sb = new StringBuilder( pemstr );
        foreach(string strip in stripstrings) {
            sb.Replace( "-----BEGIN " + strip + "-----", "" );
            sb.Replace( "-----END " + strip + "-----", "" );
            sb.Replace( "-----BEGIN RSA " + strip + "-----", "" );
            sb.Replace( "-----END RSA " + strip + "-----", "" );
        }

        string pubstr = sb.ToString().Trim();   //get string after removing leading/trailing whitespace
        try {
            return Convert.FromBase64String( pubstr );
        } catch ( FormatException ) {       //if can't b64 decode, data is not valid
            return null;
        }
    }

}

C#: Sample usage to download and decrypt PHP output

string key = @"C:\path\to\private.txt";

using(WebClient wc = new WebClient()) {
    // download encrypted string from php script
    string encrypted = wc.DownloadString( "http://127.0.0.1/encrypt.php" );

    // start stopwatch
    var watch = System.Diagnostics.Stopwatch.StartNew();
    string decrypted = crypt.decrypt( encrypted, key );
    Console.WriteLine( "Elapsed: " + watch.Elapsed.TotalSeconds.ToString() );
    Console.WriteLine(
        decrypted
    );
}

Answer 1

Replace all this junk:

        byte[] encryptedBytes = Enumerable.Range( 0, encrypted.Length -1 )
                     .Where( x => x % 2 == 0 )
                     .Select( x => Convert.ToByte( encrypted.Substring( x, 2 ), 16 ) )
                     .ToArray();

        byte[] buffer = new byte[( rsa.KeySize / 8 )]; // the number of bytes to decrypt at a time
        int bytesRead = 0;

        using ( Stream stream = new MemoryStream( encryptedBytes ) ) {
            while ( (bytesRead = stream.Read( buffer, 0, buffer.Length )) > 0 ) {
                decrypted = decrypted + Encoding.UTF8.GetString( rsa.Decrypt( buffer, false ) );
            }
        }

with

using System.Runtime.Remoting.Metadata.W3cXsd2001;
byte[] encryptedBytes = SoapHexBinary.Parse(encrypted);
byte[] decryptedBytes = new byte[encryptedBytes.Length];
int blockSize = rsa.KeySize >> 3;
int blockCount = 1 + (encryptedBytes.Length - 1) / blockSize; 
Parallel.For(0, blockCount, (i) => {
    var offset = i * blockSize;
    var buffer = new byte[Math.Min(blockSize, encryptedBytes.Length - offset)];
    Buffer.BlockCopy(encryptedBytes, offset, buffer, 0, buffer.Length);
    Buffer.BlockCopy(rsa.Decrypt(buffer, false), 0, decryptedBytes, offset, buffer.Length);
});

We use a highly-optimized builtin class for converting hexadecimal description of a byte array into that byte array. Much simpler, much faster.

Then, we skip the MemoryStream entirely, since extra wrappers can only slow things down, and streams force us into sequential operation.

Finally, we use Parallel.For to process each block, passing it through rsa.Decrypt, and storing the output at the same array index the input came from.

The result's no longer a string, you can turn it into one after the end of the parallel for if you need to, but generally byte array is better for strong arbitrary data anyway.

If your block operation changes the size (how does that work? and how did you figure out how much to stick into each block on the encryption side?) then

int blockSize = rsa.KeySize >> 3;
int blockCount = 1 + (encryptedBytes.Length - 1) / blockSize; 
var decryptedChunks = new byte[][blockCount];
Parallel.For(0, blockCount, (i) => {
    var offset = i * blockSize;
    var buffer = new byte[Math.Min(blockSize, encryptedBytes.Length - offset)];
    Buffer.BlockCopy(encryptedBytes, offset, buffer, 0, buffer.Length);
    decryptedChunks[i] = rsa.Decrypt(buffer, false);
});
var decryptedBytes = decryptedChunks.SelectMany(x => x);

Note that the parallelization will only work if your rsa.Decrypt method is thread-safe/stateless. If it's not, find one that is.

Answer 2

Try using StringBuilder and it's Append method instead of repeated string concatenations. As an additional point, you could set the capacity of the StringBuilder on instantiation to the maximum expected size of the output, to prevent array reallocations.

That is, replace decrypted = decrypted + ... where decrypted is a string, with decrypted.Append(...) where decrypted is a StringBuilder.

StringBuilders are mutable and avoid the object allocation overhead of string concatenations.