一、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被填满。这些操作可概括如下:
1
2
3
4
5
for i := 0 to 255 do
begin
    S[i]:=i;
    T[i]:=k[i mod |K|];
end
  1. 然后用T产生S的初始置换,从 S[O]到 S[255],对每个S[i],根据 T的值将S[i]与S中的另一个字节对换。概括如下:
1
2
3
4
5
6
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
  1. 因为对S的操作仅是交换,所以唯一的改变就是位置,S仍然遍历0~255 的所有元素最后,利用 PRGA生成密钥流。从S中随机选取一个元素输出，并置换 S 以便下一次取，选取过程取决于索引i和j,下面描述选取密钥序列的过程:
1
2
3
4
5
6
7
8
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
  1. 加密时，将k的值与明文字节异或;解密时,将 k的值与密文字节异或。

RC4 的逻辑结构（例子）

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

1.png

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

2.png

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

$$
\begin{aligned}
j &= [0 + S(0) + T(0)](mod 8) \
& = (0 + 0 + 5) mod 8 \
& = 5
\end{aligned}
$$

3.png

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

4.png

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

$$
\begin{aligned}
j &= [5 + S(1) + T(1)](mod 8) \
& = (5 + 1 + 6) mod 8 \
& = 4
\end{aligned}
$$

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

5.png

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

6.png

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

$$
i = (i + 1) mod 8 = (0 + 1) mod 8 = 1 \
j = [j + S(i)]mod 8 = [0 + S(1)]mod 8 = [0 + 4]mod 8 = 4\
swap(S(1), S(4))
$$

7.png

  1. 然后计算和k:

$$
t=[S(j)+S(i)]mod8 =[S(4)+S(1)]mod 8=(1+4)mod8=5\
k=S(t)=S(5)=6
$$

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

二、C++代码

代码

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#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;
}

结果

1
2
3
4
5
6
请输入明文
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。