上一篇Crypto介紹了編碼與古典密碼學的部分，接下來要進入相對複雜不少的現代密碼學囉!現代密碼學的種類繁多，如DES、AES、RSA等都被歸類於現代密碼，非對稱式的加密模式也使攻擊者解密的難度大大增加，究竟現在發展出了哪些攻擊方法來攻擊這些看起來堅不可摧的加密法呢？一起來看看進階的密碼學吧!歡迎各位來訊說明或補充筆者不足的部分喔!😊

Block Cipher

在進入現代密碼學之前，必須先了解區塊密碼的實現原理，DES、AES等高階密碼都有使用到這種方式來確保加密的安全性。Block Cipher可以被視為一種特殊的替代密碼，但一次替代的是一個區塊，而非一個字元。由於明文的長度非常大，因此對於不同的key，無法以對應表的方式處理加解密，僅能透過特殊的演算法來還原明文。

Block Cipher允許透過單一key對長度大於其的明文進行加密，但必須先將明文依照密鑰長度進行分塊，最後不足密鑰長度的區塊須以特殊的填充方法(padding)使其與其他區塊的長度相同(可攻擊的點，稍後說明)，因此命名為區塊密碼。通常在加密前會先有一個初始向量(Initial Vector，$IV$)來對原始的第一塊明文進行處理，以確保第一塊明文不會被輕易破解，而第一塊處理完成的密文則會成為第二塊明文的$IV$，以此類推完成整個加密過程。以下則是五種常見的區塊密碼模式。

Electronic CodeBook (ECB)

ECB是區塊密碼最簡單的一種模式，這種模式沒有初始向量，直接以密鑰對明文進行加密後輸出，這也意味著若是有區塊為相同的明文，將被加密成為相同的密文塊，因此最容易被攻擊。詳細加密的邏輯如下：

$C_i=E(P_i)$
$P_i=D(C_i)$

Cipher Block Chaining (CBC)

CBC模式中與ECB不同的地方在於，分塊後的明文會先與特定密文進行XOR後再進行加密處理，第一塊與$IV$ XOR，其餘與前一塊所產生的密文XOR。假設第一個區塊的index為1，CBC的加解密能夠被表示為：

$C_0=IV…C_i=E_n(P_i⊕C_{i-1})$
$C_0=IV…P_i=D_n(C_i)⊕C_{i-1}$

其中一種最常見的攻擊手法簡單來說會是利用改變某一位密文導致的解密錯誤來試出正確的明文，後面會再詳細說明。

Output FeedBack (OFB)

OFB與前面兩種模式又不同了，他是使用$IV$來進行加密，產出$IV$的密文後再與第一塊明文進行XOR，同時這個中介密文會成為下一個加密的輸入。基於XOR的特性$A⊕B=C\implies A=B⊕C，B=A⊕C$，OFB模式下的加解密操作會完全相同。詳細概念如下：

$O_0=IV…O_i=E(O_{i-1})$
$C_i=P_i⊕O_i$，$P_i=C_i⊕O_i$

由於OFB的工作模式類似流密碼，因此在改變一位密文時也只會改變一位的解密結果，安全性相較ECB與CBC高上許多。

Cipher FeedBack (CFB)

CFB的型態與OFB幾乎相同，唯一的差別是OFB拿來成為下一塊加密輸入的是IV的加密流，而CFB則是取前一塊的最終密文。詳細說明如下：

$C_0=IV$
$C_i=P_i⊕E(C_{i-1})$
$P_i=C_i⊕E(C_{i-1})$

由於取用的關聯性變複雜了，CFB的安全性稍稍高於OFB，但基本上沒有太大的差別。

Counter Mode (CTR)

最後是CTR，基本上它可以被理解為OFB的變形，首先一個固定的$Nonce$(可以視為$IV$)與計數器$Counter$透過加密者希望的方式連接，而計數器如何計數也能夠由加者者自行決定，下方以正規計數器的模式作為範例。其中計數器存在的目的為保證長時間的加密不重複輸出。而接著將$Nonce$與$Counter$組合出的字串加密後與明文XOR進行加密處理。詳細情況如下：

$O_i=Nonce$ $..$ $Counter_i$
$C_i=P_i⊕O_i，P_i=C_i⊕O_i$

因為$Nonce$與$Counter$基本上在每一塊的連接上會有關聯性，因此可以將其視為金鑰流(flow)，且實作上又比OFB更加複雜，目前幾乎可以保證安全性。

Feistel Cipher

費斯妥密碼是分組密碼最常使用的一種加密方案，包含了稍後會提到的DES(Data Encryption Standard，資料加密標準)，其優點在於加密與解密的過程十分類似，在某些程序中甚至完全相同，只需要逆向操作即可。

費斯妥密碼的加密過程會先將明文塊拆分為兩個等長的塊$(L_0,R_0)$，對單一區塊加密$n$次，使用$F$作為內部函數(各種Block Cipher Encryption更改的地方)(不須可逆)，且令每一步所使用的密鑰為$K_0,K_1…K_n$，第一次使用$R_0$作為輸入、$K_0$作為密鑰進行加密，密文與$L_0$XOR之後作為下一次加密的輸入，$R_0$則直接下放成為與下次密文XOR的對象，簡而言之就是$L$與$R$的角色互換，如此進行$n$次後將兩者合併作為輸出，因此圖案會是連續左右交錯的$X$型。以數學則可表為遞迴表達式：

$L_{i+1}=R_i$
$R_{i+1}=L_i⊕F(R_i,K_i)$

解密則十分類似，僅是將加密的過程反向做一次而已(利用XOR的可逆性)。

$R_i=L_{i+1}$
$L_i=R_{i+1}⊕F(L_{i+1},K_i)$

因為$F$函數的不可預測性，攻擊者基本上無法以這個地方作為切入點發動攻擊。

DES

終於要隆重介紹今天的主角DES了～DES是一種對稱式密鑰加密塊密碼演算法(它是對稱是加密唷!)，它其實是一個向大眾徵集足夠嚴謹加密算法的產物，最初期的草稿由IBM公司設計，1976年被美國聯邦政府的國家標準局確定為聯邦資料處理標準(FIPS)，隨後在國際上廣泛流傳開來。它的基本金鑰是56bit，由於是由美國國家機關發出，金鑰長度又相對較短，被懷疑內含美國國安局NSA的後門(sbox等置換表)，剛推出時受到了嚴密審查，也因而被公認是推動Block Cipher發展的一套加密方法。

DES現今已不是安全的加密模式，主因為其使用的56bit金鑰過短，在1999年時就曾經有全新的加密內容在一天內被破解。在安全性的考量上，可以使用DES的衍生演算法3DES來進行加密，雖然3DES也存在理論上的攻擊方法，後面會提及如何攻擊。也基於DES的不安全，它的進階加密方法AES也在數年後出現，將在下一個段落詳細介紹。

DES在加密的過程中將會有五個主要步驟，以下將逐一說明。

Initial Permutation (IP)

初始置換是DES的第一步，以64bit的明文為基準，分為一或多個明文區塊，每個明文區塊有64bit(不足補0)，且會依照以下表格進行置換，通稱為IP表：

如上所示，明文的第58位會被置換到IP表的第1位，而明文的第50位會被置換到IP表的第二位，以此類推完成整張IP表。

Subkey’s Generation

DES函數在加密時會傳入一個64bit的原始key，而這個原始key並不會被直接利用在加密中，而是先產生16組子金鑰。第零組子金鑰(不使用)的來源為以下這個表格的置換，本質上與IP表的置換原理完全一樣，這張表格稱為PC-1(Permuted choice 1)：

有發現表格中只剩下56格嗎?其實第8,16,24,32,40,48,56,64位這8位的key被指定作為**奇偶校驗位(parity bit)**，因此不會出現在表格中喔!

接著我們從左半金鑰置換表與右半金鑰置換表中，能夠得到兩個部分的金鑰$C_0$與$D_0$，接著在對其做出一個循環左移的操作，連續16次即可獲得$C_1$～$C_{16}$與$D_1$～$D_{16}$的值，其中在每次互換中的左移位數分別為：

(上為index，下為左移位數)

接著將每組$C_i$與$D_i$組合完成，產生16組56位的次金鑰，最後再以另一張表格選出48位完成16組金鑰$K_1$～$K_{16}$最終置換，這張表格稱為PC-2(Permuted choice 2)：

這次忽略的位數與上面稍有不同，為第9,18,22,25,35,38,43,54位。

Encryption

這個步驟就是應用到費斯妥密碼的想法所在了，前一個步驟產生了16種不同的金鑰，將會利用前面所提到的費斯妥密碼邏輯，一共重複16次來進行加密。而以下將詳細說明DES自訂的費斯妥函數$F$是如何運作的。

費斯妥函數$F$

DES的$F$函數作用概念如下所示：

前面有提到，費斯妥函數的輸入會是明文塊的其中一半與金鑰，如上所示。首先一半的明文$R_0$會先經過擴張置換$E$從32bit擴張到48bit(為了之後與48bit的密鑰XOR)，置換表格如下：

其中數位的明文重複出現，使輸出包括8個6bit的塊，每塊包含兩個上一列中曾經出現的最後兩位作為開頭，加上4bit對應的輸入位。

明文置換完成後，會與$K_0$進行XOR後形成中介密文，接著依照位數分別進入8個sbox(置換盒)$S_1$～$S_8$中進行處理(查表)，每個sbox處理6位，處理後輸出4位。sbox被認定提供了DES的核心安全性，若沒有sbox，密碼會是線性的，很容易被破解。$S_1$～$S_8$的置換表如下：

以110101作為$S_1$範例輸入，其符合1XXXX1與X1010X的對應，對應出的數字為3，即4bit的二進位數值0011，傳出0011作為輸出，以此類推，將$S_1$～$S_8$都以此方式產生輸出，拼湊產生共32bit的中介密文。

最後將這32bit的中介密文送進一個稱為P的置換表再次置換後完成$F$函數的作用。P置換表如下：

完成$F$函數作用，接著重複16次費斯妥密碼程序後完成加密處理步驟，獲得64位元的密文。其中這三個子步驟皆符合實用密碼所需的必要條件-混淆與擴散(confusion and diffusion)

Final Permutation (FP)

最後一個步驟事實上是第一步IP的逆處理，因此FP也被稱為inverse(IP)，處理的表格可以IP的表格推出，如下所示：

至此完成整個DES加密，輸出64bit的最終密文，若有下一塊明文則以使用者選擇的Block Cipher模式連結到下一個明文塊進行加密。P.S.這種加密真麻煩XD

若想完整了解Python的實作方式可參考此網站

Security

雖然DES最早被發現，研究它的論文也不在少數，但截至目前為止，暴力破解仍是解開DES最有效的方法(btw量子電腦的出現可能會改變這個事實)，曾經有三種發表的攻擊方法其時間複雜度$O$小於暴力破解，但因為需要大量的額外資訊($2^{43}$個以上的明文數量)，因此實用價值不高。

Triple DES

3DES，又稱TDEA(Triple Data Encryption Algorithm)，是DES在被發現不安全後產生的加強版，基本上就是重複利用DES演算法的一種模式，由於電腦運算能力的增強，原版DES由於金鑰長度過低容易被暴力破解，因此3DES利用三個不同的密鑰來對明文加密。詳細演算法如下，$K_1$～$K_3$為三把不同的金鑰：

$C=E_{K_1}(D_{K_2}(E_{K_3}(P)))$
$P=D_{K_3}(E_{K_2}(D_{K_1}(C)))$

是的你沒看錯，3DES的全加密演算法是使用$K_1$為金鑰進行DES加密，再用$K_2$為金鑰進行DES解密，最後以$K_3$進行DES加密。反之，3DES的全解密演算法則是先使用$K_3$為金鑰進行DES解密，再用$K_2$為金鑰進行DES加密，最後以$K_1$進行DES解密得到明文。

Keying Options

3DES的標準定義規範了三種金鑰選項，其中第二種及第三種已經因安全性的問題遭棄用(但可能出現在CTF競賽中)，如下所示。

Keying Option I

別名：3TDEA、三倍長度金鑰(triple-length keys)
簡而言之，三把金鑰$K_1$、$K_2$、$K_3$兩兩獨立，互不影響。
有$56\times 3=168$個獨立金鑰位，安全性最高。
可能被中間人攻擊(MITM)，故有效安全金鑰位僅有$56\times 2=112$位。

Keying Option II

別名：2TDEA、雙倍長度金鑰(double-length keys)
$K_1$與$K_2$相互獨立，且$K_1=K_3$。
有$56\times 2=112$個獨立金鑰位，雖然安全強度大於單獨使用兩次DES(double DES)(2TDEA可抵禦中間人攻擊(MITM))，但仍因金鑰長度不足而被棄用。

Keying Option III

$K_1=K_2=K_3$
此選項等同single DES，僅有$56\times 1=56$個獨立金鑰位，前兩步等同無效，安全性最低，因金鑰長度不足而被棄用。

Security

3TDEA提供了112位的有效金鑰位，據資料顯示其最佳化的攻擊仍需要$2^{32}$組額外明文、$2^{113}$步、$2^{90}$次DES加密與$2^{88}bit$的記憶體，這在目前的現實電腦仍是無稽之談，因此安全性仍舊存在，目前正在觀察量子電腦的進展，未來有機會攻破這個限制。而2TDEA雖然表面上也有112位的有效金鑰位，但其對於特定的明文攻擊強度較弱，因此被認定僅有約80位的有效金鑰位安全性。