【正文】 ?????????????????????????????????????????????????????????????????121110212111....... . . . . .............. . . . . .. . . . . .ninininninininiiiniiikkkccckkkkkkkkky k y _ w e n f e n g 1 6 3 . c o m2022/8/25 Page: 24 流密碼： 非線(xiàn)性序列 ? LFSR雖然不能直接作為密鑰流用 ， 但可作為驅(qū)動(dòng)源以其輸出推動(dòng)一個(gè) 非線(xiàn)性組合函數(shù) 所決定的電路來(lái)產(chǎn)生非線(xiàn)性序列 。 ? m序列的性質(zhì) ? n級(jí) m序列的周期為 2n－ 1，周期隨 n增加而指數(shù)級(jí)遞增； ? 只要知道 n次本原多項(xiàng)式， m序列極易生成； ? m序列極不安全，只要泄露 2n位連續(xù)數(shù)字，就可完全確定出反饋多項(xiàng)式系數(shù)。 y k y _ w e n f e n g 1 6 3 . c o m2022/8/25 Page: 22 流密碼： LFSR的周期 ? m序列： 序列 {ki}0≤i≤n的周期達(dá)到最大 2n1時(shí)，稱(chēng)該序列為 m序列。 ? 定理 ：設(shè)序列 {ki}的特征多項(xiàng)式 p(x)定義 GF(2)上， p是 p(x)的周期，則 {ki}的周期 r | p。 ? 由于 ci?GF(2)(i = 1,2,… ,n)， 所以有 2n組初始狀態(tài) ， 即有 2n個(gè)遞推序列 ， 其中非恒零的有 2n1個(gè) 。 y k y _ w e n f e n g 1 6 3 . c o m2022/8/25 Page: 15 流密碼： 反饋移位寄存器的概念 ? 基本概念 ? 級(jí)數(shù) (Stages)：存儲(chǔ)單元數(shù) n ? 狀態(tài) (State)： n個(gè)存儲(chǔ)單元的存數(shù) (ki, … , ki+n1) ? 反饋函數(shù)： f(ki, ki+1, … , ki+n1)是狀態(tài) (ki,… , ki+n1)的函數(shù) ? 線(xiàn)性反饋移位寄存器 (LFSR)： f 為線(xiàn)性函數(shù) ? 非線(xiàn)性反饋移位寄存器： f 為非線(xiàn)性函數(shù) y k y _ w e n f e n g 1 6 3 . c o m2022/8/25 Page: 16 流密碼： 反饋移位寄存器 f(ki, ki+1, …, ki+n1) ki+n1 ki+n2 ki+1 ki ki+n 輸出序列 寄存 移位 反饋 y k y _ w e n f e n g 1 6 3 . c o m2022/8/25 Page: 17 流密碼： 線(xiàn)性反饋移位寄存器 ? f(x)為 線(xiàn)性函數(shù) ，輸出序列滿(mǎn)足下式 1 0 1 1( , , ) 0 0 2i n i i n i n i n ik f k k c k c k i c? ? ? ? ? ?? ? ? ? ? ? ?， 其 中 ： ， 或 1 ， 是 模 加 法 ?？蓪⒋祟?lèi)產(chǎn)生器分為 驅(qū)動(dòng)部分 和 非線(xiàn)性組合 部分。 ? 同步流密碼加密器 ? 密鑰流產(chǎn)生器 ? 加密變換器 ? 加密變換器一般采用二元邏輯運(yùn)算 XOR，即有限域 GF(2)上討論的二元加密流密碼，變換表示為： yi = zi⊕ xi ? 一次一密亂碼本 是加法流密碼的原型 y k y _ w e n f e n g 1 6 3 . c o m2022/8/25 Page: 7 流密碼： 流密碼的密鑰流產(chǎn)生器 ? 密鑰流產(chǎn)生器的內(nèi)涵 ? 輸入： 密鑰 k和加密器中的記憶元件在時(shí)刻 i的狀態(tài) δi； ? 輸出：密鑰流 zi 狀態(tài) δi 密鑰 k 狀態(tài) δi+1 密鑰流 zi y k y _ w e n f e n g 1 6 3 . c o m2022/8/25 Page: 8 流密碼： 密鑰流生成器的設(shè)計(jì)原則 ? 足夠長(zhǎng)的周期 ? 高線(xiàn)性復(fù)雜度 ? 統(tǒng)計(jì)性能良好 ? 足夠的“混亂” ? 強(qiáng)調(diào)密鑰的作用，增加密鑰與密文之間關(guān)系的復(fù)雜性 ? 足夠的“擴(kuò)散” ? 小擾動(dòng)的影響波及到全局密文沒(méi)有統(tǒng)計(jì)特征，明文一位影響密文的多位，增加密文與明文之間關(guān)系的復(fù)雜性 ? 抵抗不同形式的攻擊 y k y _ w e n f e n g 1 6 3 . c o m2022/8/25 Page: 9 流密碼： 有限狀態(tài)自動(dòng)機(jī) (FA) ? 具有離散輸入和輸出 (輸入集和輸出集均有限 )的一種數(shù)學(xué)模型 ? 有限狀態(tài)集 S={si|i=1,2,…, l} ? 有限輸入字符集 X={Xi|i=1,2,…, m} ? 有限輸出字符集 Y={Yk|k=1,2,…, n} ? 轉(zhuǎn)移函數(shù) ? Yj＝ f1(sj, Xj) ? Sj+1 ＝ f2(sj, Xj) 即在狀態(tài) sj，輸入字符 Xj時(shí)，輸出為 Yj，狀態(tài)轉(zhuǎn)移為 Sj+1。 ? 核心問(wèn)題是密鑰流的產(chǎn)生 ——密鑰流生成器的設(shè)計(jì) ? 保持收發(fā)兩端密鑰流的精確同步是實(shí)現(xiàn)可靠解密的關(guān)鍵技術(shù) y k y _ w e n f e n g 1 6 3 . c o m2022/8/25 Page: 5 流密碼： 流密碼的基本概念 ? 流密碼的基本思想： 假設(shè)存在著明文串 x = x0x1x2… ? 利用密鑰 k和密鑰流發(fā)生器 f產(chǎn)生一個(gè)密鑰流 z = z0z1z2… 。y k y _ w e n f e n g 1 6 3 . c o m2022/8/25 Page: 1 對(duì)稱(chēng)密碼體制 楊秋偉 湖南大學(xué) 計(jì)算機(jī)與通信學(xué)院 y k y _ w e n f e n g 1 6 3 . c o m2022/8/25 Page: 2 對(duì)稱(chēng)密碼體制 ? 對(duì)稱(chēng)密碼體制的特征 ? 加密密鑰和解密密鑰相同 ? 對(duì)稱(chēng)密碼體制的主要研究課題 ? 密鑰的產(chǎn)生 ? 密鑰的管理 加密器 EK 解密器 DK 密文 明文 明文 K 密鑰產(chǎn)生器 K y k y _ w e n f e n g 1 6 3 . c o m2022/8/25 Page: 3 對(duì)稱(chēng)密碼體制組成 ? 流密碼 ? 分組密碼 ? 數(shù)據(jù)加密標(biāo)準(zhǔn) (DES) ? 高級(jí)加密標(biāo)準(zhǔn) (AES) y k y _ w e n f e n g 1 6 3 . c o m2022/8/25 Page: 4 流密碼： 流密碼引論 ? 流密碼 是將明文劃分成字符 (如單個(gè)字母 )， 或其編碼的基本單元(如按位 )， 字符分別與密鑰流作用進(jìn)行加密 ， 解密時(shí)以同步產(chǎn)生的同樣的密鑰流實(shí)現(xiàn) 。 ? 流密碼強(qiáng)度完全依賴(lài)于密鑰序列的 隨機(jī)性 (Randomness)和 不可預(yù)測(cè)性 (Unpredictability)。 其中 ，zi = f(k,δi)， δi是加密器中的記憶元件在時(shí)刻 i的狀態(tài) ， f是以密鑰k和 δi作為輸入?yún)?shù)的函數(shù)； ? 加密 ： y = y0y1y2… = Ez0(x0) Ez1(x1) Ez1(x1)… ； 內(nèi)部記憶元件 yi= Ezi(xi) xi yi k y k y _ w e n f e n g 1 6 3 . c o m2022/8/25 Page: 6 流密碼： 同步流密碼 ? 同步流密碼 ：加密器中記憶元件的存儲(chǔ)狀態(tài) δi獨(dú)立于明文字符。 y k y _ w e n f e n g 1 6 3 . c o m2022/8/25 Page: 10 流密碼： 有限狀態(tài)自動(dòng)機(jī)舉例 ? 例一 ? S={s1,s2,s3},X={x1, x2,x3},Y={y1,y2,y3} ? 轉(zhuǎn)移函數(shù) f1 x1 x2 x3 s1 s2 s3 y1 y2 y3 y3 y1 y2 y2 y3 y1 f2 x1 x2 x3 s1 s2 s3 s2 s3 s1 s1 s2 s3 s3 s1 s2 y k y _ w e n f e n g 1 6 3 . c o m2022/8/25 Page: 11 流密碼： 有限狀態(tài)自動(dòng)機(jī)舉例 ? 若輸入為x1x2x1x3x3x1 ? 初始狀態(tài) s1 ? 輸出為 y1y1y2y1y3y1 y k y _ w e n f e n g 1 6 3 . c o m2022/8/25 Page: 12 流密碼： 基于 FA的密鑰流產(chǎn)生器 ? 同步流密碼的密鑰流產(chǎn)生器可看為一個(gè)參數(shù)為 k的 FA：輸出集 Z，狀態(tài)集 Σ， 狀態(tài)轉(zhuǎn)移函數(shù) φ和輸出函數(shù) ψ， 初態(tài) ?0 ? 設(shè)計(jì)的關(guān)鍵是 φ(phi fai)和 ψ(psi psai) φ ?i ψ k k zi y k y _ w e n f e n g 1 6 3 . c o m2022/8/25 Page: 13 流密碼： 基于 FA的密鑰流產(chǎn)生器 ? 一個(gè)良好的密鑰流產(chǎn)生器 ? 極大的周期 ? 良好的統(tǒng)計(jì)特性 ? 抗線(xiàn)性分析 ? 抗統(tǒng)計(jì)分析 ? 具有非線(xiàn)性的 φ的 FA理論很不完善，通常采用線(xiàn)性 φ以及非線(xiàn)性的ψ。 ? 驅(qū)動(dòng)部分控制狀態(tài)轉(zhuǎn)移 ? 非線(xiàn)性組合部分提供統(tǒng)計(jì)特性良好的序列 y k y _ w e n f e n g 1 6 3 . c o m2022/8/25 Page: 14 流密碼： 兩種常見(jiàn) 的密鑰流產(chǎn)生器 LFSR 非線(xiàn)性組合函數(shù) zi LFSR1 LFSR2 LFSR3 非線(xiàn)性組合函數(shù) zi LFSR：線(xiàn)性反饋移位寄存器 ——流密碼產(chǎn)生密鑰流的主要組成部分。ki+n1 ki+n2 ki+1 ki 1 2 c1 c0 ki+n 輸出序列 y k y _ w e n f e n g 1 6 3 . c o m2022/8/25 Page: 18 流密碼： LFSR的特征多項(xiàng)式 ? LFSR的特征多項(xiàng)式： 以 LFSR的反饋系數(shù)所決定的一元高次多項(xiàng)式 又稱(chēng) 反饋多項(xiàng)式 。 211 2 10( ) 1 . . . nn n jn n jjf x c x c x c x c x c x???? ? ? ? ? ? ? ?y k y _ w e n f e n g 1 6 3 . c o m2022/8/25 Page: 19 流密碼： LFSR的生成函數(shù) ? 給定序列 {ki}i?0， 冪級(jí)數(shù) 稱(chēng)為該序列的 生成函數(shù) ? 定理： 令 {ki}i?0??(f)， f(x)是反饋多項(xiàng)式 ， 令 k(x)是 {ki}i?0的生成函數(shù) ，則 其中 11() iiik x k x? ??? ?()()()axkxfx?111( ) ( )jn n j ln j ljla x c x a x?????? ??y k y _ w e n f e n g 1 6 3 . c o m2022/8/25 Page: 20 流密碼 ： LFSR的生成函數(shù) ? 定理證明 ,00m in( )0010 0 0()0( ) ( ) ( ) ( )( ( ) )( ) ( ) ( )()nilililjnjn l j ljljnnjjn l j l n l j lj l j n lnjt j n tj n jk x f x k x c xc k xc k x c k xa x c k x n l tax?????????? ? ? ?? ? ? ?????????? ? ? ??????? ? ? ?