對稱密碼體制

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

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

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

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

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

6、x3,y=y1,y2,y3 n轉移函數(shù) 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 流密碼：有限狀態(tài)自動機舉例有限狀態(tài)自動機舉例 o若輸入為 x1x2x1x3x3x1 o初始狀態(tài)s1 o輸出為 y1y1y2y1y3y1 2021-5-25 page: 12 流密碼：基于基于fa的密鑰流產(chǎn)生器的密鑰流產(chǎn)生器 o同步流密碼的密鑰流產(chǎn)生器可看為一個參數(shù)為k的fa：輸出集z， 狀態(tài)集，狀態(tài)轉移函數(shù)和輸出函數(shù)，初態(tài)0 o設計的關鍵是

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

8、r3 非 線 性 組 合 函 數(shù) zi lfsr：線性反饋移位寄存器流密碼產(chǎn)生密鑰流的主要組成部分。 2021-5-25 page: 15 流密碼：反饋移位寄存器的概念反饋移位寄存器的概念 o基本概念基本概念 n級數(shù)級數(shù)(stages)：存儲單元數(shù)n n狀態(tài)狀態(tài)(state)：n個存儲單元的存數(shù)(ki, , ki+n-1) n反饋函數(shù)：反饋函數(shù)：f(ki, ki+1, , ki+n-1)是狀態(tài)(ki, ki+n-1)的函數(shù) n線性反饋移位寄存器線性反饋移位寄存器(lfsr)：f 為線性函數(shù) n非線性反饋移位寄存器：非線性反饋移位寄存器： f 為非線性函數(shù) 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)為線性函數(shù)線性函數(shù)，輸出序列滿足下式 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的反饋系數(shù)所決定的一元高次多項式 又稱反饋多項式反饋多項式。 p由于cigf(2)(i = 1,2,n)，所以有2n組初始狀態(tài)，即有2n個遞推序 列，其中非恒零的有2n-1個。 21 121 0 ( )1. n nnj nnj j f xc xc xcxc xc x 2021-5-25 page: 19 流密碼：lfsr的生成函數(shù)的生成函數(shù) p給定序列 kii0，冪級數(shù)冪級數(shù) 稱為該序列的生成函數(shù)生成函數(shù) p定理：定理：令kii0(f)，f(x)是反饋多項式，令k(x)是kii0的生成函數(shù)， 則 其中 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的生成函數(shù)的生成函數(shù) 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序列的性質(zhì)序列的性質(zhì) nn級m序列的周期為2n1，周期隨n增加而指數(shù)級遞增； n只要知道n次本原多項式，m序列極易生成； nm序列極不安全，只要泄露2n位連續(xù)數(shù)字，就可完全確定出反 饋多項式系數(shù)。 階為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雖然不能直接作為密鑰流用，但可作為驅(qū)動源以其輸出推動 一個非線性組合函數(shù)非線性組合函數(shù)所決定的電路來產(chǎn)生非線性序列。這就是所 謂非線性前饋序列生成器非線性前饋序列生成器。 nlfsr用來保證密鑰流的周期長度、平衡性等； n非線性組合函數(shù)用來保證密鑰流的各種密碼性質(zhì)，以抗擊各種 可能的攻擊。 2021-5-25 page: 25 流密碼：非線性前饋序列非線性前饋序列 o前饋函數(shù)前饋函數(shù)f(非線性組合函數(shù)) o輸出序列的周期性、隨機性、線性復雜度以及相關免疫性之間的 關系

15、 lfrs f ki 2021-5-25 page: 26 流密碼：j-k觸發(fā)器觸發(fā)器 pj-k觸發(fā)器觸發(fā)器是一個非線性器件，有兩個輸入端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觸發(fā)器的非線性序列生成器觸發(fā)器的非線性序列生成器 oak和bk被稱為非線性序列生成器的驅(qū)動序列。 o性質(zhì)性質(zhì)：設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數(shù)據(jù)加密標準(des) o高級加密標準(aes) 2021-5-25 page: 30 對稱密碼體制：分組密碼分組密碼 o分組密碼的工作原理分組密碼的工作原理 n將明文分成n個塊，m1, m2, , mn； n對每個塊執(zhí)行相同的變換，從而生成n個密文塊，c1, c2, , cn。 p分組密碼的工作模式分組密碼的工作模式：明文分組固定，消息的數(shù)據(jù)量不同，數(shù)據(jù) 格式各式各樣。為了適應各種應用環(huán)境，有四種工作模式。 n電子編碼薄模式(ebc) n密碼分組鏈接模式(cbc) n密碼反饋模式(cfb) n輸出反饋模式(ofb) 2021

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

19、密碼：分組密碼的經(jīng)典工作模式分組密碼的經(jīng)典工作模式 電子編碼薄模式 密碼分組鏈接模式 輸出反饋模式 2021-5-25 page: 33 分組密碼：分組密碼的擴散與壓縮分組密碼的擴散與壓縮 o分組密碼的基本過程分組密碼的基本過程 n將明文分成m個塊，m1, m2, , mm； n對每個塊執(zhí)行相同的變換，從而生成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的整數(shù)，并用分量形式描述。 每個分量分別用xi，yigf(2) 表示，即： n若nm，則為有數(shù)據(jù)擴展數(shù)據(jù)擴展的分組密碼； n若n n / 2 okk1,kc = 0(p ) kk1,kc = 1(p ) nt ) kk1,kc = 0(p ) 2021-5-25 page: 69 對稱密碼體制：分組密碼的線形密碼分析分組密碼的線形密碼分析 o一個重要的數(shù)學結論一個重要的數(shù)學結論(線性密碼分析的思想，抗線性密碼分析的強 度就是非線性度) n如果明文和密文的關系是n維線性關系，且系數(shù)是密鑰，則n個 明文-密文對(

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

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

23、要求的aes算法，需按下述條件判斷優(yōu)劣：a. 安全性， b. 計算效率， c. 內(nèi)存要求， d. 使用簡便性，e. 靈活性。 2021-5-25 page: 75 對稱密碼體制：高級加密標準高級加密標準(aes)的歷史的歷史 o1997年4月15日nist發(fā)起征集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，相 應的輪數(shù)為10/12/14。 2021-5-25 page: 76 aes：aes的特征的特征 oaes特征特征 naes是分組密碼，屬于square結構 n加密、解密相似但不對稱 n密鑰長度和分組長度均可變，密鑰長度和分組長度可以獨立地 指定為128比特、192比特或256比特 n有較好的數(shù)學理論作為基礎 n結構簡單、速度快 n能在多種平臺上以較快的速度實現(xiàn) 2021-5-25 page: 77

25、aes：消息分組和密鑰分組消息分組和密鑰分組 o消息分組和密鑰分組分別按字節(jié)進行劃分按字節(jié)進行劃分(一個字節(jié)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：迭代輪數(shù)與密鑰、消息分組的關系迭代輪數(shù)與密鑰、消息分組的關系 orijndael算法同算法同des一樣，由多基本的變換單位一樣，由多基本的變換單位“輪輪”多次迭代而成。多次迭代而成。 o迭代輪數(shù)與密鑰、消息分組的關系表，其中迭代輪數(shù)與密鑰、消息分組的關系表，其中 n以nr表示迭代輪數(shù) nnb表示消息分組按字節(jié)劃分的矩陣列數(shù)(行數(shù)等于4) nnk表示密鑰分組按字節(jié)劃分的矩陣列數(shù)(行數(shù)等于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函數(shù)的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的每一個字節(jié)提供一個非線形變換非線形變換，任一非零字 節(jié)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的每行運算，它只重排了元素的位置而不改變元素 本身，實質(zhì)為換位密碼，換位密碼，以128比特的明文長度為例 n對在第i行的元素，換位變換就是“循環(huán)向右移動” 4 i個位置。 o字節(jié)移位關系表 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, 內(nèi)的數(shù)表示字節(jié) 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輪密鑰的比特數(shù)等于分組長度乘以輪數(shù)加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直接被復制到密鑰數(shù)組的前四個字，w0, w1, w2, w3； nw數(shù)組中下標不為4的倍數(shù)的元素按以下規(guī)則擴展 wi = wi -1 wi - 4 2021-5-25 page: 87 aes：keyexpansion(key, w) n下標為4的倍數(shù)的元素按以下規(guī)

33、則擴展 o將一個字的四個字節(jié)循環(huán)左移一個字節(jié)，即將b0, b1, b2, b3變?yōu)?b1, b2, b3, b0； o基于subbytes對輸入字中的每個字節(jié)進行代替；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