對(duì)稱密碼體制.ppt

2020/6/7,Page:1,對(duì)稱密碼體制,楊秋偉湖南大學(xué)計(jì)算機(jī)與通信學(xué)院,2020/6/7,Page:2,對(duì)稱密碼體制,對(duì)稱密碼體制的特征加密密鑰和解密密鑰相同對(duì)稱密碼體制的主要研究課題密鑰的產(chǎn)生密鑰的管理,2020/6/7,Page:3,對(duì)稱密碼體制組成,流密碼分組密碼數(shù)據(jù)加密標(biāo)準(zhǔn)(DES)高級(jí)加密標(biāo)準(zhǔn)(AES),2020/6/7,Page:4,流密碼：流密碼引論,流密碼是將明文劃分成字符(如單個(gè)字母)，或其編碼的基本單元(如按位)，字符分別與密鑰流作用進(jìn)行加密，解密時(shí)以同步產(chǎn)生的同樣的密鑰流實(shí)現(xiàn)。流密碼強(qiáng)度完全依賴于密鑰序列的隨機(jī)性(Randomness)和不可預(yù)測(cè)性(Unpredictability)。核心問(wèn)題是密鑰流的產(chǎn)生密鑰流生成器的設(shè)計(jì)保持收發(fā)兩端密鑰流的精確同步是實(shí)現(xiàn)可靠解密的關(guān)鍵技術(shù),2020/6/7,Page:5,流密碼：流密碼的基本概念,流密碼的基本思想：假設(shè)存在著明文串x=x0 x1x2利用密鑰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),xi,yi,k,2020/6/7,Page:6,流密碼：同步流密碼,同步流密碼：加密器中記憶元件的存儲(chǔ)狀態(tài)i獨(dú)立于明文字符。同步流密碼加密器密鑰流產(chǎn)生器加密變換器加密變換器一般采用二元邏輯運(yùn)算XOR，即有限域GF(2)上討論的二元加密流密碼，變換表示為：yi=zixi一次一密亂碼本是加法流密碼的原型,2020/6/7,Page:7,流密碼：流密碼的密鑰流產(chǎn)生器,密鑰流產(chǎn)生器的內(nèi)涵輸入：密鑰k和加密器中的記憶元件在時(shí)刻i的狀態(tài)i；輸出：密鑰流zi,狀態(tài)i,密鑰k,狀態(tài)i+1,密鑰流zi,2020/6/7,Page:8,流密碼：密鑰流生成器的設(shè)計(jì)原則,足夠長(zhǎng)的周期高線性復(fù)雜度統(tǒng)計(jì)性能良好足夠的“混亂”強(qiáng)調(diào)密鑰的作用，增加密鑰與密文之間關(guān)系的復(fù)雜性足夠的“擴(kuò)散”小擾動(dòng)的影響波及到全局密文沒(méi)有統(tǒng)計(jì)特征，明文一位影響密文的多位，增加密文與明文之間關(guān)系的復(fù)雜性抵抗不同形式的攻擊,2020/6/7,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ù)Yjf1(sj,Xj)Sj+1f2(sj,Xj)即在狀態(tài)sj，輸入字符Xj時(shí)，輸出為Yj，狀態(tài)轉(zhuǎn)移為Sj+1。,2020/6/7,Page:10,流密碼：有限狀態(tài)自動(dòng)機(jī)舉例,例一S=s1,s2,s3,X=x1,x2,x3,Y=y1,y2,y3轉(zhuǎn)移函數(shù),2020/6/7,Page:11,流密碼：有限狀態(tài)自動(dòng)機(jī)舉例,若輸入為x1x2x1x3x3x1初始狀態(tài)s1輸出為y1y1y2y1y3y1,2020/6/7,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)鍵是(phifai)和(psipsai),2020/6/7,Page: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ì)特性良好的序列,2020/6/7,Page:14,流密碼：兩種常見(jiàn)的密鑰流產(chǎn)生器,LFSR：線性反饋移位寄存器流密碼產(chǎn)生密鑰流的主要組成部分。,2020/6/7,Page: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ù),2020/6/7,Page:16,流密碼：反饋移位寄存器,寄存,移位,反饋,2020/6/7,Page:17,流密碼：線性反饋移位寄存器,f(x)為線性函數(shù)，輸出序列滿足下式,2020/6/7,Page: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è)。,2020/6/7,Page:19,流密碼：LFSR的生成函數(shù),給定序列kii0，冪級(jí)數(shù)稱為該序列的生成函數(shù)定理：令kii0(f)，f(x)是反饋多項(xiàng)式，令k(x)是kii0的生成函數(shù)，則其中,2020/6/7,Page:20,流密碼：LFSR的生成函數(shù),定理證明,2020/6/7,Page: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。,2020/6/7,Page:22,流密碼：LFSR的周期,m序列：序列ki0in的周期達(dá)到最大2n-1時(shí)，稱該序列為m序列。定理：以f(x)為特征多項(xiàng)式的LFSR的輸出序列是m序列的充要條件為f(x)是本原的。m序列的性質(zhì)n級(jí)m序列的周期為2n1，周期隨n增加而指數(shù)級(jí)遞增；只要知道n次本原多項(xiàng)式，m序列極易生成；m序列極不安全，只要泄露2n位連續(xù)數(shù)字，就可完全確定出反饋多項(xiàng)式系數(shù)。,階為2n-1的n次不可約多項(xiàng)式,2020/6/7,Page:23,流密碼：LFSR的周期,m序列的破譯已知ki,ki+1,ki+2n，由遞推關(guān)系式可得出下式式中有n個(gè)線性方程和n個(gè)未知量，故可惟一解出ci，0in-1。,2020/6/7,Page:24,流密碼：非線性序列,LFSR雖然不能直接作為密鑰流用，但可作為驅(qū)動(dòng)源以其輸出推動(dòng)一個(gè)非線性組合函數(shù)所決定的電路來(lái)產(chǎn)生非線性序列。這就是所謂非線性前饋序列生成器。LFSR用來(lái)保證密鑰流的周期長(zhǎng)度、平衡性等；非線性組合函數(shù)用來(lái)保證密鑰流的各種密碼性質(zhì)，以抗擊各種可能的攻擊。,2020/6/7,Page:25,流密碼：非線性前饋序列,前饋函數(shù)F(非線性組合函數(shù))輸出序列的周期性、隨機(jī)性、線性復(fù)雜度以及相關(guān)免疫性之間的關(guān)系,2020/6/7,Page:26,流密碼：J-K觸發(fā)器,J-K觸發(fā)器是一個(gè)非線性器件，有兩個(gè)輸入端j和k，輸出為qi。輸出不僅依賴于輸入，還依賴于前一個(gè)輸出位qi-1，即其結(jié)構(gòu)及邏輯真值表如下所示,2020/6/7,Page: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)。,2020/6/7,Page:28,流密碼：多路選擇序列,有n種輸入序列b0(t),bn-1(t)，在地址序列a1(t),am-1(t)的控制下決定輸出取自某個(gè)輸入比特。Pless生成器例如取m級(jí)LFSR生成m序列作地址控制，取n級(jí)LFSR生成的m序列作為輸入序列。,2020/6/7,Page:29,對(duì)稱密碼體制組成,流密碼分組密碼數(shù)據(jù)加密標(biāo)準(zhǔn)(DES)高級(jí)加密標(biāo)準(zhǔn)(AES),2020/6/7,Page: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),2020/6/7,Page:31,分組密碼：分組密碼的工作模式比較,2020/6/7,Page:32,分組密碼：分組密碼的經(jīng)典工作模式,電子編碼薄模式,密碼分組鏈接模式,輸出反饋模式,2020/6/7,Page:33,分組密碼：分組密碼的擴(kuò)散與壓縮,分組密碼的基本過(guò)程將明文分成m個(gè)塊，M1,M2,Mm；對(duì)每個(gè)塊執(zhí)行相同的變換，從而生成m個(gè)密文塊，C1,C2,Cm。,2020/6/7,Page:34,分組密碼：分組密碼的擴(kuò)展與壓縮,將明文x和密文y表示成分別小于2m和2n的整數(shù)，并用分量形式描述。每個(gè)分量分別用xi，yiGF(2)表示，即：若nm，則為有數(shù)據(jù)擴(kuò)展的分組密碼；若nN/2Kk1,kc=0(p)Kk1,kc=1(p)Kk1,kc=0(p),2020/6/7,Page: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ì)就可以“基本上”破解密鑰。,2020/6/7,Page:70,對(duì)稱密碼體制：兩重DES,2020/6/7,Page:71,對(duì)稱密碼體制：三重DES,2020/6/7,Page:72,對(duì)稱密碼體制組成,流密碼分組密碼數(shù)據(jù)加密標(biāo)準(zhǔn)(DES)高級(jí)加密標(biāo)準(zhǔn)(AES),2020/6/7,Page:73,對(duì)稱密碼體制：高級(jí)加密標(biāo)準(zhǔn)(AES)的由來(lái),1997年1月，美國(guó)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)。,2020/6/7,Page: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是公開(kāi)的；AES為單鑰體制分組密碼；AES的密鑰長(zhǎng)度可變，可按需要增大；AES適于用軟件和硬件實(shí)現(xiàn)；AES可以自由地使用/按符合美國(guó)國(guó)家標(biāo)準(zhǔn)(ANST)策略的條件使用；滿足以上要求的AES算法，需按下述條件判斷優(yōu)劣：a.安全性，b.計(jì)算效率，c.內(nèi)存要求，d.使用簡(jiǎn)便性，e.靈活性。,2020/6/7,Page:75,對(duì)稱密碼體制：高級(jí)加密標(biāo)準(zhǔn)(AES)的歷史,1997年4月15日NIST發(fā)起征集AES的活動(dòng)(要求算法分組長(zhǎng)度128比特，密鑰長(zhǎng)度128192256比特)；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è)迭代分組密碼，塊長(zhǎng)為128/192/256bits，密鑰長(zhǎng)度為128、192、256bits，相應(yīng)的輪數(shù)為10/12/14。,2020/6/7,Page:76,AES：AES的特征,AES特征AES是分組密碼，屬于Square結(jié)構(gòu)加密、解密相似但不對(duì)稱密鑰長(zhǎng)度和分組長(zhǎng)度均可變，密鑰長(zhǎng)度和分組長(zhǎng)度可以獨(dú)立地指定為128比特、192比特或256比特有較好的數(shù)學(xué)理論作為基礎(chǔ)結(jié)構(gòu)簡(jiǎn)單、速度快能在多種平臺(tái)上以較快的速度實(shí)現(xiàn),2020/6/7,Page:77,AES：消息分組和密鑰分組,消息分組和密鑰分組分別按字節(jié)進(jìn)行劃分(一個(gè)字節(jié)8比特)，為簡(jiǎn)單起見(jiàn)，只討論密鑰長(zhǎng)度128比特、消息長(zhǎng)度192比特的情形。明文分組=a00,a30,a05,a35密鑰分組=k00,k30,k03,k33,2020/6/7,Page:78,AES：迭代輪數(shù)與密鑰、消息分組的關(guān)系,Rijndael算法同DES一樣，由多基本的變換單位“輪”多次迭代而成。迭代輪數(shù)與密鑰、消息分組的關(guān)系表，其中以Nr表示迭代輪數(shù)Nb表示消息分組按字節(jié)劃分的矩陣列數(shù)(行數(shù)等于4)Nk表示密鑰分組按字節(jié)劃分的矩陣列數(shù)(行數(shù)等于4),2020/6/7,Page:79,AES：輪變換,輪變換Round(State,RoundKey)State：輪消息矩陣，既作為輸入，又作為輸出；RoundKey：輪密鑰矩陣，它由輸入密鑰通過(guò)密鑰表導(dǎo)出。輪變換由四個(gè)不同的變換組成(除最后一輪)最后一輪記為FinalRound(State,RoundKey)它等于不使用MixColumns函數(shù)的Round(State,RoundKey),Round(State,RoundKey)SubBytes(State);ShiftRows(State);MixColumns(State);AddRoundKey(State,RoundKey);,2020/6/7,Page:80,AES：SubBytes(State),SubBytes為State的每一個(gè)字節(jié)提供一個(gè)非線形變換，任一非零字節(jié)xGF(28)被下面的變換所代換(仿射變換)y=Ax-1+b,2020/6/7,Page:81,AES：SubBytes(State),查表法定時(shí)分析攻擊計(jì)算x-1(x,x-1)計(jì)算y包含矩陣A和向量b，(x,y),aij,bij,2020/6/7,Page:82,AES：ShiftRows(State),ShiftRows在State的每行運(yùn)算，它只重排了元素的位置而不改變?cè)乇旧恚瑢?shí)質(zhì)為換位密碼，以128比特的明文長(zhǎng)度為例對(duì)在第i行的元素，換位變換就是“循環(huán)向右移動(dòng)”4i個(gè)位置。字節(jié)移位關(guān)系表,2020/6/7,Page:83,AES：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互素,2020/6/7,Page:84,AES：AddRoundKey操作,按比特在F2上相加(XOR),=,2020/6/7,Page:85,AES：密鑰編排,密鑰編排密鑰編排是指從種子密鑰得到輪密鑰的過(guò)程，它由密鑰擴(kuò)展和輪密鑰選取兩部分組成輪密鑰的比特?cái)?shù)等于分組長(zhǎng)度乘以輪數(shù)加1=32Nb(Nr+1)；種子密鑰被擴(kuò)展成為擴(kuò)展密鑰；輪密鑰從擴(kuò)展密鑰中取，其中第1輪輪密鑰取擴(kuò)展密鑰的前Nb個(gè)字，第2輪輪密鑰取接下來(lái)的Nb個(gè)字，如此下去。,2020/6/7,Page:86,AES：KeyExpansion(key,w),KeyExpansion(key,w)key用于存儲(chǔ)擴(kuò)展前的密鑰；w用于存儲(chǔ)擴(kuò)展后的密鑰；以128比特的密鑰為例輸入的密鑰key直接被復(fù)制到密鑰數(shù)組的前四個(gè)字，w0,w1,w2,w3；w數(shù)組中下標(biāo)不為4的倍數(shù)的元素按以下規(guī)則擴(kuò)展wi=wi-1wi-4,2020/6/7,Page:87,AES：KeyExpansion(key,w),下標(biāo)為4的倍數(shù)的元素按以下規(guī)則擴(kuò)展將一個(gè)字的四個(gè)字節(jié)循環(huán)左移一個(gè)字節(jié)，即將b0,b1,b2,b3變?yōu)閎1,b2,b3,b0；基于SubBytes對(duì)輸入字中的每個(gè)字節(jié)進(jìn)行代替；S盒將步驟1和步驟2的結(jié)果再與輪常量Rconi相異或。Rconi=(RCi,00,00,00)RC1=01RCi=2.(RCi-1),2020/6/7,Page:88,AES：KeyExpansion()-Nk6,KeyExpansion(bytekey4*Nk,wordwNb*(Nr+1)for(i=0;iNk;i+)wi=(key4*i,key4*i+1,key4*i+2,key4*i+3);for(i=Nk;iNb*(Nr+1);i+)temp=wi-1;if(i%Nk=0)temp=SubBytes(temp6,KeyExpansion(bytekey4*Nk,wordwNb*(Nr+1)for(i=0;iNk;i+)wi=(key4*i,key4*i+1,key4*i+2,key4*i+3);for(i=Nk;iNb*(Nr+1);i+)temp=wi-1;if(i%Nk=0)temp=SubBytes(temp8)Rconi/Nk;elseif(i%Nk=4)temp=SubBytes(temp8);