Implementation of RC4 algorithm
RC4 is a symmetric stream cipher and variable key length algorithm. This symmetric key algorithm is used identically for encryption and decryption such that the data stream is simply XORed with the generated key sequence. The algorithm is serial as it requires successive exchanges of state entries based on the key sequence. The algorithm works in two phases:
Key Scheduling Algorithm(KSA):
- It is used to generate a State array by applying a permutation using a variable-length key consisting of 0 to 256 bytes.
- The state vector is identified as S[0], S[1]…. S[255] is initialized with {0, 1, 2, …, 255}. The key K[0], K[1], …., K[255] can be of any length from 0 to 256 bytes and is used to initialize permutation S. Each K[I] and S[I] is a byte.
- K is a temporary array if the length of the key is 256 bytes copy it to K else after copying the remaining positions of K are filled with repeated Key Values until full.
S[] is permutation of 0, 1, ..., 255
key[] contains N bytes of key
for i = 0 to 255
S[i] = i
// Selects a keystream byte from
// the table
K[i] = key[i (mod N)]
i++
j = 0
for i = 0 to 255
j = (j + S[i] + K[i]) mod 256
// Swaps elements in the current
// lookup table
swap(S[i], S[j])
i = j = 0
Pseudo-Random Generation Algorithm(PRGA): It used to generate keystream byte from State vector array after one more round of permutation.
Keystream Generation(i := 0, j := 0 )
while Generating Output:
i = (i + 1) mod 256
j = (j + S[i]) mod 256
swap(S[i], S[j])
t = (S[i] + S[j]) mod 256
keystreamByte = S[t]
At each iteration, swap elements in table
and select keystream byte
Then, perform XOR between the keystream generated and the plain text for encryption.
Follow the same procedure as above for decryption, taking cipher text in place of plain text everywhere.
Examples:
Input: plain text = 001010010010, key = 101001000001, n= 3
Output:
cipher text = 110011100011
decrypted text = 001010010010Input: plain text = 1111000000001111, key = 0101010111001010, n= 4
Output:
cipher text = 0011011110100010
decrypted text = 1111000000001111
Below is the implementation of the above approach with a detailed output of all the important steps involved:
#include <bits/stdc++.h>
using namespace std;
// Global variables
string plain_text = "001010010010";
string key = "101001000001";
int n = 3;
vector<int> pt, key_list, key_stream, cipher_text,
original_text;
// Function to convert binary string to decimal
int binaryToDecimal(string binary)
{
int decimal = 0;
int base = 1;
for (int i = binary.size() - 1; i >= 0; i--) {
if (binary[i] == '1')
decimal += base;
base = base * 2;
}
return decimal;
}
// Function to convert decimal to binary string
string decimalToBinary(int decimal)
{
string binary = "";
while (decimal > 0) {
binary = (decimal % 2 == 0 ? "0" : "1") + binary;
decimal /= 2;
}
while (binary.size() < n)
binary = "0" + binary;
return binary;
}
// Function to perform KSA
void KSA(vector<int>& S)
{
int j = 0;
int N = S.size();
for (int i = 0; i < N; i++) {
j = (j + S[i] + key_list[i]) % N;
swap(S[i], S[j]);
cout << i << " ";
for (int s : S)
cout << s << " ";
cout << endl;
}
cout << "\nThe initial permutation array is : ";
for (int s : S)
cout << s << " ";
cout << endl;
}
// Function to perform PRGA
void PRGA(vector<int>& S)
{
int N = S.size();
int i = 0, j = 0;
for (int k = 0; k < pt.size(); k++) {
i = (i + 1) % N;
j = (j + S[i]) % N;
swap(S[i], S[j]);
int t = (S[i] + S[j]) % N;
key_stream.push_back(S[t]);
cout << k << " ";
for (int s : S)
cout << s << " ";
cout << endl;
}
cout << "Key stream : ";
for (int ks : key_stream)
cout << ks << " ";
cout << endl;
}
// Function to perform XOR
void XOR(vector<int>& text, vector<int>& key_stream)
{
for (int i = 0; i < text.size(); i++) {
int result = key_stream[i] ^ text[i];
text[i] = result;
}
}
// Function for encryption
void encryption()
{
// Convert plain_text and key to decimal
for (int i = 0; i < plain_text.size(); i += n) {
pt.push_back(
binaryToDecimal(plain_text.substr(i, n)));
key_list.push_back(
binaryToDecimal(key.substr(i, n)));
}
// Initialize state vector array
vector<int> S(pow(2, n));
iota(S.begin(), S.end(), 0);
// Perform KSA
KSA(S);
// Perform PRGA
PRGA(S);
// Perform XOR
XOR(pt, key_stream);
// Convert encrypted text to bits form
cipher_text = pt;
}
// Function for decryption
void decryption()
{
// Initialize state vector array
vector<int> S(pow(2, n));
iota(S.begin(), S.end(), 0);
// Perform KSA
KSA(S);
// Perform PRGA
PRGA(S);
// Perform XOR
XOR(cipher_text, key_stream);
// Convert decrypted text to bits form
original_text = cipher_text;
}
int main()
{
cout << "Plain text : " << plain_text << endl;
cout << "Key : " << key << endl;
cout << "n : " << n << endl;
cout << "\nS : ";
for (int i = 0; i < pow(2, n); i++)
cout << i << " ";
cout << endl;
cout << "Plain text ( in array form ): ";
for (int i = 0; i < plain_text.size(); i += n)
cout << binaryToDecimal(plain_text.substr(i, n))
<< " ";
cout << endl;
cout << "Key list : ";
for (int i = 0; i < key.size(); i += n)
cout << binaryToDecimal(key.substr(i, n)) << " ";
cout << endl;
cout << "\nKSA iterations : \n";
encryption();
cout << "\nCipher text : ";
for (int i : cipher_text)
cout << decimalToBinary(i);
cout << endl;
cout << "\n--------------------------------------------"
"-------------\n";
cout << "\nKSA iterations : \n";
decryption();
cout << "\nDecrypted text : ";
for (int i : original_text)
cout << decimalToBinary(i);
cout << endl;
return 0;
}
import java.util.*;
public class RC4 {
static int n = 3;
static String plain_text = "001010010010";
static String key = "101001000001";
static List<Integer> S = new ArrayList<>();
static List<Integer> key_list = new ArrayList<>();
static List<Integer> pt = new ArrayList<>();
static List<Integer> key_stream = new ArrayList<>();
static List<Integer> cipher_text = new ArrayList<>();
static List<Integer> original_text = new ArrayList<>();
public static void main(String[] args)
{
encryption();
System.out.println(
"---------------------------------------------------------");
decryption();
}
// Function for encryption
public static void encryption()
{
System.out.println("Plain text : " + plain_text);
System.out.println("Key : " + key);
System.out.println("n : " + n);
// The initial state vector array
for (int i = 0; i < Math.pow(2, n); i++) {
S.add(i);
}
System.out.println("S : " + S);
key_list = convertToDecimal(key);
pt = convertToDecimal(plain_text);
System.out.println("Plain text ( in array form ): "
+ pt);
// Making key_stream equal to length of state vector
int diff = S.size() - key_list.size();
if (diff != 0) {
for (int i = 0; i < diff; i++) {
key_list.add(key_list.get(i));
}
}
System.out.println("Key list : " + key_list);
// Perform the KSA algorithm
KSA();
// Perform PGRA algorithm
PGRA();
// Performing XOR between generated key stream and
// plain text
XOR();
}
// Function for decryption of data
public static void decryption()
{
S.clear();
key_list.clear();
pt.clear();
key_stream.clear();
// The initial state vector array
for (int i = 0; i < Math.pow(2, n); i++) {
S.add(i);
}
key_list = convertToDecimal(key);
pt = convertToDecimal(plain_text);
// Making key_stream equal to length of state vector
int diff = S.size() - key_list.size();
if (diff != 0) {
for (int i = 0; i < diff; i++) {
key_list.add(key_list.get(i));
}
}
// KSA algorithm
KSA();
// Perform PRGA algorithm
PGRA();
// Perform XOR between generated key stream and
// cipher text
do_XOR();
}
// KSA algorithm
public static void KSA()
{
int j = 0;
int N = S.size();
// Iterate over the range [0, N]
for (int i = 0; i < N; i++) {
j = (j + S.get(i) + key_list.get(i)) % N;
// Update S[i] and S[j]
Collections.swap(S, i, j);
System.out.println(i + " " + S);
}
System.out.println(
"The initial permutation array is : " + S);
}
// PGRA algorithm
public static void PGRA()
{
int N = S.size();
int i = 0, j = 0;
// Iterate over [0, length of pt]
for (int k = 0; k < pt.size(); k++) {
i = (i + 1) % N;
j = (j + S.get(i)) % N;
// Update S[i] and S[j]
Collections.swap(S, i, j);
System.out.println(k + " " + S);
int t = (S.get(i) + S.get(j)) % N;
key_stream.add(S.get(t));
}
// Print the key stream
System.out.println("Key stream : " + key_stream);
}
// Perform XOR between generated key stream and plain
// text
public static void XOR()
{
for (int i = 0; i < pt.size(); i++) {
int c = key_stream.get(i) ^ pt.get(i);
cipher_text.add(c);
}
// Convert the encrypted text to bits form
String encrypted_to_bits = "";
for (int i : cipher_text) {
encrypted_to_bits += String.format(
"%0" + n + "d",
Integer.parseInt(
Integer.toBinaryString(i)));
}
System.out.println("Cipher text : "
+ encrypted_to_bits);
}
// Perform XOR between generated key stream and cipher
// text
public static void do_XOR()
{
for (int i = 0; i < cipher_text.size(); i++) {
int p = key_stream.get(i) ^ cipher_text.get(i);
original_text.add(p);
}
// Convert the decrypted text to the bits form
String decrypted_to_bits = "";
for (int i : original_text) {
decrypted_to_bits += String.format(
"%0" + n + "d",
Integer.parseInt(
Integer.toBinaryString(i)));
}
System.out.println("Decrypted text : "
+ decrypted_to_bits);
}
// Convert to decimal
public static List<Integer>
convertToDecimal(String input)
{
List<String> list = new ArrayList<>();
List<Integer> decimalList = new ArrayList<>();
for (int i = 0; i < input.length(); i += n) {
list.add(input.substring(
i, Math.min(input.length(), i + n)));
}
for (String s : list) {
decimalList.add(Integer.parseInt(s, 2));
}
return decimalList;
}
}
# Python3 program for the above approach
# of RC4 algorithm
# Function for encryption
def encryption():
global key, plain_text, n
# Given text and key
plain_text = "001010010010"
key = "101001000001"
# n is the no: of bits to
# be considered at a time
n = 3
print("Plain text : ", plain_text)
print("Key : ", key)
print("n : ", n)
print(" ")
# The initial state vector array
S = [i for i in range(0, 2**n)]
print("S : ", S)
key_list = [key[i:i + n] for i in range(0, len(key), n)]
# Convert to key_stream to decimal
for i in range(len(key_list)):
key_list[i] = int(key_list[i], 2)
# Convert to plain_text to decimal
global pt
pt = [plain_text[i:i + n] for i in range(0, len(plain_text), n)]
for i in range(len(pt)):
pt[i] = int(pt[i], 2)
print("Plain text ( in array form ): ", pt)
# Making key_stream equal
# to length of state vector
diff = int(len(S)-len(key_list))
if diff != 0:
for i in range(0, diff):
key_list.append(key_list[i])
print("Key list : ", key_list)
print(" ")
# Perform the KSA algorithm
def KSA():
j = 0
N = len(S)
# Iterate over the range [0, N]
for i in range(0, N):
# Find the key
j = (j + S[i]+key_list[i]) % N
# Update S[i] and S[j]
S[i], S[j] = S[j], S[i]
print(i, " ", end="")
# Print S
print(S)
initial_permutation_array = S
print(" ")
print("The initial permutation array is : ",
initial_permutation_array)
print("KSA iterations : ")
print(" ")
KSA()
print(" ")
# Perform PGRA algorithm
def PGRA():
N = len(S)
i = j = 0
global key_stream
key_stream = []
# Iterate over [0, length of pt]
for k in range(0, len(pt)):
i = (i + 1) % N
j = (j + S[i]) % N
# Update S[i] and S[j]
S[i], S[j] = S[j], S[i]
print(k, " ", end="")
print(S)
t = (S[i]+S[j]) % N
key_stream.append(S[t])
# Print the key stream
print("Key stream : ", key_stream)
print(" ")
print("PGRA iterations : ")
print(" ")
PGRA()
# Performing XOR between generated
# key stream and plain text
def XOR():
global cipher_text
cipher_text = []
for i in range(len(pt)):
c = key_stream[i] ^ pt[i]
cipher_text.append(c)
XOR()
# Convert the encrypted text to
# bits form
encrypted_to_bits = ""
for i in cipher_text:
encrypted_to_bits += '0'*(n-len(bin(i)[2:]))+bin(i)[2:]
print(" ")
print("Cipher text : ", encrypted_to_bits)
encryption()
print("---------------------------------------------------------")
# Function for decryption of data
def decryption():
# The initial state vector array
S = [i for i in range(0, 2**n)]
key_list = [key[i:i + n] for i in range(0, len(key), n)]
# Convert to key_stream to decimal
for i in range(len(key_list)):
key_list[i] = int(key_list[i], 2)
# Convert to plain_text to decimal
global pt
pt = [plain_text[i:i + n] for i in range(0, len(plain_text), n)]
for i in range(len(pt)):
pt[i] = int(pt[i], 2)
# making key_stream equal
# to length of state vector
diff = int(len(S)-len(key_list))
if diff != 0:
for i in range(0, diff):
key_list.append(key_list[i])
print(" ")
# KSA algorithm
def KSA():
j = 0
N = len(S)
# Iterate over the range [0, N]
for i in range(0, N):
j = (j + S[i]+key_list[i]) % N
# Update S[i] and S[j]
S[i], S[j] = S[j], S[i]
print(i, " ", end="")
print(S)
initial_permutation_array = S
print(" ")
print("The initial permutation array is : ",
initial_permutation_array)
print("KSA iterations : ")
print(" ")
KSA()
print(" ")
# Perform PRGA algorithm
def do_PGRA():
N = len(S)
i = j = 0
global key_stream
key_stream = []
# Iterate over the range
for k in range(0, len(pt)):
i = (i + 1) % N
j = (j + S[i]) % N
# Update S[i] and S[j]
S[i], S[j] = S[j], S[i]
print(k, " ", end="")
print(S)
t = (S[i]+S[j]) % N
key_stream.append(S[t])
print("Key stream : ", key_stream)
print(" ")
print("PGRA iterations : ")
print(" ")
do_PGRA()
# Perform XOR between generated
# key stream and cipher text
def do_XOR():
global original_text
original_text = []
for i in range(len(cipher_text)):
p = key_stream[i] ^ cipher_text[i]
original_text.append(p)
do_XOR()
# convert the decrypted text to
# the bits form
decrypted_to_bits = ""
for i in original_text:
decrypted_to_bits += '0'*(n-len(bin(i)[2:]))+bin(i)[2:]
print(" ")
print("Decrypted text : ",
decrypted_to_bits)
# Driver Code
decryption()
let n = 3;
let plain_text = "001010010010";
let key = "101001000001";
let S = [];
let key_list = [];
let pt = [];
let key_stream = [];
let cipher_text = [];
let original_text = [];
// Function for encryption
function encryption() {
console.log("Plain text : " + plain_text);
console.log("Key : " + key);
console.log("n : " + n);
// The initial state vector array
for (let i = 0; i < Math.pow(2, n); i++) {
S.push(i);
}
console.log("S : " + S);
key_list = convertToDecimal(key);
pt = convertToDecimal(plain_text);
console.log("Plain text (in array form): " + pt);
// Making key_stream equal to length of state vector
let diff = S.length - key_list.length;
if (diff !== 0) {
for (let i = 0; i < diff; i++) {
key_list.push(key_list[i]);
}
}
console.log("Key list : " + key_list);
// Perform the KSA algorithm
KSA();
// Perform PGRA algorithm
PGRA();
// Performing XOR between generated key stream and plain text
XOR();
}
// Function for decryption of data
function decryption() {
S = [];
key_list = [];
pt = [];
key_stream = [];
// The initial state vector array
for (let i = 0; i < Math.pow(2, n); i++) {
S.push(i);
}
key_list = convertToDecimal(key);
pt = convertToDecimal(plain_text);
// Making key_stream equal to length of state vector
let diff = S.length - key_list.length;
if (diff !== 0) {
for (let i = 0; i < diff; i++) {
key_list.push(key_list[i]);
}
}
// KSA algorithm
KSA();
// Perform PRGA algorithm
PGRA();
// Perform XOR between generated key stream and cipher text
do_XOR();
}
// KSA algorithm
function KSA() {
let j = 0;
let N = S.length;
// Iterate over the range [0, N]
for (let i = 0; i < N; i++) {
j = (j + S[i] + key_list[i]) % N;
// Update S[i] and S[j]
[S[i], S[j]] = [S[j], S[i]];
console.log(i + " " + S);
}
console.log("The initial permutation array is: " + S);
}
// PGRA algorithm
function PGRA() {
let N = S.length;
let i = 0,
j = 0;
// Iterate over [0, length of pt]
for (let k = 0; k < pt.length; k++) {
i = (i + 1) % N;
j = (j + S[i]) % N;
// Update S[i] and S[j]
[S[i], S[j]] = [S[j], S[i]];
console.log(k + " " + S);
let t = (S[i] + S[j]) % N;
key_stream.push(S[t]);
}
// Print the key stream
console.log("Key stream : " + key_stream);
}
// Perform XOR between generated key stream and plain text
function XOR() {
for (let i = 0; i < pt.length; i++) {
let c = key_stream[i] ^ pt[i];
cipher_text.push(c);
}
// Convert the encrypted text to bits form
let encrypted_to_bits = "";
for (let i of cipher_text) {
encrypted_to_bits += i.toString(2).padStart(n, "0");
}
console.log("Cipher text : " + encrypted_to_bits);
}
// Perform XOR between generated key stream and cipher text
function do_XOR() {
for (let i = 0; i < cipher_text.length; i++) {
let p = key_stream[i] ^ cipher_text[i];
original_text.push(p);
}
// Convert the decrypted text to the bits form
let decrypted_to_bits = "";
for (let i of original_text) {
decrypted_to_bits += i.toString(2).padStart(n, "0");
}
console.log("Decrypted text : " + decrypted_to_bits);
}
// Convert to decimal
function convertToDecimal(input) {
let list = [];
let decimalList = [];
for (let i = 0; i < input.length; i += n) {
list.push(input.substring(i, Math.min(input.length, i + n)));
}
for (let s of list) {
decimalList.push(parseInt(s, 2));
}
return decimalList;
}
// Main function
function main() {
encryption();
console.log(
"---------------------------------------------------------"
);
decryption();
}
// Calling the main function
main();
Output
Plain text : 001010010010 Key : 101001000001 n : 3 S : [0, 1, 2, 3, 4, 5, 6, 7] Plain text ( in array form ): [1, 2, 2, 2] Key list : [5, 1, 0, 1, 5, 1, 0, 1] KSA iterations : 0 [5, 1, 2, 3, 4, 0, 6, 7] 1 [5, 7, 2, 3, 4, 0, 6, 1] 2 [5, 2, 7, 3, 4, 0, 6, 1] 3 [5, 2, 7, 0, 4, 3, 6, 1] 4 [5, 2, 7, 0, 6, 3, 4, 1] 5 [5, 2, 3, 0, 6, 7, 4, 1] 6 [5, 2, 3, 0, 6, 7, 4, 1] 7 [1, 2, 3, 0, 6, 7, 4, 5] The initial permutation array is : [1, 2, 3, 0, 6, 7, 4, 5] PGRA iterations : 0 [1, 3, 2, 0, 6, 7, 4, 5] 1 [1, 3, 6, 0, 2, 7, 4, 5] 2 [1, 3, 6, 2, 0, 7, 4, 5] 3 [1, 3, 6, 2, 0, 7, 4, 5] Key stream : [7, 1, 6, 1] Cipher text : 110011100011 --------------------------------------------------------- KSA iterations : 0 [5, 1, 2, 3, 4, 0, 6, 7] 1 [5, 7, 2, 3, 4, 0, 6, 1] 2 [5, 2, 7, 3, 4, 0, 6, 1] 3 [5, 2, 7, 0, 4, 3, 6, 1] 4 [5, 2, 7, 0, 6, 3, 4, 1] 5 [5, 2, 3, 0, 6, 7, 4, 1] 6 [5, 2, 3, 0, 6, 7, 4, 1] 7 [1, 2, 3, 0, 6, 7, 4, 5] The initial permutation array is : [1, 2, 3, 0, 6, 7, 4, 5] Key stream : [7, 1, 6, 1] PGRA iterations : 0 [1, 3, 2, 0, 6, 7, 4, 5] 1 [1, 3, 6, 0, 2, 7, 4, 5] 2 [1, 3, 6, 2, 0, 7, 4, 5] 3 [1, 3, 6, 2, 0, 7, 4, 5] Decrypted text : 001010010010