RC4流密码：高效、易实现的加密算法

RC4是麻省理工学院的Ron Rivest开发的，是使用最为广泛的流密码。RC4的大小由参数n确定。对于一个n位长的字（或0，1序列），有2ⁿ种不同的排列方式，对应2ⁿ个不同的元素（或状态），这些元素组成一个长为2ⁿ的数组S。RC4每次随机选取数组S中的一个元素输出作为密钥k。

为了实现输出元素的随机性，RC4包含了两个算法：密钥调度算法（Key-Scheduling Al-gorithm，KSA）和伪随机生成算法（Pseudo Random-Generation Algorithm，PRGA）。这两个算法对应密钥生成中的两个处理过程，KSA用来设置数组S的初始排序，PRGA用来随机选取元素作为密钥k输出并修改数组S的原始排序。每产生一个密钥k，数组S就被重新排列一次。

1.KSA算法

常用的RC4的n=8，此时，RC4可以生成2⁸=256个元素的数组S。KSA初始化S，取S[i]=i（i=0，1，…，255），并选择0～255中的一个子序列作为密钥，填充到密钥数组K[i]=i（i=0，1，…，255）中。填充时，这个密钥不断地重复直到填满整个密钥数组，然后利用以下算法实现数组S的初始随机化排列。

j=0；

【例3-12】 为了便于实现，取n=3，使用3位的RC4，这里是对2³=8取模，KSA算法的具体操作步骤如下：

1）由于n=3，则得到2³=8个元素的数组S，对数组S的元素进行排序。

2）选择子序列4，5，6作为种子密钥，填充密钥数组K。

3）利用以下算法实现数组S的初始随机化排列。

KSA算法的第一轮循环（即j=0，i=0）执行后，得到

将S[0]与S[4]互换得到的数组S为

当i=1，j的值为(www.xing528.com)

将S[1]与S[2]互换得到的数组S为

当循环执行完毕之后得到初始随机化的数组S。

2.PRGA算法

在KSA将数组S进行初始随机化排序的基础上，PRGA从数组S中随机选取元素作为密钥流字节，同时修改数组S的排序，以便于下一次密钥流的选取。选取过程取决于两个索引i和j，这两个索引都从0开始，选取时重复执行以下算法，直到产生与明文的长度相等的密钥流：

从此算法中可以看出，索引i保证每个元素的改变，索引j保证元素改变的随机性。

【例3-13】 假如使用4位的RC4，此时对2⁴=16取模，经过KSA算法，循环执行完毕之后得到初始随机化的数组S为

从i=0，j=0开始，PRGA算法的操作步骤为

计算t和k

得出第一个密钥字为4，其二进制表示为100。反复进行该过程，直到生成的二进制位的数量等于明文位的数量。

RC4的优点是在软件中容易实现且运行速度快。RC4广泛用于商业密码产品中，它已应用于Microsoft Windows、Lotus Notes和Oracle的SQL数据库、为网络浏览器和服务器之间的通信定义的安全套接字层（Secure Sockets Layer，SSL）。它还应用于无线系统以保护无线连接的安全，如用于属于IEEE 802.11无线LAN标准的WEP（Wired Equivalent Privacy）协议和更新的Wi-Fi保护访问协议等。目前，所用的初始密钥一般至少为128位。