RC4 implementation

Question

I am using the following implementation of the RC4 encryption algorithm in C#

/// <summary>
/// RC4 encryption algorithm
/// </summary>
/// <param name="bytes">Input bytes</param>
/// <param name="key">Key bytes</param>
/// <returns>encrypted bytes</returns>
public static byte[] Encrypt(byte[] bytes, byte[] key)
{
 byte[] z = new byte[bytes.Length];
 byte[] s = new byte[256];
 byte[] k = new byte[256];
 byte temp;
 int i, j;
 for (i = 0; i < 256; i++)
 {
 s[i] = (byte)i;
 k[i] = key[i % key.GetLength(0)];
 }
 j = 0;
 for (i = 0; i < 256; i++)
 {
 j = (j + s[i] + k[i]) % 256;
 temp = s[i];
 s[i] = s[j];
 s[j] = temp;
 }
 i = j = 0;
 for (int x = 0; x < z.GetLength(0); x++)
 {
 i = (i + 1) % 256;
 j = (j + s[i]) % 256;
 temp = s[i];
 s[i] = s[j];
 s[j] = temp;
 int t = (s[i] + s[j]) % 256;
 z[x] = (byte)(bytes[x] ^ s[t]);
 }
 return z;
}

Is it possible to optimize my implementation a bit further, eventually using unsafe code, - especially for the variable swapping? I hope for some constructive criticism.

Answer 1

public static byte[] Encrypt(byte[] bytes, byte[] key)

bytes doesn't tell me anything that I don't already know from the type. plaintext would tell me the meaning of this variable.

---

 byte[] z = new byte[bytes.Length];

Similarly, this would be more usefully named ciphertext.

---

 byte[] s = new byte[256];
 byte[] k = new byte[256];
 byte temp;
 int i, j;

Is there any benefit to reusing temp, i, and j rather than just redeclaring them in each scope? The benefit to redeclaring them is that it's more transparent that they are new variables.

---

 for (i = 0; i < 256; i++)
 {
 ...
 k[i] = key[i % key.GetLength(0)];
 }
 ...
 for (i = 0; i < 256; i++)
 {
 j = (j + s[i] + k[i]) % 256;
 ...
 }

k is used precisely once, and that's in a loop of the same length as the one which initialises it. IMO it would simplify things to eliminate the middleman and just use key[i % key.Length] in the second loop.

---

 j = (j + s[i] + k[i]) % 256;

 i = (i + 1) % 256;
 j = (j + s[i]) % 256;
 ...
 int t = (s[i] + s[j]) % 256;

Here is the big optimisation opportunity. Replacing % 256 with & 255 gives me a 25% reduction in execution time with a large plaintext.

---

 for (int x = 0; x < z.GetLength(0); x++)

I missed this at first: since it's a one-dimensional array, you can use Length instead of GetLength(0). This gives a significant further speedup.

---

I must say, though, that the code is simple enough to already be very fast. My test case is 512MB of plaintext, and the time drops from 10.2 secs to 5.4 secs.

• SRobertJames: I'm surprised that a compiler couldn't implement % 256 as & 255 - they routinely implement / 2 as >> 1. Did you benchmark in release mode, with optimizations on?