Question: Short note on RC4.
1

Mumbai University > COMPS > Sem 7 > Cryptography and System Security

Marks: 5 M

Year: May 13

 modified 3.2 years ago  • written 3.2 years ago by Sayali Bagwe • 2.2k
2
• Rivest Cipher 4 (RC4) is a stream cipher and is optimized for software implementation. It produces a keystream byte at each step.
• RC4 is based on the concept of state. At each moment a state of 256 bytes is active from which one of the bytes is randomly selected to serve as the key for encryption.
• The RC4 algorithm is simple, because it is essentially just a lookup table containing a permutation of all possible 256 byte values.
• The crucial trick that makes it a strong cipher is that each time a byte of keystream is produced, the lookup table is modified in such a way that the table always contains a permutation of ${0,1,2,..., 255}$.
• Initialization: Initialization is done in two steps-

i. In the first step, the state is initialized to values $0, 1, …, 255$. A key array $K[0], K[1]…, K[255]$ is also created. If the secret key has exactly 256 bytes, the bytes are copied to the K array otherwise the bytes are repeated until the K array is filled.

for $(i = 0 to 255)$

{

$S[i] = i$

$K[i] = key[i mod Keylength]$

}

ii. In the second step, the initialized state goes through a permutation based on the value of the bytes in K[i]. The key byte is used only in this step to define which elements are to be swapped. The state bytes are shuffled after this step.

$j = 0$

for $(i = 0 to 255)$

{

$j = (j + S[i] + K[i]) mod 256$

$swap (S[i],S[j])$

}

$i=j=0$

• Key Stream Generation: The keys in the key stream, the K’s are generated one by one. First the state is permuted on the values of state elements and the values of two individual variables i and j. second the values of two state elements in positions i and j are used to define the index of the state element that serves as K. The following code is used:

$i = (i + l) mod 256$

$j = (j + S[i]) mod 256$

$swap(S[i],S[j])$

$k = (S[i] + S[j]) mod 256$

$keystreamByte = S[k]$

• The output i.e. keystreamByte is a single byte that can be XORed with plaintext to encrypt or XORed with ciphertext to decrypt.
• The RC4 algorithm can be viewed as a self-modifying lookup table and is elegant, simple, efficient in software.RC4 is used in many applications, including SSL and WEP.