iT邦幫忙

2021 iThome 鐵人賽

DAY 6
1
Security

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

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

圖片來源:
https://makeameme.org/meme/my-reaction-when-e57a025cb8
https://memegenerator.net/instance/68345635/snow-white-rc4-go-bye-bye

參考資料:
https://sandilands.info/sgordon/teaching/css322y07s2/protected/CSS322Y07S2H03-RC4-Example.pdf
https://zh.wikipedia.org/wiki/RC4
https://cms.aaasec.com.tw/index.php/2019/07/31/s-06/
https://www.geeksforgeeks.org/rc4-encryption-algorithm/
https://en.wikipedia.org/wiki/Wired_Equivalent_Privacy
https://www.imperva.com/docs/HII_Attacking_SSL_when_using_RC4.pdf


上一篇
DAY 5- 《串流密碼1》 - OTP
下一篇
DAY 7- 《區塊密碼1》DES(1)- 加密過程
系列文
學密碼學也猜不到你的手機密碼30

尚未有邦友留言

立即登入留言