RC4密码的兴衰

在密码学中的所谓“序列加密法” (stream cipher, 有時也被称为“流加密法”) 是相对于分组加密(block cipher)而言的。意思是它不对每一组数据来加密，而是对每一个字节(byte) 甚至於每一个位(bit)来加密的。 RC4 就是最有名的序列加密法。

RC4 来头不小。它是由 RSA公司创办人之一 Ron Rivest 在 1987年所设计的。RSA公司就是由发明 RSA 加密法那三个人 Ron Rivest, Adi Shamir  和 Len Adleman所创立的， 多年来算是这类信息安全公司的老大。可是在2013年斯诺登事件曝光后，RSA公司被怀疑曾在它的一个产品 Dual_EC_DRBG (一种根据双椭圆曲线设计的伪随机变数生成算法) 替NSA 装了“后门”。

RC4 的源代码在1994年不知被谁放到公众网站上，大家才知道这个有名的序列加密法只是由短短几行的程式所产生的。 此后 RC4 可谓风行一时， 从 1997 年起很多路由器 WiFi 的 WEP 加密附件就用了 RC4。 後来路由器的 WPA (2003) ，网上所用的 https 里面的安全协议 SSL(1995) 和 TLS (1999) 都有 RC4 作为加密的选项。

 RC4 的运作是靠一个聪明而简单的程式去产生一串“密钥流”(key stream)，然后一对一的用“密钥流”中的每一个字节和要加密讯息的字节进行“异或”运算 (XOR)。比方说原来讯息第120字节是英文字母 A， 在二进制它就是 01000001 (相当于 ASCII 十进码的 65)， 假设 RC4 所产生的密钥流的第120字节是 00010101 ， 那么进行异或运算后的结果就是
          01000001  EOR  00010101 =   01010100， 那就是英文字母的 “T”。

收件的一方解密的时候也是用同一个程式对密件进行“异或”运算，那就是把密件的第120字节“T”和密钥流的第120字节 00010101 再作一次异或运算：
           01010100  EOR  00010101 =   01000001,  就是原来的英文字母的  “A”。
异或运算是按照以下的法则运行的：
0 EOR 0 = 0,    1 EOR 0  = 1,    0 EOR 1 = 1,    1 EOR 1 = 0.

RC4 怎样去“泡制”它的密钥流呢？ 其实它只是把 0，1，2，... 255 这 256个数目“洗牌”两次。而这种洗牌法远远谈不上是真正随机。

如果路由器的 WiFi 采用了WEP这个加密法，它里面的 RC4 就会利用 WiFi 密码口令作为密钥来创造出它的密钥流。假设我输入的密码口令是 "BEJINGSHANGHAIHONGKONG"，下面这个 Visual Basic 程式就能让我在笔记本中算出 RC4 所用的密钥流的最初 601字节：

Private Sub RC4_KeyStream()
  Dim S(256) As Integer
  Dim k(256) As Integer
 EntKey = "BEJINGSHANGHAIHONGKONG"
 klen = Len(EntKey)
'   klen 是密码口令 EntKey 的长度，这里的实际长度是 22
  FileNum = FreeFile
  fn = "c:\test\Rc4.csv"
  Open fn For Output As FileNum
For i = 0 To 255
    S(i) = i
    k(i) = Asc(Mid(EntKey, (i Mod klen) + 1, 1))
'   这是原密码口令 EntKey 的第 i mod klen 个字节的十进ASCII 代码 (0 –255)。
'   所谓  i mod  klen  就是 i 除以 klen 的余数
Next i
  j = 0
For i = 0 To 255
  j = (j + S(i) + k(i)) Mod 256
'  把 S[i] ， S[j] 的数值互换:
   tem = S(i)
   S(i) = S(j)
   S(j) = tem
 Next i
  i = 0
 j = 0
For m = 0 To 600
    i = m  Mod 256
    j = (j + S(i)) Mod 256
    tem = S(i)
    S(i) = S(j)
    S(j) = tem
    n = (S(i) + S(j)) Mod 256
    ks = S(n)
   Write #FileNum,  ks
Next m
Close FileNum
 MsgBox "Output file " & fn & " created"
End Sub

上面的程序所得到的密钥流是:

 152 223 105 17 207 95 150 208 150 181 145 109 137 180 45 222 53 204 133 72 233 190 140 111 19 2 213 132 174 196 182 213 239 246 28 71 152 202 43 24 136 59 141 111 5 180 73 94 170 196 24 36 10 137 203 88 130 12 190 248 154 0 81 102 189 93 104 26 148 162 61 148 25 130 59 17 60 220 109 97 222 13 236 220 76 254 107 122 102 234 250 115 84 152 185 232 173 244 71 160 179 .........

请注意只要路由器 WiFi 的密码口令不变，RC4 每次所产生的密钥流还是这些数字，这连“伪随机”也谈不上。所以在实际应用中这密码口令每次都要改动才能作为密钥这个用途。最初的改动办法是随机地找来一个数目，然后把这数目串联(concatenate)到密码口令的后头，当然这个数目还得交到收件的一方作解密之用。就算这“随机数目”是在不加密的情况下递交的，可能会被截获，但只要原密码口令没有泄露，所产生的密钥流还是比原先的好。

这就是 WEP 原初所采用的办法(注1)。不过到2001年 Fluhrer,  Mantin 和 Shamir 等人发现 RC4 密钥流的前几个字节远非随机，对它所产生的密件作高量统计分析后就可以破解，他们的发现就导致大量的路由器用户摒弃了 WEP。

其它 RC4 的用户改进了更改密码口令来作为密钥的方法，有的还故意舍弃RC4密钥流的前几千个字节。不过后来连续出现了 Klein attack (2005)， Royal Holloway attack (2013)，和 Bar Mitzvah attack (2015)。 在 2015 年9月，Google 决定把 RC4 从它的 https 里面的安全协议  TLS 中除去。IBM 对它的软件用户也发出公告指示他们怎样把 RC4 下架。

看来 RC4 的时代算是要结束了。

***********************************
(注1): WEP 的做法就是把这“随机数目”串联到密码口令的后头。比方说这次搞出来的数目是5176091184，那上面的密钥就被改成  "BEJINGSHANGHAIHONGKONG5176091184"。 后来人们发觉这种串联效果不好，就把这些数字分开来安插到原来密码口令里，或作更复杂的更改。这样的“随机数目”在英文文献中被称为“Nonce"。