RC4算法总结_rc4算法总结
RC4算法总结由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“rc4算法总结”。
一、RC4算法原理
RC4算法的原理很简单，包括初始化算法（KSA）和伪随机子密码生成算法（PRGA)两大部分。
RC4产生一个伪随机比特流（a keystream），加密的时候，把它跟明文进行比特级别的异或处理，解密时进行一样的步骤（因为异或操作是对称的）。（这个类似于Vernam cipher，只不过后者不使用伪随机比特流而直接使用随机比特流）。为了产生keystream，本密码算法使用时需要两个数据的私有空间来保存内部状态：
1.总共256个字节的序列（下面用“S“代替）
2.两个8比特的索引指针（下面用“i”和“j”代替）
比特流序列的初始化是根据key的长度（key的长度通常在40到256比特之间），使用key-scheduling 算法来进行的（KSA)，一旦完成了初始化，比特流就可以根据伪随机生成算法(PRGA)来产生。
（1）The key-scheduling algorithm(KSA)key-scheduling算法用来初始化数组“S”中的字节序列，“keylength”定义了key的字节长度，可能的范围是[1, 256]，典型的值是5到16之间，相应的key长度就是40-128比特。首先，数组“S”被初始化成identity permutation（身份鉴别的序列），随后在PRGA的算法中进行256为周期的循环列举出来，每次处理的方式都是一样的，是联合key的字节进行的。
for i from 0 to 255 S[i] := i endfor
j := 0
for i from 0 to 255
j:=(j + S[i] + key[i mod keylength])mod 256 swap(&S[i],&S[j])endfor
（2）伪随机生成算法（PRGA）
对于尽可能多的每个列举过程，PRGA算法修改 内部的状态并输出keystream的一个字节。在每次循环中，PRGA把i加一，并把i所指向的S值加到j上去，然后交换S[i]和S[j]的值，最后 输出S[i]和S[j]的和(取256的模)对应的S值。至多经过256次，S每个位置上的值都被交换一次。
i := 0 j := 0
while GeneratingOutput: i :=(i + 1)mod 256 j :=(j + S[i])mod 256 swap(&S[i],&S[j])output S[(S[i] + S[j])mod 256] endwhile
二、RC4算法实现
实现一
假设S-box的长度为256，密钥长度为Len。
KSA部分：
先来看看算法的初始化部分（用C代码表示）：
其中，参数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 =0, j = 0, k[256] = {0};
for(i=0;i
{
s[i]=i;
k[i]=key[i%Len];
}
for(i=0;i
{
j=(j+s[i]+k[i])%256;
swap(s,x,y);
} } 在初始化的过程中，密钥的主要功能是将S-box搅乱，i确保S-box的每个元素都得到处理，j保证S-box的搅乱是随机的。而不同的S-box在经过伪随机子密码生成算法的处理后可以得到不同的子密钥序列，将S-box和明文进行xor运算，得到密文，解密过程也完全相同。
PRGA部分：
再来看看算法的加密部分（用C代码表示）：
其中，参数1是上边rc4_init函数中，被搅乱的S-box;
参数2是需要加密的数据data;
参数3是data的长度.void rc4_crypt(unsigned char *s, unsigned char *Data, unsigned long Len)
{
int x = 0, y = 0, t = 0, i = 0;
for(i=0;i
{
x=(x+1)%256;
y=(y+s[x])%256;
t=(s[x]+s[y])%256;swap(s,x,y);
Data[i] ^= s[t];
} }
最后，在main函数中，调用顺序如下：
void main()
{
unsigned char s[256] = {0};//S-box
unsigned char key[256] = {”just for test“};
unsigned char pData[512] = ”这是一个用来加密的数据Data“;ULONG len = strlen(pData);printf(”pData = %sn“,pData);printf(”key = %s, length = %dn“,key,strlen(key));
rc4_init(s,(unsigned char *)key,strlen(key));//初始化
rc4_crypt(s,(unsigned char *)pData,len);//加密
printf(”pData = %snn“,pData);
rc4_crypt(s,(unsigned char *)pData,len);//解密
printf(”pData = %snn",pData);}
实现二（对实现一的改进）
许多流加密算法都是基于Linear feedback shift register（LFSRs, 寄存器线性反馈移位）, 虽然在硬件上有效率但是在软件实现上却可能比较慢。RC4的设计避免了LFSRs的使用，对于软件实现是相当理想的，它只需字节操作，使用了256字节的 状态数组（从S[0]到S[255]）, k字节的key内存（从key[0]到key[k-1]），整数i,j和k。进行256的取模操作可以用255的字节AND来进行（在有些平台上，只需简单地进行字节相加，忽略掉溢出即可）。
/*交换数组s中的两个元素*/ void swap(unsigned char *s, unsigned int i, unsigned int j){ unsigned char temp = s[i];s[i] = s[j];s[j] = temp;}
/*KSA算法初始化s-box*/ void rc4_init(unsigned char *s, unsigned char *key, unsigned long length){ unsigned int i = 0, j = 0;unsigned char temp = 0;for(i = 0;i
s[i] = i;} for(i = 0;i
} } /*和255进行逻辑与运算相当于对256求模*/ j =(j+s[i]+key[i%length])&255;swap(s, i, j);/*PRGA算法生成伪随机序列*/ void rc4_crypt(unsigned char *s, unsigned char *data, unsigned long length){ int x = 0, y = 0, t = 0, i = 0;for(i=0;i
x =(x+1)&255;
y =(y+s[x])&255;
swap(s, x, y);
t =(s[x]+s[y])&255;
data[i] ^= s[t];} }
