對稱密碼體制

關(guān)于對稱密碼體制第1頁，講稿共61頁，2023年5月2日，星期三概述對稱密碼體制就是在加密和解密是用到的密鑰相同，或者加密密鑰和解密密鑰之間存在著確定的轉(zhuǎn)換關(guān)系。對稱密碼體制又有兩種不同的實現(xiàn)方式，即分組密碼和序列密碼（或稱流密碼）。第2頁，講稿共61頁，2023年5月2日，星期三流密碼與分組密碼流密碼每次加密數(shù)據(jù)流中的一位或一個字節(jié)。分組密碼，就是先把明文劃分為許多分組，每個明文分組被當(dāng)作一個整體來產(chǎn)生一個等長（通常）的密文分組。通常使用的是64位或128位分組大小。分組密碼的實質(zhì)，是設(shè)計一種算法，能在密鑰控制下，把n比特明文簡單而又迅速地置換成唯一n比特密文，并且這種變換是可逆的（解密）。第3頁，講稿共61頁，2023年5月2日，星期三分組密碼分組密碼算法實際上就是在密鑰的控制下，簡單而迅速地找到一個置換，用來對明文分組進行加密變換，一般情況下對密碼算法的要求是：分組長度m足夠大（64~128比特）密鑰空間足夠大（密鑰長度64~128比特）密碼變換必須足夠復(fù)雜（包括子密鑰產(chǎn)生算法）第4頁，講稿共61頁，2023年5月2日，星期三分組密碼的設(shè)計思想擴散(diffusion)

將明文及密鑰的影響盡可能迅速地散布到較多個輸出的密文中。產(chǎn)生擴散的最簡單方法是通過“置換(Permutation)”（比如：重新排列字符）?；煜?confusion)其目的在于使作用于明文的密鑰和密文之間的關(guān)系復(fù)雜化，是明文和密文之間、密文和密鑰之間的統(tǒng)計相關(guān)特性極小化，從而使統(tǒng)計分析攻擊不能奏效。通常的方法是“代換（Substitution)”（回憶愷撒密碼）。第5頁，講稿共61頁，2023年5月2日，星期三分組密碼的設(shè)計技術(shù)將大的明文分組再分成幾個小段，分別完成各個小段的加密置換，最后進行并行操作。采用乘積密碼技術(shù)。第6頁，講稿共61頁，2023年5月2日，星期三DES(DataEncryptionStandard)

美國國家標(biāo)準(zhǔn)局NBS于1973年5月發(fā)出通告，公開征求一種標(biāo)準(zhǔn)算法用于對計算機數(shù)據(jù)在傳輸和存儲期間實現(xiàn)加密保護的密碼算法。1975年美國國家標(biāo)準(zhǔn)局接受了美國國際商業(yè)機器公司IBM推薦的一種密碼算法并向全國公布，征求對采用該算法作為美國信息加密標(biāo)準(zhǔn)的意見。經(jīng)過兩年的激烈爭論，美國國家標(biāo)準(zhǔn)局于1977年7月正式采用該算法作為美國數(shù)據(jù)加密標(biāo)準(zhǔn)。1980年12月美國國家標(biāo)準(zhǔn)協(xié)會正式采用這個算法作為美國的商用加密算法。第7頁，講稿共61頁，2023年5月2日，星期三DES的實質(zhì)DES是一種對稱密碼體制，它所使用的加密和解密密鑰是相同的，是一種典型的按分組方式工作的密碼。其基本思想是將二進制序列的明文分成每64bit一組，用長為64bit(56bit)的密鑰對其進行16輪代換和置換加密，最后形成密文。第8頁，講稿共61頁，2023年5月2日，星期三DES的基本加密流程加密前，先將明文分成64bit的分組，然后將64bit二進制碼輸入到密碼器中，密碼器對輸入的64位碼首先進行初始置換，然后在64bit主密鑰產(chǎn)生的16個子密鑰控制下進行16輪乘積變換，接著再進行末置換就得到64位已加密的密文。第9頁，講稿共61頁，2023年5月2日，星期三DES算法的一般描述第10頁，講稿共61頁，2023年5月2日，星期三0.子密鑰產(chǎn)生器

密鑰（64bit）除去第8，16，…，64位，共8個校驗位置換選擇1（PC-1）Ci（28bit）Di（28bit）循環(huán)左移ti+1位循環(huán)左移ti+1位置換選擇2（PC-2）Ki（48bit）第11頁，講稿共61頁，2023年5月2日，星期三置換選擇1第12頁，講稿共61頁，2023年5月2日，星期三移位次數(shù)表第i次迭代12345678910111213141516循環(huán)左移次數(shù)1122222212222221若C1=c1c2…c28，D1=d1d2…d28則C2=c2c3…c28c1，D2=d2d3…d28d1。第13頁，講稿共61頁，2023年5月2日，星期三置換選擇2置換選擇PC-2將C中第9182225位和D中第791526位刪去，并將其余數(shù)字置換位置后送出48bit數(shù)字作為第i次迭代時所用的子密鑰kiCiDi=b1b2…b56，則ki=b14b17b11b24…b36b29b32

第14頁，講稿共61頁，2023年5月2日，星期三1.初始置換將64個明文比特的位置進行置換，得到一個亂序的64bit明文組，然后分成左右兩段，每段為32bit以L和R表示。第15頁，講稿共61頁，2023年5月2日，星期三2.乘積變換Li-1(32比特)Ri-1(32比特)選擇擴展運算E48比特寄存器子密鑰Ki(48比特)48比特寄存器選擇壓縮運算S32比特寄存器置換運算PLi(32比特)Ri(32比特)Li=Ri-1Ri=Li-1F(Ri-1,Ki)第16頁，講稿共61頁，2023年5月2日，星期三選擇擴展運算E對原第321458912131617202124252829各位重復(fù)一次得到數(shù)據(jù)擴展。1，2，…………3232123454567898910111213121314151617161718192021202122232425242526272829282930313211，2，…………48選擇擴展運算結(jié)果(48bit)E的輸入(32bit)第17頁，講稿共61頁，2023年5月2日，星期三選擇壓縮運算S將前面送來的48bit數(shù)據(jù)自左至右分成8組，每組6bit。然后并行送入8個S盒，每個S盒為一非線性代換網(wǎng)絡(luò)，有4個輸出。

第18頁，講稿共61頁，2023年5月2日，星期三S盒的內(nèi)部結(jié)構(gòu)第19頁，講稿共61頁，2023年5月2日，星期三S盒的內(nèi)部計算若輸入為b1b2b3b4b5b6其中b1b6兩位二進制數(shù)表達了0至3之間的數(shù)。b2b3b4b5為四位二進制數(shù)，表達0至15之間的某個數(shù)。在S1表中的b1b6行b2b3b4b5列找到一數(shù)m（0≤m≤15），若用二進制表示為m1m2m3m4，則m1m2m3m4便是它的4bit輸出。例如，輸入為001111，b1b6=01=1，b2b3b4b5=0111=7，即在S1盒中的第1行第7列求得數(shù)1，所以它的4bit輸出為0001。第20頁，講稿共61頁，2023年5月2日，星期三關(guān)于S盒S盒是DES的核心，也是DES算法最敏感的部分，其設(shè)計原理至今仍諱莫如深，顯得非常神秘。所有的替換都是固定的，但是又沒有明顯的理由說明為什么要這樣，有許多密碼學(xué)家擔(dān)心美國國家安全局設(shè)計S盒時隱藏了某些陷門，使得只有他們才可以破譯算法，但研究中并沒有找到弱點。第21頁，講稿共61頁，2023年5月2日，星期三置換運算P對S1至S8盒輸出的32bit數(shù)據(jù)進行坐標(biāo)變換置換P輸出的32bit數(shù)據(jù)與左邊32bit即Ri-1諸位模2相加所得到的32bit作為下一輪迭代用的右邊的數(shù)字段，并將Ri-1并行送到左邊的寄存器作為下一輪迭代用的左邊的數(shù)字段。第22頁，講稿共61頁，2023年5月2日，星期三3.逆初始置換IP-1

將16輪迭代后給出的64bit組進行置換得到輸出的密文組1，2，…………64408481656246432397471555236331386461454226230375451353216129364441252206028353431151195927342421050185826331419491757251，2，…………64密文(64bit)置換碼組(64bit)第23頁，講稿共61頁，2023年5月2日，星期三第24頁，講稿共61頁，2023年5月2日，星期三DES的解密解密算法與加密算法相同，只是子密鑰的使用次序相反。第25頁，講稿共61頁，2023年5月2日，星期三DES的安全性DES在20多年的應(yīng)用實踐中，沒有發(fā)現(xiàn)嚴(yán)重的安全缺陷，在世界范圍內(nèi)得到了廣泛的應(yīng)用，為確保信息安全做出了不可磨滅的貢獻。存在的安全弱點：密鑰較短：56位密鑰空間約為7.2*1016。1997年6月RockeVerser小組通過因特網(wǎng)利用數(shù)萬臺微機歷時4個月破譯了DES；1998年7月，EFF用一臺25萬美元的機器，歷時56小時破譯DES。存在弱密鑰：有的密鑰產(chǎn)生的16個子密鑰中有重復(fù)者?；パa對稱性：C=DES(M,K),則C’=DES(M’,K’)，其中，M’,C’,K’是M,C,K的非。第26頁，講稿共61頁，2023年5月2日，星期三DES具有良好的雪崩效應(yīng)雪崩效應(yīng)：明文或密鑰的微小改變將對密文產(chǎn)生很大的影響。特別地，明文或密鑰的某一位發(fā)生變化，會導(dǎo)致密文的很多位發(fā)生變化。DES顯示了很強的雪崩效應(yīng)兩條僅有一位不同的明文，使用相同的密鑰，僅經(jīng)過3輪迭代，所得兩段準(zhǔn)密文就有21位不同。一條明文，使用兩個僅一位不同的密鑰加密，經(jīng)過數(shù)輪變換之后，有半數(shù)的位都不相同。第27頁，講稿共61頁，2023年5月2日，星期三多重DESDES在窮舉攻擊下相對比較脆弱，因此需要用某種算法來替代它，有兩種解決方法：設(shè)計全新的算法；用DES進行多次加密，且使用多個密鑰，即多重DES。這種方法能夠保護用于DES加密的已有軟件和硬件繼續(xù)使用。第28頁，講稿共61頁，2023年5月2日，星期三二重DES(DoubleDES)給定明文P和兩個加秘密鑰k1和k2，采用DES對P進行加密E，有密文C=EK2(EK1(P))對C進行解密D，有明文P=DK1(DK2(C))EEPXCK2K1加密圖DDK2K1CXP解密圖第29頁，講稿共61頁，2023年5月2日，星期三二重DES很難抵擋住中間相遇攻擊法（Meet-in-the-MiddleAttack)C=EK2(EK1(P))從圖中可見

X=EK1(P)=DK2(C)EEPCXK1K2DDCPXK2K1加密解密第30頁，講稿共61頁，2023年5月2日，星期三

若給出一個已知的明密文對（P,C)做：對256個所有密鑰K1做對明文P的加密，得到一張密鑰對應(yīng)于密文X的一張表；類似地對256個所有可能的密鑰K2做對密文C的解密，得到相應(yīng)的“明文”X。做成一張X與K2的對應(yīng)表。比較兩個表就會得到真正使用的密鑰對K1,K2。第31頁，講稿共61頁，2023年5月2日，星期三帶有雙密鑰的三重DES

（TripleDESwithTwoKeys)Tuchman給出雙密鑰的EDE模式（加密-解密-加密）：

C=EK1(DK2(EK1(P)))……對P加密

P=DK1(EK2(DK1(C)))……對C解密這種替代DES的加密較為流行并且已被采納用于密鑰管理標(biāo)準(zhǔn)（TheKeyManagerStandardsANSX9.17和ISO8732).第32頁，講稿共61頁，2023年5月2日，星期三EDEDEDCBAPPAB

CK1K2K1K1K2K1加密圖解密圖第33頁，講稿共61頁，2023年5月2日，星期三到目前為止，還沒有人給出攻擊三重DES的有效方法。對其密鑰空間中密鑰進行蠻干搜索，那么由于空間太大為2112=5×1033，這實際上是不可行的。注意：1*.Merkle和Hellman設(shè)法創(chuàng)造一個條件，想把中間相遇攻擊（meet-in-the-middleattack）的方法用于三重DES，但目前也不太成功。2*.雖然對上述帶雙密鑰的三重DES到目前為止還沒有好的實際攻擊辦法，但人們還是放心不下，又建議使用三密鑰的三重DES，此時密鑰總長為168bits.

C=EK3(DK2(EK1(P)))第34頁，講稿共61頁，2023年5月2日，星期三高級加密標(biāo)準(zhǔn)AES

1997年1月，美國國家標(biāo)準(zhǔn)局NIST向全世界密碼學(xué)界發(fā)出征集21世紀(jì)高級加密標(biāo)準(zhǔn)（AES——AdvancedEncryptionStandard）算法的公告，并成立了AES標(biāo)準(zhǔn)工作研究室，1997年4月15日的例會制定了對AES的評估標(biāo)準(zhǔn)。第35頁，講稿共61頁，2023年5月2日，星期三AES的要求（1）AES是公開的；（2）AES為單鑰體制分組密碼；（3）AES的密鑰長度可變，可按需要增大；（4）AES適于用軟件和硬件實現(xiàn)；（5）AES可以自由地使用，或按符合美國國家標(biāo)準(zhǔn)（ANST）策略的條件使用；第36頁，講稿共61頁，2023年5月2日，星期三算法衡量條件滿足以上要求的AES算法，需按下述條件判斷優(yōu)劣a.安全性b.計算效率c.內(nèi)存要求d.使用簡便性e.靈活性。第37頁，講稿共61頁，2023年5月2日，星期三AES的評審1998年4月15日全面征集AES算法的工作結(jié)束。1998年8月20日舉行了首屆AES討論會，對涉及14個國家的密碼學(xué)家所提出的候選AES算法進行了評估和測試，初選并公布了15個被選方案，供大家公開討論。

CAST-256，RC-6，CRYPTON-128，DEAL-128，

FROG，DFC，LOKI-97，MAGENTA，

MARS，HPC,RIJNDAEL，SAFER+，

SERPENT，E-2，TWOFISH。這些算法設(shè)計思想新穎，技術(shù)水平先進，算法的強度都超過3-DES，實現(xiàn)速度快于3-DES。

第38頁，講稿共61頁，2023年5月2日，星期三AES的評審1999年8月9日NIST宣布第二輪篩選出的5個候選算法為：

MARS(C.Burwick等,IBM），RC6TM（R.Rivest等,RSALab.)，RIJNDEAL(J.Daemen,比)，SERPENT(R.Anderson等，英、以、挪威)，TWOFISH(B.Schiener)。2000年10月2日，NIST宣布Rijndael作為新的AES第39頁，講稿共61頁，2023年5月2日，星期三AES加密數(shù)學(xué)基礎(chǔ)群:是一個代數(shù)系統(tǒng)，它由一個非空集合組成，在集合上定義了一個二元運算，其滿足：封閉性：對任意的，；結(jié)合律：對任何的，有；單位元：存在一個元素(稱為單位元)，對任意元素有：；逆元：對任意，存在一個元素(稱為逆元)，使得。記作：

第40頁，講稿共61頁，2023年5月2日，星期三交換群與有限群若群還滿足交換律，即對任何，有：，則稱為交換群(或加法群，阿貝爾群等)。若集合G中只含有有限多個元素，則我們稱為有限群，此時，把集合G中元素的個數(shù)稱為有限群的階。第41頁，講稿共61頁，2023年5月2日，星期三群的性質(zhì)群中的單位元是惟一的；消去律成立，即對任意的：如果，則如果，則群中的每一元素的逆元是惟一的。第42頁，講稿共61頁，2023年5月2日，星期三域域是一個代數(shù)系統(tǒng)，它由一個(至少包含兩個元素的)非空集合F組成，在集合F上定義有兩個二元運算：加法與乘法，并滿足下面條件：

F的元素關(guān)于加法成交換群，記其單位元為“0”(稱為域的零元)F關(guān)于乘法成交換群，記其單位元為“1”(稱其為域的單位元)

乘法在加法上滿足分配律，即記為

第43頁，講稿共61頁，2023年5月2日，星期三有限域若集合F只包含有限個元素，則稱這個域F為有限域。有限域中元素的個數(shù)稱為該有限域的階。若有一任意的素數(shù)P和正整數(shù)，存在階有限域，這個有限域記為。當(dāng)n=1時，有限域稱為素域。第44頁，講稿共61頁，2023年5月2日，星期三GF(28)域上的多項式表示及運算一個字節(jié)的元素的二進制展開成的多項式系數(shù)為：例如，上的“37”(為十六進制)，其二進制為“00110111”，對應(yīng)多項式為：第45頁，講稿共61頁，2023年5月2日，星期三GF(28)4域上的多項式表示及運算一個四個字節(jié)的字(有32比特位)可以看作是域上的多項式，每個字對應(yīng)于一個次數(shù)小于4的多項式。

兩個域上的元素相加時，將這兩個元素對應(yīng)多項式系數(shù)相加即得到結(jié)果，相加時采用比特異或來實現(xiàn)。兩個域上的元素相乘時，要將結(jié)果對一個特定的多項式取模，以使相乘后的結(jié)果還是一個4字節(jié)的向量。

第46頁，講稿共61頁，2023年5月2日，星期三AES加密算法的具體實現(xiàn)AES每輪要經(jīng)過四次變換，分別是

字節(jié)代換運算(SubByte())ShiftRows()(行移位)變換MixColumns()（列混合）變換AddRoundKey()(輪密鑰的混合)變換

我們用的128bit的密鑰（循環(huán)次數(shù)為10），那么每次加密的分組長為128bit，16個字節(jié)，每次從明文中按順序取出16個字節(jié)假設(shè)為a0a1a2a3a4a5a6a7a8a9a10a11a12a13a14a15，這16個字節(jié)在進行變換前先放到一個4×4的矩陣中。如下頁圖所示：第47頁，講稿共61頁，2023年5月2日，星期三a0a4a8a12a1a5a9a13a2a6a10a14a3a7a11a15這個矩陣稱為狀態(tài)（state）

以后所有的變換都是基于這個矩陣進行的，到此，準(zhǔn)備工作已經(jīng)完成?，F(xiàn)在按照前面的順序進行加密變換，首先開始第一次循環(huán)的第一個變換：字節(jié)代換(SubByte())。第48頁，講稿共61頁，2023年5月2日，星期三字節(jié)代換(SubByte())

a0a4a8a12a1a5a9a13a2a6a10a14a3a7a11a15s00s01s02s03s10s11s12s13s20s21s22s23s30s31s32s33out0out4out8out12out1out5out9out13out2out6out10out14out3out7out11out15查表第49頁，講稿共61頁，2023年5月2日，星期三字節(jié)代換-S盒變換(查表)S12={53},則X=5,Y=3,out9=ed第50頁，講稿共61頁，2023年5月2日，星期三ShiftRows()(行移位)變換s00s01s02s03s10s11s12s13s20s21s22s23s30s31s32s33s00s01s02s03s11s12s13s10s22s23s20s21s33s30s31s32行變換示意圖SS′第51頁，講稿共61頁，2023年5月2日，星期三MixColumns()（列混合）變換S’0cS’1cS’2cS’3cS0cS1cS2cS3c02030101010203010101020303010102

S’0c＝({02}●S0c)⊕({03}●S1c)⊕S2c⊕S3c，但這個結(jié)果可能會超出一個字節(jié)的存儲范圍，所以實際上還要對結(jié)果進行處理。第52頁，講稿共61頁，2023年5月2日，星期三3.4序列密碼(流密碼)“一次一密”密碼在理論上是不可攻破的。流密碼則由“一次一密”密碼啟發(fā)而來。流密碼目前的理論已經(jīng)比較成熟，工程實現(xiàn)也比較容易，加密效率高，在許多重要領(lǐng)域得到應(yīng)用?！耙淮我幻堋泵艽a使用的密鑰是和明文一樣長的隨機序列，密鑰越長越安全，但長密鑰的存儲、分配都很困難。第53頁，講稿共61頁，2023年5月2日，星期三流密碼的密鑰流流密碼的關(guān)鍵就是產(chǎn)生密鑰流的算法，該算法必須能夠產(chǎn)生可變長的、隨機的、不可預(yù)測的密鑰流。保持通信雙方的精確同步是流密碼實際應(yīng)用中的關(guān)鍵技術(shù)。由于通信雙方必須能夠產(chǎn)生相同的密鑰流，所以這種密鑰流不可能是真隨機序列，只能是偽隨機流。明文流密文流密鑰流第54頁，講稿共61頁，2023年5月2日，星期三流密碼的結(jié)構(gòu)典型的流密碼每次加密一位或一個字節(jié)明文。將初始密鑰(種子)輸入到發(fā)生器，輸出一個隨機數(shù)(密鑰)。偽隨機字節(jié)發(fā)生器(密鑰流發(fā)生器)明文字節(jié)流M密文字節(jié)流C密鑰Kk異或加密偽隨機字節(jié)發(fā)生器(密鑰流發(fā)生器)密鑰Kk異或解密明文字節(jié)流M11001100明文01101100密鑰流10100000密文第55頁，講稿共61頁，2023年5月2日，星期三設(shè)計流密碼需要考慮的因素密鑰流的周期要長。偽隨機數(shù)發(fā)生器產(chǎn)生的并非完全隨機的序列，它是一個產(chǎn)生確定的比特流的函數(shù)，該比特流最終將產(chǎn)生