RC4算法

明文^密钥key=密文

关键在于密钥key的形成

一、RC4相关变量

1、密钥流：

密文=明文^密钥流(密钥流长度等于明文)

2、状态向量S：

长度为256，S[0],S[1].....S[255]。每个单元都是一个字节，算法运行的任何时候，S都包括0-255的8比特数的排列组合，只不过值的位置发生了变换。

3、临时向量T：

长度为256，每个单元也是一个字节。如果密钥的长度是256字节，就直接把密钥的值赋给T，否则，轮转地将密钥的每个字节赋给T。

4、密钥K：

长度为1-256字节，注意密钥的长度keylen与明文长度、密钥流的长度没有必然关系，通常密钥的长度16字节（128比特）。

二、简版RC4(看不懂就先看步骤三来理解)

1、先初始化状态向量S（256个字节，用来作为密钥流生成的种子1）
按照升序，给每个字节赋值0,1,2,3,4,5,6…,254,255

2、初始密钥（由用户输入），长度任意
如果输入长度小于256个字节，则进行轮转，直到填满

例如输入密钥的是1,2,3,4,5 , 那么填入的是1,2,3,4,5,1,2,3,4,5,1,2,3,4,5…

由上述轮转过程得到256个字节的向量T（用来作为密钥流生成的种子2）

3、开始对状态向量S进行置换操作（用来打乱初始种子1）
按照下列规则进行

从第零个字节开始，执行256次，保证每个字节都得到处理

j = 0;

for (i = 0 ; i < 256 ; i++){

j = (j + S[i] + T[i]) mod 256;

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

}

这样处理后的状态向量S几乎是带有一定的随机性了

4、最后是秘钥流的生成与加密，假设明文字节数是datalength=1024个字节（当然可以是任意个字节）

i=0;

j=0;

while(datalength–){//相当于执行1024次，这样生成的秘钥流也是1024个字节

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];这里的K就是当前生成的一个秘钥流中的一位

//可以直接在这里进行加密，当然也可以将密钥流保存在数组中，最后进行异或就ok

data[]=data[]^k； //进行加密，"^"是异或运算符

}

解密异或两次就是原文，所以只要把密钥流重新拿过来异或一次就能得到原文了

三、RC4包含的两个算法

1、KSA 密钥调度算法(不懂看下第二张图片例子，看了就懂了)

编程看图一，理解看图二。

实现对原始数据的随机化排列，即打乱S表。

步骤：初始化S表，选取S表子序列作为密钥填充到密钥数组R中，循环256次，交换S~i~和S~j~

2、PRGA 伪随机密钥序列生成算法、随机选取数据作为密钥字节，并输出密钥流

从S中随机选取元素作为密钥流字节，同时修改数组S的排序，以便下一次密钥流的选取。

步骤：S~i~和S~j~交换得到新数组，根据交换完成的数组计算h和k(k为密钥，从S中选，h为选择k时数组的下标)

注意生成的是二进制位，将二进制与明文字符异或运算输出。

四、RC4加密流程(1和2对应上面的第一步)

1、初始化S和T

初始化S盒：直接构造一个S[256]，遍历0-255，然后创建临时T[256]，用于存储种子秘钥，长度不够循环填充直到T被填满，根据T[i]将S[i]与S中的另外一个字节对换，对S的操作仅仅是交换，唯一改变的是位置，但里面的元素是没变的还是0-255；

for i=0 to 255 do
    S[i]=i;
    T[i]=K[ I mod keylen ];

2、初始排列S

j=0;
for i=0 to 255 do
    j= ( j+S[i]+T[i])mod256;
    swap(S[i],S[j]);

3、产生密钥流

由于异或运算的对合性，RC4加密解密使用同一套算法:

i,j=0;

for r=0 to len do  //r为明文长度，r字节

i=(i+1) mod 256;

    j=(j+S[i])mod 256;

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

    t=(S[i]+S[j])mod 256;

    k[r]=S[t];

自己话小结：

先置换S~i~和S~j~256次，j生产的规则为j=j+S~1~+R~1~，得到S
然后再置换S~i~和S~j~，得到新的S，根据新S计算h，h为S下标，S~h~即为k。
最后将k与明文异或。

C代码：

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef unsigned longULONG;

/*定义初始数组和秘钥数组
  参数1是一个256长度的char型数组，定义为: unsigned char sBox[256];
  参数2是密钥，其内容可以随便定义：char key[256];
  参数3是密钥的长度，Len = strlen(key);*/
void rc4_init(unsigned char*s, unsigned char*key, unsigned long Len)
{
    int i, j = 0;
    char k[256] = {0};
    unsigned char tmp = 0;
    for(i = 0; i<256; i++)
    {
        s[i] = i;                   //给初始数组s赋值
        k[i] = k[i % Len];           //填充秘钥数组k
    }
    for(i = 0; i<256; i++)
    {
        j = (j + s[i] + k[i]) % 256;   //打乱初始数组s的顺序
        tmp = s[i];                    
        s[i] = s[j];
        s[j] = tmp;
    }
}

/*加密
  参数1是上边rc4_init函数中，被搅乱的S-box;
  参数2是需要加密的数据data;
  参数3是data的长度.*/
//注意递增的是明文数组Data[k],i会自增，j也会随着s[i]而改变
void rc4_crypt(unsigned char*s, unsigned char*Data, unsigned long Len)
{
    int i = 0,j = 0,t = 0;
    unsigned long k = 0;
    unsigned char tmp;
    for(k = 0; k < Len; k++)
    {
        i = (i + 1) % 256;
        j = (j + s[i]) % 256;
        tmp = s[i];
        s[i] = s[j];
        s[j] = tmp;
        t = (s[i] + s[j]) % 256;
        Data[k] ^= s[t]; 
    }
}

/*主函数*/
int main()
{
    unsigned char s[256] = { 0 }; unsigned char s2[256] = { 0 };
    char key[10] = {"tallmewhy"};
    char pData[42] ={0xF5, 0x8C, 0x8D, 0xE4, 0x9F, 0xA5, 0x28, 0x65, 0x30, 0xF4, 
        0xEB, 0xD3, 0x24, 0xA9, 0x91, 0x1A, 0x6F, 0xD4, 0x6A, 0xD7, 
        0x0B, 0x8D, 0xE8, 0xB8, 0x83, 0x4A, 0x5A, 0x6E, 0xBE, 0xCB, 
        0xF4, 0x4B, 0x99, 0xD6, 0xE6, 0x54, 0x7A, 0x4F, 0x50, 0x14,
        0xE5, 0xEC};             //512保证缓冲区足够大
    unsigned long len = strlen(pData);
    int i;

    printf("pData=%s\n", pData);
    printf("key=%s,length=%d\n\n", key, strlen(key));
    rc4_init(s,(unsigned char*)key,strlen(key));   //完成初始化
    printf("完成对s[i]的初始化，如下：\n\n");
    //输出初始化后的S-box
    for(i = 0; i<256; i++)
    {
        printf("%02X", s[i]);                  //输出16进制。%02X是C语言中的格式控制符，用于将整数以16进制输出，并且宽度为2位，不足则左侧补0。
        if(i && (i+1) %16 == 0)putchar('\n');  //换行
    }
    printf("\n\n");

    for(i = 0; i<256; i++)      //用s2[i]暂时保留经过初始化的s[i]，因为加解密时会改变原来的s，所以用s2来进行加解密
    {
        s2[i] = s[i];
    }

    printf("已经初始化，现在加密：\n\n");
    rc4_crypt(s, (unsigned char*)pData, len);
    printf("pData=%s\n\n",pData);

    printf("已经加密，现在解密：\n\n");
    rc4_crypt(s2,(unsigned char*)pData, len);
    printf("pData=%s\n\n",pData);
    return 0;
}

运行结果

五、识别和魔改

1:逆向特征

出现很多循环条件都<256，也出现多次%256，最后还进行了异或等。

首先根据原理我们可以看到会初始化一个256字节的数组

其次会将一个key也填充到数组中

函数的话大概率都是两个参数,一个是key 一个是keylen

2:魔改RC4
其实RC4魔改还是比较难的，稍有改变，整个算法就完全不同了。因此，大多数赛题将rc4与其他算法进行组合来加密flag

常见变化位置：

密钥经过上一步的其他加密后传入

s盒内部数据固定

rc4加密后数据进行重加密

注：若转载请注明大神论坛来源（本贴地址）与作者信息。