DAY 8- 《區塊密碼1》DES(2)- 密鑰生成及安全性

2021 iThome 鐵人賽

DAY 8

Security

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

13th鐵人賽對稱式加密法區塊加密

chen_yanlong

團隊Obit0 Studio

2021-09-20 00:35:56

3292 瀏覽

これはです。

子密鑰生成

上一篇說到，在 DES 加密過程中的第二步，需要重複進行16次，
而每一次都會使用到一個子密鑰，因此總供需要16個子密鑰。
子密鑰有48位元，由56位元的原始密鑰產生。

現在要先來澄清一件事情。

輸入密鑰時需要輸入64位元，而真正會使用到的只有56位元，剩下的8位元作為奇偶校驗。
我們先將64位元分成8組，每組8位元。每一組的最後一個位元作為奇偶校驗（parity bit）。
如果左邊7個位元有奇數/偶數個1，那奇偶校驗元就是1/0 。

輸入 DES 的密鑰會經過以下這張表的轉換成為密鑰，
而這經過這張表的轉換之後，校驗元將會被去除。

所以我們現在有一個56位元的密鑰。
接著這個密鑰會進入下一輪（PC-2）。

在這一輪總共會進行16回合，
每一回合都先將56位元分成左右兩半，
左右兩半都會向左移動1（1,2,9,16回合）或2位元。
移動過後再經過下表的轉換成為子密鑰。

安全性

暴力破解

暴力破解就是試過每一種密鑰可能的破解方式。
以 DES 來看，因為其密鑰只有56位元，因此所有的密鑰可能只有 $2^{56}$ 種。
這是其最大的缺點，
如此短的密鑰讓現代電腦技術可以用很短的時間破解。
甚至在西元1999年就有機器可以在一天之內破解 DES （DES challenge 3）。

分析攻擊

DES 在實務上可以抵抗分析攻擊。（我們之後再來看什麼是分析攻擊。）
而事實上分析攻擊在 DES 發佈後才被發現。

3DES（Triple DES）

3DES顧名思義就是做3次DES，
比較特別的是，我們在做第二次DES的時候用的是解密，而不是加密。

$y = DES_{k_3}(DES^{-1}_{k_2}(DES_{k_1}(x)))$

注意到每一次使用的密鑰是不一樣的，所以總密鑰長度是168位元。
不過其有效的密鑰長度只有112位元（如果使用meet-in-the-middle attack）。

Meet-in-the-middle attack

一種用空間代替時間的攻擊方法，什麼意思呢？
假設我們今天用的不是3DES，我們用2DES。
照理來說，2DES會有 $2^{112}$ 的安全性（因為有兩把不同的k），但其實他只有 $2^{57}$ 的安全性。
2DES 加密兩次，加密第一次後的訊息我們稱為中間值好了。
明文到中間值的密鑰叫做k1，另一個叫做k2。