Проблема с кодировкой символов при расшифровке в PHP из C #

Думаю, у меня есть для вас хороший.

У меня есть код C #, который шифрует и дешифрует строки . Это выглядит примерно так:

    public static string EncryptString(String toEncrypt, String key)
    {
        Debug.WriteLine("Encrypting string: " + toEncrypt + "&key:" + key);
        Rijndael AES = Rijndael.Create();
        AES.KeySize = 128;
        AES.BlockSize = 128;
        AES.Mode = CipherMode.ECB;
        AES.Padding = PaddingMode.Zeros;
        MD5CryptoServiceProvider Hasher = new MD5CryptoServiceProvider();
        AES.Key = Hasher.ComputeHash(UTF8Encoding.UTF8.GetBytes(key));
        ICryptoTransform crypto = AES.CreateEncryptor(AES.Key, AES.IV); 
        byte[] txt = UTF8Encoding.UTF8.GetBytes( HEADER + toEncrypt);
        byte[] cipherText = crypto.TransformFinalBlock(txt, 0, txt.Length);
        return Convert.ToBase64String(cipherText);;
    }

Когда я шифрую или расшифровываю на C #, это работает как шарм. В php у меня есть алгоритм дешифрования, который выглядит следующим образом:

    if($msg!= "" && $key != "")
    {           
        $msg = parseMsg($msg);
        mcrypt_get_key_size ( MCRYPT_RIJNDAEL_128,  MCRYPT_MODE_ECB);
        $decrypted = mcrypt_decrypt(MCRYPT_RIJNDAEL_128, md5($key,true), base64_decode($msg),MCRYPT_MODE_ECB);      
        $headerLoc = strpos($decrypted,$correctHeader);         
        /*$decrypted = str_replace($correctHeader,"",$decrypted);
        for($x = 0; $x < 31; $x++)
        { 
            // an attempt at getting rid of control characters
            $decrypted = str_replace(chr($x),"",$decrypted);
        }*/
    }

Закомментированный код - это лишь некоторые из моих попыток правильно декодировать строку. Странно то, что иногда это работает, а иногда нет даже без странных персонажей.

Например:

Herp Derp с ключом: красный работает

Сообщение Herp Derp с ключом-меч-рыбой не работает.

Длинные сообщения с ключом красный не работают.

Нет сообщения с ключевым-меч-рыбой. работает.

Может ли это означать, что длина ключа сообщения является частью проблемы?

Я убедился, что сообщение и ключ правильно передаются между php и C #, это определенно проблема с кодировкой / decoding, и, основываясь на выплевывающем мусоре, я думаю, что это связано с кодировкой UTF8 . Я подозреваю, что режим заполнения тоже возможный виновник, есть идеи? Редактировать: Я не заметил 1 или 2 отсутствующих плюсов, из-за которых вся строка была прервана, Извините, стек: \ *

Кто-нибудь знает, как это исправить?

Изменить После перехода на ключ размер, струны не работают. С сообщением Herp Derp и красным паролем php выводит расшифровку как .�ʇ'y-�US2 ~ h \ �0�nAZ = � \ 2 / ����� | �a���R�`� / �� ����nY� <[B�NB�