RC4 Tutorial with Animation

The RC4 Key scheduling algorithm

RC4 is the most popular stream cipher. It’s popular because it’s fast, and it’s fast because it’s simple. There are other, newer ciphers that outperform RC4 in different ways, but RC4 is still the most widespread stream cipher.

Looking at the optimized C or assembly source code for RC4 can be a little disorienting, but the algorithm’s operation is simple: Given a key, RC4 creates a pseudo-random keystream that can be used to encrypt data. The rc4.c source code below clearly illustrates each step in the algorithm, and rc4demo.c provides an animation of RC4′s individual steps.

Overview

First, the RC4 algorithm creates a “state,” which begins as an array containing the values 0-255 in order. The algorithm then iterates through the array and swaps the elements around, based on the key value. The original key can then be discarded, because RC4 only uses the state to create a pseudo-random keystream, by algorithmically selecting elements and spitting them out. The added benefit of the keystream’s sole reliance on the state is that the original key doesn’t need to be kept in memory.

The Algorithm

1. Initialize the state.
2. Perform the key-scheduling algorithm (KSA) on the state, based on the input key (which can then be discarded).
3. Algorithmically select elements of the (now scrambled) state and output them as the keystream.

Initialization

Initially, the state is an identity permutation containing the values 0 through 255:

The key-scheduling algorithm

RC4′s KSA uses a loop to iterate through the state and perform the following operation, which generates j and swaps State[i] and State[j]:

The pseudo-random number generation algorithm

In a loop, RC4′s PRNGA deterministically selects elements from the state and outputs them as a keystream with the following code:

RC4 in C

The following code is a fully functional implementation of RC4, written for readability. The full source is here: rc4.c. Change the value of OUTPUT to see more or less information from each step.

RC4 demo with animation

RC4 keystream generation

To see an animation of the RC4 algorithm’s steps, download and compile rc4demo.c with  $gcc rc4demo.c -o rc4demo. To run it, type$ ./rc4demo.

To see an example of RC4 with a smaller state, which can be helpful for learning purposes, change the values of SIZE and SQRT to reflect a smaller state with SIZE = SQRT*SQRT.

The code on this page was written for readability. To see what the source code for RC4 looks like in the BSD or Linux kernels, check the links below.

RC4 on Wikipedia (includes pseudocode)

crypto/rc4/rc4.c Source - RC4 in the FreeBSD kernel (very easy to read)

linux/crypto/arc4.c - RC4 in the Linux kernel (not so easy to read)

One thought on “RC4 Tutorial with Animation”

1. Very good explanation.
You have decoded RC4 in best possible way.
Thanks
Ashok