RC4 (idea)

RC4 was developed in 1987 by Ron Rivest (of RSA fame). It is a variable-key-size cypher. It was proprietary for seven years, until, in September 1994, the source code was posted anonymously to the Cyberpunks mailing list. It spread quickly to sci.crypt and to various ftp sites around the world. Legal licencees of the algorithm confirmed that it was indeed the genuine article. RSA Data Security tried to re-assert their ownership of the algorithm and claim that it was still a trade secret, but by that point it was too late, having been distributed and discussed on Usenet, at conferences and in university courses.

RC4 is very popular amongst programmers due to the simplicity of the algorithm and the fact that it is very easily remembered.

RC4 works in Output Feedback mode. The plaintext is entirely independent of the keystream. There is an 8 * 8 S-Box (containing S₀ through S₂₅₅). The contents of the S-Box is a permutation of the numbers 0 through 255, this permuation being a function of the variable-length key. It also has two counters, i and j both of which are initialised to zero.

To generate a random byte, B do the following:

i = (i + 1) mod 256
j = (j + Si) mod 256
swap the contents of Si and Sj
t = (Si + Sj) mod 256
B = St

The byte B is then XORed with the plaintext to generate cyphertext, or with the cyphertext to decrypt it.

Initializing the S-Box is also very easy. To initalize the S-Box do the following:

1) Fill the S-Box linearly, S_i = i (so S₀ = 0 ... S₂₅₅ = 255)
2) Create a second 256 byte array, K. Fill K with the key, repeating the key as necessary to fill all 256 bytes of K.
3) Set index j to zero.
4)

for i = 0 to 255
{
  j = (j + Si + Ki) mod 256
  swap the contents of Si and Sj
}

Thats it... one initialized S-Box

This algorithm is very fast, roughly ten times as fast as DES (and so even faster than triple-DES).

As of 1996 there had been no serious attempts of a cryptanalysis of RC4, indeed now in 2002 most of the cryptanalytic attempts have centered on finding weak keys and groups of closely related keys that allow for more sophisticated attacks on the cypher by revealing information about the contents of the S-Box. But since RC4 can be in 2¹⁷⁰⁰ different states (256! * 256²) it seems likely that the number of weak keys is small compared to the number of usefull (or strong) keys. RC4 can also be easily extended to increase its security, for example by extending it to 16-bit variant with a 16 * 16 S-Box and using 16 bit words.

Although RC4 has been out "in the wild" for many years now, it is still owned by RSA Data Security (RSADSI) who would be likely to sue any company that uses an unlicenced version of RC4 in a comercial product.

Currently RC4 is used in several products and protocols, such as Lotus Notes, Oracle Secure SQL, the Wireless Encryption Protocol (WEP) and the Cellular Digital Packet Data specification (CDPD) amongst others. For more information read a book such as Bruce Schneier's exellent "Applied Cryptography" ("the book the NSA wanted never to be published...") or just google on RC4.