常见加解密算法02 - RC4算法分析

RC4是一种广泛使用的流密码，它以其简洁和速度而闻名。区别于块密码，流密码特点在于按位或按字节来进行加密。

RC4由Ron Rivest在1987年设计，尽管它的命名看起来是第四版，实际上它是第一个对外发布的版本。

RC4算法的实施过程简洁明了，主要包括初始化和生成密钥流这两个阶段。

下面我们就一边解析算法，一边分析其代码实现。

初始化

该阶段的核心任务是利用一个可变长度的密钥来初始化一张S盒，即一个包含0至255所有字节的256长度数组。初始化步骤如下：

初始填充S盒，按顺序排列0至255的数值。
使用密钥对S盒进行置换。每个S盒中的元素都会根据密钥中的字节进行一定的交换。这个过程叫做密钥调度算法（KSA）。

说的形象一点就是：在桌子上有256个小盒子（从0到255编号），初始时每个盒子里面的数字和它的编号一样。现在，你开始根据密钥来交换这些盒子里面的数字，直到所有的盒子都被重新排列。

经过多轮置换，这256个数字的顺序就变得无规律。将此与洗牌对比，虽然结果看似随机，实则完全受密钥控制。

现在，我们来看一下代码实现：

private static void initAndPermute(char[] byteKey) {
    if (byteKey.length > 256 || byteKey.length < 1) {
        System.out.println("Key length must be between 1 to 256 chars");
    } else {
        // Creation of initial state and key bytes
        keylength = byteKey.length;
        for (int i = 0; i < 256; i++) {
            S[i] = i;
            K[i] = byteKey[i % keylength];
        }
        // Permuting state bytes based on values of key bytes
        int j = 0;
        for (int i = 0; i < 256; i++) {
            j = (j + S[i] + K[i]) % 256;
            int temp = S[i];
            S[i] = S[j];
            S[j] = temp;
        }
    }
}

第一个 for 循环里面，就是初始化 S 盒。我们还看到同时也给 K 数组赋值了，这里说明了一个问题，K 的长度大于 256 之后，后面的其实没用，所以我们的密钥不用写太长，除非写一个变种算法。

看第二个循环，j = (j + S[i] + K[i]) % 256; 我们把它看成一个数学表达式 j = f(i)，这个表达式最终会生成一个 0-255 之间的一个数字 j，然后将 i 与 j 位置进行交换，这样就扰乱了 S 盒的数字顺序。

操作 (PRGA)

在操作阶段，RC4生成伪随机流，称为密钥流。这个密钥流会与明文按位异或来生成密文。同样，将密钥流与密文按位异或，可以得到原始明文。操作过程如下：

初始化两个指针i和j（都开始于0）。
在每次操作中，i递增1，j加上S盒在i位置的值，并使用新的j值来更新S盒中的元素位置。
选取i和j指向的两个元素，将它们加起来，并根据这个总和得到S盒中的某个元素作为密钥流的一部分。
重复此过程，直到生成了足够长的密钥流，可以与明文进行异或操作。

上面的步骤比较难以理解，但是我们利用数学的思想来看：

首先，定义两个变量 i 与 j，然后给它们赋值，i = f(i), j = f(i, j) ，然后再定义一个变量 key，key = f2(i, j) 。这个key就是根据 S 盒生成的密钥流，只要 S 的顺序固定，那么生成的密钥流就是固定的。有了密钥流，那么我们就可以与明文做异或操作。

看代码：

private static char[] encryptRC4(char[] plainText) {
    char[] cipherText = new char[plainText.length];
    int i = 0;
    int j = 0;
    int key;
    int plainTextLen = 0;
    while (plainTextLen < plainText.length) {
        // Key generation
        i = (i + 1) % 256;
        j = (j + S[i]) % 256;
        int temp = S[i];
        S[i] = S[j];
        S[j] = temp;
        key = S[(S[i] + S[j]) % 256];
        // Encryption
        cipherText[plainTextLen] = (char) (plainText[plainTextLen] ^ key);
        plainTextLen++;
    }
    return cipherText;
}

有的小伙伴可能想得多一点，既然是使用异或做操作，那么加密算法其实就是解密算法！

是的，异或这个东西很神奇， x ^ y ^ y 还是 x。既然加密算法保证了 S 一定的情况下，生成的 key 是一样的，所以解密算法可以直接使用加密算法。

C 实现

#define N 256   // 2^8

void swap(unsigned char *a, unsigned char *b) {
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

int KSA(char *key, unsigned char *S) {

    int len = strlen(key);
    int j = 0;

    for(int i = 0; i < N; i++)
        S[i] = i;

    for(int i = 0; i < N; i++) {
        j = (j + S[i] + key[i % len]) % N;

        swap(&S[i], &S[j]);
    }

    return 0;
}

int PRGA(unsigned char *S, char *plaintext, unsigned char *ciphertext) {

    int i = 0;
    int j = 0;

    for(size_t n = 0, len = strlen(plaintext); n < len; n++) {
        i = (i + 1) % N;
        j = (j + S[i]) % N;

        swap(&S[i], &S[j]);
        int rnd = S[(S[i] + S[j]) % N];

        ciphertext[n] = rnd ^ plaintext[n];

    }

    return 0;
}

int RC4(char *key, char *plaintext, unsigned char *ciphertext) {

    unsigned char S[N];
    KSA(key, S);

    PRGA(S, plaintext, ciphertext);

    return 0;
}