How can I make my decrypt method more efficient?
If you can assume that every index in the encrypted message is included in the key, You can loop over the key and encrypted message together, placing each letter into the correct decrypted message slot directly:

public static char[] decrypt(char[] encrypted, int[] key)
{
    char[] decrypted = new char[encrypted.length];

    for (int i = 0; i &lt; encrypted.length; i++)
    {
        decrypted[key[i]] = encrypted[i];
    }

    return decrypted;
}