宣传一波 更好的阅读体验 👉 个人blog

一、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

1. 然后用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

1. 因为对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

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

RC4的逻辑结构（例子）

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

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

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}$$

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

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)互换:

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

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))$$

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++代码

代码

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

#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。