一、RC4 算法介绍

RC4是由麻省理工学院的 Rivest 开发的,他也是RS4的开发者之一。RC4 的突出优点是在软件中很容易实现。RC4 可能是世界上使用最广泛的序列密码,它已应用于 MicrosoftWindows、Lotus Notes 和其他软件应用程序中,应用于安全套接字层(SSL,Secure SocketsLayer)以保护因特网的信息流，还应用于无线系统以保护无线链路的安全等。

RC4 是一个典型的基于非线性数组变换的序列密码。它以一个足够大的数组为基础,对其进行非线性变换，产生密钥序列，一般把这个大数组称为 S盒。RC4的S盒大小随参数n的值变化而变化,理论上来说,S盒长度为 $N=2^n$”个元素,每个元素n比特。通常n=8,这也是本书示例所选取值,此时,生成共有$ 256(=2^8)$个元素的数组 S。RC4 包含两个处理过程:一个是密钥调度算法(KSA,Key-Scheduling Algorithm),用来置乱S盒的初始排列;另一个是伪随机生成算法(PRGA,Pseudo RandomGeneration Algorithm)用来输出随机序列并修改S的当前排列顺序

流程

1. KSA首先初始化S,即S[i]=i(i=0~255),同时建立一个临时数组向量 T(|T|=256),如果种子密钥K的长度为 256 字节(|K|=256),则直接将 K 赋给T,否则,若种子密钥K的长度(记为|K|)小于|T|,则将K的值赋给T的前|K|个元素,并不断重复加载K的值直到 T被填满。这些操作可概括如下:

for i := 0 to 255 do
begin 
    S[i]:=i;
    T[i]:=k[i mod |K|];
end

2. 然后用T产生S的初始置换,从 S[O]到 S[255],对每个S[i],根据 T的值将S[i]与S中的另一个字节对换。概括如下:

j:=0;
for i:= 0 to 255 do
begin
    j:=(j + S[i] + T[i]) (mod 256);
	swap(S[i], S[j]); // 交换s[i]和s[j]
end

3. 因为对S的操作仅是交换,所以唯一的改变就是位置,S仍然遍历0~255 的所有元素最后,利用 PRGA生成密钥流。从S中随机选取一个元素输出，并置换 S 以便下一次取，选取过程取决于索引i和j,下面描述选取密钥序列的过程:

i,j:=0
while(true)
    i:=i + 1(mod 256);
	j:= j + S[i](mod 256);
	swap(S[i], S[j]);
	t:= S[i] + S[j] (mod 256);
	k := S[t];
end

4. 加密时，将k的值与明文字节异或;解密时,将 k的值与密文字节异或。

RC4的逻辑结构（例子）

1. 下面以元素长为3比特(即n=3)的RC4 为例来演示它的工作过程。显然,3位RC4的所有操作是对$2^3=8$取模。数组 S只有$2^3=8$个元素,初始化为:

2. 接着选取一个密钥,该密钥是由 0~7的数以任意顺序组成的。例如,选取5、6、7作为密钥。该密钥如下填人临时数组 T中:

3. 然后执行 S数组的初始置换,以i=0和j=0开始。使用更新公式后，j为:

$$\begin{array}{rl}j& =[0+S(0)+T(0)](mod8)\\ & =(0+0+5)mod8\\ & =5\end{array}$$

4. 因此,S数组的第一个操作是将 S(0)与 S(5)互换

5. 索引i加1后，j的下一个值为:

$$\begin{array}{rl}j& =[5+S(1)+T(1)](mod8)\\ & =(5+1+6)mod8\\ & =4\end{array}$$

6. 即将S数组的S(1)与S(4)互换:

7. 当该循环执行完后,数组 S就被随机化:

8. 下面数组 S就可以用来生成随机数序列了。从j=0和i=0开始,RC4 计算第一个随机数的过程如下:

$$\begin{gathered} i=(i+1)mod8=(0+1)mod8=1 \\ j=[j+S(i)]mod8=[0+S(1)]mod8=[0+4]mod8=4 \\ swap(S(1),S(4)) \end{gathered}$$

9. 然后计算和k:

$$\begin{gathered} t=[S(j)+S(i)]mod8=[S(4)+S(1)]mod8=(1+4)mod8=5 \\ k=S(t)=S(5)=6 \end{gathered}$$

10. 第一个随机数为 6,其二进制表示为 110。反复进行该过程,直到生成的密钥序列长度等于明文的长度。

二、C++代码

代码

核心代码上面的伪代码给过了，这里直接带进去就行了（￣︶￣）↗

#include<iostream>
#include<string>

using namespace std;

const int N = 1e6+10;

// 在C++中，char类型通常被视为有符号类型，其取值范围为-128到127
//无符号整数的取值范围为0到255
unsigned char s[256]; // S盒子

string text; // 明文密文统一用text
string secret_key; // 密钥

void init() // KSA初始化S盒
{
    unsigned key_len = secret_key.size();
    unsigned char T[256] = {0}; // 临时数组向量
    for(unsigned int i = 0; i < 256; i ++ ) 
    {
        s[i] = i;
        T[i] = secret_key[i % key_len];
    }
    for(int i = 0, j = 0; i < 256; i ++ )
    {
        j = (j + s[i] + T[i]) % 256;
        swap(s[i], s[j]);
    }
}

void encrypt_encode() // 加密或者解密都是再次经过这个函数
{
    init();
    unsigned int len = text.length();
    unsigned char k, i = 0, j = 0, t;
    for(unsigned int h = 0; h < len; h ++ )
    {
        i = (i + 1) % 256;
		j = (j + s[i]) % 256;
		swap(s[i], s[j]);
		t = (s[i] + s[j]) % 256;
		k = s[t];
		text[h] ^= k;
    }
}

int main()
{
    cout << "请输入明文" << endl;
    cin >> text;
    cout << "请输入密钥" << endl;
    cin >> secret_key;
    encrypt_encode();
    cout << "加密后的密文：" << text << endl;
    encrypt_encode();
    cout << "解密后的明文：" << text << endl;
    
    return 0;
}

结果

请输入明文
123
请输入密钥
123
加密后的密文：b聦
解密后的明文：123

三、小结

1. 加密时,将 k的值与明文字节异或;解密时,将k 的值与密文字节异或。
2. 为了保证安全强度,目前的 RC4 至少使用 128 位密,以防止穷举搜索攻击。
3. RC4 算法可看成一个有限状态自动机,把 S表和索引的具体取值称为 RC4的一个状态:$T=(S_0,S_1...S_{255},i,j)$。对状态 T进行非线性变化,产生出新的状态,并输出密钥序列中的一个字节k,大约有$$2^{1700}(256!\times 256^2)$$种可能状态。
4. 用大的数据表 S 和字长来实现这个思想是可能,如可定义 16 位 RC4。