iT邦幫忙

第 12 屆 iThome 鐵人賽

DAY 4
0
Security

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

[Day 4] 004 - 對稱密鑰演算法 - Symmetric-key algorithm(一)

對稱密鑰演算法 - DES

對稱式的加密很簡單,就是『加密解密用同一個金鑰』。

以目前的加密的方案來說,通常都是幾個單純的替換或、位移和XOR。
而且金鑰也會跟著做相對應的變化,以生成內部新的金鑰。
然後跑多次這些流程。

一樣的我們把對稱的優點跟缺點都列一下:

  • 優點:
    1. 因為都是簡單的位移、替換、XOR,對CPU來說是簡單的任務,因此速度快。
      • 這邊想講一下,電腦硬體結構來說,XOR、位移、替換都是硬體最擅長的事情。
        比起乘、除來說更加地快且簡單。
    2. 可加密大量的資料,能夠利用加密串接的方法來增加加密的資料量。
      • 你要說非對稱為何不能使用,那就是下下一章節的事情。
    3. 目前最主流的AES加密,有專門的Hardware或指令集支援
    4. 主流的幾個加密,都十分地安全,目前除了旁路攻擊才有可能被破解。
  • 缺點:
    1. 因為金鑰是同一把的關係,傳送金鑰變得很重要。
    2. 太多的對稱加密,有些加密其實不安全,但要理解全部的算法很困難。
    3. 金鑰、資料一點點損毀、串改,就會跟整個資料說再見。

接下來我想拿目前經典的一些加密演算來介紹,以便大家更理解目前對稱加密的方案。


DES

資料加密標準 - Data Encryption Standard - 縮寫為 DES

論文在這邊:DATA ENCRYPTION STANDARD (DES)

接下來我們所使用的圖片都是來自1999年10月25號所發布的,DATA ENCRYPTION STANDARD 文檔,在此標記。

是以前美國所使用的國家加密標準。

所使用56位金鑰,但也因金鑰長度過短,導致安全性有疑慮,就被棄用。

這邊要提的一件事情就是,輸入的金鑰其實有64位,但因為只有56位被使用,其他8位元被用於『奇偶校驗』,不參與實際的加密流程。

所以有效長度為56位,但輸入金鑰時一樣要給64位元喔~


大綱與總覽流程

好的,好的,好的,我們原理、機制等等的都先不要看,來看圖一。


圖一

請看這張圖一,這就是DES的加密的全貌。

我簡單將過程列舉一下:

  1. IP
  2. 資料切割成左右。
  3. 右邊資料作F函數後跟左邊做XOR。
  4. 然後左右邊對調後重複3的動作,重複16次。
  5. 最後在做逆IP。

能看到 INPUT 的資料先做了一次IP,而IP是什麼?請看圖二:


圖二

其實就是位移,可以看到數字1-64就是把輸入進來的64位元的資料,做新的排序。

然後我們看到,將資料分成右邊跟左邊。

將右邊的資料丟入一個F的函數,這個F函數需要金鑰跟資料。

F函數輸出的資料跟左邊的資料作XOR。

兩者換邊,右邊是經過處理的資料,左邊是原本上一輪的右邊資料。

就這樣做16次後,再做一次逆IP(位移)。

就是那麼簡單~


F函數(費斯妥函数)

來看一下另一個重點,F函數,請看圖三。


圖三

你能看到R指的是右邊的進來的資料,K就是金鑰了。

你會問,奇怪金鑰不是64位元,被捨棄了8位元後也應該有56位元吧?為什麼只剩下48位元?

下面的金鑰生成會提到的。

先回來看F函數的動作,能看到動作被分成了4個部分:

我也列舉一下步驟:

  1. 擴張資料。
  2. 與回合金鑰混合。
  3. 進到S盒子中轉換,從6個資料變成4個。
  4. 做P的位移。

那我們一個一個來說說。

擴張

R進來後先做擴充成48位元,依照下面的圖四。

應該知道有些資料就會重複了。


圖四

與回合金鑰混合

把『擴增完的資料』跟『回合金鑰』做XOR。

這也沒什麼問題。

S盒子

這部份比較複雜,但細分就不難。

先把資料分成8塊,放進S盒子中又稱為『替換盒』。

這些S盒子會利用替換表來替換如圖五,圖五的是S1的盒子。


圖五

然後將6個輸出變成4個輸出。

S盒子將原本是線性的轉換變成了非線性的轉換。

要是沒有使用S盒子的話,會使破解變得容易許多。

畢竟之前的都是線性位移、相同資料且鄰境的擴增跟XOR,現在這提供了非線性的替換。

做P的位移

最後做P,而P是一個固定的位移或稱為置換的動作(不是替換喔)如下圖六。


圖六

在Wiki的解釋了,第四步的設計目:這個設計是為了將每個S盒的4位元輸出在下一回合的擴張後,使用4個不同的S盒進行處理。

F函數 結論

S盒,P置換和E擴張各自滿足了克勞德·香農在1940年代提出的實用密碼所需的必要條件,「混淆與擴散」。

來自:資料加密標準Wiki


金鑰的擴充與生成

當然啦,金鑰這邊也要做擴充與生成。

一樣先看圖七:


圖七

我也列舉一下步驟:

  1. 先做PC1後,金鑰被分成兩部分。
  2. 將金鑰位移,輸出到PC2。
  3. 位移完的金鑰,繼續做步驟2。

好我們一樣慢慢看。

做PC1

能看到Key(64位元)進去後,被PC1(Permuted Choice 1)分成了兩部分。

C0跟D0,怎麼分的,看下圖八。


圖八

你會發現到,有些位元消失了,這也就是上面重點提過的,有些不參與算法本身。

也就是最後輸出為56位元,其中8位元被拿去做『奇偶校驗』了。

然後被分成了兩個28位元C0跟CD。

位移

接著能看到兩個部分被位移了,而且位移的數量也不同,請看下面這張圖九。


圖九

你能看到因為做的次數不一樣,位移的量也不一樣。

接著看到PC2(Permuted Choice 2)將56位元的金鑰挑出了48位元,一樣看圖十。


圖十

金鑰變化 結論

說真的,其實很簡單,但卻也帶來了金鑰的變化,使得每一次參與加密的金鑰都會是不同的部分。


加、解密差異

  • 加、解密的差異與相同:
    1. 金鑰生成順序一樣,同一套電路就能生成加、解密的金鑰(且金鑰生成相同)。
    2. 解密時可以使用同一套電路來做解密。

講解一下為什麼能同一套電路作解密好了。

一樣看圖十一


圖十一

你可以看到左半邊的資料去XOR右邊經過F函數的資料。

而且右半的資料跟上一次的資料是相同的,表示我將資料進行F函數後會得到同一個結果。

而還原了左半邊的資料,同時看圖十二。


圖十二

能看到還原出來的左半邊資料是上一次循環的右半邊資料,而上一次的右半邊跟這一次的左半邊是同一個。

因此一樣經過過F函數後,得到的結果會一樣;而結果一樣,所以跟這一次的右半邊做XOR得到的,就是上一回的結果。

所以加密、解密可以使用同一套的電路。

唯一不同的就是,金鑰要從最後的到最前的。

看一下圖十三:


圖十三

結論

真是漫長的旅途,能看到其實每一個步驟來說,很簡單卻又十分的複雜。

能知道一件事,大部分都是替換、位移跟XOR。

也是電路最為擅長的事情,能將電路設計完後,變成全自動的加密硬體插件。

而且這樣的設計可逆性好像也不錯。

再說了,加解、密同一套電路能節省很多電路的資源,同時也能做的小巧。

真的缺憾就是金鑰長度真的不長。

3DES

而因此衍生出了3DES

看完DES後,3DES就是將三個金鑰分別做DES加密與解密。

做三次的DES不是全部都加密喔,是加密->解密->加密。

什麼意思?

其實就是資料先用第一個金鑰做加密,加密完的資料用第二個金鑰做解密的動作,最後再用第三個金鑰做加密。

其中第三個動作就是將解密的動作來做加密。

為什麼要這樣做?

原因很簡單,相容性。這樣的設計就能相容於一般的DES了。

假如三支金鑰都相同的話,那麼第一次的加密跟第二次的解密會抵銷掉,因此只有第三次的加密有效。

那你可能會說,為何要那麼麻煩去相容。

向下相容這件事情比你想的還要更重要,想想世界上都用這樣的系統,突然要改也不是一瞬間能改的,更別提成本了。

這方面就要由大神做經濟分析了。

那如果三支金鑰都不同,DES的金鑰其長度就能是56*3=168位元了。

這不就將DES金鑰過短因此不安全的問題解決了,變得很安全了嗎?

總歸來說,實際上還是做DES的加密核心。

看到這邊有沒有覺得收穫滿滿呢?


參考資料

DATA ENCRYPTION STANDARD (DES)

資料加密標準 WiKi

混淆與擴散 WiKi

3DES WiKi

AES-NI 與 Secure Key 構成 Intel® Data Protection Technology


上一篇
[Day 3] 003 - 古典密碼
下一篇
[Day 5] 005 - 對稱密鑰演算法 - Symmetric-key algorithm(二)
系列文
無趣的密碼學,有趣的加密!30

1 則留言

0
dennysora
iT邦新手 5 級 ‧ 2020-09-06 00:26:55

你們下一篇想先看AES還是RC5?

dennysora iT邦新手 5 級 ‧ 2020-09-07 00:07:48 檢舉

我決定先放RC5。

我要留言

立即登入留言