Conventional Cryptography - A Classical Introduction to Cryptography: Applications for Communications Security - page 47

patent on RC4, but RC4 is a registered trademark of RSA Data Security. RC4 is widely
used, for instance in SSL/TLS (see Section 12.3). In particular, some Internet browsers
and servers may use RC4 as a default encryption algorithm for protected transactions.

RC4 works as a finite automaton with an internal state . It reads a plaintext as a byte
stream and produces a ciphertext as a byte stream. Its heart is actually a key-stream
generator which is used for the one-time pad algorithm. In an initialization stage, a
secret key is processed without producing keys. The automaton ends up in an internal
state which is thus uniquely derived from the secret key only. Then, every time unit,
the automaton updates its internal state and produces a key byte which is XORed to a
plaintext byte in order to lead to a ciphertext byte.

of all bytes. The internal state consists of
two bytes i and j and a permutation S of this set which is encoded as an array
S [0]

We consider the set { 0 , 1 ,..., 255 }

, S [1] ,..., S [255]. All operations are done on bytes (i.e. additions are taken

modulo 256).

In the initialization, we process a key which is represented as a sequence
K [0] bytes. The internal state is first initialized as fol-

lows. Byte j is set to 0, and the permutation S is set to the identity, i.e. S [ i ]

, K [1] ,..., K [ − 1] of

= i

for i = 0 , 1 ,..., 255. Key bytes are then iteratively processed, and the bytes i and j

are reset to 0.

1: j ← 0

2: for i = 0to255 do

3: S [ i ] ← i

4: end for
5: for i = 0to255 do

6: j ← j + S [ i ] + K [ i mod ]

7: swap S [ i ] and S [ j ]
8: end for
9: i

← 0

10: j ← 0

The key size is typically between 5 and 16 bytes (i.e. between 40 and 256 bits).

It is important that we never use the same state twice. Thus, plaintexts are iteratively
encrypted, which means that the initial state for a new plaintext is equal to the final
state for the previous plaintext.

The key-stream generator works as follows. Every time unit, we perform the
following sequence of instructions.

1: i ← i + 1

2: j S [ i ]

3: swap S [ i ] and S [ j ]
4: output S [ S [ i ]

← j +

+ S [ j ]]