分組密碼的工作模式

2019-11-09 15:03:05

字體：大中小

供稿：網(wǎng)友

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

Ecb encryption.png

Ecb decryption.png

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

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

Cbc encryption.png

Cbc decryption.png

若第一個塊的下標(biāo)為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是最為常用的工作模式。它的主要缺點在于加密過程是串行的，無法被并行化，而且消息必須被填充到塊大小的整數(shù)倍。解決后一個問題的一種方法是利用密文竊取。注意在加密時，平文中的微小改變會導(dǎo)致其后的全部密文塊發(fā)生改變，而在解密時，從兩個鄰接的密文塊中即可得到一個平文塊。因此，解密過程可以被并行化，而解密時，密文中一位的改變只會導(dǎo)致其對應(yīng)的平文塊和下一個平文塊中對應(yīng)位發(fā)生改變，不會影響到其它平文的內(nèi)容。3.填充密碼塊鏈接（PCBC）填充密碼塊鏈接（PCBC，PRopagating cipher-block chaining）或稱為平文密碼塊鏈接（Plaintext cipher-block chaining），是一種可以使密文中的微小更改在解密時導(dǎo)致平文大部分錯誤的模式，并在加密的時候也具有同樣的特性。

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中，而在其它場合的應(yīng)用較少。對于使用PCBC加密的消息，互換兩個鄰接的密文塊不會對后續(xù)塊的解密造成影響。正因為這個特性，Kerberos v5沒有使用PCBC。4.密文反饋（CFB）密文反饋（CFB，Cipher feedback）模式類似于CBC，可以將塊密碼變?yōu)樽酝降牧髅艽a；工作過程亦非常相似，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相同，即若密文的一整塊發(fā)生錯誤，CBC和CFB都仍能解密大部分數(shù)據(jù)，而僅有一位數(shù)據(jù)錯誤。若需要在僅有了一位或一字節(jié)錯誤的情況下也讓模式具有自同步性，必須每次只加密一位或一字節(jié)。可以將移位寄存器作為塊密碼的輸入，以利用CFB的自同步性。為了利用CFB制作一種自同步的，可以處理任意位情況錯誤的流密碼，需要使用一個與塊的大小相同的移位寄存器，并用IV將寄存器初始化。然后，將寄存器內(nèi)容使用塊密碼加密，然后將結(jié)果的最高x位與平文的x進行異或，以產(chǎn)生密文的x位。下一步將生成的x位密文移入寄存器中，并對下面的x位平文重復(fù)這一過程。解密過程與加密過程相似，以IV開始，對寄存器加密，將結(jié)果的高x與密文異或，產(chǎn)生x位平文，再將密文的下面x位移入寄存器。下式中Si是移位寄存器的第i個狀態(tài)，a << x是指將a移位x位，head(a, x)是指a的高x位，n則是指IV的位數(shù)。 $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位發(fā)生錯誤，則密碼在移位寄存器恢復(fù)與加密時的狀態(tài)相同之前，輸出不正確的結(jié)果，而當(dāng)寄存器狀態(tài)恢復(fù)后，密碼即可以重新同步，恢復(fù)正常輸出，因此最多只有一塊數(shù)據(jù)發(fā)生錯誤。與CBC相似，平文的改變會影響接下來所有的密文，因此加密過程不能并行化；而同樣的，與CBC類似，解密過程是可以并行化的。在解密時，密文中一位數(shù)據(jù)的改變僅會影響兩個平穩(wěn)塊：對應(yīng)平文塊中的一位數(shù)據(jù)與下一塊中全部的數(shù)據(jù)，而之后的數(shù)據(jù)將恢復(fù)正常。CFB擁有一些CBC所不具備的特性，這些特性與OFB和CTR的流模式相似：只需要使用塊密碼進行加密操作，且消息無需進行填充（雖然密文竊取也允許數(shù)據(jù)不進行填充）。5.輸出反饋（OFB）輸出反饋模式（Output feedback, OFB）可以將塊密碼變成同步的流密碼。它產(chǎn)生密鑰流的塊，然后將其與平文塊進行異或，得到密文。與其它流密碼一樣，密文中一個位的翻轉(zhuǎn)會使平文中同樣位置的位也產(chǎn)生翻轉(zhuǎn)。這種特性使得許多錯誤校正碼，例如奇偶校驗位，即使在加密前計算而在加密后進行校驗也可以得出正確結(jié)果。由于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的輸出塊與其前面所有的輸出塊相關(guān)，因此不能并行化處理。然而，由于平文和密文只在最終的異或過程中使用，因此可以事先對IV進行加密，最后并行的將平文或密文進行并行的異或處理。可以利用輸入全0的CBC模式產(chǎn)生OFB模式的密鑰流。這種方法十分實用，因為可以利用快速的CBC硬件實現(xiàn)來加速OFB模式的加密過程。6.計數(shù)器模式（CTR）注意：CTR模式（Counter mode，CM）也被稱為ICM模式（Integer Counter Mode，整數(shù)計數(shù)模式）和SIC模式（Segmented Integer Counter）。與OFB相似，CTR將塊密碼變?yōu)榱髅艽a。它通過遞增一個加密計數(shù)器以產(chǎn)生連續(xù)的密鑰流，其中，計數(shù)器可以是任意保證不產(chǎn)生長時間重復(fù)輸出的函數(shù)，但使用一個普通的計數(shù)器是最簡單和最常見的做法。使用簡單的、定義好的輸入函數(shù)是有爭議的：批評者認為它“有意的將密碼系統(tǒng)暴露在已知的、系統(tǒng)的輸入會造成不必要的風(fēng)險”。目前，CTR已經(jīng)被廣泛的使用了，由輸入函數(shù)造成的問題被認為是使用的塊密碼的缺陷，而非CTR模式本身的弱點。無論如何，有一些特別的攻擊方法，例如基于使用簡單計數(shù)器作為輸入的硬件差錯攻擊。CTR模式的特征類似于OFB，但它允許在解密時進行隨機存取。由于加密和解密過程均可以進行并行處理，CTR適合運用于多處理器的硬件上。注意圖中的“nonce（隨機數(shù)）”與其它圖中的IV（初始化向量）相同。IV、隨機數(shù)和計數(shù)器均可以通過連接，相加或異或使得相同平文產(chǎn)生不同的密文。

Ctr encryption.png

Ctr decryption.png

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

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

下一篇：算法（一）時間復(fù)雜度