1、2021-5-25page: 1 對稱密碼體制 楊秋偉 湖南大學 計算機與通信學院 2021-5-25 page: 2 對稱密碼體制 o對稱密碼體制的特征對稱密碼體制的特征 n加密密鑰和解密密鑰相同 p對稱密碼體制的主要研究課題對稱密碼體制的主要研究課題 n密鑰的產生 n密鑰的管理 加密器 ek 解密器 dk 密文密文明文明文 明文明文 k 密鑰產生器 k 2021-5-25 page: 3 對稱密碼體制組成 o流密碼 o分組密碼 o數據加密標準(des) o高級加密標準(aes) 2021-5-25 page: 4 流密碼：流密碼引論流密碼引論 o流密碼流密碼是將明文劃分成字符(如單個字母)

2、，或其編碼的基本單元 (如按位)，字符分別與密鑰流作用進行加密，解密時以同步產生的 同樣的密鑰流實現。 o流密碼強度完全依賴于密鑰序列的隨機性隨機性(randomness)和不可預測不可預測 性性(unpredictability)。 n核心問題是密鑰流的產生密鑰流生成器的設計 n保持收發兩端密鑰流的精確同步是實現可靠解密的關鍵技術 2021-5-25 page: 5 流密碼：流密碼的基本概念流密碼的基本概念 o流密碼的基本思想：流密碼的基本思想：假設存在著明文串x = x0 x1x2 n利用密鑰k和密鑰流發生器f產生一個密鑰流z = z0z1z2。其中， zi = f(k,i)，i是加密器中

3、的記憶元件在時刻i的狀態，f是以密鑰 k和i作為輸入參數的函數； n加密加密： y = y0y1y2 = ez0(x0) ez1(x1) ez1(x1)； 內部記憶元件 yi= ezi(xi) xiyi k 2021-5-25 page: 6 流密碼：同步流密碼同步流密碼 o同步流密碼同步流密碼：加密器中記憶元件的存儲狀態i獨立于明文字符。 o同步流密碼加密器同步流密碼加密器 n密鑰流產生器 n加密變換器 p加密變換器一般采用二元邏輯運算xor，即有限域gf(2)上討論 的二元加密流密碼，變換表示為：yi = zi xi p一次一密亂碼本一次一密亂碼本是加法流密碼的原型 2021-5-25 p

4、age: 7 流密碼：流密碼的密鑰流產生器流密碼的密鑰流產生器 o密鑰流產生器的內涵密鑰流產生器的內涵 n輸入：密鑰k和加密器中的記憶元件在時刻i的狀態i； n輸出：密鑰流zi 狀態狀態i 密鑰密鑰k 狀態狀態i+1 密鑰流密鑰流zi 2021-5-25 page: 8 流密碼：密鑰流生成器的設計原則密鑰流生成器的設計原則 o足夠長的周期足夠長的周期 o高線性復雜度高線性復雜度 o統計性能良好統計性能良好 o足夠的足夠的“混亂混亂” n強調密鑰的作用，增加密鑰與密文之間關系的復雜性 o足夠的足夠的“擴散擴散” n小擾動的影響波及到全局密文沒有統計特征，明文一位影響密 文的多位，增加密文與明文之

5、間關系的復雜性 o抵抗不同形式的攻擊抵抗不同形式的攻擊 2021-5-25 page: 9 流密碼：有限狀態自動機有限狀態自動機(fa) o具有離散輸入和輸出(輸入集和輸出集均有限)的一種數學模型 n有限狀態集s=si|i=1,2,l n有限輸入字符集x=xi|i=1,2,m n有限輸出字符集y=yk|k=1,2,n n轉移函數 o yjf1(sj, xj) o sj+1 f2(sj, xj) 即在狀態sj，輸入字符xj時，輸出為yj，狀態轉移為sj+1。 2021-5-25 page: 10 流密碼：有限狀態自動機舉例有限狀態自動機舉例 o例一例一 ns=s1,s2,s3,x=x1, x2,

6、x3,y=y1,y2,y3 n轉移函數 f1x1x2x3 s1 s2 s3 y1 y2 y3 y3 y1 y2 y2 y3 y1 f2x1x2x3 s1 s2 s3 s2 s3 s1 s1 s2 s3 s3 s1 s2 2021-5-25 page: 11 流密碼：有限狀態自動機舉例有限狀態自動機舉例 o若輸入為 x1x2x1x3x3x1 o初始狀態s1 o輸出為 y1y1y2y1y3y1 2021-5-25 page: 12 流密碼：基于基于fa的密鑰流產生器的密鑰流產生器 o同步流密碼的密鑰流產生器可看為一個參數為k的fa：輸出集z， 狀態集，狀態轉移函數和輸出函數，初態0 o設計的關鍵是

7、(phi fai)和(psi psai) i k k zi 2021-5-25 page: 13 流密碼：基于基于fa的密鑰流產生器的密鑰流產生器 o一個良好的密鑰流產生器一個良好的密鑰流產生器 n極大的周期 n良好的統計特性 n抗線性分析 n抗統計分析 o具有非線性的的fa理論很不完善，通常采用線性以及非線性的 。可將此類產生器分為驅動部分驅動部分和非線性組合非線性組合部分。 n驅動部分控制狀態轉移 n非線性組合部分提供統計特性良好的序列 2021-5-25 page: 14 流密碼：兩種常見兩種常見的密鑰流產生器的密鑰流產生器 lfsr 非線性組合函數 zi lfsr1 lfsr2 lfs

8、r3 非 線 性 組 合 函 數 zi lfsr：線性反饋移位寄存器流密碼產生密鑰流的主要組成部分。 2021-5-25 page: 15 流密碼：反饋移位寄存器的概念反饋移位寄存器的概念 o基本概念基本概念 n級數級數(stages)：存儲單元數n n狀態狀態(state)：n個存儲單元的存數(ki, , ki+n-1) n反饋函數：反饋函數：f(ki, ki+1, , ki+n-1)是狀態(ki, ki+n-1)的函數 n線性反饋移位寄存器線性反饋移位寄存器(lfsr)：f 為線性函數 n非線性反饋移位寄存器：非線性反饋移位寄存器： f 為非線性函數 2021-5-25 page: 16

9、流密碼：反饋移位寄存器反饋移位寄存器 f(ki, ki+1, , ki+n-1) ki+n-1 ki+n-2ki+1ki ki+n 輸出序列 寄存 移位 反饋 2021-5-25 page: 17 流密碼：線性反饋移位寄存器線性反饋移位寄存器 of(x)為線性函數線性函數，輸出序列滿足下式 1011 ( ,)002 i nii nini ni kf kkc kckic ，其中：，或1， 是模 加法。 ki+n-1ki+n-2ki+1ki cn-1cn-2c1c0ki+n 輸出序列 2021-5-25 page: 18 流密碼：lfsr的特征多項式的特征多項式 olfsr的特征多項式：的特征多項

10、式：以lfsr的反饋系數所決定的一元高次多項式 又稱反饋多項式反饋多項式。 p由于cigf(2)(i = 1,2,n)，所以有2n組初始狀態，即有2n個遞推序 列，其中非恒零的有2n-1個。 21 121 0 ( )1. n nnj nnj j f xc xc xcxc xc x 2021-5-25 page: 19 流密碼：lfsr的生成函數的生成函數 p給定序列 kii0，冪級數冪級數 稱為該序列的生成函數生成函數 p定理：定理：令kii0(f)，f(x)是反饋多項式，令k(x)是kii0的生成函數， 則 其中 1 1 ( ) i i i k xk x ( ) ( ) ( ) a x k

11、x f x 1 11 ( )() jn njl njl jl a xcxa x 2021-5-25 page: 20 流密碼：lfsr的生成函數的生成函數 o定理證明定理證明 , 00 min() 00 1 000 () 0 ( ) ( )()() () ( )()() ( ) n il il il j n j n lj l jl jnn jj n lj ln lj l jlj n l n j tj nt j nj k x f xk xc x ckx ckxckx a xc kxnlt a x 2021-5-25 page: 21 流密碼：lfsr的周期的周期 olfsr 周期的真正涵義？周期

12、的真正涵義？ o定義定義：設p(x)是gf(2)上的多項式，使p(x)|(xp-1)的最小p稱為p(x)的 周期或者階。 o定理定理：設序列ki的特征多項式p(x)定義gf(2)上，p是p(x)的周期， 則ki的周期r | p。 o定理定理：設序列ki的特征多項式p(x)定義gf(2)上，且p(x)是不可約 多項式， p是p(x)的周期，則ki的周期為p。 2021-5-25 page: 22 流密碼：lfsr的周期的周期 om序列：序列：序列ki0in的周期達到最大2n-1時，稱該序列為m序列。 o定理：定理：以f(x)為特征多項式的lfsr的輸出序列是m序列的充要條件 為f(x)是本原的。

13、 om序列的性質序列的性質 nn級m序列的周期為2n1，周期隨n增加而指數級遞增； n只要知道n次本原多項式，m序列極易生成； nm序列極不安全，只要泄露2n位連續數字，就可完全確定出反 饋多項式系數。 階為2n-1的n次不 可約多項式 2021-5-25 page: 23 流密碼：lfsr的周期的周期 om序列的破譯序列的破譯 n已知ki, ki+1, ki+2n，由遞推關系式可得出下式 n式中有n個線性方程和n個未知量，故可惟一解出ci，0in-1。 12 1 1 1 0 21 21 11 . . . . . . . . . . . . ni ni ni nninini niii niii

14、 k k k c c c kkk kkk kkk 2021-5-25 page: 24 流密碼：非線性序列非線性序列 olfsr雖然不能直接作為密鑰流用，但可作為驅動源以其輸出推動 一個非線性組合函數非線性組合函數所決定的電路來產生非線性序列。這就是所 謂非線性前饋序列生成器非線性前饋序列生成器。 nlfsr用來保證密鑰流的周期長度、平衡性等； n非線性組合函數用來保證密鑰流的各種密碼性質，以抗擊各種 可能的攻擊。 2021-5-25 page: 25 流密碼：非線性前饋序列非線性前饋序列 o前饋函數前饋函數f(非線性組合函數) o輸出序列的周期性、隨機性、線性復雜度以及相關免疫性之間的 關系

15、 lfrs f ki 2021-5-25 page: 26 流密碼：j-k觸發器觸發器 pj-k觸發器觸發器是一個非線性器件，有兩個輸入端j和k，輸出為qi。輸出 不僅依賴于輸入，還依賴于前一個輸出位qi-1，即 p其結構及邏輯真值表如下所示 121112 (), ii qxx qxx xjk 其中分別為 和 的輸入。 jkqk 0 0 1 1 0 1 0 1 qk-1 0 1 1k q j k r = qk-1 qk 2021-5-25 page: 27 流密碼：j-k觸發器的非線性序列生成器觸發器的非線性序列生成器 oak和bk被稱為非線性序列生成器的驅動序列。 o性質性質：設ak和bk分

16、別為x級和y級m序列。當x和y互素，且a0 + b0 =1時，序列ck的周期為(2x-1)(2y-1)。 lfsr1 lfsr2 ak bk j k ck 2021-5-25 page: 28 流密碼：多路選擇序列多路選擇序列 p有n種輸入序列b0(t), bn-1(t) ，在地址序列a1(t),am -1 (t)的控制下 決定輸出取自某個輸入比特。 pless生成器生成器 n例如取m級lfsr生成m序列作地址控制，取n級lfsr生成的m 序列作為輸入序列。 )()()( 110 tbtbtb n )( )( )( 1 1 0 ta ta ta m 制 控 址 地 可供選擇的輸入 2021-5

17、-25 page: 29 對稱密碼體制組成 o流密碼 o分組密碼 o數據加密標準(des) o高級加密標準(aes) 2021-5-25 page: 30 對稱密碼體制：分組密碼分組密碼 o分組密碼的工作原理分組密碼的工作原理 n將明文分成n個塊，m1, m2, , mn； n對每個塊執行相同的變換，從而生成n個密文塊，c1, c2, , cn。 p分組密碼的工作模式分組密碼的工作模式：明文分組固定，消息的數據量不同，數據 格式各式各樣。為了適應各種應用環境，有四種工作模式。 n電子編碼薄模式(ebc) n密碼分組鏈接模式(cbc) n密碼反饋模式(cfb) n輸出反饋模式(ofb) 2021

18、-5-25 page: 31 分組密碼：分組密碼的工作模式比較分組密碼的工作模式比較 模式描述用途 電碼本模式(ecb)每個明文組獨立地以同一密鑰加密。傳送短數據 密碼分組鏈接模式 (cbc) 加密算法的輸入是當前明文組與前一密文組 的異或。 傳送數據分組； 認證。 密碼反饋模式(cfb)每次只處理輸入的j比特，將上一次的密文用 作加密算法的輸入以產生偽隨機輸出，該輸 出再與當前明文異或以產生當前密文。 傳送數據流；認 證。 輸出反饋模式(ofb)與cfb類似，不同之處是本次加密算法的輸 入為前一次加密算法的輸出。 有擾信道上(無線 通訊)傳送數據流 2021-5-25 page: 32 分組

19、密碼：分組密碼的經典工作模式分組密碼的經典工作模式 電子編碼薄模式 密碼分組鏈接模式 輸出反饋模式 2021-5-25 page: 33 分組密碼：分組密碼的擴散與壓縮分組密碼的擴散與壓縮 o分組密碼的基本過程分組密碼的基本過程 n將明文分成m個塊，m1, m2, , mm； n對每個塊執行相同的變換，從而生成m個密文塊，c1, c2, , cm。 解密加密 密鑰k=(k0, k1, kt-1 )密鑰k=(k0, k1, kt-1 ) 明文x=(x0, x1, xm-1) 密文x=(y0, y1, yn-1) 明文x=(x0, x1, xm-1) 2021-5-25 page: 34 分組密碼

20、：分組密碼的擴展與壓縮分組密碼的擴展與壓縮 p將明文x和密文y表示成分別小于2m和2n的整數，并用分量形式描述。 每個分量分別用xi，yigf(2) 表示，即： n若nm，則為有數據擴展數據擴展的分組密碼； n若n n / 2 okk1,kc = 0(p ) kk1,kc = 1(p ) nt ) kk1,kc = 0(p ) 2021-5-25 page: 69 對稱密碼體制：分組密碼的線形密碼分析分組密碼的線形密碼分析 o一個重要的數學結論一個重要的數學結論(線性密碼分析的思想，抗線性密碼分析的強 度就是非線性度) n如果明文和密文的關系是n維線性關系，且系數是密鑰，則n個 明文-密文對(

21、而不是2n個)就可以破解密鑰； n如果明文與密文的關系是n維r次函數關系，且系數是密鑰，則 nr 個明文-密文對就可以破解密鑰； n如果雖然次數r較大，但明文與密文的關系“非常逼近”一個n 維線性關系，則n個明文-密文對就可以“基本上”破解密鑰。 2021-5-25 page: 70 對稱密碼體制：兩重兩重des 2021-5-25 page: 71 對稱密碼體制：三重三重des 2021-5-25 page: 72 對稱密碼體制組成 o流密碼 o分組密碼 o數據加密標準(des) o高級加密標準(aes) 2021-5-25 page: 73 對稱密碼體制：高級加密標準高級加密標準(aes)

22、的由來的由來 p1997年1月，美國nist向全世界密碼學界發出征集21世紀高級加密 標準(advanced encryption standard, aes)算法的公告，并成立了 aes標準工作研究室，1997年4月15日的例會制定了對aes的評估 標準。 2021-5-25 page: 74 對稱密碼體制：高級加密標準的評估標準高級加密標準的評估標準 o高級加密標準(aes)的評估標準 naes是公開的； naes為單鑰體制分組密碼； naes的密鑰長度可變，可按需要增大； naes適于用軟件和硬件實現； naes可以自由地使用/按符合美國國家標準(anst)策略的條件 使用； n滿足以上

23、要求的aes算法，需按下述條件判斷優劣：a. 安全性， b. 計算效率， c. 內存要求， d. 使用簡便性，e. 靈活性。 2021-5-25 page: 75 對稱密碼體制：高級加密標準高級加密標準(aes)的歷史的歷史 o1997年4月15日nist發起征集aes的活動(要求算法分組長度128比 特，密鑰長度128192256比特)； o1998年8月20日第一次aes候選大會，公布了15個候選算法； o1999年3月22日舉行了第二次aes候選大會，選出5個候選算法； o2000年4月25日舉行了第三次aes候選大會； o2000年10月2日公布rijndael算法作為候選算法。比利時

24、的joan daemen和vincent rijmen 設計的 rijndael 算法：是一個迭代分組密 碼，塊長為128/192/256 bits，密鑰長度為128、192、256 bits，相 應的輪數為10/12/14。 2021-5-25 page: 76 aes：aes的特征的特征 oaes特征特征 naes是分組密碼，屬于square結構 n加密、解密相似但不對稱 n密鑰長度和分組長度均可變，密鑰長度和分組長度可以獨立地 指定為128比特、192比特或256比特 n有較好的數學理論作為基礎 n結構簡單、速度快 n能在多種平臺上以較快的速度實現 2021-5-25 page: 77

25、aes：消息分組和密鑰分組消息分組和密鑰分組 o消息分組和密鑰分組分別按字節進行劃分按字節進行劃分(一個字節8比特)，為簡單 起見，只討論密鑰長度128比特、消息長度192比特的情形。 n明文分組 = a00, , a30, , a05, , a35 n密鑰分組 = k00, , k30, , k03, , k33 a00a01a02a03a04a05 a10a11a12a13a14a15 a20a21a22a23a24a25 a30a31a32a33a34a35 k00k01k02k03 k10k11k12k13 k20k21k22k23 k30k31k32k33 2021-5-25 pag

26、e: 78 aes：迭代輪數與密鑰、消息分組的關系迭代輪數與密鑰、消息分組的關系 orijndael算法同算法同des一樣，由多基本的變換單位一樣，由多基本的變換單位“輪輪”多次迭代而成。多次迭代而成。 o迭代輪數與密鑰、消息分組的關系表，其中迭代輪數與密鑰、消息分組的關系表，其中 n以nr表示迭代輪數 nnb表示消息分組按字節劃分的矩陣列數(行數等于4) nnk表示密鑰分組按字節劃分的矩陣列數(行數等于4) nrnb=4nb=6nb=8 nk=4 10 12 14 nk=6 12 12 14 nk=8 14 14 14 2021-5-25 page: 79 aes：輪變換輪變換 o輪變換輪變

27、換round(state, roundkey) nstate：輪消息矩陣，既作為輸入，又作為輸出； nroundkey：輪密鑰矩陣，它由輸入密鑰通過密鑰表導出。 o輪變換由四個不同的變換組成輪變換由四個不同的變換組成(除最后一輪除最后一輪) o最后一輪記為最后一輪記為finalround(state, roundkey) n它等于不使用mixcolumns函數的round(state, roundkey) round(state, roundkey) subbytes(state); shiftrows(state); mixcolumns(state); addroundkey(state,

28、 roundkey); 2021-5-25 page: 80 aes：subbytes(state) osubbytes為state的每一個字節提供一個非線形變換非線形變換，任一非零字 節xgf(28)被下面的變換所代換(仿射變換仿射變換) y = ax-1 + b 2021-5-25 page: 81 aes： subbytes(state) o查表法查表法定時分析攻擊定時分析攻擊 n計算x-1 (x, x-1) n計算y包含矩陣a和向量b，(x, y) a00a01a02a03a04a05 a10a11a12a13a14a15 a20a21a22a23a24a25 a30a31a32a33

29、a34a35 b00b01b02b03b04b05 b10b11b12b13b14b15 b20b21b22b23b24b25 b30b31b32b33b34b35 s-box aij bij 2021-5-25 page: 82 aes：shiftrows(state) oshiftrows在state的每行運算，它只重排了元素的位置而不改變元素 本身，實質為換位密碼，換位密碼，以128比特的明文長度為例 n對在第i行的元素，換位變換就是“循環向右移動” 4 i個位置。 o字節移位關系表 nbc1c2c3 4321 6321 8314 2021-5-25 page: 83 aes：mixco

30、lumns(state) omixcolumns在state的每列上作用，列作為gf(28)上的多項式，每次 迭代的輸出為一列 s(x) = c(x) . s(x) mod(x4 + 1) 其中，c(x) = 03 . x3 + 01 . x3 + 01 . x3 + 02, 內的數表示字節 c(x)與與x4 + 1互素互素 2021-5-25 page: 84 aes：addroundkey操作操作 o按比特在f2上相加(xor) a00a01a02a03a04a05 a10a11a12a13a14a15 a20a21a22a23a24a25 a30a31a32a33a34a35 k00k0

31、1k02k03k04k05 k10k11k12k13k14k15 k20k21k22k23k24k25 k30k31k32k33k34k35 = b00b01b02b03b04b05 b10b11b12b13b14b15 b20b21b22b23b24b25 b30b31b32b33b34b35 2021-5-25 page: 85 aes：密鑰編排密鑰編排 o密鑰編排密鑰編排 n密鑰編排是指從種子密鑰得到輪密鑰的過程，它由密鑰擴展和輪 密鑰選取兩部分組成 o輪密鑰的比特數等于分組長度乘以輪數加1 = 32 nb (nr + 1)； o種子密鑰被擴展成為擴展密鑰； o輪密鑰從擴展密鑰中取，其中

32、第1輪輪密鑰取擴展密鑰的前nb個字， 第2輪輪密鑰取接下來的nb個字，如此下去。 2021-5-25 page: 86 aes：keyexpansion(key, w) okeyexpansion(key, w) nkey用于存儲擴展前的密鑰； nw用于存儲擴展后的密鑰； o以以128比特的密鑰為例比特的密鑰為例 n輸入的密鑰key直接被復制到密鑰數組的前四個字，w0, w1, w2, w3； nw數組中下標不為4的倍數的元素按以下規則擴展 wi = wi -1 wi - 4 2021-5-25 page: 87 aes：keyexpansion(key, w) n下標為4的倍數的元素按以下規

33、則擴展 o將一個字的四個字節循環左移一個字節，即將b0, b1, b2, b3變為 b1, b2, b3, b0； o基于subbytes對輸入字中的每個字節進行代替；s盒盒 o將步驟1和步驟2的結果再與輪常量rconi相異或。 orconi = (rci, 00, 00, 00) nrc1 = 01 nrci = 2 . (rci - 1) 2021-5-25 page: 88 aes：keyexpansion() - nk6 keyexpansion(byte key4 * nk, word wnb * (nr + 1) for(i = 0; i nk; i+) wi = (key4 * i, key4 * i + 1, key4 * i + 2, key4 * i + 3); for(i = nk; i nb * (nr + 1); i+) temp = wi - 1; if(i % nk = 0) temp = subbytes(temp 6 keyexpansion(byte key