RC4

历史

RC4是Ron Rivest于1987年为RSA Security 设计的流密码，是面向字节运算的变长密钥流密码。该算法使用随机排列。分析表明，改密码的周期可能完全大于$10^100$。该密码可在软件中快速运行。RC4被用于WiFi保护访问（WPA）协议中，RC4已被RSA Security 保留为商业密钥。

RC4算法：从1到256字节（8到2048位）的变长密钥用于初始化元素为S[0],S[1],S[2],……,S[255]的256字节状态向量S。任何时候，S包含从0到255的所有8位数字的排列。对于加密和解密操作，以系统方式选择255项之一来由S生成字节k。随着每个k值的生成，S中的这些项将再次被置换。

初始化S

首先，将S中的各项按升序设置为0到255之间的值，即S[0] = 0,S[1] = 1,S[2] = 2,……,S[255] = 255。同时，创建一个临时向量T。若密钥K的长度为256字节，则将K赋给T。否则，对于长度为keylen字节的密钥，从K复制T的前keylen个元素，然后根据需要重复K次，直到填满T。概括如下：

for (int i = 0; i <= 255; i ++)
{
    S[i] = i;
    T[i] = K[i % keylen];
}

接下来，使用T生成S的初始置换。这涉及从S[0]开始并运行到S[255]，且对每个S[i]，根据下面的T[i]方案，将S[i]与S中的另一个字节交换：

int j = 0;
for (int i = 0; i <= 255; i ++)
{
    j = (j + S[i] + T[i]) % 256;
    swap(S[i], S[j]);
}

因为只是对S中的元素进行交换，相当于重排列，所以S中仍然包含从0到255的所有数字。

流生成

初始化S向量后，就不再使用输入密钥。流生成涉及循环遍历所有元素S[i]，并且对每个S[i]，根据S的当前配置规定的方案，将S[i]与S中的另一个字节交换。到达S[255]后，继续该过程，从S[0]重新开始：

while(1)
{
    int i = (i + 1) % 256;
    int j = (j + S[i]) % 256;
    swap(S[i], S[j]);
    int t = (S[i] + S[j]) % 256;
    k = S[t];
}

加密时，将k值与明文的下一个字节异或。解密时，将k值与密文的下一个字节异或。

RC4原理图

RC4的强度

RC4存在弱点，已经禁止使用了。

加解密代码：

#include<iostream>
#include<string>
using namespace std;

int s[256];
int t[256];

string key="0123456789";

void swap(int* s1,int* s2){
    int temp=*s1;
    *s1=*s2;
    *s2=temp;
}

void init(){
    //初始化s和t数组
    for(int i=0;i<256;i++){
        s[i]=i;
        t[i]=atoi(&(const char)(key.at(i%key.length()))); // t保存char的地址
    }

    int j=0;
    for(int i=0;i<256;i++){
        j=(j+s[j]+t[j])%256;
        swap(s+i,s+j);  // 打乱S数组
    }
}

void encode(int* start,int length){
    int pos=0;
    int i=0,j=0;
    while(pos++<length){
        i=(i+1)%256;
        j=(j+s[i])%256;
        swap(s+i,s+j); //再次打乱

        int temp=(s[i]+s[j])%256;
        int k=s[temp];//这里取值
        *start^=k;//异或
        start++;
    }
}
void decode(int* start,int length){
    encode(start,length);//重复做一遍即可解密
}

void print(int* a,int length,string startMessage=""){
    cout<<startMessage<<" ";
    for(int i=0;i<length;i++){
        cout<<*(a+i)<<" ";
    }
    cout<<endl;
}

int main(){
    init();
    int a[10]={0,1,2,3,4,5,6,7,8,9};
    print(a,10,"原数组");
    encode(a,10);
    print(a,10,"加密后");
    init();
    decode(a,10);
    print(a,10,"解密后");
}