密码学那些事儿之RC4算法

最近杭州的天气用一个字概括就是：

大家注意防寒防热哦~

言归正传，这次我们要介绍一种新的流密码算法RC4，其实原本介绍一个A5咱就可以拥抱组密码DES和AES的。不过，RC4和安全领域的WiFi网络安全息息相关，所以咱就先绕个路，介绍一下RC4再去研究组密码。

RC4实现

上来就粗暴的先撸一段代码，刺激不？

咱依然使用Java撸代码，RC4的算法也比较简单。整个加密过程分为两步：初始化和数据加密。别着急，我们会依次介绍的。咱把用户秘钥设为字符串key，那么，key[i]为第i+1个字符。

01

初始化

主要目标是根据秘钥生成加密用的字串，是整数数组，设为S，长度为256bits。同时，需要一个同样长度为256bit类型为byte的辅助数组，设为M。整个过程具体分为三个步骤：

Step1：为S赋初值。遍历从0到255数字，依次存入S中，S[i]=i；

Step2：为M赋初值。遍历从0到255数字，M[i]=(byte)key[i%len(key)]；

Step3：结合M进一步混淆S。设置中间变量j初始值为0,仍然遍历0到255数字。j=(j+S[i]+key[i]) % 256。tmp = S[i],S[i] = S[j], S[j]=tmp。

02

数据加密

主要目标是根据S对输入的明文data进行加密。对于data中的每个字符，加密要经过三个操作（中间变量有i,j,t三个，i，j初始值为0。x代表data中的第x个字符）。

Step1：获取i和j。i = ( i + 1 ) % 256;j = (j + S[i]) % 256;交换S[i]和S[j]；

Step2：获取t。(S[i]+(S[j] % 256)) % 256；

Step3：加密data[x]。data[x] ^ S[t]。

同样，由于使用的是可逆运算异或，所以解密和加密是完全相同的，只需要将输入字符换成加密后的字符串即可。

WEP协议

是时候干点儿不太严肃的事儿了，要不给位看官都睡着了。

01

概念和原理

所谓的有线等效协议（WEP：WiredEquivalent Privacy）顾名思义，就是在无线传输的网络上模拟出和有限传输等效的协议。它在1997年被纳入802.11标准，为啥不说是无线局域网通用的标准？因为这样听起来比较高大上。

后来，因为它发现了很多安全问题，于2003年被WPA（Wi-FiProtected Access）取代了。它主要是靠RC4加密算法保障消息的机密性，CRC-32完整性校验算法保障消息的完整性。

在具体分析其攻击方法之前，我们先来看一下协议的详细内容。

原谅我很不正经的放了个本篇最不正经的图，毕竟也是手撸了大半天才弄好的。出来晒晒。莫慌，咱首先介绍一下协议中的关键词含义。

IV（InitializationVector）：初始化向量。我感觉就是包的编号，有意思的是标准协议并没有规定IV的值是如何产生的，所以大多数供应商都省懒，直接从0开始依次递增编号，因为其长度有限，所以在繁忙的网络中一般2-5h就会重复。

这也就为后续的安全问题埋下了伏笔。

Secret Key：加密秘钥，通常会和IV编号简单拼接，作为RC4秘钥。

PRNG（PseudorandomNumber Generator）：伪随机数产生器，就是一组用来将密钥转换为密钥串的规则。在WEP中指的是RC4算法。

Integrity Alg：此处指CRC-32算法。

然后，我们再说明一下数据包传递的详细步骤。

网络中WEP的数据包分为三部分：IV，秘文（Cipher Text）和ICV。ICV是直接计算明文得到的值（公式2），密文则首先是IV与SecretKey拼接，然后经过RC4算法产生秘钥，最后将秘钥与明文异或获得的（公式1）。整个加密过程如下：

注意！是三部分哦~所以还有个明文的IV！

AP接收到数据包后，解密过程如下：

然后判断ICV’与ICV是否相同，不相同则丢弃。

最后，咱再看一下WEP认证方式，它的认证方式有两种，一种是开放系统认证（Open System Authentication），只需SSID（Service Set Identifier：服务集身份标识）即可加入网络；另一种是共享秘钥认证（Shared Key Authentication）需要SSID和秘钥。

相比之下，后者更为安全。后者的认证过程如下（为了方便解释，我们将发送无线网络的设备比如路由器记为AP（Access Point）；使用无线网络的设备比如个人手机记为Client）：

Step1:Client向AP发出请求认证的请求；

Step2:AP回复一个明文的认证字段（Clear-TextChallenge）；

Step3:Client使用WEP秘钥将明文的字段加密，并发送到AP；

Step4:AP将密文解密，对比解密后的明文是否和原明文一致，如果一致则返回认证成功报文。

02

WEP协议安全性

因为RC4属于流密码算法，它的秘钥key不能出现相同的，为啥？一旦相同以后，再产生的秘钥就都相同了，也就是在周期性的使用重复秘钥！

但是，WEP中的IV长度只有24bit，并且还明文出现在数据包头部。研究人员发现，对于这样长度的IV当数据包达到5000个时就有50%可能性出现重复的秘钥！

早在2001年，Scott Fluhrer，Itsik Mantin和Adi Shamir就发现了WEP秘钥的破解方法。其用时最优情况下可以达到1分钟以内。这种攻击方法已经集成到了开源工具Aircrack-ng中。

到了2007年，Erik Tews, Andrei Pychkine, and Ralf-Philipp Weinmann优化了攻击方法，能够在获取40000个数据包的情况下，破解104bit的WEP协议。