對(duì)稱密碼體制

2023/2/4Page:1對(duì)稱密碼體制楊秋偉湖南大學(xué)計(jì)算機(jī)與通信學(xué)院2023/2/4Page:2對(duì)稱密碼體制對(duì)稱密碼體制的特征加密密鑰和解密密鑰相同對(duì)稱密碼體制的主要研究課題密鑰的產(chǎn)生密鑰的管理加密器EK解密器DK密文明文明文K密鑰產(chǎn)生器K2023/2/4Page:3對(duì)稱密碼體制組成流密碼分組密碼數(shù)據(jù)加密標(biāo)準(zhǔn)(DES)高級(jí)加密標(biāo)準(zhǔn)(AES)2023/2/4Page:4流密碼：流密碼引論流密碼是將明文劃分成字符(如單個(gè)字母)，或其編碼的基本單元(如按位)，字符分別與密鑰流作用進(jìn)行加密，解密時(shí)以同步產(chǎn)生的同樣的密鑰流實(shí)現(xiàn)。流密碼強(qiáng)度完全依賴于密鑰序列的隨機(jī)性(Randomness)和不可預(yù)測(cè)性(Unpredictability)。核心問題是密鑰流的產(chǎn)生——密鑰流生成器的設(shè)計(jì)保持收發(fā)兩端密鑰流的精確同步是實(shí)現(xiàn)可靠解密的關(guān)鍵技術(shù)2023/2/4Page:5流密碼：流密碼的基本概念流密碼的基本思想：假設(shè)存在著明文串x=x0x1x2…利用密鑰k和密鑰流發(fā)生器f產(chǎn)生一個(gè)密鑰流z=z0z1z2…。其中，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)xiyik2023/2/4Page:6流密碼：同步流密碼

同步流密碼：加密器中記憶元件的存儲(chǔ)狀態(tài)δi獨(dú)立于明文字符。同步流密碼加密器密鑰流產(chǎn)生器加密變換器加密變換器一般采用二元邏輯運(yùn)算XOR，即有限域GF(2)上討論的二元加密流密碼，變換表示為：yi=zi⊕xi一次一密亂碼本是加法流密碼的原型2023/2/4Page:7流密碼：流密碼的密鑰流產(chǎn)生器密鑰流產(chǎn)生器的內(nèi)涵輸入：密鑰k和加密器中的記憶元件在時(shí)刻i的狀態(tài)δi；輸出：密鑰流zi狀態(tài)δi密鑰k狀態(tài)δi+1密鑰流zi2023/2/4Page:8流密碼：密鑰流生成器的設(shè)計(jì)原則足夠長的周期高線性復(fù)雜度統(tǒng)計(jì)性能良好足夠的“混亂”強(qiáng)調(diào)密鑰的作用，增加密鑰與密文之間關(guān)系的復(fù)雜性足夠的“擴(kuò)散”小擾動(dòng)的影響波及到全局密文沒有統(tǒng)計(jì)特征，明文一位影響密文的多位，增加密文與明文之間關(guān)系的復(fù)雜性抵抗不同形式的攻擊2023/2/4Page: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。2023/2/4Page:10流密碼：有限狀態(tài)自動(dòng)機(jī)舉例例一S={s1,s2,s3},X={x1,x2,x3},Y={y1,y2,y3}轉(zhuǎn)移函數(shù)f1x1x2x3s1s2s3y1y2y3y3y1y2y2y3y1f2x1x2x3s1s2s3s2s3s1s1s2s3s3s1s22023/2/4Page:11流密碼：有限狀態(tài)自動(dòng)機(jī)舉例若輸入為x1x2x1x3x3x1初始狀態(tài)s1輸出為

y1y1y2y1y3y12023/2/4Page: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)鍵是φ(phifai)和ψ(psipsai)φiψkkzi2023/2/4Page:13流密碼：基于FA的密鑰流產(chǎn)生器一個(gè)良好的密鑰流產(chǎn)生器極大的周期良好的統(tǒng)計(jì)特性抗線性分析抗統(tǒng)計(jì)分析具有非線性的φ的FA理論很不完善，通常采用線性φ以及非線性的ψ?？蓪⒋祟惍a(chǎn)生器分為驅(qū)動(dòng)部分和非線性組合部分。驅(qū)動(dòng)部分控制狀態(tài)轉(zhuǎn)移非線性組合部分提供統(tǒng)計(jì)特性良好的序列2023/2/4Page:14流密碼：兩種常見的密鑰流產(chǎn)生器LFSR非線性組合函數(shù)ziLFSR1LFSR2LFSR3非線性組合函數(shù)ziLFSR：線性反饋移位寄存器——流密碼產(chǎn)生密鑰流的主要組成部分。2023/2/4Page:15流密碼：反饋移位寄存器的概念基本概念級(jí)數(shù)(Stages)：存儲(chǔ)單元數(shù)n狀態(tài)(State)：n個(gè)存儲(chǔ)單元的存數(shù)(ki,…,ki+n-1)反饋函數(shù)：f(ki,ki+1,…,ki+n-1)是狀態(tài)(ki,…,ki+n-1)的函數(shù)線性反饋移位寄存器(LFSR)：f

為線性函數(shù)非線性反饋移位寄存器：f

為非線性函數(shù)2023/2/4Page:16流密碼：反饋移位寄存器f(ki,ki+1,…,ki+n-1)ki+n-1ki+n-2ki+1kiki+n輸出序列寄存移位反饋2023/2/4Page:17流密碼：線性反饋移位寄存器f(x)為線性函數(shù)，輸出序列滿足下式ki+n-1ki+n-2ki+1kicn-1cn-2c1c0ki+n輸出序列2023/2/4Page:18流密碼：LFSR的特征多項(xiàng)式LFSR的特征多項(xiàng)式：以LFSR的反饋系數(shù)所決定的一元高次多項(xiàng)式又稱反饋多項(xiàng)式。由于ciGF(2)(i=1,2,…,n)，所以有2n組初始狀態(tài)，即有2n個(gè)遞推序列，其中非恒零的有2n-1個(gè)。2023/2/4Page:19流密碼：LFSR的生成函數(shù)

給定序列{ki}i0，冪級(jí)數(shù)稱為該序列的生成函數(shù)定理：令{ki}i0(f)，f(x)是反饋多項(xiàng)式，令k(x)是{ki}i0的生成函數(shù)，則其中2023/2/4Page:20流密碼：LFSR的生成函數(shù)

定理證明2023/2/4Page:21流密碼：LFSR的周期LFSR周期的真正涵義？？？？定義：設(shè)p(x)是GF(2)上的多項(xiàng)式，使p(x)|(xp-1)的最小p稱為p(x)的周期或者階。定理：設(shè)序列{ki}的特征多項(xiàng)式p(x)定義GF(2)上，p是p(x)的周期，則{ki}的周期r|p。定理：設(shè)序列{ki}的特征多項(xiàng)式p(x)定義GF(2)上，且p(x)是不可約多項(xiàng)式，p是p(x)的周期，則{ki}的周期為p。2023/2/4Page:22流密碼：LFSR的周期m序列：序列{ki}0≤i≤n的周期達(dá)到最大2n-1時(shí)，稱該序列為m序列。定理：以f(x)為特征多項(xiàng)式的LFSR的輸出序列是m序列的充要條件為f(x)是本原的。m序列的性質(zhì)n級(jí)m序列的周期為2n－1，周期隨n增加而指數(shù)級(jí)遞增；只要知道n次本原多項(xiàng)式，m序列極易生成；m序列極不安全，只要泄露2n位連續(xù)數(shù)字，就可完全確定出反饋多項(xiàng)式系數(shù)。階為2n-1的n次不可約多項(xiàng)式2023/2/4Page:23流密碼：LFSR的周期m序列的破譯已知ki,ki+1,…,ki+2n，由遞推關(guān)系式可得出下式式中有n個(gè)線性方程和n個(gè)未知量，故可惟一解出ci，0in-1。2023/2/4Page:24流密碼：非線性序列LFSR雖然不能直接作為密鑰流用，但可作為驅(qū)動(dòng)源以其輸出推動(dòng)一個(gè)非線性組合函數(shù)所決定的電路來產(chǎn)生非線性序列。這就是所謂非線性前饋序列生成器。LFSR用來保證密鑰流的周期長度、平衡性等；非線性組合函數(shù)用來保證密鑰流的各種密碼性質(zhì)，以抗擊各種可能的攻擊。2023/2/4Page:25流密碼：非線性前饋序列前饋函數(shù)F(非線性組合函數(shù))輸出序列的周期性、隨機(jī)性、線性復(fù)雜度以及相關(guān)免疫性之間的關(guān)系LFRSF…ki…2023/2/4Page:26流密碼：J-K觸發(fā)器J-K觸發(fā)器是一個(gè)非線性器件，有兩個(gè)輸入端j和k，輸出為qi。輸出不僅依賴于輸入，還依賴于前一個(gè)輸出位qi-1，即其結(jié)構(gòu)及邏輯真值表如下所示JKqk00110101qk-101⊕⊕⊙JKR=qk-1qk2023/2/4Page:27流密碼：J-K觸發(fā)器的非線性序列生成器{ak}和{bk}被稱為非線性序列生成器的驅(qū)動(dòng)序列。性質(zhì)：設(shè){ak}和{bk}分別為x級(jí)和y級(jí)m序列。當(dāng)x和y互素，且a0+b0=1時(shí)，序列{ck}的周期為(2x-1)(2y-1)。LFSR1LFSR2{ak}{bk}JK{ck}2023/2/4Page:28流密碼：多路選擇序列有n種輸入序列b0(t),…,

bn-1(t)，在地址序列a1(t),…,am-1

(t)的控制下決定輸出取自某個(gè)輸入比特?！?/p>

Pless生成器例如取m級(jí)LFSR生成m序列作地址控制，取n級(jí)LFSR生成的m序列作為輸入序列?？晒┻x擇的輸入2023/2/4Page:29對(duì)稱密碼體制組成流密碼分組密碼數(shù)據(jù)加密標(biāo)準(zhǔn)(DES)高級(jí)加密標(biāo)準(zhǔn)(AES)2023/2/4Page:30對(duì)稱密碼體制：分組密碼分組密碼的工作原理將明文分成n個(gè)塊，m1,m2,…,mn；對(duì)每個(gè)塊執(zhí)行相同的變換，從而生成n個(gè)密文塊，c1,c2,…,cn。分組密碼的工作模式：明文分組固定，消息的數(shù)據(jù)量不同，數(shù)據(jù)格式各式各樣。為了適應(yīng)各種應(yīng)用環(huán)境，有四種工作模式。電子編碼薄模式(EBC)密碼分組鏈接模式(CBC)密碼反饋模式(CFB)輸出反饋模式(OFB)2023/2/4Page:31分組密碼：分組密碼的工作模式比較模式描述用途電碼本模式(ECB)每個(gè)明文組獨(dú)立地以同一密鑰加密。傳送短數(shù)據(jù)密碼分組鏈接模式(CBC)加密算法的輸入是當(dāng)前明文組與前一密文組的異或。傳送數(shù)據(jù)分組；認(rèn)證。密碼反饋模式(CFB)每次只處理輸入的j比特，將上一次的密文用作加密算法的輸入以產(chǎn)生偽隨機(jī)輸出，該輸出再與當(dāng)前明文異或以產(chǎn)生當(dāng)前密文。傳送數(shù)據(jù)流；認(rèn)證。輸出反饋模式(OFB)與CFB類似，不同之處是本次加密算法的輸入為前一次加密算法的輸出。有擾信道上(無線通訊)傳送數(shù)據(jù)流2023/2/4Page:32分組密碼：分組密碼的經(jīng)典工作模式電子編碼薄模式密碼分組鏈接模式輸出反饋模式2023/2/4Page:33分組密碼：分組密碼的擴(kuò)散與壓縮分組密碼的基本過程將明文分成m個(gè)塊，M1,M2,…,Mm；對(duì)每個(gè)塊執(zhí)行相同的變換，從而生成m個(gè)密文塊，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)

2023/2/4Page:34分組密碼：分組密碼的擴(kuò)展與壓縮將明文x和密文y表示成分別小于2m和2n的整數(shù)，并用分量形式描述。每個(gè)分量分別用xi，yiGF(2)表示，即：若n>m，則為有數(shù)據(jù)擴(kuò)展的分組密碼；若n<m，則為有數(shù)據(jù)壓縮的分組密碼。分組密碼就是將||x||映射為||y||，(||x||∈{0,1,…,2m-1},||y||∈{0,1,…,2n-1})即為到其自身的一個(gè)置換，即

y=(x)2023/2/4Page:35分組密碼：分組密碼的置換設(shè)明文分組長度為n比特，則明文分組的取值為2n。為了使加密運(yùn)算可逆，每一個(gè)明文對(duì)應(yīng)的密文唯一，這樣的變換是可逆的，并稱明文到密文的變換為置換?；镜闹脫Q左循環(huán)移位(Shiftleftcircular)代換、右循環(huán)移位(Shiftrightcircular)代換模2n加1(Additionwithmodule)代換線性變換(Lineartransformation)換位(Transposition)代換連線交叉或坐標(biāo)置換仿射變換(Affinetransform)2023/2/4Page:36分組密碼：Feistel網(wǎng)絡(luò)Feistel網(wǎng)絡(luò)將nbit明文分成為左右各半、長為n/2bit的段，以L和R表示。然后進(jìn)行多輪迭代，其第i輪迭代的輸出為前輪輸出的函數(shù)

Li

=Ri-1

Ri

=Li-1f(Ri-1,ki)

式中，ki是第i輪用的子密鑰，f是任意密碼輪函數(shù)。Feistel網(wǎng)絡(luò)的特征保證加密和解密可采用同一算法實(shí)施。在設(shè)計(jì)整個(gè)分組密碼的代換網(wǎng)絡(luò)時(shí)，要求輸出的每比特密文都和輸入的明文及密鑰各比特有關(guān)，這對(duì)增加密碼強(qiáng)度有好處。2023/2/4Page:37分組密碼：迭代分組密碼迭代分組密碼：若以一個(gè)簡(jiǎn)單函數(shù)f，進(jìn)行多次迭代，就稱其為迭代密碼。每次迭代稱作一輪(Round)，相應(yīng)函數(shù)f稱作輪函數(shù)。每一輪輸出都是以前一輪輸出作為輸入?yún)?shù)的函數(shù)，即yi=f[yi-1,

ki]，其中ki是第i輪迭代用的子密鑰，由秘密密鑰k通過密鑰生成算法產(chǎn)生。子密鑰產(chǎn)生器fffy0=xy1yi-1y2yik1k2ki-1k2023/2/4Page:38分組密碼：分組密碼的填充問題問題的由來分組加密法是作用于有固定大小的明文/密文塊。如果明文的大小不是塊大小的整數(shù)倍怎樣處理？？？分組密碼的填充：添加足夠多的特殊字符，使得明文長度是塊大小的整數(shù)倍。

填充必須可逆一種可行的填充方法用文件結(jié)束字符表示明文分組的最后一個(gè)字節(jié)；每一個(gè)分組都必須以0、1或者0、1交替的模式填充，即使明文以分組的邊界結(jié)束，也必須添加一個(gè)整分組。2023/2/4Page:39分組密碼：分組密碼的評(píng)估分組密碼如何才算是安全？？密鑰必須足夠大，使強(qiáng)力攻擊失效或者得不償失—愷撒密碼；如果加密法通過了隨機(jī)測(cè)試，在一定時(shí)間內(nèi)能給人以安全性。雪崩條件(avalanchecondition)：任何輸入位或密鑰位與輸出位之間不應(yīng)有任何連續(xù)，即密文中不能有內(nèi)容含有關(guān)于密鑰或明文的提示。精確密文雪崩標(biāo)準(zhǔn)：無論密文塊的任意一位有變，密文塊每個(gè)位發(fā)生改變的概率為50%；精確密鑰雪崩標(biāo)準(zhǔn)：對(duì)于一個(gè)長度固定的明文塊，當(dāng)密鑰的任意一位發(fā)生改變時(shí)，密文款每個(gè)位發(fā)生改變的概率為50%。2023/2/4Page:40對(duì)稱密碼體制組成流密碼分組密碼數(shù)據(jù)加密標(biāo)準(zhǔn)(DES)高級(jí)加密標(biāo)準(zhǔn)(AES)2023/2/4Page:41對(duì)稱密碼體制：數(shù)據(jù)加密標(biāo)準(zhǔn)( DES)的歷史20世紀(jì)70年代中期，美國政府認(rèn)為需要一個(gè)功能強(qiáng)大的標(biāo)準(zhǔn)加密系統(tǒng)，提出開發(fā)這種加密法的請(qǐng)求；1973年5月15日，國家標(biāo)準(zhǔn)局(NationalBureauofStandards,NBS)開始公開征集標(biāo)準(zhǔn)加密算法，并公布了它的設(shè)計(jì)要求 算法必須提供高度的安全性算法必須有詳細(xì)的說明，并易于理解算法的安全性取決于密鑰，不依賴于算法算法適用于所有用戶算法適用于不同應(yīng)用場(chǎng)合算法必須高效、經(jīng)濟(jì)算法必須能被證實(shí)有效算法必須是可出口的2023/2/4Page:42對(duì)稱密碼體制：數(shù)據(jù)加密標(biāo)準(zhǔn)( DES)的歷史IBM提出的Lucifer加密系統(tǒng)在此次征集中獲得了勝利；1977年，根據(jù)美國國家安全局的建議進(jìn)行了一些修改后，Lucifer成為數(shù)據(jù)加密標(biāo)準(zhǔn)(dataencryptionstandard,DES)；1980年，DES成為美國標(biāo)準(zhǔn)化協(xié)會(huì)(ANSI)標(biāo)準(zhǔn)；1983年，國際化標(biāo)準(zhǔn)組織贊同DES作為國際標(biāo)準(zhǔn)，稱之為DEA-1；1984年2月，ISO成立的數(shù)據(jù)加密技術(shù)委員會(huì)(SC20)在DES基礎(chǔ)上制定數(shù)據(jù)加密的國際標(biāo)準(zhǔn)工作；DES最后被高級(jí)加密標(biāo)準(zhǔn)(advancedencryptionstandard,AES)代替。2023/2/4Page:43DES：數(shù)據(jù)加密標(biāo)準(zhǔn)(DES)的特征數(shù)據(jù)加密標(biāo)準(zhǔn)(DES)的特征分組加密算法：明文和密文為64位分組長度；對(duì)稱算法：加密和解密除密鑰編排不同外，使用同一算法；密鑰長度：64位，但每個(gè)字節(jié)第8位為奇偶校驗(yàn)位，可忽略；密鑰可為任意的56位數(shù)，但存在弱密鑰，盡量避開；采用混亂和擴(kuò)散的組合，每個(gè)組合先替代后置換，共16輪；只使用了標(biāo)準(zhǔn)的算術(shù)和邏輯運(yùn)算，易于實(shí)現(xiàn)。2023/2/4Page:44DES：加/解密流程輸入64比特明文數(shù)據(jù)初始置換IP在密鑰控制下十六輪迭代初始逆置換IP-1輸出64比特密文數(shù)據(jù)交換左右32比特2023/2/4Page:45DES：算法處理流程初始置換IP第1輪置換選擇1循環(huán)左移置換選擇2k1第2輪置換選擇2循環(huán)左移k2第16輪k16置換選擇2循環(huán)左移32位對(duì)換逆初始置換IP－164位密文48位64位明文64位密鑰2023/2/4Page:46DES：初始置換IP和IP-1IP和IP-1在密碼意義上作用不大，因?yàn)檩斎虢Mx與其輸出組y=IP(x)(或IP-1(x))是已知的一一對(duì)應(yīng)關(guān)系。它們的作用在于打亂原來輸入x的ASCII碼字劃分的關(guān)系，并將原來明文的校驗(yàn)位x8,x16,,x64變成為IP輸出的一個(gè)字節(jié)。IPIP—12023/2/4Page:47DES：乘積變換乘積變換是DES算法的核心部分將經(jīng)過IP置換后的數(shù)據(jù)分成32bit的左右兩組；每次迭代時(shí)只對(duì)右邊的32bit進(jìn)行一系列的加密變換，在此輪迭代即將結(jié)束時(shí)，把左邊的32bit與右邊得到的32bit逐位模2相加，作為下一輪迭代時(shí)右邊的段；將原來右邊未經(jīng)變換的段直接送到左邊的寄存器中作為下一輪迭代時(shí)左邊的段；在每一輪迭代時(shí)，右邊的段要經(jīng)過選擇擴(kuò)展運(yùn)算E、密鑰加密運(yùn)算、選擇壓縮運(yùn)算S、置換運(yùn)算P和左右混合運(yùn)算。2023/2/4Page:48DES：乘積變換工作流程Li-1(32位)Ri-1(32位)擴(kuò)展運(yùn)算E(48位)模2求和(48位)密鑰產(chǎn)生器壓縮運(yùn)算S(32位)置換運(yùn)算P(32位)模2求和(32位)Li(32位)Ri(32位)2023/2/4Page:49DES：選擇擴(kuò)展運(yùn)算選擇擴(kuò)展運(yùn)算E：將輸入的32bitRi-1擴(kuò)展成48bit的輸出令s表示E原輸入數(shù)據(jù)比特的原下標(biāo)，則E的輸出是將原下標(biāo)s0或1(mod4)的各比特重復(fù)一次得到的，即對(duì)原第32,1,4,5,8,9,12,13,16,17,20,21,24,25,28,29各位都重復(fù)一次,實(shí)現(xiàn)數(shù)據(jù)擴(kuò)展。擴(kuò)展2023/2/4Page:50DES：加密運(yùn)算和壓縮運(yùn)算密鑰加密運(yùn)算：將子密鑰產(chǎn)生器輸出的48bit子密鑰ki與選擇擴(kuò)展運(yùn)算E輸出的48bits數(shù)據(jù)按位模2相加。選擇壓縮運(yùn)算S：將前面送來的48bit數(shù)據(jù)自左至右分成8組，每組為6bit；而后并行送入8個(gè)S一盒，每個(gè)S盒為一非線性代換網(wǎng)絡(luò)，有4個(gè)輸出。48bit寄存器32bit寄存器S1S2S3S4S5S6S7S86位4位選擇函數(shù)組2023/2/4Page:51DES：壓縮運(yùn)算-s盒s盒的工作原理基于s-表：以表S1為例子說明使用方法

01234567891011121314150

1441312151183106125907101574142131106121195382411481362111512973105031512824917511314100613S11

0110

0

1020010輸入6位輸出4位2023/2/4Page:52DES：置換和左右混合置換運(yùn)算P：對(duì)S1至S8盒輸出的32bit數(shù)據(jù)進(jìn)行坐標(biāo)置換。左右混合運(yùn)算：置換P輸出的32bit數(shù)據(jù)與左邊32bit，即Ri-1，逐位模2相加，所得到的32bit作為下一輪迭代用的右邊的數(shù)字段。并將Ri-1并行送到左邊的寄存器，作為下一輪迭代用的左邊的數(shù)字段。2023/2/4Page:53DES：子密鑰產(chǎn)生器子密鑰產(chǎn)生器：在64bit初始密鑰中有8位為校驗(yàn)位，其位置號(hào)為8、16、32、48、56和64。其余56位為有效位，用于子密鑰計(jì)算。置換選擇PC1：將這56位送入置換選擇PC1進(jìn)行坐標(biāo)置換；循環(huán)移位置換：將上述結(jié)果分成兩組28bit，分別送入C和D寄存器中。在各次迭代中，C和D寄存器分別將存數(shù)進(jìn)行左循環(huán)移位置換；置換選擇PC2：每次移位后，將C和D寄存器原存數(shù)送給置換選擇PC2。置換選擇PC2將C中第9、18、22、25位和D中第7、9、15、26位刪去，并將其余數(shù)字置換位置后送出48bit數(shù)字作為第i次迭代時(shí)所用的子密鑰ki。2023/2/4Page:54DES：子密鑰產(chǎn)生器2023/2/4Page:55DES：加/解密數(shù)學(xué)描述加密過程L0R0IP(64bit明文)LiRi-1RiLi-1f(Ri-1,

ki)i=1,...,16(64bit密文)IP-1(R16L16)解密過程：DES的加密運(yùn)算是可逆的，其解密過程可類似地進(jìn)行。R16L16IP(64bit密文)Ri-1Li

Li-1Rif(Li-1,ki)i=16,...,1(64bit明文)IP-1(R0L0)2023/2/4Page:56DES：公開性和脆弱性DES的脆弱性DES的安全性完全依賴于所用的密鑰，56位不太可能提供足夠的安全性DES的半公開性S盒的設(shè)計(jì)原理至今未公布，可能隱含有陷井幾種攻擊的計(jì)算代價(jià)強(qiáng)力攻擊：255次嘗試差分密碼分析法：247次嘗試線性密碼分析法：243次嘗試2023/2/4Page:57DES：算法分析互補(bǔ)性：若明文組x逐位取補(bǔ)，密鑰k逐位取補(bǔ)，且y=DESk(x)，則有，稱這種特性為算法上的互補(bǔ)性。這種互補(bǔ)性會(huì)使DES在選擇明文破譯下所需的工作量減半。弱密鑰：DES算法在每次迭代時(shí)都有一個(gè)子密鑰供加密用。如果給定初始密鑰k，各輪的子密鑰都相同，即有k1=k2=…=k16，就稱給定密鑰k為弱密鑰(Weakkey)。半弱密鑰：兩個(gè)不同密鑰將同一明文加密成相同密文，一個(gè)用來加密，一個(gè)用來解密。2023/2/4Page:58DES：算法分析RSA數(shù)據(jù)安全公司提供10000美元獎(jiǎng)金?，F(xiàn)已被DESCHALL小組經(jīng)過近四個(gè)月的努力，通過Internet搜索了3×1016個(gè)密鑰，找出了DES的密鑰，恢復(fù)出明文。1998年5月美國ElectronicFrontierFoundation)宣布，他們以一臺(tái)價(jià)值20萬美元的計(jì)算機(jī)改裝成的專用解密機(jī)，用56小時(shí)破譯了56bits密鑰DES。1991年研究表明DES搜索機(jī)成本如下。資本成本時(shí)間成本$1萬2.5天$10萬6小時(shí)$100萬35分鐘$1000萬3.5分鐘2023/2/4Page:59對(duì)稱密碼體制：DES的差分密碼分析差分攻擊是一種選擇明文攻擊，對(duì)DES中的非線形的s-box的分析s-box輸入為6bit，輸出為4bit，設(shè)為s(x)；選擇二進(jìn)制數(shù)a,b和c都為6bit，d為4bit；a異或b＝c，則s(a)異或s(b)=d的概率遠(yuǎn)遠(yuǎn)大于1/16(抗差分攻擊的分組密碼此概率恒等1/2n，n為s-box輸出位數(shù))；由此性質(zhì)可得部分密鑰的信息，通過窮舉就可以得出密鑰。2023/2/4Page:60對(duì)稱密碼體制：分組密碼的差分密碼分析差分密碼分析是一種攻擊迭代分組密碼的選擇明文統(tǒng)計(jì)分析破譯法，與一般統(tǒng)計(jì)分析法不同之處是，它不是直接分析密文或密鑰的統(tǒng)計(jì)相關(guān)性，而是分析明文差分和密文差分之間的統(tǒng)計(jì)相關(guān)性。給定一個(gè)r輪迭代密碼，對(duì)已知n長明文對(duì)X和X’，定義其差分為X=X(X’)-1，其中，表示n-bits組X的集合中定義的群運(yùn)算，(X’)-1為X’在群中的逆元。在密鑰k作用下，各輪迭代所產(chǎn)生的中間密文差分為

Yi=Yi(Y’i)-10ir

2023/2/4Page:61對(duì)稱密碼體制：分組密碼的差分密碼分析i=0時(shí)，Y0=X，Y’0=X’，Y0=X。i=r時(shí)，Y=Yr，ki是第i輪加密的子密鑰，Yi=f(Yi－1,ki)。由于XX’，因此，Yie(單位元)，即YiF2n－{e}。每輪迭代所用子密鑰ki與明文統(tǒng)計(jì)獨(dú)立，且可認(rèn)為服從均勻分布。

Y’0=X’Y’1

Y’2

Y’r－1

Y’r

Y0=X

Y1

Y2

Yr－1

Yr

f

f

…

fk(1)

k(2)

k(r)

f

f

…

fX=Y0

Y1

Y2

Yr－1

Y=Yr2023/2/4Page:62對(duì)稱密碼體制：分組密碼的差分密碼分析輸入一對(duì)X和X‘，則差分△X已知。同理，輸出△Y已知；由于擴(kuò)展置換E和P-盒已知，則△A和△C已知；雖然無法知道B和B’，但是△B=△A；對(duì)任意給定的△A，△C值不一定相同。將△A和△C聯(lián)合起來，可以猜測(cè)的A異或ki及△A異或ki的位值，應(yīng)為A和△A已知，故可推測(cè)ki的信息。XE△XE(X)ki⊕△AS-盒PY△B△C△Y2023/2/4Page:63對(duì)稱密碼體制：分組密碼的差分密碼分析差分密碼分析的r-輪特征明文對(duì)Y0和Y0’的差分序列a0,…,ar(其中ai是第i輪輸出Yi和Yi’的差分)r-輪特征a0,…,ar條件下，輪函數(shù)輸出特定差分的概率pi=P(△F(Y)=ai|△Y=ai-1)

即為輸入差分為ai-1的條件下，輪函數(shù)F的輸出差分為ai的概率。r-輪特征的概率r-輪特征a0,…,ar條件下，r-輪特征的概率為p=p0

×

p1

×…×

pr2023/2/4Page:64對(duì)稱密碼體制：分組密碼的差分密碼分析差分密碼分析步驟找出一個(gè)(r-1)-輪特征，使它的概率達(dá)到最大；均勻選擇Y0并計(jì)算Y0’，使得Y0和Y0’的差分為a0，找出在實(shí)際密鑰加密下所得到的密文Yr和Yr’。若最后一輪的子密鑰kr有2m個(gè)可能krm，則設(shè)置2m個(gè)計(jì)數(shù)器；用每個(gè)子密鑰解密Yr和Yr’，得到Y(jié)r-1和Yr-1’，如果差分是ar-1，則對(duì)應(yīng)計(jì)數(shù)器加一；重復(fù)第二步，直到一個(gè)或幾個(gè)計(jì)數(shù)器的值明顯高于其它計(jì)數(shù)器，輸出它們所對(duì)應(yīng)的子密鑰(或部分比特)。2023/2/4Page:65對(duì)稱密碼體制：分組密碼的差分密碼分析研究結(jié)果表明，迭代密碼的簡(jiǎn)單輪函數(shù)f在如下意義下通常是密碼上弱的：對(duì)于Yi=f(Yi－1,ki)和Y’i=f(Y’i－1,ki)，若三元組(Yi,Yi,Y’i)的一個(gè)或者多個(gè)值是已知的，則確定子密鑰ki是容易的。從而，若密文對(duì)已知，并且最后一輪的輸入對(duì)的差分能以某種方式得到，則一般來說，確定最后一輪的子密鑰或其一部分是可行的。在差分密碼分析中，通過選擇具有特定差分值Y0的明文對(duì)(Y0,Y’0)，使得最后一輪的輸入差分以很高的概率取特定值來達(dá)到這一點(diǎn)。2023/2/4Page:66對(duì)稱密碼體制：分組密碼的線形密碼分析線性密碼分析的內(nèi)涵使用線性近似值來描述分組密碼線性密碼分析的原理將明文的一些位、密文的一些位分別進(jìn)行異或運(yùn)算；將這個(gè)結(jié)果進(jìn)行異或。2023/2/4Page:67對(duì)稱密碼體制：分組密碼的線形密碼分析假設(shè)條件設(shè)明文分組長度和密文分組長度都為n比特，密鑰分組長度為m比特；明文：P[1],…,P[n]；密文：P[1],…,P[n]；密鑰：K[1],…,K[m]。定義A[i,…,j]=P[i]⊕…⊕P[j]線性分析的目標(biāo)找出有效的線性方程：P[i1,…,ia]⊕C[j1,…,jb]=K[k1,…,kc]；上面的線性方程將得到一個(gè)位，這一位是將密鑰的一些位進(jìn)行異或運(yùn)算的結(jié)果。2023/2/4Page:68對(duì)稱密碼體制：分組密碼的線形密碼分析方程成立的概率p(如果p≠1/2，那么就可以使用該偏差，用得到的明文及對(duì)應(yīng)的密文來猜測(cè)密鑰的位值)如果p≠1/2，則稱該方程是有效的線性逼近；如果|p-1/2|是最大的，則稱該方程是最有效的線性逼近。設(shè)N表示明文數(shù)，T是使方程左邊為0的明文數(shù)T>N/2①K[k1,…,kc]=0(p>?)②K[k1,…,kc]=1(p<?)T<N/2

①K[k1,…,kc]=1(p>?)②K[k1,…,kc]=0(p<?)2023/2/4Page:69對(duì)稱密碼體制：分組密碼的線形密碼分析一個(gè)重要的數(shù)學(xué)結(jié)論(線性密碼分析的思想，抗線性密碼分析的強(qiáng)度就是非線性度)如果明文和密文的關(guān)系是n維線性關(guān)系，且系數(shù)是密鑰，則n個(gè)明文-密文對(duì)(而不是2n個(gè))就可以破解密鑰；如果明文與密文的關(guān)系是n維r次函數(shù)關(guān)系，且系數(shù)是密鑰，則nr

個(gè)明文-密文對(duì)就可以破解密鑰；如果雖然次數(shù)r較大，但明文與密文的關(guān)系“非常逼近”一個(gè)n維線性關(guān)系，則n個(gè)明文-密文對(duì)就可以“基本上”破解密鑰。2023/2/4Page:70對(duì)稱密碼體制：兩重DES2023/2/4Page:71對(duì)稱密碼體制：三重DES2023/2/4Page:72對(duì)稱密碼體制組成流密碼分組密碼數(shù)據(jù)加密標(biāo)準(zhǔn)(DES)高級(jí)加密標(biāo)準(zhǔn)(AES)2023/2/4Page:73對(duì)稱密碼體制：高級(jí)加密標(biāo)準(zhǔn)( AES)的由來1997年1月，美國NIST向全世界密碼學(xué)界發(fā)出征集21世紀(jì)高級(jí)加密標(biāo)準(zhǔn)(AdvancedEncryptionStandard,AES)算法的公告，并成立了AES標(biāo)準(zhǔn)工作研究室，1997年4月15日的例會(huì)制定了對(duì)AES的評(píng)估標(biāo)準(zhǔn)。2023/2/4Page:74對(duì)稱密碼體制：高級(jí)加密標(biāo)準(zhǔn)的評(píng)估標(biāo)準(zhǔn)高級(jí)加密標(biāo)準(zhǔn)(AES)的評(píng)估標(biāo)準(zhǔn)AES是公開的；AES為單鑰體制分組密碼；AES的密鑰長度可變，可按需要增大；AES適于用軟件和硬件實(shí)現(xiàn)；AES可以自由地使用/按符合美國國家標(biāo)準(zhǔn)(ANST)策略的條件使用；滿足以上要求的AES算法，需按下述條件判斷優(yōu)劣：a.安全性，b.計(jì)算效率，c.內(nèi)存要求，d.使用簡(jiǎn)便性，e.靈活性。2023/2/4Page:75對(duì)稱密碼體制：高級(jí)加密標(biāo)準(zhǔn)( AES)的歷史1997年4月15日NIST發(fā)起征集AES的活動(dòng)(要求算法分組長度128比特，密鑰長度128／192／256比特)；1998年8月20日第一次AES候選大會(huì)，公布了15個(gè)候選算法；1999年3月22日舉行了第二次AES候選大會(huì)，選出5個(gè)候選算法；2000年4月25日舉行了第三次AES候選大會(huì)；2000年10月2日公布Rijndael算法作為候選算法。比利時(shí)的JoanDaemen和VincentRijmen設(shè)計(jì)的Rijndael算法：是一個(gè)迭代分組密碼，塊長為128/192/256bits，密鑰長度為128、192、256bits，相應(yīng)的輪數(shù)為10/12/14。2023/2/4Page:76AES：AES的特征AES特征AES是分組密碼，屬于Square結(jié)構(gòu)加密、解密相似但不對(duì)稱密鑰長度和分組長度均可變，密鑰長度和分組長度可以獨(dú)立地指定為128比特、192比特或256比特有較好的數(shù)學(xué)理論作為基礎(chǔ)結(jié)構(gòu)簡(jiǎn)單、速度快能在多種平臺(tái)上以較快的速度實(shí)現(xiàn)2023/2/4Page:77AES：消息分組和密鑰分組消息分組和密鑰分組分別按字節(jié)進(jìn)行劃分(一個(gè)字節(jié)8比特)，為簡(jiǎn)單起見，只討論密鑰長度128比特、消息長度192比特的情形。明文分組=a00,…,a30,…,a05,…,a35密鑰分組=k00,…,k30,…,k03,…,k33a00a01a02a03a04a05a10a11a12a13a14a15a20a21a22a23a24a25a30a31a32a33a34a35k00k01k02k03k10k11k12k13k20k21k22k23k30k31k32k332023/2/4Page:78AES：迭代輪數(shù)與密鑰、消息分組的關(guān)系Rijndael算法同DES一樣，由多基本的變換單位“輪”多次迭代而成。迭代輪數(shù)與密鑰、消息分組的關(guān)系表，其中以Nr表示迭代輪數(shù)Nb表示消息分組按字節(jié)劃分的矩陣列數(shù)(行數(shù)等于4)Nk表示密鑰分組按字節(jié)劃分的矩陣列數(shù)(行數(shù)等于4)NrNb=4Nb=6Nb=8Nk=4101214Nk=6

121214Nk=81414142023/2/4Page:79AES：輪變換輪變換—Round(State,RoundKey)State：輪消息矩陣，既作為輸入，又作為輸出；RoundKey：輪密鑰矩陣，它由輸入密鑰通過密鑰表導(dǎo)出。輪變換由四個(gè)不同的變換組成(除最后一輪)最后一輪記為FinalRound(State,RoundKey)它等于不使用MixColumns函數(shù)的Round(State,RoundKey)Round(State,RoundKey){SubBytes(State);ShiftRows(State);MixColumns(State);AddRoundKey(State,

RoundKey);

}2023/2/4Page:80AES：SubBytes(State)SubBytes為State的每一個(gè)字節(jié)提供一個(gè)非線形變換，任一非零字節(jié)x∈GF(28)被下面的變換所代換(仿射變換)y=Ax-1+b2023/2/4Page:81AES：SubBytes(State)查表法——定時(shí)分析攻擊計(jì)算x-1——(x,x-1)計(jì)算y——包含矩陣A和向量b，(x,y)a00a01a02a03a04a05a10a11a12a13a14a15a20a21a22a23a24a25a30a31a32a33a34a35b00b01b02b03b04b05b10b11b12b13b14b15b20b21b22b23b24b25b30b31b32b33b34b35S-boxaijbij2023/2/4Page:82AES：ShiftRows(State)ShiftRows在State的每行運(yùn)算，它只重排了元素的位置而不改變?cè)乇旧?，?shí)質(zhì)為換位密碼，以128比特的明文長度為例對(duì)在第i行的元素，換位變換就是“循環(huán)向右移動(dòng)”4–i個(gè)位置。字節(jié)移位關(guān)系表NbC1C2C34321632183142023/2/4Page:83AES：MixColumns(State)MixColumns在State的每列上作用，列作為GF(28)上的多項(xiàng)式，每次迭代的輸出為一列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互素2023/2/4Page:84AES：AddRoundKey操作按比特在F2上相加(XOR)a00a01a02a03a04a05a10a11a12a13a14a15a20a21a22a23a24a25a30a31a32a33a34a35k00k01k02k03k04k05k10k11k12k13k14k15k20k21k22k23k24k25k30k31k32k33k34k35=b00b01b02b03b04b05b10b11b12b13b14b15b20b21b22b23b24b25b30b31b32b33b34b352023/2/4Page:85AES：密鑰編排密鑰編排密鑰編排是指從種子密鑰得到輪密鑰的過程，它由密鑰擴(kuò)展和輪密鑰選取兩部分組成輪密鑰的比特?cái)?shù)等于分組長度乘以輪數(shù)加1=[32×

Nb

×

(Nr+1)]；種子密鑰被擴(kuò)展成為擴(kuò)展密鑰；輪密鑰從擴(kuò)展密鑰中取，其中第1輪輪密鑰取擴(kuò)展密鑰的前Nb個(gè)字，第2輪輪密鑰取接下來的Nb個(gè)字，如此下去。2023/2/4Page:86AES：KeyExpansion(key[],w[])KeyExpansion(key[],w[])key[]用于存儲(chǔ)擴(kuò)展前的密鑰；w[]用于存儲(chǔ)擴(kuò)展后的密鑰；以128比特的密鑰為例輸入的密鑰key[]直接被復(fù)制到密鑰數(shù)組的前四個(gè)字，w[0],w[1],w[2],w[3]；w數(shù)組中下標(biāo)不為4的倍數(shù)的元素按以下規(guī)則擴(kuò)展w[i]=w[i-1]⊕

w[i-4]2023/2/4Page:87AES：KeyExpansion(key