分組密碼的工作模式

2019-11-09 15:03:05

字體：大中小

來源：轉載

供稿：網友

一、理論基礎1.概述密碼學中，塊密碼的工作模式允許使用同一個塊密碼密鑰對多于一塊的數據進行加密，并保證其安全性。塊密碼自身只能加密長度等于密碼塊長度的單塊數據，若要加密變長數據，則數據必須先被劃分為一些單獨的密碼塊。通常而言，最后一塊數據也需要使用合適填充方式將數據擴展到符合密碼塊大小的長度。一種工作模式描述了加密每一數據塊的過程，并常常使用基于一個通常稱為初始化向量的附加輸入值以進行隨機化，以保證安全。工作模式主要用來進行加密和認證。對加密模式的研究曾經包含數據的完整性保護，即在某些數據被修改后的情況下密碼的誤差傳播特性。后來的研究則將完整性保護作為另一個完全不同的，與加密無關的密碼學目標。部分現代的工作模式用有效的方法將加密和認證結合起來，稱為認證加密模式。雖然工作模式通常應用于對稱加密，它亦可以應用于公鑰加密，例如在原理上對RSA進行處理，但在實用中，公鑰密碼學通常不用于加密較長的信息，而是使用混合加密方案。2.歷史和標準化最早出現的工作模式，ECB，CBC，OFB和CFB可以追溯到1981年。2001年，NIST修訂了其早先發布的工作模式工作列表，加入了AES，并加入了CTR模式。最后，在2010年1月，NIST加入了XTS-AES，而其余的可信模式并沒有為NIST所認證。例如CTS是一種密文竊取的模式，許多常見的密碼學運行庫提供了這種模式。ECB，CBC，OFB，CFB，CTR和XTS模式僅僅提供了機密性；為了保證加密信息沒有被意外修改或惡意篡改，需要采用分離的消息驗證碼，例如CBC-MAC。密碼學社群認識到了對專用的保證完整性的方法的需求，NIST因此提出了HMAC，CMAC和GMAC。HMAC在2002年通過了認證，CMAC在2005年通過，GMAC則在2007年被標準化。在發現將認證模式與加密模式聯合起來的難度之后，密碼學社區開始研究結合了加密和認證的單一模式，這種模式被稱為認證加密模式（AE，Authenticated Encryption），或稱為authenc。AE模式的例子包括CCM，GCM，CWC，EAX，IAPM和OCB?，F在，工作模式為許多國家和國內的標準認證實體所定義，其中最有影響力的來源是美國的NIST，而其它有影響力的組織包括ISO，IEC，IEEE，美國的ANSI，以及IETF。3.初始化向量（IV）初始化向量（IV，Initialization Vector）是許多工作模式中用于隨機化加密的一塊數據，因此可以由相同的明文，相同的密鑰產生不同的密文，而無需重新產生密鑰，避免了通常相當復雜的這一過程。初始化向量與密鑰相比有不同的安全性需求，因此IV通常無須保密，然而在大多數情況中，不應當在使用同一密鑰的情況下兩次使用同一個IV。對于CBC和CFB，重用IV會導致泄露平文首個塊的某些信息，亦包括兩個不同消息中相同的前綴。對于OFB和CTR而言，重用IV會導致完全失去安全性。另外，在CBC模式中，IV在加密時必須是無法預測的；特別的，在許多實現中使用的產生IV的方法，例如SSL2.0使用的，即采用上一個消息的最后一塊密文作為下一個消息的IV，是不安全的。4.填充 (密碼學)塊密碼只能對確定長度的數據塊進行處理，而消息的長度通常是可變的。因此部分模式（即ECB和CBC）需要最后一塊在加密前進行填充。有數種填充方法，其中最簡單的一種是在平文的最后填充空字符以使其長度為塊長度的整數倍，但必須保證可以恢復平文的原始長度；例如，若平文是C語言風格的字符串，則只有串尾會有空字符。稍微復雜一點的方法則是原始的DES使用的方法，即在數據后添加一個1位，再添加足夠的0位直到滿足塊長度的要求；若消息長度剛好符合塊長度，則添加一個填充塊。最復雜的則是針對CBC的方法，例如密文竊取，殘塊終結等，不會產生額外的密文，但會增加一些復雜度。布魯斯·施奈爾和尼爾斯·弗格森提出了兩種簡單的可能性：添加一個值為128的字節（十六進制的80），再以0字節填滿最后一個塊；或向最后一個塊填充n個值均為n的字節。CFB，OFB和CTR模式不需要對長度不為密碼塊大小整數倍的消息進行特別的處理。因為這些模式是通過對塊密碼的輸出與平文進行異或工作的。最后一個平文塊（可能是不完整的）與密鑰流塊的前幾個字節異或后，產生了與該平文塊大小相同的密文塊。流密碼的這個特性使得它們可以應用在需要密文和平文數據長度嚴格相等的場合，也可以應用在以流形式傳輸數據而不便于進行填充的場合。二、分組工作模式1.電子密碼本（ECB）最簡單的加密模式即為電子密碼本（Electronic codebook，ECB）模式。需要加密的消息按照塊密碼的塊大小被分為數個塊，并對每個塊進行獨立加密。

Ecb encryption.png

Ecb decryption.png

本方法的缺點在于同樣的平文塊會被加密成相同的密文塊；因此，它不能很好的隱藏數據模式。在某些場合，這種方法不能提供嚴格的數據保密性，因此并不推薦用于密碼協議中。下面的例子顯示了ECB在密文中顯示平文的模式的程度：該圖像的一個位圖版本（左圖）通過ECB模式可能會被加密成中圖，而非ECB模式通常會將其加密成右圖。

原圖使用ECB模式加密提供了偽隨機性的非ECB模式右圖是使用CBC，CTR或任何其它的更安全的模式加密左圖可能產生的結果—與隨機噪聲無異。注意右圖看起來的隨機性并不能表示圖像已經被安全的加密；許多不安全的加密法也可能產生這種“隨機的”輸出。ECB模式也會導致使用它的協議不能提供數據完整性保護，易受到重放攻擊的影響，因此每個塊是以完全相同的方式解密的。例如，“夢幻之星在線：藍色脈沖”在線電子游戲使用ECB模式的Blowfish密碼。在密鑰交換系統被破解而產生更簡單的破解方式前，作弊者重復通過發送加密的“殺死怪物”消息包以非法的快速增加經驗值。2.密碼塊鏈接（CBC）1976年，IBM發明了密碼分組鏈接（CBC，Cipher-block chaining）模式。在CBC模式中，每個平文塊先與前一個密文塊進行異或后，再進行加密。在這種方法中，每個密文塊都依賴于它前面的所有平文塊。同時，為了保證每條消息的唯一性，在第一個塊中需要使用初始化向量。

Cbc encryption.png

Cbc decryption.png

若第一個塊的下標為1，則CBC模式的加密過程為 $C_i = E_K(P_i /oplus C_{i-1}), C_0 = IV$

而其解密過程則為

$P_i = D_K(C_i) /oplus C_{i-1}, C_0 = IV$ CBC是最為常用的工作模式。它的主要缺點在于加密過程是串行的，無法被并行化，而且消息必須被填充到塊大小的整數倍。解決后一個問題的一種方法是利用密文竊取。注意在加密時，平文中的微小改變會導致其后的全部密文塊發生改變，而在解密時，從兩個鄰接的密文塊中即可得到一個平文塊。因此，解密過程可以被并行化，而解密時，密文中一位的改變只會導致其對應的平文塊和下一個平文塊中對應位發生改變，不會影響到其它平文的內容。3.填充密碼塊鏈接（PCBC）填充密碼塊鏈接（PCBC，PRopagating cipher-block chaining）或稱為平文密碼塊鏈接（Plaintext cipher-block chaining），是一種可以使密文中的微小更改在解密時導致平文大部分錯誤的模式，并在加密的時候也具有同樣的特性。

Pcbc encryption.png

Pcbc decryption.png

加密和解密算法如下： $C_i = E_K(P_i /oplus P_{i-1} /oplus C_{i-1}), P_0 /oplus C_0 = IV$ $P_i = D_K(C_i) /oplus P_{i-1} /oplus C_{i-1}, P_0 /oplus C_0 = IV$ PCBC主要用于Kerberos v4和WASTE中，而在其它場合的應用較少。對于使用PCBC加密的消息，互換兩個鄰接的密文塊不會對后續塊的解密造成影響。正因為這個特性，Kerberos v5沒有使用PCBC。4.密文反饋（CFB）密文反饋（CFB，Cipher feedback）模式類似于CBC，可以將塊密碼變為自同步的流密碼；工作過程亦非常相似，CFB的解密過程幾乎就是顛倒的CBC的加密過程： $C_i = E_K (C_{i-1}) /oplus P_i$ $P_i = E_K (C_{i-1}) /oplus C_i$ $C_{0} = / /mbox{IV}$

Cfb encryption.png

Cfb decryption.png

上述公式是描述的是最簡單的CFB，在這種模式下，它的自同步特性僅僅與CBC相同，即若密文的一整塊發生錯誤，CBC和CFB都仍能解密大部分數據，而僅有一位數據錯誤。若需要在僅有了一位或一字節錯誤的情況下也讓模式具有自同步性，必須每次只加密一位或一字節?？梢詫⒁莆患拇嫫髯鳛閴K密碼的輸入，以利用CFB的自同步性。為了利用CFB制作一種自同步的，可以處理任意位情況錯誤的流密碼，需要使用一個與塊的大小相同的移位寄存器，并用IV將寄存器初始化。然后，將寄存器內容使用塊密碼加密，然后將結果的最高x位與平文的x進行異或，以產生密文的x位。下一步將生成的x位密文移入寄存器中，并對下面的x位平文重復這一過程。解密過程與加密過程相似，以IV開始，對寄存器加密，將結果的高x與密文異或，產生x位平文，再將密文的下面x位移入寄存器。下式中Si是移位寄存器的第i個狀態，a << x是指將a移位x位，head(a, x)是指a的高x位，n則是指IV的位數。 $C_i = /mbox{head}(E_K (S_{i-1}), x) /oplus P_i$ $P_i = /mbox{head}(E_K (S_{i-1}), x) /oplus C_i$ $S_i = / ((S_{i-1} << x) + C_i) /mbox{ mod } 2^n$ $S_{0} = / /mbox{IV}$ 若密文的x位發生錯誤，則密碼在移位寄存器恢復與加密時的狀態相同之前，輸出不正確的結果，而當寄存器狀態恢復后，密碼即可以重新同步，恢復正常輸出，因此最多只有一塊數據發生錯誤。與CBC相似，平文的改變會影響接下來所有的密文，因此加密過程不能并行化；而同樣的，與CBC類似，解密過程是可以并行化的。在解密時，密文中一位數據的改變僅會影響兩個平穩塊：對應平文塊中的一位數據與下一塊中全部的數據，而之后的數據將恢復正常。CFB擁有一些CBC所不具備的特性，這些特性與OFB和CTR的流模式相似：只需要使用塊密碼進行加密操作，且消息無需進行填充（雖然密文竊取也允許數據不進行填充）。5.輸出反饋（OFB）輸出反饋模式（Output feedback, OFB）可以將塊密碼變成同步的流密碼。它產生密鑰流的塊，然后將其與平文塊進行異或，得到密文。與其它流密碼一樣，密文中一個位的翻轉會使平文中同樣位置的位也產生翻轉。這種特性使得許多錯誤校正碼，例如奇偶校驗位，即使在加密前計算而在加密后進行校驗也可以得出正確結果。由于XOR操作的對稱性，加密和解密操作是完全相同的： C_i = P_i /oplus O_i

$O_i = / E_K (O_{i-1})$ $O_{0} = / /mbox{IV}$

Ofb encryption.png

Ofb decryption.png

每個使用OFB的輸出塊與其前面所有的輸出塊相關，因此不能并行化處理。然而，由于平文和密文只在最終的異或過程中使用，因此可以事先對IV進行加密，最后并行的將平文或密文進行并行的異或處理?？梢岳幂斎肴?的CBC模式產生OFB模式的密鑰流。這種方法十分實用，因為可以利用快速的CBC硬件實現來加速OFB模式的加密過程。6.計數器模式（CTR）注意：CTR模式（Counter mode，CM）也被稱為ICM模式（Integer Counter Mode，整數計數模式）和SIC模式（Segmented Integer Counter）。與OFB相似，CTR將塊密碼變為流密碼。它通過遞增一個加密計數器以產生連續的密鑰流，其中，計數器可以是任意保證不產生長時間重復輸出的函數，但使用一個普通的計數器是最簡單和最常見的做法。使用簡單的、定義好的輸入函數是有爭議的：批評者認為它“有意的將密碼系統暴露在已知的、系統的輸入會造成不必要的風險”。目前，CTR已經被廣泛的使用了，由輸入函數造成的問題被認為是使用的塊密碼的缺陷，而非CTR模式本身的弱點。無論如何，有一些特別的攻擊方法，例如基于使用簡單計數器作為輸入的硬件差錯攻擊。CTR模式的特征類似于OFB，但它允許在解密時進行隨機存取。由于加密和解密過程均可以進行并行處理，CTR適合運用于多處理器的硬件上。注意圖中的“nonce（隨機數）”與其它圖中的IV（初始化向量）相同。IV、隨機數和計數器均可以通過連接，相加或異或使得相同平文產生不同的密文。

Ctr encryption.png

Ctr decryption.png

三、擴展內容1.誤差傳播在消息驗證碼和認證加密的廣泛應用之前，常常有人討論塊密碼工作模式的“誤差傳播”特性，作為工作模式性能的一部分。例如，若密文傳輸中一個數據塊的錯誤會導致采用ECB模式生成的平文中同樣一個塊的錯誤，而CBC模式中會導致兩個平文塊出錯。有人認為這樣的特性在應對隨機誤差（例如傳輸噪聲）時會是有益的，而還有人認為這樣的特性使得攻擊者更容易篡改消息的一部分。無論如何，若使用了適當的完整性保護措施，這樣的誤差很可能會導致整個消息重發。若需要應對隨機誤差，則應當在發送密文之前增加錯誤校正碼。2.認證加密一些工作模式在設計中希望將保密性和認證性結合起來，例如XCBC，ACBC，APM，OCB，EAX，CWC，CCM和GCM。認證加密模式被可以分為單次處理和兩次處理兩種類型。然而，對密碼學用戶社群而言，不幸的是，許多單次處理的認證加密算法，例如OCB，是為專利所保護的。另外，有的模式也允許為未加密的關聯數據進行認證，因此被稱為AEAD（Authenticated-Encryption with Associated-Data，用于關聯數據的認證加密）。例如，EAX是一種兩次處理的AEAD方法，而OCB模式是單次的。3.其它模式和密碼學概念除了上文中提到的模式以外，還有很多其它的塊密碼工作模式。有的被公眾所接受，有其詳細描述了，甚至被標準化了，并在使用中；而有的則被認為是不安全的，而從未使用過；另外一些則并沒有被分類為保密，認證或簽名加密，例如密鑰反饋模式（KFM，Key Feedback Mode）和AES-hash。NIST維護著一張塊密碼工作模式列表。磁盤加密通常使用特殊目的、專門設計的模式?？梢哉{節的小數據塊加密模式（LRW，XEX和XTS）和大數據塊的模式（CMC和EME）是設計用于加密磁盤區塊的。塊密碼也可以用于其它加密協議中，在這些協議中，塊密碼的使用方式與前述工作模式相似。在一切協議中，為了保證其安全性，必須在構建工作模式時特別注意。有數種方法可以用塊密碼構建密碼散列函數，參見單向壓縮函數。消息認證碼（MAC）通常由塊密碼得到，例如CBC-MAC，OMAC和PMAC。認證加密也采用塊密碼作為其中的一部，其同時使用加密和MAC以提供保密性和數據完整性，例如IAPM，CCM，CWC，EAX，GCM和OCB。轉自：http://blog.163.com/kevinlee_2010/blog/static/16982082020113853451308/

上一篇：PBOC3.0中使用的國密SM2算法

下一篇：算法（一）時間復雜度