密碼學(xué)基礎(chǔ)課件：第七講 對(duì)稱密碼學(xué)

1、第七講 對(duì)稱密碼學(xué)-2DES三重DESFeistel網(wǎng)絡(luò)DES ，算法 算法：分組長度為64 bits (8 bytes)，密文分組長度也是64 bits。密鑰長度為64 bits，有8 bits奇偶校驗(yàn)，有效密鑰長度為56 bits。算法主要包括：初始置換IP、16輪迭代的乘積變換、逆初始置換IP-1以及16個(gè)子密鑰產(chǎn)生器。 初始置換IP：將64 bit明文的位置進(jìn)行置換，得到一個(gè)亂序的64 bit明文組，而后分成左右兩段，每段為32 bit，以L0和R0表示，IP中各列元素位置號(hào)數(shù)相差為8，相當(dāng)于將原明文各字節(jié)按列寫出，各列比特經(jīng)過偶采樣和奇采樣置換后，再對(duì)各行進(jìn)行逆序。將陣中元素按行讀出

2、構(gòu)成置換輸出。 逆初始置換IP-1。將16輪迭代后給出的64 bit組進(jìn)行置換，得到輸出的密文組。輸出為陣中元素按行讀得的結(jié)果。DES ，算法 輸入 64 bit明文數(shù)據(jù) 初始置換IP 乘積變換 （16輪迭代） 逆初始置換IP-1 64 bit密文數(shù)據(jù) 輸出標(biāo)準(zhǔn)數(shù)據(jù)加密算法DES ，算法 IP和IP-1在密碼意義上作用不大，因?yàn)檩斎虢Mx與其輸出組y=IP(x) (或IP-1(x)是已知的一一對(duì)應(yīng)關(guān)系。IP置換是為了把明文按奇數(shù)位和偶數(shù)位劃分為兩部分，然后進(jìn)行Feistel。IP逆置換是為了解密方便。 乘積變換。它是DES算法的核心部分。將經(jīng)過IP置換后的數(shù)據(jù)分成32 bit的左右兩組，在迭代過

3、程中彼此左右交換位置。每次迭代時(shí)只對(duì)右邊的32 bit進(jìn)行一系列的加密變換，在此輪迭代即將結(jié)束時(shí)，把左邊的32 bit與右邊得到的32 bit逐位模2相加，作為下一輪迭代時(shí)右邊的段，并將原來右邊未經(jīng)變換的段直接送到左邊的寄存器中作為下一輪迭代時(shí)左邊的段。在每一輪迭代時(shí)，右邊的段要經(jīng)過選擇擴(kuò)展運(yùn)算E、密鑰加密運(yùn)算、選擇壓縮運(yùn)算S、置換運(yùn)算P和左右混合運(yùn)算。初始置換IP和初始逆置換IP1 Li-1(32bit) Ri-1(32bit) 選擇擴(kuò)展運(yùn)算 E 48 bit寄存器 按bit模2加密 48 bit寄存器 選擇壓縮運(yùn)算 S 32 bit寄存器 置換運(yùn)算 P 按bit模2和 Li (32bit)

4、 Ri (32bit)乘積變換框圖密鑰產(chǎn)生器DES ，算法 選擇擴(kuò)展運(yùn)算E。將輸入的32 bit Ri-1擴(kuò)展成48 bit的輸出，其變換表在下面給出。令s表示E原輸入數(shù)據(jù)比特的原下標(biāo)，則E的輸出是將原下標(biāo)s0或1(mod 4)的各比特重復(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ò)展。將表中數(shù)據(jù)按行讀出得到48 bit輸出。 密鑰加密運(yùn)算。將子密鑰產(chǎn)生器輸出的48 bit子密鑰ki與選擇擴(kuò)展運(yùn)算E輸出的48 bits數(shù)據(jù)按位模2相加。 選擇壓縮運(yùn)算S。將前面送來的48 bit數(shù)

5、據(jù)自左至右分成8組，每組為6 bit。而后并行送入8個(gè)S一盒，每個(gè)S盒為一非線性代換網(wǎng)絡(luò)，有4個(gè)輸出。 選擇擴(kuò)展運(yùn)算32 | 01 02 03 04 | 0504 | 05 06 07 08 | 0908 | 09 10 11 12 | 1312 | 13 14 15 16 | 1716 | 17 18 19 20 | 2120 | 21 22 23 24 | 2524 | 25 26 27 28 | 2928 | 29 30 31 32 | 01DES ，算法 6 bit 選擇函數(shù)組 4 bit 選擇壓縮運(yùn)算S 48 bit 寄存器32 bit 寄存器S1S2S3S4S5S6S7S8DES

6、子密鑰產(chǎn)生器 將64 bit初始密鑰經(jīng)過置換選擇PC1、循環(huán)移位置換、置換選擇PC2給出每次迭代加密用的子密鑰ki。在64 bit初始密鑰中有8位為校驗(yàn)位，其位置號(hào)為8、16、32、48、56和64。其余56位為有效位，用于子密鑰計(jì)算。將這56位送入置換選擇PC1。經(jīng)過坐標(biāo)置換后分成兩組，每級(jí)為28 bit，分別送入C寄存器和D寄存器中。在各次迭代中，C和D寄存器分別將存數(shù)進(jìn)行左循環(huán)移位置換，移位次數(shù)已規(guī)定好。每次移位后，將C和D寄存器原存數(shù)送給置換選擇PC2。置換選擇PC2將C中第9、18、22、25位和D中第7、9、15、26位刪去，并將其余數(shù)字置換位置后送出48 bit數(shù)字作為第i次迭代

7、時(shí)所用的子密鑰ki。子密鑰的產(chǎn)生置換選擇1（PC-1）和置換選擇2（PC-2） 圖 4-2-7S-Box對(duì)每個(gè)盒，6比特輸入中的第1和第6比特組成的二進(jìn)制數(shù)確定的行，中間4位二進(jìn)制數(shù)用來確定的列。中相應(yīng)行、列位置的十進(jìn)制數(shù)的4位二進(jìn)制數(shù)表示作為輸出。例如輸入為101001，則行數(shù)和列數(shù)的二進(jìn)制表示分別是11和0100，即第3行和第4列，的第3行和第4列的十進(jìn)制數(shù)為3，用4位二進(jìn)制數(shù)表示為0011，所以的輸出為0011。 DES ，算法加密過程:運(yùn)算進(jìn)行16次后就得到密文組。 L0R0 IP(64 bit 輸入碼) LiRi-1 i=1,., 16 RiLi-1f(Ri-1, ki) i=1,.

8、 , 16 64 bit密文IP-1 (R16L16)解密過程:DES的加密運(yùn)算是可逆的，其解密過程可類似地進(jìn)行。 R16L16 IP(64 bit密文) Ri-1 Li i=16,. , 1 Li-1Rif(Li-1, ki) i=16,., 1 64 bit明文IP-1 (R0L0) DES安全性 DES的密鑰量為256=7.21016= 72 057 594 037 927 9361017個(gè)。若要對(duì)DES進(jìn)行密鑰搜索破譯，分析者在得到一組明文-密文對(duì)條件下，可對(duì)明文用不同的密鑰加密，直到得到的密文與已知的明文-密文對(duì)中的相符，就可確定所用的密鑰了。密鑰搜索所需的時(shí)間取決于密鑰空間的大小和

9、執(zhí)行一次加密所需的時(shí)間。若假定DES加密操作需時(shí)為100s(一般微處理器能實(shí)現(xiàn))，則搜索整個(gè)密鑰空間需時(shí)為7.21015秒，近似為2.28108年。若以最快的LSI器件，DES加密操作時(shí)間可降到5s，也要1.1104年才能窮盡密鑰。但是由于差分和線性攻擊法的出現(xiàn)以及計(jì)算技術(shù)的發(fā)展，按Wiener介紹，在1993年破譯DES的費(fèi)用為100萬美元，需時(shí)3個(gè)半小時(shí)。如果將密鑰加大到80 bits，采用這類搜索機(jī)找出一個(gè)密鑰所需的時(shí)間約為6700年。 DES ，安全性 1997年1月28日，美國的RSA數(shù)據(jù)安全公司在RSA安全年會(huì)上公布了一項(xiàng)“秘密密鑰挑戰(zhàn)”競(jìng)賽，其中包括懸賞1萬美元破譯密鑰長度為56

10、比特的DES。美國克羅拉多洲的程序員Verser從1997年2月18日起，用了96天時(shí)間，在Internet上數(shù)萬名志愿者的協(xié)同工作下，成功地找到了DES的密鑰，贏得了懸賞的1萬美元。1998年7月電子前沿基金會(huì)（EFF）使用一臺(tái)25萬美圓的電腦在56小時(shí)內(nèi)破譯了56比特密鑰的DES。1999年1月RSA數(shù)據(jù)安全會(huì)議期間，電子前沿基金會(huì)用22小時(shí)15分鐘就宣告破解了一個(gè)DES的密鑰。 雙密鑰的三重DES（Triple DES with Two Keys)C=EK1(DK2(EK1(P) P=DK1(EK2( DK1(C)對(duì)雙密鑰的三重DES的分析該模式由IBM設(shè)計(jì), 可與常規(guī)加密算法兼容這種替

11、代DES的加密較為流行并且已被采納用于密鑰管理標(biāo)準(zhǔn)（The Key Manager Standards ANSX9.17和ISO8732).交替使用K1和K2可以抵抗中間相遇攻擊.如果C=EK2(EK1(P) ,在已知明文攻擊下，只需要256+1次加解密到目前為止，還沒有人給出攻擊三重DES的有效方法。對(duì)其密鑰空間中密鑰進(jìn)行蠻干搜索，那么由于空間太大為2112=51033，這實(shí)際上是不可行的。若用差分攻擊的方法，相對(duì)于單一DES來說復(fù)雜性以指數(shù)形式增長，要超過1052。DES 實(shí)現(xiàn)一撇我們知道swap操作可以使用異或操作完成x=xy; y=xy; x=xy1: x=xy; y2:x=xy; y

12、=(xy)y=x3:x=(xy)(x)=y或者t=xy; y=ty; x=xt那么swap and move操作可以這樣完成DES 實(shí)現(xiàn)一撇swap and movet=(xsize)yy=ytx=x(t2對(duì)應(yīng)0 0 16 1718 19 20 1222 23 24 2526 27 28 29DES 實(shí)現(xiàn)一撇t=r2l對(duì)應(yīng)t =00 10 216 317 418 519 620 721 822 923 1024 1125 1226 1327 1428 1529此時(shí)對(duì)t進(jìn)行mask,t=t&0 x3333，得到DES 實(shí)現(xiàn)一撇t =0 0 216 317 0 0 620 721 0 0 1024 1125 0 0 1428 1529此時(shí)進(jìn)行l(wèi)=lt，得到l =0 1 16 17 r = 16 17 18 19 4 5 20 21 20 21 22 23 8 9 24 25 24 25 26 27 12 13 28 29 28 29 30 31DES 實(shí)現(xiàn)一撇再進(jìn)行r=r(t2)得到l