對稱密碼體制

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

同步流密碼：加密器中記憶元件的存儲狀態(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和加密器中的記憶元件在時刻i的狀態(tài)δi；輸出：密鑰流zi狀態(tài)δi密鑰k狀態(tài)δi+1密鑰流zi2023/2/4Page:8流密碼：密鑰流生成器的設(shè)計原則足夠長的周期高線性復(fù)雜度統(tǒng)計性能良好足夠的“混亂”強(qiáng)調(diào)密鑰的作用，增加密鑰與密文之間關(guān)系的復(fù)雜性足夠的“擴(kuò)散”小擾動的影響波及到全局密文沒有統(tǒng)計特征，明文一位影響密文的多位，增加密文與明文之間關(guān)系的復(fù)雜性抵抗不同形式的攻擊2023/2/4Page:9流密碼：有限狀態(tài)自動機(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時，輸出為Yj，狀態(tài)轉(zhuǎn)移為Sj+1。2023/2/4Page:10流密碼：有限狀態(tài)自動機(jī)舉例例一S={s1,s2,s3},X={x1,x2,x3},Y={y1,y2,y3}轉(zhuǎn)移函數(shù)f1x1x2x3s1s2s3y1y2y3y3y1y2y2y3y1f2x1x2x3s1s2s3s2s3s1s1s2s3s3s1s22023/2/4Page:11流密碼：有限狀態(tài)自動機(jī)舉例若輸入為x1x2x1x3x3x1初始狀態(tài)s1輸出為

y1y1y2y1y3y12023/2/4Page:12流密碼：基于FA的密鑰流產(chǎn)生器同步流密碼的密鑰流產(chǎn)生器可看為一個參數(shù)為k的FA：輸出集Z，狀態(tài)集Σ，狀態(tài)轉(zhuǎn)移函數(shù)φ和輸出函數(shù)ψ，初態(tài)0設(shè)計的關(guān)鍵是φ(phifai)和ψ(psipsai)φiψkkzi2023/2/4Page:13流密碼：基于FA的密鑰流產(chǎn)生器一個良好的密鑰流產(chǎn)生器極大的周期良好的統(tǒng)計特性抗線性分析抗統(tǒng)計分析具有非線性的φ的FA理論很不完善，通常采用線性φ以及非線性的ψ。可將此類產(chǎn)生器分為驅(qū)動部分和非線性組合部分。驅(qū)動部分控制狀態(tài)轉(zhuǎn)移非線性組合部分提供統(tǒng)計特性良好的序列2023/2/4Page:14流密碼：兩種常見的密鑰流產(chǎn)生器LFSR非線性組合函數(shù)ziLFSR1LFSR2LFSR3非線性組合函數(shù)ziLFSR：線性反饋移位寄存器——流密碼產(chǎn)生密鑰流的主要組成部分。2023/2/4Page:15流密碼：反饋移位寄存器的概念基本概念級數(shù)(Stages)：存儲單元數(shù)n狀態(tài)(State)：n個存儲單元的存數(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的特征多項式LFSR的特征多項式：以LFSR的反饋系數(shù)所決定的一元高次多項式又稱反饋多項式。由于ciGF(2)(i=1,2,…,n)，所以有2n組初始狀態(tài)，即有2n個遞推序列，其中非恒零的有2n-1個。2023/2/4Page:19流密碼：LFSR的生成函數(shù)

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

定理證明2023/2/4Page:21流密碼：LFSR的周期LFSR周期的真正涵義？？？？定義：設(shè)p(x)是GF(2)上的多項式，使p(x)|(xp-1)的最小p稱為p(x)的周期或者階。定理：設(shè)序列{ki}的特征多項式p(x)定義GF(2)上，p是p(x)的周期，則{ki}的周期r|p。定理：設(shè)序列{ki}的特征多項式p(x)定義GF(2)上，且p(x)是不可約多項式，p是p(x)的周期，則{ki}的周期為p。2023/2/4Page:22流密碼：LFSR的周期m序列：序列{ki}0≤i≤n的周期達(dá)到最大2n-1時，稱該序列為m序列。定理：以f(x)為特征多項式的LFSR的輸出序列是m序列的充要條件為f(x)是本原的。m序列的性質(zhì)n級m序列的周期為2n－1，周期隨n增加而指數(shù)級遞增；只要知道n次本原多項式，m序列極易生成；m序列極不安全，只要泄露2n位連續(xù)數(shù)字，就可完全確定出反饋多項式系數(shù)。階為2n-1的n次不可約多項式2023/2/4Page:23流密碼：LFSR的周期m序列的破譯已知ki,ki+1,…,ki+2n，由遞推關(guān)系式可得出下式式中有n個線性方程和n個未知量，故可惟一解出ci，0in-1。2023/2/4Page:24流密碼：非線性序列LFSR雖然不能直接作為密鑰流用，但可作為驅(qū)動源以其輸出推動一個非線性組合函數(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ā)器是一個非線性器件，有兩個輸入端j和k，輸出為qi。輸出不僅依賴于輸入，還依賴于前一個輸出位qi-1，即其結(jié)構(gòu)及邏輯真值表如下所示JKqk00110101qk-101⊕⊕⊙JKR=qk-1qk2023/2/4Page:27流密碼：J-K觸發(fā)器的非線性序列生成器{ak}和{bk}被稱為非線性序列生成器的驅(qū)動序列。性質(zhì)：設(shè){ak}和{bk}分別為x級和y級m序列。當(dāng)x和y互素，且a0+b0=1時，序列{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)的控制下決定輸出取自某個輸入比特?！?/p>

Pless生成器例如取m級LFSR生成m序列作地址控制，取n級LFSR生成的m序列作為輸入序列?？晒┻x擇的輸入2023/2/4Page:29對稱密碼體制組成流密碼分組密碼數(shù)據(jù)加密標(biāo)準(zhǔn)(DES)高級加密標(biāo)準(zhǔn)(AES)2023/2/4Page:30對稱密碼體制：分組密碼分組密碼的工作原理將明文分成n個塊，m1,m2,…,mn；對每個塊執(zhí)行相同的變換，從而生成n個密文塊，c1,c2,…,cn。分組密碼的工作模式：明文分組固定，消息的數(shù)據(jù)量不同，數(shù)據(jù)格式各式各樣。為了適應(yīng)各種應(yīng)用環(huán)境，有四種工作模式。電子編碼薄模式(EBC)密碼分組鏈接模式(CBC)密碼反饋模式(CFB)輸出反饋模式(OFB)2023/2/4Page:31分組密碼：分組密碼的工作模式比較模式描述用途電碼本模式(ECB)每個明文組獨(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個塊，M1,M2,…,Mm；對每個塊執(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)

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

y=(x)2023/2/4Page:35分組密碼：分組密碼的置換設(shè)明文分組長度為n比特，則明文分組的取值為2n。為了使加密運(yùn)算可逆，每一個明文對應(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è)計整個分組密碼的代換網(wǎng)絡(luò)時，要求輸出的每比特密文都和輸入的明文及密鑰各比特有關(guān)，這對增加密碼強(qiáng)度有好處。2023/2/4Page:37分組密碼：迭代分組密碼迭代分組密碼：若以一個簡單函數(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é)束字符表示明文分組的最后一個字節(jié)；每一個分組都必須以0、1或者0、1交替的模式填充，即使明文以分組的邊界結(jié)束，也必須添加一個整分組。2023/2/4Page:39分組密碼：分組密碼的評估分組密碼如何才算是安全？？密鑰必須足夠大，使強(qiáng)力攻擊失效或者得不償失—愷撒密碼；如果加密法通過了隨機(jī)測試，在一定時間內(nèi)能給人以安全性。雪崩條件(avalanchecondition)：任何輸入位或密鑰位與輸出位之間不應(yīng)有任何連續(xù)，即密文中不能有內(nèi)容含有關(guān)于密鑰或明文的提示。精確密文雪崩標(biāo)準(zhǔn)：無論密文塊的任意一位有變，密文塊每個位發(fā)生改變的概率為50%；精確密鑰雪崩標(biāo)準(zhǔn)：對于一個長度固定的明文塊，當(dāng)密鑰的任意一位發(fā)生改變時，密文款每個位發(fā)生改變的概率為50%。2023/2/4Page:40對稱密碼體制組成流密碼分組密碼數(shù)據(jù)加密標(biāo)準(zhǔn)(DES)高級加密標(biāo)準(zhǔn)(AES)2023/2/4Page:41對稱密碼體制：數(shù)據(jù)加密標(biāo)準(zhǔn)( DES)的歷史20世紀(jì)70年代中期，美國政府認(rèn)為需要一個功能強(qiáng)大的標(biāo)準(zhǔn)加密系統(tǒng)，提出開發(fā)這種加密法的請求；1973年5月15日，國家標(biāo)準(zhǔn)局(NationalBureauofStandards,NBS)開始公開征集標(biāo)準(zhǔn)加密算法，并公布了它的設(shè)計要求 算法必須提供高度的安全性算法必須有詳細(xì)的說明，并易于理解算法的安全性取決于密鑰，不依賴于算法算法適用于所有用戶算法適用于不同應(yīng)用場合算法必須高效、經(jīng)濟(jì)算法必須能被證實(shí)有效算法必須是可出口的2023/2/4Page:42對稱密碼體制：數(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é)會(ANSI)標(biāo)準(zhǔn)；1983年，國際化標(biāo)準(zhǔn)組織贊同DES作為國際標(biāo)準(zhǔn)，稱之為DEA-1；1984年2月，ISO成立的數(shù)據(jù)加密技術(shù)委員會(SC20)在DES基礎(chǔ)上制定數(shù)據(jù)加密的國際標(biāo)準(zhǔn)工作；DES最后被高級加密標(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位分組長度；對稱算法：加密和解密除密鑰編排不同外，使用同一算法；密鑰長度：64位，但每個字節(jié)第8位為奇偶校驗位，可忽略；密鑰可為任意的56位數(shù)，但存在弱密鑰，盡量避開；采用混亂和擴(kuò)散的組合，每個組合先替代后置換，共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位對換逆初始置換IP－164位密文48位64位明文64位密鑰2023/2/4Page:46DES：初始置換IP和IP-1IP和IP-1在密碼意義上作用不大，因為輸入組x與其輸出組y=IP(x)(或IP-1(x))是已知的一一對應(yīng)關(guān)系。它們的作用在于打亂原來輸入x的ASCII碼字劃分的關(guān)系，并將原來明文的校驗位x8,x16,,x64變成為IP輸出的一個字節(jié)。IPIP—12023/2/4Page:47DES：乘積變換乘積變換是DES算法的核心部分將經(jīng)過IP置換后的數(shù)據(jù)分成32bit的左右兩組；每次迭代時只對右邊的32bit進(jìn)行一系列的加密變換，在此輪迭代即將結(jié)束時，把左邊的32bit與右邊得到的32bit逐位模2相加，作為下一輪迭代時右邊的段；將原來右邊未經(jīng)變換的段直接送到左邊的寄存器中作為下一輪迭代時左邊的段；在每一輪迭代時，右邊的段要經(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ù)一次得到的，即對原第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個S一盒，每個S盒為一非線性代換網(wǎng)絡(luò)，有4個輸出。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：對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位為校驗位，其位置號為8、16、32、48、56和64。其余56位為有效位，用于子密鑰計算。置換選擇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次迭代時所用的子密鑰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è)計原理至今未公布，可能隱含有陷井幾種攻擊的計算代價強(qiáng)力攻擊：255次嘗試差分密碼分析法：247次嘗試線性密碼分析法：243次嘗試2023/2/4Page:57DES：算法分析互補(bǔ)性：若明文組x逐位取補(bǔ)，密鑰k逐位取補(bǔ)，且y=DESk(x)，則有，稱這種特性為算法上的互補(bǔ)性。這種互補(bǔ)性會使DES在選擇明文破譯下所需的工作量減半。弱密鑰：DES算法在每次迭代時都有一個子密鑰供加密用。如果給定初始密鑰k，各輪的子密鑰都相同，即有k1=k2=…=k16，就稱給定密鑰k為弱密鑰(Weakkey)。半弱密鑰：兩個不同密鑰將同一明文加密成相同密文，一個用來加密，一個用來解密。2023/2/4Page:58DES：算法分析RSA數(shù)據(jù)安全公司提供10000美元獎金?，F(xiàn)已被DESCHALL小組經(jīng)過近四個月的努力，通過Internet搜索了3×1016個密鑰，找出了DES的密鑰，恢復(fù)出明文。1998年5月美國ElectronicFrontierFoundation)宣布，他們以一臺價值20萬美元的計算機(jī)改裝成的專用解密機(jī)，用56小時破譯了56bits密鑰DES。1991年研究表明DES搜索機(jī)成本如下。資本成本時間成本$1萬2.5天$10萬6小時$100萬35分鐘$1000萬3.5分鐘2023/2/4Page:59對稱密碼體制：DES的差分密碼分析差分攻擊是一種選擇明文攻擊，對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對稱密碼體制：分組密碼的差分密碼分析差分密碼分析是一種攻擊迭代分組密碼的選擇明文統(tǒng)計分析破譯法，與一般統(tǒng)計分析法不同之處是，它不是直接分析密文或密鑰的統(tǒng)計相關(guān)性，而是分析明文差分和密文差分之間的統(tǒng)計相關(guān)性。給定一個r輪迭代密碼，對已知n長明文對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對稱密碼體制：分組密碼的差分密碼分析i=0時，Y0=X，Y’0=X’，Y0=X。i=r時，Y=Yr，ki是第i輪加密的子密鑰，Yi=f(Yi－1,ki)。由于XX’，因此，Yie(單位元)，即YiF2n－{e}。每輪迭代所用子密鑰ki與明文統(tǒng)計獨(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對稱密碼體制：分組密碼的差分密碼分析輸入一對X和X‘，則差分△X已知。同理，輸出△Y已知；由于擴(kuò)展置換E和P-盒已知，則△A和△C已知；雖然無法知道B和B’，但是△B=△A；對任意給定的△A，△C值不一定相同。將△A和△C聯(lián)合起來，可以猜測的A異或ki及△A異或ki的位值，應(yīng)為A和△A已知，故可推測ki的信息。XE△XE(X)ki⊕△AS-盒PY△B△C△Y2023/2/4Page:63對稱密碼體制：分組密碼的差分密碼分析差分密碼分析的r-輪特征明文對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對稱密碼體制：分組密碼的差分密碼分析差分密碼分析步驟找出一個(r-1)-輪特征，使它的概率達(dá)到最大；均勻選擇Y0并計算Y0’，使得Y0和Y0’的差分為a0，找出在實(shí)際密鑰加密下所得到的密文Yr和Yr’。若最后一輪的子密鑰kr有2m個可能krm，則設(shè)置2m個計數(shù)器；用每個子密鑰解密Yr和Yr’，得到Y(jié)r-1和Yr-1’，如果差分是ar-1，則對應(yīng)計數(shù)器加一；重復(fù)第二步，直到一個或幾個計數(shù)器的值明顯高于其它計數(shù)器，輸出它們所對應(yīng)的子密鑰(或部分比特)。2023/2/4Page:65對稱密碼體制：分組密碼的差分密碼分析研究結(jié)果表明，迭代密碼的簡單輪函數(shù)f在如下意義下通常是密碼上弱的：對于Yi=f(Yi－1,ki)和Y’i=f(Y’i－1,ki)，若三元組(Yi,Yi,Y’i)的一個或者多個值是已知的，則確定子密鑰ki是容易的。從而，若密文對已知，并且最后一輪的輸入對的差分能以某種方式得到，則一般來說，確定最后一輪的子密鑰或其一部分是可行的。在差分密碼分析中，通過選擇具有特定差分值Y0的明文對(Y0,Y’0)，使得最后一輪的輸入差分以很高的概率取特定值來達(dá)到這一點(diǎn)。2023/2/4Page:66對稱密碼體制：分組密碼的線形密碼分析線性密碼分析的內(nèi)涵使用線性近似值來描述分組密碼線性密碼分析的原理將明文的一些位、密文的一些位分別進(jìn)行異或運(yùn)算；將這個結(jié)果進(jìn)行異或。2023/2/4Page:67對稱密碼體制：分組密碼的線形密碼分析假設(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]；上面的線性方程將得到一個位，這一位是將密鑰的一些位進(jìn)行異或運(yùn)算的結(jié)果。2023/2/4Page:68對稱密碼體制：分組密碼的線形密碼分析方程成立的概率p(如果p≠1/2，那么就可以使用該偏差，用得到的明文及對應(yīng)的密文來猜測密鑰的位值)如果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對稱密碼體制：分組密碼的線形密碼分析一個重要的數(shù)學(xué)結(jié)論(線性密碼分析的思想，抗線性密碼分析的強(qiáng)度就是非線性度)如果明文和密文的關(guān)系是n維線性關(guān)系，且系數(shù)是密鑰，則n個明文-密文對(而不是2n個)就可以破解密鑰；如果明文與密文的關(guān)系是n維r次函數(shù)關(guān)系，且系數(shù)是密鑰，則nr

個明文-密文對就可以破解密鑰；如果雖然次數(shù)r較大，但明文與密文的關(guān)系“非常逼近”一個n維線性關(guān)系，則n個明文-密文對就可以“基本上”破解密鑰。2023/2/4Page:70對稱密碼體制：兩重DES2023/2/4Page:71對稱密碼體制：三重DES2023/2/4Page:72對稱密碼體制組成流密碼分組密碼數(shù)據(jù)加密標(biāo)準(zhǔn)(DES)高級加密標(biāo)準(zhǔn)(AES)2023/2/4Page:73對稱密碼體制：高級加密標(biāo)準(zhǔn)( AES)的由來1997年1月，美國NIST向全世界密碼學(xué)界發(fā)出征集21世紀(jì)高級加密標(biāo)準(zhǔn)(AdvancedEncryptionStandard,AES)算法的公告，并成立了AES標(biāo)準(zhǔn)工作研究室，1997年4月15日的例會制定了對AES的評估標(biāo)準(zhǔn)。2023/2/4Page:74對稱密碼體制：高級加密標(biāo)準(zhǔn)的評估標(biāo)準(zhǔn)高級加密標(biāo)準(zhǔn)(AES)的評估標(biāo)準(zhǔn)AES是公開的；AES為單鑰體制分組密碼；AES的密鑰長度可變，可按需要增大；AES適于用軟件和硬件實(shí)現(xiàn)；AES可以自由地使用/按符合美國國家標(biāo)準(zhǔn)(ANST)策略的條件使用；滿足以上要求的AES算法，需按下述條件判斷優(yōu)劣：a.安全性，b.計算效率，c.內(nèi)存要求，d.使用簡便性，e.靈活性。2023/2/4Page:75對稱密碼體制：高級加密標(biāo)準(zhǔn)( AES)的歷史1997年4月15日NIST發(fā)起征集AES的活動(要求算法分組長度128比特，密鑰長度128／192／256比特)；1998年8月20日第一次AES候選大會，公布了15個候選算法；1999年3月22日舉行了第二次AES候選大會，選出5個候選算法；2000年4月25日舉行了第三次AES候選大會；2000年10月2日公布Rijndael算法作為候選算法。比利時的JoanDaemen和VincentRijmen設(shè)計的Rijndael算法：是一個迭代分組密碼，塊長為128/192/256bits，密鑰長度為128、192、256bits，相應(yīng)的輪數(shù)為10/12/14。2023/2/4Page:76AES：AES的特征AES特征AES是分組密碼，屬于Square結(jié)構(gòu)加密、解密相似但不對稱密鑰長度和分組長度均可變，密鑰長度和分組長度可以獨(dú)立地指定為128比特、192比特或256比特有較好的數(shù)學(xué)理論作為基礎(chǔ)結(jié)構(gòu)簡單、速度快能在多種平臺上以較快的速度實(shí)現(xiàn)2023/2/4Page:77AES：消息分組和密鑰分組消息分組和密鑰分組分別按字節(jié)進(jìn)行劃分(一個字節(jié)8比特)，為簡單起見，只討論密鑰長度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)出。輪變換由四個不同的變換組成(除最后一輪)最后一輪記為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的每一個字節(jié)提供一個非線形變換，任一非零字節(jié)x∈GF(28)被下面的變換所代換(仿射變換)y=Ax-1+b2023/2/4Page:81AES：SubBytes(State)查表法——定時分析攻擊計算x-1——(x,x-1)計算y——包含矩陣A和向量b，(x,y)a00a01a02a03a04a05a10a11a12a13a14a15a20a21a22a23a24a25a30a31a32a33a34a35b00b01b02b03b04b05b10b11b12b13b14b15b20b21b22b23b24b25b30b31b32b33b34b35S-boxaijbij2023/2/4Page:82AES：ShiftRows(State)ShiftRows在State的每行運(yùn)算，它只重排了元素的位置而不改變元素本身，實(shí)質(zhì)為換位密碼，以128比特的明文長度為例對在第i行的元素，換位變換就是“循環(huán)向右移動”4–i個位置。字節(jié)移位關(guān)系表NbC1C2C34321632183142023/2/4Page:83AES：MixColumns(State)MixColumns在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互素2023/2/4Page:84AES：AddRoundKey操作按比特在F2上相加(XOR)a00a01a02a03a04a05a10a11a12a13a14a15a20a21a22a23a24a25a30a31a32a33a34a35k00k01k02k03k04k05k10k11k12k13k14k15k20k21k22k23k24k25k30k31k32k33k34k35=b00b01b02b03b04b05b10b11b12b13b14b15b20b21b22b23b24b25b30b31b32b33b34b352023/2/4Page:85AES：密鑰編排密鑰編排密鑰編排是指從種子密鑰得到輪密鑰的過程，它由密鑰擴(kuò)展和輪密鑰選取兩部分組成輪密鑰的比特數(shù)等于分組長度乘以輪數(shù)加1=[32×

Nb

×

(Nr+1)]；種子密鑰被擴(kuò)展成為擴(kuò)展密鑰；輪密鑰從擴(kuò)展密鑰中取，其中第1輪輪密鑰取擴(kuò)展密鑰的前Nb個字，第2輪輪密鑰取接下來的Nb個字，如此下去。2023/2/4Page:86AES：KeyExpansion(key[],w[])KeyExpansion(key[],w[])key[]用于存儲擴(kuò)展前的密鑰；w[]用于存儲擴(kuò)展后的密鑰；以128比特的密鑰為例輸入的密鑰key[]直接被復(fù)制到密鑰數(shù)組的前四個字，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