iT邦幫忙

2021 iThome 鐵人賽

DAY 8
0
Security

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

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

これはです 。

子密鑰生成

上一篇說到,在 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位元,因此所有的密鑰可能只有 https://chart.googleapis.com/chart?cht=tx&chl=2%5E%7B56%7D 種。
這是其最大的缺點,
如此短的密鑰讓現代電腦技術可以用很短的時間破解。
甚至在西元1999年就有機器可以在一天之內破解 DES (DES challenge 3)。

分析攻擊

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

3DES(Triple DES)

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

https://chart.googleapis.com/chart?cht=tx&chl=y%20%3D%20DES_%7Bk_3%7D(DES%5E%7B-1%7D_%7Bk_2%7D(DES_%7Bk_1%7D(x)))

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

Meet-in-the-middle attack

一種用空間代替時間的攻擊方法,什麼意思呢?
假設我們今天用的不是3DES,我們用2DES。
照理來說,2DES會有 https://chart.googleapis.com/chart?cht=tx&chl=2%5E%7B112%7D 的安全性(因為有兩把不同的k),但其實他只有 https://chart.googleapis.com/chart?cht=tx&chl=2%5E%7B57%7D 的安全性。
2DES 加密兩次,加密第一次後的訊息我們稱為中間值好了。
明文到中間值的密鑰叫做k1,另一個叫做k2。

明文→中間值→密文

假設攻擊者有一對明文密文對,他窮舉所有的k2把密文解密成中間值。
於是他會有 https://chart.googleapis.com/chart?cht=tx&chl=2%5E%7B56%7D 個中間值。

接著他窮舉每一個k1得到 https://chart.googleapis.com/chart?cht=tx&chl=2%5E%7B56%7D 個中間值,然後跟剛才得到的中間值做比對。
他就得到k1和k2了。

所以實際上2DES的安全性只有 https://chart.googleapis.com/chart?cht=tx&chl=2%5E%7B56%7D%2B2%5E%7B56%7D%20%3D%202%5E%7B57%7D


好啦講完了DES,非常複雜。
不過他已經被 AES(先進加密標準)所取代,所以我們明後天要來看AES是什麼。

圖片來源:
https://crypto.stackexchange.com/questions/32042/why-are-there-256-possible-des-keys-when-there-are-64-key-bits
https://www.commonlounge.com/discussion/5c7c2828bf6b4724b806a9013a5a4b99
https://memegenerator.net/instance/40957521/super-sad-cat-des-encryption-make-kittehs-sad

參考資料:
https://www.freeswan.org/freeswan_trees/freeswan-1.5/doc/DES.html
https://www.commonlounge.com/discussion/5c7c2828bf6b4724b806a9013a5a4b99


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

尚未有邦友留言

立即登入留言