# RC4 as pencil & paper cipher

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.