What is RC 4 Algorithm?

RC4(Rivest Cipher) is a stream cipher designed in 1987 by Ron Rivest. It is a variable key size with byte-oriented operations.

The important components of RC4 are:

Key Input: It creates an eight-bit numbergenerally termed byte that is called a cipher.
Key-Scheduling: It helps in generating a random stream of keys for the given input size.
Pseudo-random-key generation: It helps in making the generated keystream as complex as possible.

Pseudo code

//Intialization
for i=0 to 255 do
S[i]=i; 
T[i]=k[i mod keylen] 
// Key Scheduling 
j=0
for i=0 to 255 do
j=(j+S[i]+T[i]) mod 256;
swap(S[i] and S[j])
end  for
// Pseudo-Random-Key-Generation 
while(true)
i=i+1
j=(j+S[i])mod256;
swap(S[i]and S[j]);
t=(S[i]+S[j]) mod256;
key stream=S[t]
end for

Procedure

In this, an initial vector was created and named S-array with entries [0,1,2,.....254,255] totaling to 256-bytes in length.
A temporary vector named T-array is created.
If the length of the key is 256, the bytes key is assigned to T.
Else, the length of(K-len) bytes elements are copied from K, and K is repeated as many times to fill the array.
We use T-array to produce the Initial permutation of S with S[0] to S[255].
Each S[i] in the algorithm swaps it with another byte in S-array.
The output of this is a Keystream.

Encryption and decryption

Encryption - (Plain Text)XOR(Keystream).

Decryption-(CipherText)XOR(Keystream).

Uses

It is used in data communication and networking protocols.
RC4 is used in the Secure Sockets Layer/Transport Layer Security(SSL/TLS), which provides communication between Web browsers and users.

Explanation of the algorithm

Lets try to understand the working of this algorithm with an simple example:

Assume an S-array of length is S=[0 1 2 3 4 5 6 7]
Assume given Key an Plain Text as:

K=[1 2 3 6]
PT=[1 2 2 2]

Intialize the state vector ‘S’ and temporary vector T. S is intialized and S[i]=i and T is intialized and key is repeated until the length of S-array is met.

T=[1 2 3 6 1 2 3 6]

Key Scheduling

Now as,
i=0 to 7 do
j=(j+S[i]+T[i]) mod 8
swap( S[i] ,S[j])

If i=0

j=(0+0+1) mod8=1
swap(S[0],S[1])
S=[1 0 2 3 4 5 6 7]

For i=1

j=(1+0+2) mod8=3
swap(S[1],S[3])
S=[1 3 2 0 4 5 6 7]

For i=2

j=(3+2+3) mod8=0
swap(S[2],S[0])
S=[2 3 1 0 4 5 6 7]

For i=3

j=(0+0+6) mod8=6
swap(S[3],S[6])
S=[2 3 1 6 4 5 0 7]

For i=4

j=(6+4+1) mod8=3
swap(S[4],S[3])
S=[2 3 1 4 6 5 0 7]

For i=5

j=(3+5+2) mod8=2
swap(S[5],S[2])
S=[2 3 5 4 6 1 0 7]

For i=6

j=(2+0+3) mod8=5
swap(S[6],S[5])
S=[2 3 5 4 6 0 1 7]

For i=7

j=(5+7+6) mod8=2
swap(S[7],S[2])
S=[2 3 7 4 6 0 1 5]

Now finally the S is obtained

S=[2 3 7 4 6 0 1 5]

Pseudo-Random-Key-Generation

Now as,
i,j=0
while(true)
i=(i+1) mod 8
j=(j+S[i])mod 8
swap( S[i] ,S[j])
t=(S[i]+S[j]) mod 8;
k=S(t)

First iteration

i=(0+1) mod 8=1
j=(0+3)mod 8=3
swap( S[1] ,S[3])
t=(4+3) mod 8=7
k=S(7)=5

Second iteration

S=[2 4 7 3 6 0 1 5]
i=(1+1) mod 8=2
j=(3+7)mod 8=2
swap( S[2] ,S[2])
t=(7+7) mod 8=6
k=S(6)=1

Third iteration

S=[2 4 7 3 6 0 1 5]
i=(2+1) mod 8=3
j=(2+3)mod 8=5
swap( S[3] ,S[2])
S=[2 4 7 0 6 3 1 5]
t=(0+3) mod 8=3
k=S(3)=0

Fourth iteration

S=[2 4 7 3 6 0 1 5]
i=(3+1) mod 8=4
j=(5+6)mod 8=3
swap( S[4] ,S[3])
S=[2 4 7 6 0 3 1 5]
t=(0+6) mod 8=6
k=S(6)=1
The Key Stream obtained is =[5 1 0 1]

Example

def KSA(key):
  S = list(range(256))
  j=0
  key_length=len(key)
  for i in range(256):
    j=(j+S[i]+key[i% key_length]) % 256
    S[i],S[j]= S[j],S[i]
  return S

def PRGA(S,n):
    i=0
    j=0
    key=[]

    while n>0:
     n=n-1
     i=(i+1)%256
     j=(j+S[i])%256
     S[i],S[j]=S[j],S[i]
     K=S[(S[i]+S[j])% 256]
     key.append(K)
    return key
     
key ="Hello"
PT= " MISSION ACCOMPLISHED"
import numpy as np
def prep_key_array(s):
   return[ord(c)for c in s]
key=prep_key_array(key)
keystream=np.array(PRGA(KSA(key),len(PT)))
print(keystream)

Free Resources

License: Creative Commons-Attribution-ShareAlike 4.0 (CC-BY-SA 4.0)