3.2　對稱密鑰加密

對稱密鑰加密（symmetric key cryptography），又稱為私鑰加密、單鑰加密，因同一個密鑰既用于加密又用于解密而得名。

密鑰實際上就是一串二進制數據。既然對稱加密方法的密鑰也要用于解密，那么密鑰一定要被妥善保護好、絕不示人，這是其稱為私鑰的原因。又由于密文的合法接受者也需要這個私鑰，所以如何在通信雙方間安全地分享密鑰就顯得非常重要。

對稱密鑰加密是實現信息保密的主要手段，具有如下技術特點：

?　密鑰是關鍵（Key is key）?，F代加密技術的加密算法可以公布，加密代碼也可以公開，只要保護好密鑰，密文就是安全的。

?　密鑰長度決定安全性。密鑰越長則加密強度越大，因為窮舉密鑰幾乎是嘗試破解的唯一方式，那么密鑰每增加1位，就可以給破解者的計算工作量增加1倍，密鑰增加1字節，破解工作量就是原來的256倍，相當于原本1天就可破解，現在則需要將近1年。

?　對稱加密算法被設計為具有很高的計算效率，可面向大量數據的加密，如文件、數據庫、流媒體等，然而密鑰的安全生成、安全分發、安全存儲、安全使用需要較大的管理工作量。

對稱密鑰加密可分為流式加密和分組加密兩大類，前者適用于流媒體應用，例如在線播放音樂或視頻，后者應用范圍更廣，適用于絕大多數需要數據加密的場合。常用的對稱密鑰加密技術有BLOWFISH、TEA、DES、AES、IDEA、SM4、RC4等，本章選取其中具有代表性的SM4和DES來展開算法細節。

在比特幣核心系統中并沒有直接采用對稱密鑰加密技術，這應該與比特幣提倡信息透明化有關，而且存儲的信息也比較單一。但是在區塊鏈擴展應用中，當需要對保存的私密信息進行保護時，對稱密鑰加密技術就有用武之地了。

3.2.1　分組加密技術原理

分組加密（block ciphering）是以一定長度的數據塊為單位，對其進行整體變換，從明文塊生成密文塊，密文塊與明文等長，一塊數據加密完成后繼續加密下一塊，密文塊也是依次執行解密。就加密算法本身而言，每一塊數據的加密或解密運算都可以獨立進行。

設分組大小為nB（字節）。明文數據交付加密前，需要先進行數據填充（填充數據可為任意數值），如圖3.5所示，使總長度為n的整數倍。最后4字節為長度字段，用以表示有效數據長度，以便解密后完全恢復原始數據。

顯然，對nb（位）的分組，有2ⁿ個不同的明文分組和2ⁿ個不同的密文分組，相互間共有2ⁿ！個非奇異的映射（變換）關系。

不失一般性，設n=4，如圖3.6所示，4b明文分組M=（M₃M₂M₁M₀）共有2⁴=16種編碼組合，編碼器的16個輸出分別為X₀~X_f，共有2⁴！=20，922，789，888，000種不同的映射關系。設對于一種特定的映射關系轉換為Y₀~Y_f，可解碼為4b，輸出C=（C₃C₂C₁C₀），C即為明文M加密后的密文。例如，4b明文為1001（十六進制9），編碼結果應為X₉，在圖3.6所示的映射關系下被轉換為Y₇，則可解碼并輸出密文0111。在相同的映射關系下，若以C為密文輸入、M為明文輸出，則為解密操作。

“不對啊，4位明文不是應該就只有16種編碼組合，怎么會弄出16！個映射關系呢？”Bob有點不在狀態，腦子一時轉不過彎來。

樂于助人的Alice一如既往地耐心解釋：“映射是從編碼器的16個輸出到解碼器的16個輸入之間的不同關系。對于例子中的映射關系，X₉映射為Y₇、X₂映射為Y₀，如果換一種映射關系，例如只把Y₀和Y₁上兩根線調換位置，其他不變，那么X₉仍然映射為Y₇，X₂就映射為Y₁了。所以編碼組合與映射關系是不同的概念?！?/p>

當映射關系改變時，同一個明文可輸出不同的密文，這就相當于采用了不同的密鑰而產生不同的加密結果。換句話說，映射關系就是密鑰，每一種變換就是一個密鑰。因此，映射關系需要像個“黑盒子”一樣嚴密保護起來。

這個加密模型窮盡了所有的編碼和映射關系，在技術上已經無法更好了，因此被稱為是“理想分組加密”方法，保密性達到最佳。然而，理想歸理想，該模型存在一個不容忽視的問題：密鑰過長。如圖3.6所示的映射關系可表示為如圖3.7所示的編碼對應表，每一種不同映射產生一張表，nb明文總共可得2ⁿ！張表。不失一般性，將明文編碼統一為升序排列，密文一行所代表的就是密鑰，則密鑰長度為n×2ⁿb。對于常用的64b分組，其密鑰長度將達到驚人的10²¹b。過長的密鑰對數據加密的計算和管理均會帶來不利影響。

所以實際的分組加密算法設計采用的是理想分組加密的近似體制，相當于取不同映射關系的一個子集，以減少映射關系數為代價，換取較短的密鑰長度，雖然犧牲了一部分保密性，但使加密方法更具有實用性。

根據信息論創始人香農（Claude Shannon）的加密理論，使用信息編碼的混淆（confusion）和擴散（diffusion）方法，可以抵抗基于統計方法的密碼分析（破解）?；煜梢员M可能使密文和密鑰間的統計關系復雜化，防止密鑰被發現；擴散則使明文的統計特征消散在密文中，可以讓每個明文編碼單元盡可能多地影響多個密文編碼單元。

費斯托（Feistel）模型就是基于香農理論設計的對稱密鑰加密統一架構。各種對稱密鑰加密算法都是參照這一模型設計的。在Feistel模型中，數據運用代換（substitution）和置換（swap）操作進行處理，分別就是混淆和擴散的實際應用。代換采用函數運算方法，置換通過數據的交叉換位實現。

設：明文和密文為2wb，密鑰為K。圖3.8所示即為Feistel加密的算法結構。該模型由i輪加密運算組成，每輪具有相似的運算方法，分別使用由密鑰K生成的該輪次的子密鑰K_i。每輪2wb輸入被分為wb的左半部分和wb的右半部分，進行代換運算，在輸出前左、右兩部分進行置換運算。算法結束前再進行一次左右置換運算，最終合并成2wb的密文。

解密過程與加密過程完全一致（注意不是逆向進行），但解密時逆序使用子密鑰。這一論斷的正確性可被證明，如下：

不失一般性，設加密算法執行16輪，再設：加密時，明文為LE₀|RE₀，輸出密文為RE₁₆|LE₁₆；解密時，密文為LD₀|RD₀，輸出密文為RD₁₆|LD₁₆。

顯然有：

LD₀=RE₁₆，　RD₀=LE₁₆

對于加密過程有：

LE₁₆=RE₁₅，　RE₁₆=LE₁₅⊕f（RE₁₅，K₁₆）

其中，⊕表示按位異或運算（位相同得0，相異得1），其“優秀”性質是一個數被另一個數異或兩次就會還原。

按照解密過程第1輪算法有：

LD₀=RE₁₆，　RD₀=LE₁₆，　LD₁=RD₀=LE₁₆=RE₁₅

RD₁=LD₀⊕f（RD₀，K₁₆）=RE₁₆⊕f（RE₁₅，K₁₆）=[LE₁₅⊕f（RE₁₅，K₁₆）]⊕f（RE₁₅，K₁₆）=LE₁₅

因此，解密第1輪輸出LE₁₅|RE₁₅，正是加密第16輪輸入左右互換的值。

依此類推，解密第16輪：

LD₁₆=RE₀，　RD₁₆=LE₀

最終換位輸出為LE₀|RE₀，正是原始明文（證畢）。

Feistel加密模型采用的i輪次運算又稱為迭代（iteration）操作。迭代輪次數越多，密文信息的混淆和擴散越徹底，保密性就越強，但會有加解密速度越慢的“后遺癥”，作為妥協，通常選擇16輪迭代。此外，分組長度和密鑰長度越長，安全性能也越好，但同樣存在拖慢運算速度的弊端，常見的分組長度選擇64b或128b，密鑰長度則會根據算法指標、密級要求來確定。

3.2.2　SM4算法

SM4算法（原名SMS4）是基于Feistel模型的對稱密鑰分組加密算法，作為中國的第一個商用密碼國家標準，于2006年1月發布。

SM4采用的數據分組長度和密鑰長度均為128b，數據處理單位為8b和32b，進行32輪非線性迭代運算。

如圖3.9所示，SM4將128b的明文分割為4個32b分組塊，采用8次循環，每次使用輪函數f進行4輪迭代（故總共為32輪迭代），每輪使用一個子密鑰（輪密鑰）。子密鑰由128b的密鑰經擴展函數g生成。最后，反向排列32b的X₃₂~X₃₅，合并為128b的密文。

SM4的加密運算過程可用如圖3.10所示的等價變換圖表示。

設X_j為32b寄存器，k_i為輪密鑰。SM4每輪的迭代運算由按位異或（⊕）、循環左移（＜＜＜）和變換函數S所組成，輪函數f定義如下：

X_i+4=f（X_i，X_i+1，X_i+2，X_i+3，k_i）

=X_i⊕T（X_i+1⊕X_i+2⊕X_i+3⊕k_i），i=0，1，…，31

T（x）=L（S（x））

L（x）=x⊕（x＜＜＜2）⊕（x＜＜＜10）⊕（x＜＜＜18）⊕（x＜＜＜24）

如圖3.11所示，32b的S函數由4個并列的8b單元的S-box變換所構成。S-box采用查表選擇法，使用如表3.1所示的置換選擇表，屬于一種非線性變換方式。表中的256個數值從0x00到0xff，具有唯一性。設S-box的8b輸入為十六進制0xRC，S-box以R為行號、C為列號查表，所得的數據作為S-box的輸出結果。例如，輸入0x2a應查行號為2、列號為a的數據，經S-box輸出為0x0b。

SM4加密算法每輪使用不同的32b子密鑰，每個子密鑰都是由128b原始密鑰K經變換生成。設4個32b常數為FK_i（i=0，1，2，3）：

FK₀=0xA3B1BAC6，　FK₁=0x56AA3350，

FK₂=0x677D9197，　FK₃=0xB27022DC

又設32b參數為CK_i（i=0，1，2，…，31），定義：CK_i=<ck[i][0]|ck[i][1]|ck[i][2]|ck[i][3]>，即CK_i是由4個一組的8b數值ck[i][j]（j=0，1，2，3）拼接而成，而ck[i][j]可根據其下標進行取值：ck[i][j]=（4i+j）×7（mod 256）。由此可得32個CK_i參數為：

      00070e15 1c232a31 383f464d 545b6269 70777e85 8c939aa1 a8afb6bd c4cbd2d9
      e0e7eef5 fc030a11 181f262d 343b4249 50575e65 6c737a81 888f969d a4abb2b9
      c0c7ced5 dce3eaf1 f8ff060d 141b2229 30373e45 4c535a61 686f767d 848b9299
      a0a7aeb5 bcc3cad1 d8dfe6ed f4fb0209 10171e25 2c333a41 484f565d 646b7279

將密鑰K分割為4個32b數值，即K=（K₀，K₁，K₂，K₃）。設每輪使用的子密鑰為k_i（i=0，1，2，…，31），Z_j為中間變量，密鑰變換算法如下：

Z_j=K_j⊕FK_j，　j=0，1，2，3

k_i=Z_i+4=Z_i⊕T′（Z_i+1⊕Z_i+2⊕Z_i+3⊕CK_i）

T′（x）=L′（S（x）），　L′（x）=x⊕（x?13）⊕（x?23）

可見，SM4子密鑰的生成同樣采用了加密運算中的S函數變換，迭代運算方法也很類似，便于算法的實現。

SM4算法的解密過程與加密完全相同，但逆序使用子密鑰。

3.2.3　DES算法

數據加密標準（Data Encryption Standard，DES）是信息加密領域最著名、應用最廣泛的對稱密鑰加密技術，于1977年作為美國聯邦標準發布，被全球各國廣泛采用。DES采用DEA（Data Encryption Algorithm）算法，但習慣上稱之為DES算法。

DES符合Feistel模型，針對64b數據塊（分組）進行加密和解密操作。DES采用的密鑰為64b的任意數，每字節的最高位作為奇偶校驗位，因此實際密鑰長度為56b。

輸入明文被劃分成64b分組單元，DES對每個分組進行16輪迭代運算，每輪使用一個48b的子密鑰，而子密鑰由56b的原始密鑰變換而來。

DES算法首先對64b（設編號為1~64）的輸入分組作初始置換（Initial Permutation，IP），置換規則如表3.2所示：第6位置換到第24位的位置，第57位置換到第33位的位置。即把位排列次序“打亂”，最后輸出自然地分為32b的L₀、R₀兩部分。

隨后，DES進入16輪的迭代運算f，包括擴展換位運算、選擇壓縮運算、置換運算等步驟，每輪使用一個子密鑰K_i。運算過程如表3.3所示。

經過16輪次迭代運算f后，得到L₁₆和R₁₆，以此作為輸入，進行如表3.4所示的逆置換（IP^-1）操作，即可得到輸出的64b密文。IP^-1正好是IP的逆變換，例如，第1位經過IP后，在第40位的位置；而通過IP^-1后，從第40位換回到第1位的位置。

擴展換位運算E可實現32b到48b變換，如表3.5所示，位排列次序發生變化，部分位被復制。

置換運算P實現的是32b的換位操作，如表3.6所示，對位排列次序進行了調整。

選擇壓縮運算S如圖3.12所示。輸入的48b數據被均分為8份，各為6b，分別由S所包含的S₁~S₈8個選擇函數（S-box）進行處理。每個選擇函數的功能是把6b數據變換為4b數據，最終把48b輸入值壓縮轉換為32b。

選擇函數S₁~S₈采用查表變換方法。如表3.7所示，每個S-box均占有4行（0~3行）、每行16列（0~15列）的數值矩陣。設輸入6b數據為D₁D₂D₃D₄D₅D₆，令列號=D₂D₃D₄D₅（取值0，1，2，…，15），行號=D₁D₆（取值0，1，2，3），查表得到對應的數以4b表示，即得到S-box輸出。例如，S₈輸入110110，則行、列號為（2，11），查表得6，輸出為0110。

16輪迭代運算f中，每輪使用的子密鑰K₀~K₁₅來自64b初始會話密鑰K（bit₀~bit₆₃）。先實施密鑰縮小選擇換位運算1（如表3.8所示），換位的同時順便去除了校驗位（每字節的最高位，如bit₇），得到各28b的兩部分P和Q，作為每次計算子密鑰的輸入。

共16次密鑰變換（i=0，1，2，…，15）的計算方式一致：對P和Q分別進行M[i]位循環左移，M[i]={1，1，2，2，2，2，2，2，1，2，2，2，2，2，2，1}，得P和Q，合并得到56b后，再實施縮小選擇換位運算2（如表3.9所示），即獲得用于第i輪迭代運算的48b子密鑰K_i。

DES解密運算方法和加密完全一致，只是逆向使用子密鑰。

DES在誕生之初，有人曾估計要使用耗資2000萬美元的專用計算機連續運行12小時才可能將其破解，當時它被認為很強大。然而，這一經典的算法如今面臨安全性嚴重不足的問題，一方面是破解方法不斷被探索，另一方面是56b密鑰長度太短，很難抵抗性能越來越強大的計算機進行的暴力攻擊。

改善DES保密性的一種可行方式為三重DES（triple DES），即對一個明文分組用3個相同或不同的密鑰實施3次DES加密（或解密）運算，可獲得大約相當于112b長度密鑰的強度。設：加密操作為E，解密操作為D，密鑰為K₁、K₂、K₃，則可采用以下4種模型之一實現加密：E（K₁）E（K₂）E（K₃）；E（K₁）D（K₂）E（K₃）；E（K₁）E（K₂）E（K₁）；E（K₁）D（K₂）E（K₁）。

DES加密實際應用時，根據在加密過程中對明文分組不同的處理手段，分為4種工作方式（如圖3.13所示），有的支持并行計算，有的可加強密文分組之間的相關性。

DES算法的改進是高級加密標準（Advanced Encryption Standard，AES）。