← Back

#### RC4

- Tool
- About

What

Just the full version of RC4 which works on a 256-bytes 'keystream'. (previous tool: RC4 Mini ('16'-byte) was for educational/demo purposes only)

Detailed Explanation

note: The explanation below is from Somitra Sanadhya's answer on "What is an intuitive explanation of the RC4...and its weaknesses?" on Quora.com.
The RC4 cipher consists of two parts: 1. The Key Scheduling Algorithm (KSA), and 2. The Pseudo Random (Byte) Generation Algorithm (PRGA). The KSA takes a neatly arranged array of 256 elements (bytes containing values 0, 1, 2, ..., 255 in this order), and then uses a variable length secret key to turn the array into a pseudo-random order. Once the KSA has finished, the array is supposed to "look" randomly arranged.
After the KSA, the PRGA part starts and this part outputs one byte at a time. Each PRGA step further perturbs the array a little while outputting one byte.
The C-code for the RC4 is given below: (Note that we are using modulo function as "mod" in the code below for clarity. In a program, this needs to be replaced by %. Further, swap(x,y) is the function to swap the values of x and y.)
KSA:

    for(i=0; i<256; i++) S[i] := i; // initialize the array
    j := 0
    for(i=0; i<256; i++){
       j := (j + S[i] + key[i mod keylength]) mod 256;
      swap(S[i], S[j]);
    }

PRGA:

    i := 0; j := 0;
    do{
      i := (i + 1) mod 256;
      j := (j + S[i]) mod 256;
     swap(S[i], S[j]);
     K := S[(S[i] + S[j]) mod 256];
        output K;
    }while(required);

The KSA aims to use the following method to produce a random permutation of a given array S. Take an index i which moves over the entire array once, one step at a time. Take another index j which randomly moves over the array. Then swap the contents of S[i] and S[j]. Do this while i covers all the elements of the array. Note that Donald Knuth provides a similar looking (but different) algorithm in his classic book, and analyzes to show that the array at the end of the procedure will be uniformly random, if the choice of j was uniformly random at each step.
The trick in RC4 is to use the secret key to compute j at each step in the above procedure. Since the secret key is unknown to an adversary, the array produced at the end of KSA will not be known to anyone other than the genuine users. The size of the array is chosen to be large enough (i.e. 256) to ensure that probability of guessing an array location after the KSA is small (i.e. 1/256 if the array was indeed uniformly random at the end of KSA).
One of the troubles with RC4 is that the j is computed in each step based on a secret key and not "chosen uniformly at random" as suggested by Knuth. The second problem is that even if j was chosen uniformly at random, this method of producing a random array does not work. This causes the state of RC4 to be somewhat predictable, having high correlations with the secret key. Once an adversary can estimate some bytes of the state after KSA, he can also predict the output of initial few bytes of RC4 PRGA. For example, the first such result was shown by Mantin and Shamir who showed that the second byte of RC4 PRGA is highly biased to be the byte 0. If the PRGA output was uniformly random, one would expect that any byte could be produced with probability 1/256. However, this result showed that the second byte is 0 with probability 1/128 (i.e. double the probability), and this is independent of the secret key.
Later, many other biases of RC4 were shown. Many of them are listed on the wikipedia page: RC4.
The crucial theme underlying most of the weaknesses of RC4 is that the initial few output bytes of RC4 are highly correlated to the secret key.
Next

So, this was the explanation and implementation of RC4! Next we will have a random generation tool, and then, the highly historically influential block cipher called DES or the Data Encryption Standard.
Bye till then.
:-)
Post-17 Ended.

Input String
Key String (upto 256 characters)
Encrypt Decrypt
done
Output String