密碼學(xué)原理與實(shí)踐第二版課件

2023/7/1第2章對(duì)稱密鑰密碼體系理解密碼學(xué)的基本原理掌握DES加密算法了解A5和IDEA加密算法理解序列密碼原理2023/7/12.1密碼體制原理與分類(I)加密解密明文P密文C明文P加密密鑰Ke解密密鑰KdC=E(Ke,P)P=D(Kd,E(Ke,P)對(duì)稱密碼體制(symmetriccryptosystem)-單鑰加密密鑰和解密密鑰是相同的非對(duì)稱密碼體制(asymmetriccryptosystem)-公鑰密碼加密密鑰和解密密鑰是成對(duì)出現(xiàn)加密過(guò)程和解密過(guò)程不同，使用的密鑰也不同2023/7/1密碼算法安全準(zhǔn)則與分類密碼的安全性原則公開(kāi)的密碼算法才是安全的，保密的算法只在小范圍內(nèi)設(shè)計(jì)和研究。按照密鑰使用方法分對(duì)稱密碼算法(symmetriccipher)：又稱傳統(tǒng)密碼算法(conventionalcipher)或秘密密鑰算法、單密鑰算法。非對(duì)稱密鑰算法(asymmetriccipher)，又稱公開(kāi)密鑰算法(public-Keycipher)。按照明文的處理方法分分組密碼(blockcipher)：將明文分成固定長(zhǎng)度的組，用同一密鑰和算法對(duì)每一塊加密，輸出也是固定長(zhǎng)度的密文。流密碼(streamcipher)：又稱序列密碼，每次加密一位或一字節(jié)的明文。

2023/7/12.1.4密碼分析可破譯密碼當(dāng)給予足夠的時(shí)間和計(jì)算資源的時(shí)候，破譯者能確定的加密算法。對(duì)可破譯性的評(píng)估基于當(dāng)前的技術(shù)。窮舉攻擊攻擊者對(duì)一條密文嘗試所有可能的密鑰，直到得到有意義的明文。Kerckhoff原則：加密算法應(yīng)建立在算法的公開(kāi)不影響明文和密鑰的安全的基礎(chǔ)上。這一原則得到普遍承認(rèn)，成為判定密碼強(qiáng)度的衡量標(biāo)準(zhǔn)，實(shí)際上也成為古典密碼和現(xiàn)代密碼的分界線。2023/7/1攻擊類型密碼分析者已知的信息唯密文攻擊加密算法；要解密的密文已知明文攻擊加密算法；要解密的密文；用(與待解密文)同一密鑰加密的多個(gè)明密文對(duì)選擇明文攻擊加密算法；要解密的密文；分析者任選明文，并用(與待解密文)同一密鑰加密的密文選擇密文攻擊加密算法；要解密的密文；分析者有目的選擇密文，并用(與待解密文)同一密鑰解密的對(duì)應(yīng)明文選擇文本攻擊加密算法；要解密的密文；分析者任選明文，并用(與待解密文)同一密鑰加密的密文；分析者有目的選擇密文，并用(與待解密文)同一密鑰解密的對(duì)于明文傳統(tǒng)密碼體制基于加密信息的攻擊類型2023/7/1密碼的安全性與攻擊復(fù)雜性無(wú)條件安全(Unconditionallysecure)無(wú)論破譯者有多少密文,他也無(wú)法解出對(duì)應(yīng)的明文,即使他解出了,他也無(wú)法驗(yàn)證結(jié)果的正確性.一次一密計(jì)算上安全的破譯密碼的代價(jià)超出密文信息的價(jià)值破譯密碼的時(shí)間超出密文信息的有效生命期攻擊復(fù)雜性：數(shù)據(jù)時(shí)間存儲(chǔ)量2023/7/1古典密碼古典密碼的加密方法一般是文字置換，使用手工或機(jī)械變換的方式實(shí)現(xiàn)。古典密碼系統(tǒng)已經(jīng)初步體現(xiàn)出近代密碼系統(tǒng)的雛形，它比古代加密方法復(fù)雜，其變化較小。單表代替密碼：Caesar密碼；多表代替密碼：Vigenere密碼、Hill密碼；轉(zhuǎn)輪密碼：二戰(zhàn)中的Enigma。2023/7/1現(xiàn)代密碼計(jì)算機(jī)的發(fā)展使得基于復(fù)雜計(jì)算的密碼成為可能，密碼學(xué)成為一門新的學(xué)科。對(duì)稱密鑰密碼算法的發(fā)展：1977年DES正式成為標(biāo)準(zhǔn)1977年公鑰密碼(非對(duì)稱密碼）出現(xiàn)90年代逐步出現(xiàn)橢圓曲線等其他公鑰算法一些新的密碼技術(shù)，如，混沌密碼、量子密碼等2023/7/1愷撒密碼的破譯分析一般的愷撒密碼加密：ci=E(pi)=(pi+k)mod26解密：pi=E(ci)=(ci-k)mod26其中k為密鑰，1k25一般的愷撒密碼的破譯分析已知加密和解密算法需要測(cè)試的密鑰只有25個(gè)明文所用的語(yǔ)言是已知的，且其意義易于識(shí)別?？梢圆捎酶F舉攻擊2023/7/1代換密碼substitutioncipherABCDEFGHIJKLMNOPQRSTUVWXYZwordABCEFGHIJKLMNPQRSTUVXYZ2023/7/1置換密碼置換密碼體制1.61.明文與密文字母不變，利用轉(zhuǎn)換打亂明文字母的位置和次序。存儲(chǔ)空間與報(bào)文長(zhǎng)度相關(guān)。2.完全保留字符的統(tǒng)計(jì)信息3.使用多輪加密可提高安全性2023/7/12.2數(shù)據(jù)加密標(biāo)準(zhǔn)(DES)

2.2.1DES算法

DES加密算法如圖2-3所示，由以下四個(gè)部分組成。2023/7/11.初始置換函數(shù)IPDES對(duì)64位明文分組進(jìn)行操作。首先，64位明文分組x經(jīng)過(guò)一個(gè)初始置換函數(shù)IP，產(chǎn)生64位的輸出x0，再將分組x0分成左半部分L0和右半部分R0，即：

x0=IP(x)=L0R0置換表如表2-1所示。此表順序?yàn)閺纳系较拢瑥淖笾劣?。如初始置換把明文的第58位換至第1位，把第50位換至第二位，以此類推。2023/7/1表2-1初始置換IP585042342618102605244362820124625446383022146645648403224168574941332517915951433527191136153453729211356355473931231572023/7/1圖2-5DES加密算法2023/7/1

2．獲取子密鑰Ki

DES加密算法的密鑰長(zhǎng)度為56位，但一般表示為64位，其中，每個(gè)第8位用于奇偶校驗(yàn)。在DES加密算法中，將用戶提供的64位初始密鑰經(jīng)過(guò)一系列的處理得到K1，K2，…，K16，分別作為1～16輪運(yùn)算的16個(gè)子密鑰?，F(xiàn)在來(lái)看如何獲得這16個(gè)子密鑰。首先，將64位密鑰去掉8個(gè)校驗(yàn)位，用密鑰置換PC–1置換剩下的56位密鑰；再將56位分成前28位C0和后28位D0兩部分，即PC–1(K56)=C0D0。密鑰置換PC-1如表2-2所示。2023/7/1表2-2密鑰置換PC–157494133251791585042342618102595143352719113605244366355473931231576254463830221466153453729211352820124

2023/7/1

接下來(lái)，根據(jù)輪數(shù)，這兩部分分別循環(huán)左移1位或2位。具體每輪移位的位數(shù)如表2-3所示。表2-3每輪移動(dòng)的位數(shù)輪次12345678910111213141516位數(shù)11222222122222212023/7/1

移動(dòng)后，將兩部分合并成56位后通過(guò)壓縮置換PC–2后得到48位子密鑰，即Ki=PC-2(CiDi)。壓縮置換如表2-4所示。表2-4壓縮置換PC–214171124153281562110231912426816727201324152313747553040514533484449395634534642503629329,18?2023/7/1圖2-6子密鑰產(chǎn)生2023/7/13．密碼函數(shù)F1)函數(shù)F的操作步驟密碼函數(shù)F的輸入是32比特?cái)?shù)據(jù)和48比特的子密鑰，其操作步驟如圖2-5所示。(1)擴(kuò)展置換(E)。將數(shù)據(jù)的右半部分Ri從32位擴(kuò)展為48位。位選擇函數(shù)(也稱E盒)如表2-5所示。2023/7/1圖2-7F(Ri,Ki)計(jì)算2023/7/1表2-5擴(kuò)展置換(E)32123

4

54

5678

989101112131213141516171617

18192021202122232425242526272829282930313212023/7/1(2)異或。擴(kuò)展后的48位輸出E(Ri)與壓縮后的48位密鑰Ki作異或運(yùn)算。

(3)S盒替代。將異或得到的48位結(jié)果分成八個(gè)6位的塊，每一塊通過(guò)對(duì)應(yīng)的一個(gè)S盒產(chǎn)生一個(gè)4位的輸出。八個(gè)S盒如表2-6所示。2023/7/1

S盒的具體置換過(guò)程為：某個(gè)Si盒的6位輸入的第1位和第6位形成一個(gè)2位的二進(jìn)制數(shù)(從0～3)，對(duì)應(yīng)表中的某一行；同時(shí)，輸入的中間4位構(gòu)成4位二進(jìn)制數(shù)(從0～15)對(duì)應(yīng)表中的某一列(注意：行和列均從0開(kāi)始計(jì)數(shù))。例如，第8個(gè)S盒的輸入為001011，前后2位形成的二進(jìn)制數(shù)為01，對(duì)應(yīng)第8個(gè)S盒的第1行；中間4位為0101，對(duì)應(yīng)同一S盒的第5列。從表2-6中可得S8盒的第1行第5列的數(shù)為3，于是就用0011代替原輸入001011。

2023/7/1表2-6S盒S1盒1441312151183106125907015741421311061211953841148136211151297310501512824917511314100613S2盒15181461134972131205103134715281412011069115014711104131581269321513810131542116712051492023/7/1S3盒1009146315511312711428137093461028514121115113649815301112125101471101306987415143115212S4盒7131430691012851112415138115615034721211014910690121171315131452843150610113894511127214S5盒21241710116853151301491411212471315015103986421111013781591256301411812711421361509104532023/7/1S6盒1211015926801334147511101542712956113140113891415528123704101131164321295151011141760813S7盒4112141508133129751061130117491101435122158614111312371410156805926111381410795015142312S8盒13284615111109314501271151381037412561101492711419121420610131535821147410813151290356112023/7/1

(4)P盒置換。將八個(gè)S盒的輸出連在一起生成一個(gè)32位的輸出，輸出結(jié)果再通過(guò)置換P產(chǎn)生一個(gè)32位的輸出即：F(Ri,Ki)。表2-7為P盒置換。至此，密碼函數(shù)F的操作就完成了。最后，將P盒置換的結(jié)果與最初的64位分組的左半部分異或，然后左、右半部分交換，接著開(kāi)始下一輪計(jì)算。2023/7/1表2-7P盒置換16720212912281711523265183110282414322739191330622114252023/7/1

2)函數(shù)F的設(shè)計(jì)

函數(shù)F是DES加密的核心，它依賴于S盒的設(shè)計(jì)。這也適用于其它的對(duì)稱分組加密算法。下面我們簡(jiǎn)單討論一下有關(guān)F函數(shù)的一些通用設(shè)計(jì)準(zhǔn)則以及S盒設(shè)計(jì)問(wèn)題。

(1)F的設(shè)計(jì)準(zhǔn)則。函數(shù)F的基本功能就是“擾亂(confusion)”輸入，因此，對(duì)于F來(lái)說(shuō)，其非線性越高越好，也就是說(shuō)，要恢復(fù)F所做的“擾亂”操作越難越好。2023/7/1

其它的設(shè)計(jì)準(zhǔn)則還包括嚴(yán)格雪崩準(zhǔn)則(SAC)和比特獨(dú)立準(zhǔn)則(BIC)

。所謂SAC，就是要求算法具有良好的雪崩效應(yīng)，輸入當(dāng)中的一個(gè)比特發(fā)生變化都應(yīng)當(dāng)使輸出產(chǎn)生”盡可能多”

的比特變化。嚴(yán)格地說(shuō)，就是當(dāng)任何單個(gè)輸入比特位i發(fā)生變換時(shí)，一個(gè)S盒的第j比特輸出位發(fā)生變換的概率應(yīng)為1/2，且對(duì)任意的i,j都應(yīng)成立。

BIC的意思是當(dāng)單個(gè)輸入比特位i發(fā)生變化時(shí)，輸出比特位j,k的變化應(yīng)當(dāng)互相獨(dú)立，且對(duì)任意的i,j,k均應(yīng)成立。

SAC和BIC可以有效的增強(qiáng)F函數(shù)的“擾亂”功能。2023/7/1

(2)S盒設(shè)計(jì)。S盒的設(shè)計(jì)在對(duì)稱分組密碼研究領(lǐng)域中起著舉足輕重的作用。本質(zhì)上，S盒的作用就是對(duì)輸入向量進(jìn)行處理，使得輸出看起來(lái)更具隨機(jī)性，輸入和輸出之間應(yīng)當(dāng)是非線性的，很難用線性函數(shù)來(lái)逼近。顯然，S盒的尺寸是一個(gè)很重要的特性。一個(gè)S盒其輸入為n比特，輸出為m比特。DES的S盒大小為6×4。S盒越大，就越容易抵制差分和線性密碼分析。2023/7/1Mister和Adams提出了很多的S盒設(shè)計(jì)原則，其中包括要求S盒滿足SAC和BIC的原則，以及S盒的所有列的全部線性組合應(yīng)當(dāng)滿足一類稱為bent函數(shù)的高度非線性布爾函數(shù)的原則。Bent函數(shù)具有很多有趣的特性，其中，高度非線性和最高階的嚴(yán)格雪崩準(zhǔn)則對(duì)于S盒的設(shè)計(jì)尤為重要。2023/7/1

Nyberg提出了以下幾種S盒的設(shè)計(jì)和實(shí)踐原則：●隨機(jī)性：采用某些偽隨機(jī)數(shù)發(fā)生器或隨機(jī)數(shù)表格來(lái)產(chǎn)生S盒的各個(gè)項(xiàng)?！耠S機(jī)測(cè)試：隨機(jī)選擇S盒各個(gè)項(xiàng)，然后按照不同準(zhǔn)則測(cè)試其結(jié)果?！駭?shù)學(xué)構(gòu)造：根據(jù)某些數(shù)學(xué)原理來(lái)產(chǎn)生S盒。其好處就是可以根據(jù)數(shù)學(xué)上的嚴(yán)格證明來(lái)抵御差分和線性密碼分析，并且可以獲得很好的擴(kuò)散(Diffusion)特性。2023/7/1

4．末置換函數(shù)IP-1

末置換是初始置換的逆變換。對(duì)L0和R0進(jìn)行16輪相同的運(yùn)算后，將得到的兩部分?jǐn)?shù)據(jù)合在一起，經(jīng)過(guò)一個(gè)末置換函數(shù)就可得到64位的密文c，即：

c=IP-1(R16L16)（16指的是16輪）表2-8列出了該變換。2023/7/1表2-8末置換IP-1408481656246432397471555236331386461454226230375451353216129364441252206028353431151195927342421050185826331419491757252023/7/15．總結(jié)根據(jù)上面所述，可以將DES算法歸結(jié)如下：子密鑰生成：

C[0]D[0]=PC–1(K)for1<=i<=16{C[i]=LS[i](C[i?1])D[i]=LS[i](D[i?1])K[i]=PC–2(C[i]D[i])}2023/7/1加密過(guò)程：L[0]R[0]=IP(x)