對稱密鑰演算法 - 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