基于RC4流密码改进算法下的无线网络安全解析

◆赵明阳

（保山学院 云南 678000）

基于RC4流密码改进算法下的无线网络安全解析

◆赵明阳

（保山学院 云南 678000）

RC4流密码算法凭借其高效且容易实现等优点，广泛应用于计算机网络安全和数据库信息安全等领域中。但是，随着计算机无线网络的飞速发展以及在各行各业中的普及，无线网络安全技术成为了人们所密切关注的话题。本文将从流密码算法的工作原理及设计原则入手。重点解析原RC4流密码易被攻击等不足之处，提出一种基于随机改进型RC4_n_m的算法确保无线网络的安全。

RC4;流密码;随机性;RC4_n_m;无线网络安全

0 引言

RC4加密算法是在 1987 年由罗纳德·李维斯特（Ron Rivest）设计的一种密钥长度可变的流加密算法簇。是由其核心部分的S-box长度可为任意值，但一般为256字节。该算法的速度可以达到 DES（Data Encryption Standard 即数据加密标准）加密的10倍左右[1]。但是随着无线网络数字技术的高速发展，RC4加密算法也并非无懈可击，特别近几年来的大量研究表明，RC4加密算法存在以下几种安全隐患。即：错误引用攻击、区分攻击和弱密钥攻击[2]。

1 RC4流密码算法

1.1 RC4流密码的构成

从运算过程中 RC4流密码可以分为密钥编制算法和伪随机序列生成算法。而从内部结构可分为S-box，状态变化函数和输出函数。

假设内部状态由状态表S-box和指针i，j组成。则内部状态可由函数IS(it，jt，st)表示。数组里面的it，jt分别指向S-box。它们不但可以控制St的变化，同时还控制着输出函数。RC4算法中内部状态S-box的转换过程如图1、图2、图3所示。

图1 将S和K进行初始化图

图2 S的初始化状态

图3 RC4流密码生成

1.2 RC4算法中的状态函数变化

在状态变化函数中用来改变的it、jt和St，使得RC4算法中的内部状态不断在发生着变化，如上图所示。则在S-box的状态函数可用St+1=G(it，jt-1，St-1)。

这里有一点需要强调的是it的增加并不局限在jt和St的参数变化中。如果当RC4算法进行了N=2n-1次循环算法后。那么，jt的每一个存储单元将被 it全部遍历一边。即当运算方式完成 2n-1次后，存在St中的每一个位置将被全部置换。

在上中第三步骤流密码生成时，引入一个 swap交换操作（swap操作是指：实现交换两个容器内所有元素的功能。要交换的容器的类型必须匹配，必须是相同类型的容器，而且所存储的元素类型也必须相同[3]）。使得 RC4算法中输出流密码的随机性将变得更强，从而达到安全保护作用。

假设，在RC4加密算法中，如果没有swap交换操作，那么是否生成的流密码顺序是一个周期为2n+1的序列呢？

根据上述假设，我们可根据流密码序列产生的算法可知：

Zt=S[S[it]+S[jt]]，而Zt+2n+1=S[S[it+2

n+1]]+S[S[jt+2

n+1]]，此算法中的加法是模上的2n+1。因此可得到：

此时，如果RC4加密算法中缺少swap交换操作，将St看作常数函数，按照上图的第二步骤。递归可得到：

1.3 RC4的算法描述及编制算法

RC4算法是基于非线性变化的流密码算法，其算法有两个方面构成。一方面密钥编制算法(Key Sehedule Algorithim)简称KSA，由可变长度密码流产生密钥流生成器的初始状态S0。另一方面伪随机序列生成算法PRGA（Pseudo Random Generation Algorithm），根据初始状态生成密码流序列，与明文相异最终生成密文[4]。

1.3.1 密钥编制算法（KSA）

假设随机选取一个密钥，对 S-box进行初始化，将 it遍历S-box的每个位置。则每一次的更新势必将会jt在St-1[it]和选取的密钥作用下生成一个新值。经过多步的遍历后，则密钥编制算法就产生了RC4的初始状态S0。RC4密钥编制算法关键伪代码如下所示：

1.3.2 伪随机序列生成算法（PRGA）

伪随机序列生成算法（PRGA）的生成原理其实就是在 S-box中不断地变换元素的位置，同时随机选择一个元素作为输出便可以得到RC4密钥流顺序。如图4伪随机序列生成算法生成图所示：

这里假设密钥编制算法（KSA）的初始状态为S0，初始化指针it和jt。交换St中的指针it和jt，同时更新算法中的j。这时伪随机序列生成器就不断的更换S-box中对应字节的位置，每一次的变换都把S中St[it]+St[jt]位置值输出，那么这个位置值就是字长为8bit的密钥流。伪随机序列生成算法（PRGA）的关键部分伪代码如下所示：

图4 伪随机序列生成算法生成图

2 RC4算法安全性分析

随着无线网络技术的不断发展和更新，原有的 RC4算法安全性也受到了巨大的威胁。其中典型的攻击方式有：弱密钥攻击、区分攻击、错误引入攻击等。现对常见的一些攻击方式进行简要介绍。

2.1 弱密钥攻击

弱密钥的攻击主要是攻击者通过分析一部分密钥所在密钥流中的的特性，探测出更多的密钥。使探测到的密钥输出密钥流顺序与原有的密钥流产生对比。每输出一串密码流都和已经破译的密码流进行序列对比，试图找出之间的关系信息。

2.2 区分攻击

假设攻击者能从密码流序列产生器和一个随机函数区分开来，则称之为区分攻击。如果该区分攻击算法的复杂程度低于穷举密钥攻击复杂度，那么这个区分攻击就是有效的。

2.3 错误引入攻击

如果当攻击者不能采取一种有效的方式使用密码机，而引入一张错误机制。使得原有的密码机输出错误的密码流。攻击者通过这个错误的密码流分析出里面的密码排列顺序。将正确和错误的加密结果进行分析比对，找到二者之间的差异。从而破解密码机的密钥则我们称之为错误引入攻击[5]。

3 改进型RC4_n_m算法分析

3.1 RC4_n_m算法主要思想

针对上一模块中提出传统的RC4加密算法中极易受到错误引入攻击、区分攻击、若密钥攻击等安全因素的攻击外。现在我们提出一套改进型的RC4_n_m算法。该算法以随机置换变量为基础。能够有效抵御上述几种攻击且简洁易生成[6]。它的特点如下：

（1）随机置换的特点，对于内部状态表按非线性进行运算，在动态的情况下扩展状态表的元素取值空间，且状态表中的元素处于不断更新的情况下，使得状态表可以多次被重复使用。

（2）在RC4加密算法过程中引入一个秘密数，该秘密数随着状态表的不断更新变化而变化，使得RC4_n_m算法生成的伪随机序列及秘密参数和状态表是随机性的。保证了其安全性。

（3）RC4_n_m算法由状态表的前后两个状态同时决定，增强了流密码序列的随机生成性。进而进一步提高了RC4_n_m算法的安全性。且伪随机序列生成的输入为32位，远远高于原有RC4算法的8位数。

3.2 RC4_n_m算法的描述

3.2.1 密钥编制算法

RC4算法的S-box的每个元素取值范围在0-255之间，范围很小。很容易受到区分攻击。现在将RC4_n_m算法引入，扩展S-box的每个元素取值范围在0-2m(m≥8)。为了进一步提高随机性，我们采用交换操作和整数模加法[7]。密钥编制算法生成过程如图5、图6、图7、图8所示：

图5 初始无序的S-box展示图

图6 对S、K附初值表示图

图7 S的初始状态图

图8 输出秘密数k展示图

这里假设k为一个秘密数，Key为种子密钥，L为密钥的长度。则编制RC4_n_m算法在S-box变化过程的部分伪代码如下：

3.2.2 伪随机序列生成算法

基于RC4_n_m算法对原有RC4的伪随机序列生成算法进行改进：首先，RC4算法的中的S-box中元素是0-28-1的全排列，状态表的更新仅仅只是S-box中的两个元素，以至于S-box在更新前后的状态变化不是很大，甚至可以忽略。所以这个细节也被攻击者所利用。但是RC4_n_m算法中的S-box元素的取值范围0-2m(m≥8)，所以相比传统的RC4算法S-box中的取值就越大，安全性也就越高。再次，传统的RC4算法只是通过一次交换操作来更新输出状态，极易被区分攻击。而在RC4_n_m算法中，因为采用了安全级较高的秘密数k御妆台表中的i和j 位置的值加模M。确保了随机输出性的安全级别变高。RC4_n_m伪随机序列生成算法的部分伪代码如下：

在RC4_n_m伪随机序列生成算法阶段，获得密钥编制算法结束后生成的秘密数和初始状态S0，则伪随机序列生成算法不断地更新着S-box中元素。保证了生成密钥流的安全性。假设Z为密钥流序列，S0为初始状态，RC4_n_m伪随机序列生成算法变换过程如下图所示。

图9 秘密数k更新过程图

图10 密钥流的生成图

图11 更新状态表展示图

3.3 RC4_n_m算法的效率分析

RC4_n_m在进行密钥编制算法和伪随机序列生成时，使得动态的随机性置换S-box中的元素，S-box中的元素均匀分布，密钥流序列的输出状态由前后状态表共同决定。假设 RC4_8_32，S-box的元素为256个十六进制的32位的数。相比传统的RC4算法得8位数，RC4_8_32的加密效率是其传统RC4算法的4倍。

4 结语

计算机无线网络安全技术是一个人们密切关心的话题，而RC4流密码的安全性随着计算机技术的快速发展也受到了严峻的挑战。本文通过对传统的 RC4算法进行改进，引入了一种基于随机置换的RC4_n_m算法，理论上解决了传统RC4算法局限性。从随机性、效率性和抗攻击性等无线网络安全技术角度出发验证了其安全有效性。

但是，RC4_n_m在密钥编制算法中，假如使S-box中的元素全部更新的轮数暂时计为R，那么当R的数值为多少时才是密钥编制算法中最安全的呢？又如RC4_n_m算法是一种对称码体制，和当下的非对称码体制如何组合达到流密码算法最安全性，也是下一步流密码、无线网络安全技术研究的新方向。

[1]赵明阳．基于 RC4加密算法对无线网络安全技术的研究[J]．网络安全技术与应用，2017．

[2]沈静．RC4算法及其安全性分析［D]．广州大学，2007．

[3]刘志巍．密码算法的随机性测试研巧[D]．西安电子科技大学，2011．

[4]王信敏，郑世慧．PRGA的初始状态与RC4算法的安全性[J]．计算机工程与应用，2009．

[5]王信敏．RC4算法的分祈[D]．山东大学，2005．

[6]尤加勇．现代序列密码的设汁与分析[D]．国防科学技术大学，2007．

[7]李琴，曾凡平．RC4密码的改进方法及其性能分析[J]．计算机工程，2008．