iT邦幫忙

第 12 屆 iThome 鐵人賽

DAY 5
0
Security

無趣的密碼學,有趣的加密!系列 第 5

[Day 5] 005 - 對稱密鑰演算法 - Symmetric-key algorithm(二)

對稱密鑰演算法 - RC5

我們看過了非常複雜的DES之後。

我們來看點簡單的(再加上今天出門,太累了)。


RC5

李維斯特密碼 5 - Rivest Cipher 5(RC5)

我們簡單的先看一下圖一:


圖一

RC5可是被稱為很簡潔的對稱式加密之一了。

在圖中並沒有什麼其他的難懂的東西,無非都是XOR、位移、相加。

比較麻煩的是RC5的金鑰擴充,或稱為金鑰生成。

圖片中的步驟很簡單的。
但圖中沒寫到的幾個要件,我先提一下。

  1. 加密的話,是兩個字(其長度可以是32、64、128位元)。
  2. 金鑰長度可以是0到2040位元
  3. 回合次數可以是1到255次。

加密

圖中還少了一個前置步驟,在這邊先提出來。

必須先把字A跟字B跟『金鑰』相加。

加密過程

  1. 字A跟金鑰第1部分、字B跟金鑰第2部分相加。
  2. 然後把A跟B做XOR後,向左位移B個字元,每一次位移都將把最左邊的字元移到最右邊,做循環移動,再加上金鑰的第3部分,得到新的A。
  3. 再把新的A跟B做XOR後,向左移動新A個位元,每一次位移都將把最左邊的字元移到最右邊,做循環移動,再加上金鑰的第4部分,得到新的B。
  4. 把2跟3步驟,重複N次。
  5. 將資料A跟B回傳。

Python 的範例Code

A = A + S[0]
B = B + S[1]
for i in range(1,n+1):
    A = rotl((A ^ B), B) + S[2 * i]
    B = rotl((B ^ A), A) + S[2 * i + 1]
return A,B

def rotl(num, bits):
    bit = num & (1 << (bits-1))
    num <<= 1
    if(bit):
        num |= 1
    num &= (2**bits-1)

    return num

上述程式碼修改自RC5 WiKi
rotl 來自 Rot GitHub


解密

其實就是把這個過程顛倒過來。

解密過程

  1. 把B字減掉金鑰的第N部分,向右移動A個位元,每一次位移都將把最右邊的字元移到最左邊,做循環移動,再把A跟做完前述的動作的B做XOR後,得到還原B。
  2. 把A字減掉金鑰的第N-1部分,向右移動還原B位元,每一次位移都將把最右邊的字元移到最左邊,做循環移動,再把做完前述的動作的A跟還原B做XOR後,得到還原A。
  3. 把2跟3步驟,重複N次。
  4. 最終還原B跟金鑰第2部分、最終還原A跟金鑰第1部分相減。
  5. 將資料A跟B回傳。

Python 的範例Code

for i in range(n,0,-1):
    B = rotr((B - S[2 * i + 1]), A) ^ A
    A = rotr((A - S[2 * i]), B) ^ B
B = B - S[1]
A = A - S[0]
return A,B

def rotr(num, bits):
    num &= (2**bits-1)
    bit = num & 1
    num >>= 1
    if(bit):
        num |= (1 << (bits-1))

    return num

上述程式碼修改自RC5 WiKi
rotr 來自 Rot GitHub


金鑰擴充與生成

這個部分比較複雜,我們一樣慢慢看。

  1. 第一個點,就是先設定 一個字的長度(w) 了,可以是16、32、64位元。
  2. 然後我們將一個字去除以8,得到一個之後將會用到的參數u。
    • u = w/8
  3. 先把傳進來的 金鑰長度(l) 去除以u之後無條件去小數點得到一個c,長度最小要為1。
    • c = ceil(l/u)
  4. 做一個空的 臨時金鑰陣列(L[]) ,然後從 金鑰長度(l) - 1到0,將 目前循環的次數(i) 除以u的位子向右8個位元後加入 目前循環的次數(i)金鑰(K)
    • i = loop l-1 down to 0
    • L[i/u] = (L[i/u] << 8) + K[i]
  5. 然後做一個空的 隨機陣列(S[]) ,這個陣列的第0個資料是『 自然對數(e) - 2後乘2的 一個字的長度(w) 次方,並取奇數』。
    • S[0] = X
    • X = Odd((e-2)*2^w)
      1. w=16 時 X = 0xB7E1
      2. w=32 時 X = 0xB7E15163
      3. w=64 時 X = 0xB7E151628AED2A6B
  6. 之後填滿隨機陣列,從1到 加密的輪數(r) +1乘2,其數字是,上一筆數字加上『 黃金比率(Φ) - 1乘2的 一個字的長度(w) 的次方,並取奇數』。
    • i = loop 1 to 2*(r+1)
    • S[i] = X
    • X = Odd((Φ-2)*2^w)
      1. w=16 時 X = 0x9E37
      2. w=32 時 X = 0x9E3779B9
      3. w=64 時 X = 0x9E3779B97F4A7C15
  7. 將接下來的步驟重複3乘『 金鑰有多少字(c)加密輪數(r) + 1乘2,取最大的那個』。
    • Loop 3*max(c,2*(r+1)) time
  8. 設定A=B=i=j=0。
    • A=B=i=j=0
  9. A會等於 隨機陣列第i筆(S[i]) ,而每一次做『 隨機陣列第i筆(S[i]) + A + B後,向左3位元,每一次位移都將把最左邊的字元移到最右邊,做循環移動』。
    • A = S[i] = (S[i] + A + B) <<< 3
  10. B會等於臨時金鑰陣列第j筆(L[j]),而每一次做『臨時金鑰陣列第j筆(L[j]) + A + B 後,向左 A + B 位元,每一次位移都將把最左邊的字元移到最右邊,做循環移動』。
    • B = L[j] = (L[j] + A + B) <<< (A + B)
  11. i為『i加1取 加密的輪數(r) + 1乘2 餘數』。
    • i = (i + 1) % 2*(r+1)
  12. j為『j加1取 金鑰有多少字(c) 餘數』。
    • j = (j + 1) % c
  13. 完成7的循環後將S輸出為金鑰。
    • return S

上述程式碼修改必解析自RC5 WiKi


RC5 結論

能看到其實RC5的加解密十分的漂亮,同時也做到很好的混淆。

RC6原本也是AES的候選之一,而RC6跟RC5差別只在於『加密的字』。

RC6可加密的字從2個變成了4個。

而核心的流程依然不變。

金鑰的生產或擴充比較複雜,其他的地方其實還不算太難。

但有注意到一件事,這個算法用到了『+』,也算是位移的一種,很多算法不用+其實就是怕溢位的問題就是了。

然後金鑰的生成也是很多數學的公式在裡面,不單單只是列表、對照、位移。

今天寫的東西不多,但依然介紹了整體的流程,同時也是很好把程式碼實現的。

RC5也是很安全的,提供的加密字元也能到256位元。

雖然看起來只有兩字,但一個字元最高可以支援到128位元。


參考資料

RC5 WiKi

Rot GitHub


上一篇
[Day 4] 004 - 對稱密鑰演算法 - Symmetric-key algorithm(一)
下一篇
[Day 6] 006 - 對稱密鑰演算法 - Symmetric-key algorithm(三)(上)
系列文
無趣的密碼學,有趣的加密!30

尚未有邦友留言

立即登入留言