5
\$\begingroup\$

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
    );
}
\$\endgroup\$
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Ben Voigt Jan 1 '17 at 6:12
  • \$\begingroup\$ @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. \$\endgroup\$ – Kraang Prime Jan 1 '17 at 6:14
8
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 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 ? \$\endgroup\$ – Kraang Prime Jan 1 '17 at 6:36
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – Ben Voigt Jan 1 '17 at 6:41
  • \$\begingroup\$ 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. \$\endgroup\$ – Kraang Prime Jan 1 '17 at 6:54
  • 1
    \$\begingroup\$ @KraangPrime: A little bit of Math.Min (see edit) will take care of the short end block. \$\endgroup\$ – Ben Voigt Jan 1 '17 at 7:03
  • \$\begingroup\$ 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. \$\endgroup\$ – Kraang Prime Jan 1 '17 at 7:32
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Kraang Prime Jan 1 '17 at 5:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.