RC4加密算法学习
算法分析
背景
RC4（来自Rivest Cipher 4的缩写）是一种流加密算法，密钥长度可变。它加解密使用相同的密钥，因此也属于对称加密算法。RC4是有线等效加密（WEP）中采用的加密算法，也曾经是TLS可采用的算法之一。 ----wiki https://zh.wikipedia.org/zh-hans/RC4
加密(解密)原理
RC4由伪随机数生成器和异或运算组成。RC4的密钥长度可变，范围是[1,255]。RC4一个字节一个字节地加解密。给定一个密钥，伪随机数生成器接受密钥并产生一个S盒。S盒用来加密数据，而且在加密过程中S盒会变化。
由于异或运算的对合性，RC4加密解密使用同一套算法
下面用C语言实现:
首先看加密过程的几个基本变量
- S-Box就是S盒，是一个256长度的char型数组，每个单元都是一个字节，算法运行的任何时候，S都包括0-255的8比特数的排列组合，只不过值的位置发生了变换
- 密钥K char key[256] 密钥的长度keylen与明文长度，密钥流的长度没有必然关系
- 临时向量k，长度也为256，每个单元也是一个字节。如何密钥的长度是256字节，就直接把密钥的值赋给k，否则，轮转地将每个字节赋给k
(1)初始化:
包含三个参数
参数1是一个256长度的char型数组，定义为:unsigned char sBox[256];
参数2是密钥，其内容可以随便定义: char key[256]；
参数3是密钥长度，Len=strlen(key);
初始化长度为256的S盒。第一个for循环将0到255的互不重复的元素装入S盒。第二个for循环根据密钥打乱S盒。
i确保S-box的每个元素都得到处理，j保证S-box的搅乱是随机的
856
void rc4_init(unsigned char *s,unsigned char *key,unsigned long Len)
{
int i=0,j=0;
char k[256]={0};
unsigned char tmp=0;
for(i=0;i<256;i++)
{
s[i]=i;
k[i]=key[i%Len]; //把key循环赋给k[]里
}
//打乱SBox,只是其中的元素进行了随机交换
for(i=0;i<256;i++)
{
j=(j+s[i]+k[i])%256; //!这是一个伪随机数
tmp=s[i];
s[i]=s[j];
s[j]=tmp;
}
}(2)加解密
包含三个参数
参数1是上边rc4_init函数中被搅乱的S-box
参数2是需要加密的数据data
参数3是data的长度
每收到一个字节，就进行while循环，通过一定的算法定位S盒中的一个元素，并与输入字节异或，得到k。循环中还改变了S盒。如果输入的是明文，输出的就是密文；如果输入的是密文，输出的就是明文。
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;
//实际上就是Data的每个字节与Sbox的一个伪随机位置进行字节异或，进行一次还改变S盒子
for(k=0;k<Len;k++)
{
//通过一定算法生成伪随机数,再打乱S-box
i=(i+1)%256;
j=(j+s[i])%256;
tmp=s[i];
s[i]=s[j]; //交换s[x]和s[y]
s[j]=tmp;
//再生成一个随机位置，对明文进行异或
t=(s[i]+s[j])%256;
Data[k]^=s[t];
}
}(3)主函数
int main()
{
unsigned char s[256]={0},s2[256]={0};
char key[256]={"HelloWorld"};
char pData[512]="HelloWorld";
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,len);
printf("完成对S[i]的初始化，如下:\n\n");
//输出S[i]
for(i=0;i<256;i++)
{
printf("%02X",s[i]);
if(i&&(i+1)%16==0)
{
putchar('\n');
}
}
printf("\n\n");
//用s2[i]暂时保存初始化过的s[i],用来解密
for(i=0;i<256;i++)
{
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);
}输出结果
pData=HelloWorld
key=HelloWorld,length=10
完成对S[i]的初始化，如下:
32121C207C79CFAFBC29D5BE2DDC162C
3E1A97663F8C98915115C199638DE968
8B226C4D43C557E208C056ED190C5440
10460B839BC4ABC9CE49EF7414B40D01
4C0EA082FAA31D23424B531FE7049DD6
62D2EE319FDA73EB7A703BEC59DFB907
77F2BD02D9457536275E41A4901E6D7D
E4373A06872F47EA5D816588FECAB70F
AD5F4ADBCBA16ABABFD348508F177EB2
9592B12BA2615C3C869EE03864B8DD58
0596C2FFA70334D8C37FB5256F94AE00
71B03576BBF769215B288E553DE326A8
DEF6D7670A934E13F1E8306E72FBCD1B
89AAE17BD1D0B6809A44FDACA539F4F5
2EE6C65A852A094FD4F3788A60F833F0
F9B39CA918E56BFCC7CC84241152A6C8
已经初始化，现在加密:
pData=7��K�l��
已经加密，现在解密:
pData=HelloWorld逆向分析
rc4共有两个函数 sub_E41000,sub_E410E0
下面来具体分析这两个函数，具体解释都放在图里了，看图即可
sub_E41000初始化
函数头如下，三个值
sub_E41000(&v6, &v10, strlen(&v10));
对应上面源码
void rc4_init(unsigned char *s,unsigned char *key, unsigned long Len)
伪代码
sub_E410E0 加密
sub_E410E0(&v6, v3, strlen(v3));
对应上面的源码:
void rc4_crypt(unsigned char *s,unsigned char *Data,unsigned long Len)
伪代码
int __usercall sub_E410E0@<eax>(int result@<eax>, int a2, unsigned int a3)
{
int v3; // ecx
int v4; // esi
unsigned int v5; // edi
unsigned __int8 v6; // dl
v3 = 0;
v4 = 0;
v5 = 0;
if ( a3 )
{
do
{
v3 = (v3 + 1) % 256;
v6 = *(v3 + result);
v4 = (v6 + v4) % 256;
*(v3 + result) = *(v4 + result);
*(v4 + result) = v6;
*(v5++ + a2) ^= *((v6 + *(v3 + result)) % 256 + result); // Data[k]^=s[t];
}
while ( v5 < a3 );
}
return result;
}魔改RC4
RC4内部取随机数的算法可以进行魔改，关键要识别特征，逆向算法或者根据直接拿密文用原加密程序直接异或出明文
常见变化位置
- 密钥经过上一步的其他加密后传入
- s盒内部数据固定
- rc4加密后数据进行重加密
总结
识别特征，内部多次限制256次循环，mod256,以及读取数据strlen的特点
参考网址：
https://zh.wikipedia.org/zh-hans/RC4
https://zh.wikipedia.org/wiki/S%E7%9B%92
https://ctf-wiki.github.io/ctf-wiki/crypto/streamcipher/special/rc4/