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.