Building RC4 Keystream Generator: A Hands-On Tutorial for CSCI 181

Introduction to RC4 and the Assignment

RC4 (Rivest Cipher 4) is a stream cipher widely used in protocols like WEP and TLS. In this tutorial, we'll build a keystream generator as required by Homework 3 for CSCI 181. The program takes three inputs: integer n (word size in bits), integer l (plaintext length in characters), and a secret key as a bit array. It outputs a keystream of length n * l. We'll implement two key functions: DecimalToBinary and ConvertBitArraytoInt, with thorough comments. This tutorial is designed to help you understand the inner workings of RC4 and prepare you for similar stream cipher tasks in cybersecurity courses.

Understanding the Helper Functions

DecimalToBinary Function

The DecimalToBinary function converts a decimal integer to a binary array of length n. For example, DecimalToBinary(100, 8) returns [0,1,1,0,0,1,0,0]. This is essential for converting key bytes or internal state values into bit form. Here's a Python implementation:

def DecimalToBinary(number, n):
    """
    Converts a decimal integer to a binary array of length n.
    Args:
        number (int): The decimal number to convert.
        n (int): The length of the output array.
    Returns:
        list: Array of bits (most significant bit first).
    """
    binary = []
    for i in range(n-1, -1, -1):
        bit = (number >> i) & 1
        binary.append(bit)
    return binary

This function uses bit shifting to extract each bit, ensuring the output length is exactly n. If the number requires fewer bits, leading zeros are added.

ConvertBitArraytoInt Function

The ConvertBitArraytoInt function takes a bit array and n, and converts every n bits into a decimal integer. For instance, ConvertBitArraytoInt([1,0,0,0,0,0,1,1,1,0,0,1], 3) returns [4, 0, 7, 1]. This is used to convert the secret key (given as bits) into decimal values for the RC4 initialization.

def ConvertBitArraytoInt(k, n):
    """
    Converts a bit array into an array of integers, each representing n bits.
    Args:
        k (list): Array of bits.
        n (int): Number of bits per integer.
    Returns:
        list: Array of decimal integers.
    """
    result = []
    for i in range(0, len(k), n):
        chunk = k[i:i+n]
        value = 0
        for bit in chunk:
            value = (value << 1) | bit
        result.append(value)
    return result

This function ensures the key is properly formatted for the RC4 Key Scheduling Algorithm (KSA).

Implementing the RC4 Keystream Generator

The core RC4 algorithm consists of two phases: Key Scheduling Algorithm (KSA) and Pseudo-Random Generation Algorithm (PRGA). The KSA initializes a permutation array S of size 2^n using the key. The PRGA generates keystream bytes by swapping elements in S.

Step 1: Key Scheduling Algorithm (KSA)

First, we initialize the S array with values 0 to 2^n - 1. Then we permute it based on the key.

def KSA(key, n):
    """
    Key Scheduling Algorithm for RC4.
    Args:
        key (list): Array of integers (key bytes).
        n (int): Word size in bits.
    Returns:
        list: Permuted array S of length 2^n.
    """
    size = 1 << n  # 2^n
    S = list(range(size))
    j = 0
    for i in range(size):
        j = (j + S[i] + key[i % len(key)]) % size
        S[i], S[j] = S[j], S[i]
    return S

Step 2: Pseudo-Random Generation Algorithm (PRGA)

The PRGA generates keystream bytes by iterating and swapping.

def PRGA(S, n, length):
    """
    Pseudo-Random Generation Algorithm for RC4.
    Args:
        S (list): Initialized permutation array.
        n (int): Word size in bits.
        length (int): Number of bytes to generate.
    Returns:
        list: Keystream bytes (list of integers).
    """
    i = 0
    j = 0
    keystream = []
    size = len(S)
    for _ in range(length):
        i = (i + 1) % size
        j = (j + S[i]) % size
        S[i], S[j] = S[j], S[i]
        t = (S[i] + S[j]) % size
        keystream.append(S[t])
    return keystream

Step 3: Generating the Keystream Bit Array

Finally, we combine everything to output the keystream as a bit array of length n * l.

def generate_keystream(n, l, key_bits):
    """
    Generates RC4 keystream as a bit array.
    Args:
        n (int): Word size in bits.
        l (int): Plaintext length in characters.
        key_bits (list): Secret key as bit array.
    Returns:
        list: Keystream bit array of length n*l.
    """
    # Convert key_bits to decimal key bytes
    key = ConvertBitArraytoInt(key_bits, n)
    # KSA
    S = KSA(key, n)
    # PRGA to generate l bytes (each byte is n bits)
    keystream_bytes = PRGA(S, n, l)
    # Convert each byte to n-bit binary and flatten
    keystream_bits = []
    for byte in keystream_bytes:
        bits = DecimalToBinary(byte, n)
        keystream_bits.extend(bits)
    return keystream_bits

Example: Encrypting a Message

Suppose we want to encrypt the message M = "BACDDAH" with key K = [1,2,3,6] when n=3. First, convert the key to bits: each decimal number to 3 bits: 1->001, 2->010, 3->011, 6->110. So key_bits = [0,0,1,0,1,0,0,1,1,1,1,0]. Then run generate_keystream(3, 7, key_bits) to get a keystream of length 21 bits. The keystream (as bits) would be something like: [0,1,0,1,0,0,1,1,0,1,0,1,0,0,1,1,0,1,0,0,1] (example). Then XOR each plaintext character's 3-bit ASCII representation with the keystream to get ciphertext bits.

Part (c) and (d): Larger Example

For n=8, l=24, and a long key (80 bits given), run the generator to produce a keystream of 192 bits. Then XOR with the given ciphertext to recover the plaintext. For instance, if the keystream is [1,0,1,0,...] and ciphertext is [1,1,1,0,...], XOR yields the plaintext bits, which can be grouped into 8-bit ASCII characters. The plaintext might be something like "HELLO WORLD" or any meaningful message. This demonstrates RC4's use in real encryption.

Understanding CFB and CBC Modes

CFB Mode Error Propagation

In CFB mode, two bit errors in C2 affect the decryption of C2 and C3. Specifically, Bob will correctly decrypt blocks M1, M4-M10, but M2 and M3 will be completely wrong because the feedback chain is broken.

CBC Mode and CPA Security

If the IV is reused in CBC mode, an attacker can determine if two messages are identical. For example, if Eve knows M and M' and sees C and C', she can ask Bob to encrypt M (or M') and compare the first block ciphertext. If the IV is fixed, the first block ciphertext will match, revealing which is which. This breaks CPA security.

Conclusion

By implementing these functions, you gain a deep understanding of RC4 and stream ciphers. Remember to comment your code thoroughly for clarity. Good luck with your CSCI 181 assignment!