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

2021 iThome 鐵人賽

DAY 6

Security

學密碼學也猜不到你的手機密碼系列第 6 篇

13th鐵人賽串流加密對稱式加密法

chen_yanlong

團隊Obit0 Studio

2021-09-18 00:00:30

3752 瀏覽

分享至

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在後來被指出他所產生的密鑰並不隨機，存在統計上的偏誤，並且密文有洩漏明文資訊的可能，
因此已不再被建議使用。
最後一個參考資料詳細的解說，不過有點艱深就是了（而且是英文...）。