从RFC6229中理解RC4算法

一、RC4概述

RC4是在1987年提出，和DES算法一样。是一种对称加密算法，也就是说使用的密钥为单钥（或称为私钥）。但不同于DES算法的是。RC4不是对明文进行分组处理，而是通过字节流的方式依次加密明文中的每个字节，同样的，解密的时候也是依次对密文中的每个字节进行解密。

RC4算法的一个特点是可变密钥，可变范围在1256字节，也就是8位2048位

二、RC4算法框架

RC4算法简单、易于描述，主要使用一个S表来生成密钥流，分为密钥调度算法（KSA）和伪随机数生成算法（PRGA）两个步骤。其中KSA使用原始密钥生成S表，PRGA利用S表来产生密钥流序列。

上面已经说过了，原始密钥K是可变的，而加密单位的话以一个字节为准。

1 密钥调度算法（Key Scheduling Algorithm，KSA）

密钥调度算法的作用是，利用原始密钥K来生成S表

这里的密钥K的长度为1~256字节。S表类似于一个数组，其大小为256，表示为S[0]~S[255]，其中每个S表单元可以存放一个字节（8位）

S表的生成分为初始化和置换两部分：

• 初始化

  • 首先对S表的每个单元依照编号从0~255依次填充（二进制序列）。即S[0]=0；S[1]=1；……S[255]=255
  • 接着建立一个临时数组T，称为T表，其大小与S表相同。使用原始密钥K对T表进行填充。如果K的长度等于256，则直接将K赋值给T表。如果K的长度小于256，则T表剩余的部分继续使用密钥K循环填充，直到填满为止。假设密钥K=123，T表长度为7，则T表=1231231

  用代码来描述的话如下

  1 2 3 4 5 6 7 8 9 10 11

  unsigned char S[256]; //状态向量S表 unsigned char T[256]; //临时向量T表 vector<char> K; int keylen; //密钥长度，keylen个字节，取值范围为1-256 for(int i = 0; i < 256; i++)//对S表、T表的每个单元进行填充 { //填充S表 S[i] = i; //填充T表，使用密钥K循环填充，keylen为密钥K的长度 T[i] = K[i % keylen]; }

• 置换

  置换过程就是根据一定的规则，对S表中的单元交换位置，交换的规则为：

  初始化一个变量j=0，然后对于S表的第i个单元，计算得j=(j+S[i]+T[i])mod256，括号中的j为上一次计算得出的j值

  每次计算出j后，交换S[i]和S[j]的值

  以上的代码如下：

  1 2 3 4 5 6 7 8

  int j=0; for(int i=0;i<256;++i){ j=(j+S[i]+T[i])%256; //cout<<"j="<<j<<endl; S[i]=S[i]+S[j]; S[j]=S[i]-S[j]; S[i]=S[i]-S[j]; }

  经过置换后，S表中的内容也没有发生实质性的变化，只是各个字节被打乱了位置而已

2 伪随机数生成算法（Pseudo-Random Generation Algorithm，PRGA）

在经过KSA后，S表被建立了起来，之后的任务就是从S表中选取字节单元，输出密钥流序列

为了使生成的密钥流序列更加的随机，PRGA每生成一个字节的密钥流，就会打乱一次S表

生成密钥流、打乱S表的步骤如下：

• 初始化：首先初始化两个变量i=0，j=0
• 递增：然后每次在生成一字节的密钥流之前，i+=1（但不能超过256，需要mod256），j+=S[i]（但不能超过256，需要mod256）
• 交换打乱：交换S[i]和S[j]的值，用来打乱S表
• 输出：这时就可以输出一字节的密钥流，密钥流取自S表的第S[i]+S[j]的值取余256

重复上述步骤，即可生成多个字节的密钥流序列，代码如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

int i = 0,j = 0;//初始化i，j为0
while(true)
{
    //i自增1
    i = (i + 1) % 256;
    //j自增S[i]
    j = (j + S[i]) % 256;
    //交换，打乱S表
    swap(S[i], S[j]);
    //使用变量t保存输出S表的第几个单元
    t = (S[i] + S[j]) % 256;
    //输出一字节的密钥流序列k
    k = S[t];
}

通过以上方式，就可以得到一系列字节的流密钥序列。之后，使用一字节的流密钥序列与一字节的明文序列异或可以得到密文；同理，使用一字节的流密钥序列与一字节的密文序列异或可以得到明文