RC4 key schedule and algorithm design

Question

I've looked up RC4 algorithm and it's seems easy enough but some parts of it seem random to me. In the key schedule part take for example the following part :

j = (j + S[i] + key[i % keylen]) % 256

I can understand most of it:

• the key[i % keylen] is padding in-case that the key is shorter than 256 bytes, and
• the % 256 is to ensure that j will be in the range of 0-255 when performing the swap.

But why do we need the j = j + S[i]?

Is there a mathematical explanation to this or is it just to add some randomness? Also regarding to the pseudo random generator part: can someone point me to a reference which offers an explanation for the not so obvious operations?

I've looked for explanations on the internet but couldn't really find anywhere that explain those bits.

Answer 1

The correction question you should ask about why various operations in RC4 (or, for that matter, any other cipher) are there would be "if I were to remove that, what would the impact be? Would this weaken the cipher in some way?"

At your current state of knowledge, that may be a rather imponderable question, but it is still the correct one. I can try to give you a simple example: if you remove the $S[i]$ from the update of $j$, leaving

j = (j + key[i % keylen]) % 256

Then $j$ will follow a much simpler trajectory through the array as we run the key setup routine. In particular, if the key bytes just happen to sum to a multiple of 256 (which will happen 1/256 of the time for a random key), then $j$ will visit only (at most) keylen bytes of the array; all the other elements of the array will participate in one swap. Now, it's not immediately clear how a bias like this might influence the cipher; however it is quite plausible that it wouldn't be good.