DAY 6- 《串流密码2》- RC4

RC语音，最小最快最清晰。

讲完简单的OTP，要来点好玩的。
今天要来介绍另一个串流加密方法，Rivest Cipher 4（RC4）。

RC4

RC4 由 Ron Rivest 所设计，他是 RSA的共同设计者（RSA会在日後介绍）。
之所以介绍 RC4，是因为他被 WEP（Wired Equivalent Privacy）、TLS 所使用，曾用来保护无线传输。
除了他的作者很有名之外，他的速度也因为简单而有AES的两倍之快。
不过，WEP後来被 WPA （使用RC4+TKIP）及 WPA2 （使用AES）所取代。
且 RC4 也在後来（2015年）被禁止在 TLS 中使用，因为它存在一些漏洞。

总之，RC4不是一个安全的演算法，但是它曾经被大量的使用。
RC4相较於前面所介绍的加密演算法复杂了很多，所以要花多一点耐心才看得懂。

首先先来看一个小的RC4好帮助理解，注意到这个是简化版的。
我们要来加密[5,3,6,7]这串讯息

第一部分前置作业

1.建立一个 S-box（写作 S）
S-box 包含0-7的数字照顺序排列，
我们把它写成一个列表[0, 1, 2, 3, 4, 5, 6, 7]

2. 决定密钥
假设密钥是 [1 2 3 ] 好了，最好是随机的，不过为了方便解释。

3.建立密钥列表 K
这个列表要由刚才决定的密钥所组成，
且长度要跟 S 一样，
如果密钥不够长的话就一直重复直到够长。
所以我们的 K 会长成这样 [1, 2, 3, 1, 2, 3, 1, 2]

第二部分把 S 打乱

如果你不想知道怎麽把 S 打乱的话，可以直接跳到第三部分；
如果你想知道的话，奉上程序码：

S = [0,1,2,3,4,5,6,7]
K = [1,2,3,1,2,3,1,2]

j = 0 
for i in range(8):
    j = ( j + S[i] + K[i] ) %8  # "%" 就是取余数的意思，也就是mod 8 的意思
    S[i], S[j] = S[j], S[i]     # 将 S 中的「第i项」跟「第j项」互换

我示范第一圈好了

第一圈一开始 j = 0, i = 0
所以经过 j = ( j + S[i] + K[i] )运算後，j = 0+0+1=1
接着要将 S 中的「第0项」跟「第1项」互换
S 会变成 [1,0,2,3,4,5,6,7]

以下我列出每一圈的互换结果，
有兴趣的话可以自行验证看

[1, 0, 2, 3, 4, 5, 6, 7]
[1, 3, 2, 0, 4, 5, 6, 7]
[2, 3, 1, 0, 4, 5, 6, 7]
[2, 0, 1, 3, 4, 5, 6, 7]
[2, 0, 1, 3, 7, 5, 6, 4]
[2, 0, 1, 3, 7, 4, 6, 5]
[2, 0, 1, 3, 7, 4, 6, 5]
[2, 0, 1, 3, 7, 5, 6, 4]

进行完总共8圈之後，S 会变成[2, 0, 1, 3, 7, 5, 6, 4]
因为仅仅是做了交换的动作，所以0-7的每个数字都一样会在 S 里面。

第三部分加密


i, j = 0, 0
flag = 0
while flag < len(P):
    
    i = (i + 1) % 8
    j = (j +S[i]) % 8       # S = [2, 0, 1, 3, 7, 5, 6, 4]
    S[i], S[j] = S[j], S[i]
    t = (S[i] + S[j] ) % 8
    k = S[t]

		flag += 1

经过每一圈的运算我们会获得一个k，而我们再把这个 k 跟明文的每个数字做 XOR 就会得到密文。
比如说第一圈：
一开始 i = 0, j = 0 ，经过运算会变成 i = 1, j = 0
接着将 S 中的「第1项」跟「第0项」互换得到 [0, 2, 1, 3, 7, 5, 6, 4]

t = 2+0 = 2
k = S[2] = 1

於是第一个密钥k = 1 = 001(二进位)
跟明文[5,3,6,7]中的第一个字元5 = 101，每一位两两做XOR
就会得到100 = 4，

於是第一个字元被加密成4。
接着完成每个字元的加密会得到[4, 0, 4, 4]

完整的简易版RC4我放在这里
里面的 K 跟 P 可以自行更改

S = [0,1,2,3,4,5,6,7]
K = [1,2,3,1,2,3,1,2]
P = [5,3,6,7]

j = 0 
for i in range(8):
    j = ( j + S[i] + K[i] ) %8
    S[i], S[j] = S[j], S[i]

i, j = 0, 0
flag = 0
c_list = []
while flag < len(P):
    
    i = (i + 1) % 8
    j = (j +S[i]) % 8
    S[i], S[j] = S[j], S[i]
    t = (S[i] + S[j] ) % 8
    k = S[t]
    
    k = '{:03b}'.format(k)
    p = '{:03b}'.format(P[flag])
    c  = ''
    for n in range(3):
        c += str(int(k[n])^int(p[n]))
    c_list.append(int(c, 2))
    flag += 1
    
print(c_list)

讲完了简易版，完整版其实就不远了。

完整版的 RC4 其实就是将模数设为256
也就是只要将S-box的长度变为256，以及每个mod 8 都换成 mod 256 就行了。

RC4在後来被指出他所产生的密钥并不随机，存在统计上的偏误，并且密文有泄漏明文资讯的可能，
因此已不再被建议使用。
最後一个参考资料详细的解说，不过有点艰深就是了（而且是英文...）。