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

• Ben Voigt: Congratulations, you've discovered (one of the reasons) why asymmetric encryption isn't used for large data structures like certificate chains. Instead, asymmetric encryption is used only to protect a session key, and that session key is used in a fast symmetric encryption algorithm to process the entire message.
• Kraang Prime: @BenVoigt - it is very fast from php as I presume the encryption is done in parallel. In c#, if I want parallel, i need to handle it manually -- which is really the last leg of this.

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.

• Kraang Prime: Nice. Quick question regarding storing at the same place -- the encrypted bytes are 512 blocks, however the decrypted data may be smaller -- what happens to the output if (for example) block one decrypted is 490 bytes, and block 2 is 480 bytes --- does block 2 get stored starting at 512/513 leaving around 32 bytes (in this case) of null ?
• Ben Voigt: @KraangPrime: Are you sure the size variation isn't coming from your Encoding.UTF8 step? Anyway, you can keep a list of chunks and assemble them after decryption finishes, see edit.
• Kraang Prime: ok, that last bit should work. just a note that the order of the params in BlockCopy() is not correct which is fine, this definitely set me on the right track. One other thing to note, is that the last block may be smaller thank 512 which was accounted for before, but not sure how to accomodate this using the current blockcopy method. will paste the error.
• Ben Voigt: @KraangPrime: A little bit of Math.Min (see edit) will take care of the short end block.
• Kraang Prime: I am accepting this as the solution. I will post the final results of this (functional) at the bottom of your question as an edit. Also awarding on SO :) The hex decryption method didn't seem to save any time over the LINQ one, but I will definitely investigate other things such as memory/etc usage. ( FYI - this cut the time down to around 30% of the original time it cost to execute.

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.

• Kraang Prime: I think you missed where I was essentially discarding the data in a subsequent test (look at the first code - single line) replacing it with byte[] tmp = rsa.Decrypt( buffer, false ); with negligible performance improvement. I was just looking at possibly some form of parallel processing hack as the time lost is on the actual rsa.Decrypt() call. Using StringBuilder is a good idea though. I upvoted for that but I think I would like to see something where that rsa.Decrypt() is processing multiple chunks at the same time and then concatenating the results when all completed.