RC4 is a well-known stream cipher, extremely simple —I’d say minimalist— and strong enough to be still used, spite of some documented weaknesses which, mostly, fall on the key schedule.

RC4 uses a 256-symbol alphabet, so it operates at byte level. The main object of RC4 is a S-box, S, which contains a permutation of the alphabet driven by a key through a key schedule. Then, each iteration modifies the permutation and yields a byte used to mask the plaintext. The pseudocode:

i := 0
j := 0
while GeneratingOutput {
    i := (i + 1) mod 256
    j := (j + S[i]) mod 256
    swap values of S[i] and S[j]
    T := S[(S[i] + S[j]) mod 256]
    output T
}

This simplicity allows us to build a pencil-and-paper (p&p) cipher based on its design.

Algorithm

Our version will use a 26-symbol alphaber, the common English one with letters A-Z. Each letter have internally a numeric value from 0 to 25: A = 0, B = 1, ... Z = 25. This value can be used to mask the plaintext by adding the cipher output mod 26; also, addition modulo 26 can be arranged with a table, so crossing both summands in a row/column the value is quickly given.

We need a paper strip where we write two instances of the alphabet. We have also a deck of 26 cards with a different letter drawn on each one; or a set of 26 scrabble pieces with all possible letters.

The key will be taken by shuffling the deck; so a it is a random permutation of the alphabet; for example:

 R Q G N Y P H I T M D B C E J K Z F A U X W O V L S

Now we put the key over the strip, fully coincident with one of the instances of the alphabet (the first letter of the key beside the A letter of the alphabet). The first letter of both are marked with a pointer, say a bean or a coin:

      ·
      R Q G N Y P H I T M D B C E J K Z F A U X W O V L S
... Z A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
      ·

Procedure

Now we move the upper pointer one position to the right (in case of overflow go to the begining) and rise the pointed letter (Q); then we move the lower pointer to the position represented by this one on the lower alphabet, and rise the upper letter (Z). This can be summarize in the following figure:

        Q                             Z
      R · G N Y P H I T M D B C E J K   F A U X W O V L S
... Z A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
                                      ·

Both letters [Q,Z] are interchanged and their values added modulo 26: $16 + 25 \mod 26 = 15$ (this addition can be done with a table, as mentioned), so Q + Z = P. We look for P in the lower alphabet and selects the upper letter as output:

        ·                           *  
      R Z G N Y P H I T M D B C E J K Q F A U X W O V L S
... Z A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
                                    ^ ·

So, we get K as the output and we use it to mask the first plaintext letter.

The last step is to shift the paper strip (lower alphabet) in such a way that an A is placed besides the lower pointer:

        ·                              
      R Z G N Y P H I T M D B C E J K Q F A U X W O V L S
... J K L M N O P Q R S T U V W X Y Z A B C D E F G H I J K ...
                                      ·

Then we are ready for the next iteration.

Pseudocode

If we translate to computer language this procedure, it shows a tiny deviation from standard RC4 algorithm as shown earlier in this post. This is the new algorithm:

i := 0
j := 0
while GeneratingOutput {
    k : = j
    i := (i + 1) mod 26
    j := (j + S[i]) mod 26
    swap values of S[i] and S[j]
    T := S[(S[i] + S[j] + k) mod 26]
    output T
}

I think this modification adds nothing (good or bad) to the security of the algorithm but makes it friendly por p&p implementation.

Key schedule

In this p&p version there is no need of a key schedule. The alphabet permutation can be transmitted as a key. Nevertheless it is possible to use a numeric key to obtain a permutation from it. The number of permutations is $26!$ and, if you want to set the initial positions of counter as part of the key then $(26!)26^2$ is the number of all possible combinations. So $\log_2 \left( 26! \times 26^2 \right) \simeq 98\,\mathrm{bits}$; a random number of 98 bits can be used to calculate an initial state setting.

A small challenge

Now I propose a small challenge: with the key given in the example I encrypted a text as:

ZDNSG FRZFF KJFTS QIGEY C 

What is the original plaintext?

Conclusion

Due to the simple RC4 design it is possible to build over it a p&p cipher with a typical 26-letter alphabet. The key space is 98 bit large —not too bad for a toy cipher— and key schedule is not needed. But other weakness of original RC4 (say, the imperfect random oracle behavior) can be amplified because of the shrinked alphabet.


P.S. 2016-11-04 Johannes Bauer gently provided a nice python program to test the algorithm.