《網(wǎng)絡(luò)信息安全》課件第2章

第2章密碼技術(shù)2.1密碼學(xué)基本概念2.2古典密碼2.3對(duì)稱密碼2.4公鑰密碼2.5消息驗(yàn)證和數(shù)字簽名

習(xí)題

2.1密碼學(xué)基本概念

密碼學(xué)是研究如何實(shí)現(xiàn)數(shù)據(jù)加密的學(xué)科，密碼學(xué)包括兩方面內(nèi)容，即密碼編碼學(xué)和密碼分析學(xué)。將數(shù)據(jù)保密的技術(shù)和科學(xué)叫做密碼編碼學(xué)，與此對(duì)應(yīng)的是破譯密文的技術(shù)和科學(xué)叫做密碼分析學(xué)。

假設(shè)發(fā)送者Alice想安全地發(fā)送消息m給接收者Bob，利用加密技術(shù)的通信過(guò)程如圖2-1所示。由于竊聽者Eve只能看到加密后的密文信息故不能知道消息m的內(nèi)容。其中，消息m被稱為明文(plaintext)。對(duì)需要保密的消息進(jìn)行編碼的過(guò)程稱為加密，編碼的規(guī)則稱為加密算法，被加密的消息稱為密文(ciphertext)，而把密文轉(zhuǎn)變?yōu)槊魑牡倪^(guò)程稱為解密，解密的規(guī)則稱為解密算法。

圖2-1加密和解密

密碼算法是用于加密和解密的數(shù)學(xué)函數(shù)，如果密碼算法的保密性是基于算法的保密，這種算法稱為受限制的算法，這種算法具有歷史意義，但按照現(xiàn)在的安全標(biāo)準(zhǔn)，它們的保密性已遠(yuǎn)遠(yuǎn)不夠，現(xiàn)代密碼學(xué)采用密鑰來(lái)解決這個(gè)問(wèn)題，密鑰用K來(lái)表示(如圖2-2所示)。加密算法和解密算法通常在一對(duì)密鑰(K)的控制下進(jìn)行，分別稱為加密密鑰和解密密鑰。

圖2-2有密鑰的加密和解密

一個(gè)現(xiàn)代密碼系統(tǒng)(體制)包括所有可能的明文、密文、密鑰、加密算法和解密算法，所有這些算法的安全性都基于密鑰的安全性，而不是基于算法的細(xì)節(jié)的安全性。這就意味著算法可以公開，即使竊聽者知道你的算法也沒(méi)有關(guān)系，如果他不知道你使用的具體密鑰，就不可能閱讀到你的消息。密碼系統(tǒng)根據(jù)密鑰可以分為兩類，即為對(duì)稱密鑰系統(tǒng)和公鑰系統(tǒng)。對(duì)稱密鑰系統(tǒng)就是加密密鑰能夠從解密密鑰中推算出來(lái)，反過(guò)來(lái)也成立。在大多數(shù)對(duì)稱算法中，加/解密密鑰是相同的。公鑰系統(tǒng)又稱公開密鑰系統(tǒng)或非對(duì)稱密鑰系統(tǒng)，有兩個(gè)密鑰，一個(gè)是公開的，用K1表示，誰(shuí)都可以使用，也叫加密密鑰；另一個(gè)是私人密鑰，用K2來(lái)表示，只能由采用此系統(tǒng)的人自己掌握，也叫解密密鑰。從公開的密鑰推不出私人密鑰。

數(shù)據(jù)加密算法有很多種，密碼算法標(biāo)準(zhǔn)化是信息化社會(huì)發(fā)展的必然趨勢(shì)，是世界各國(guó)保密通信領(lǐng)域的一個(gè)重要課題。按照發(fā)展進(jìn)程來(lái)分，經(jīng)歷了古典密碼、對(duì)稱密鑰密碼和公開密鑰密碼階段。古典密碼算法有替代加密、置換加密；對(duì)稱加密算法包括DES和AES；非對(duì)稱加密算法包括RSA等。目前在數(shù)據(jù)通信中使用最普遍的算法有DES算法、RSA算法和PGP算法等。

2.2古

典

密

碼

1．代替密碼

(1)單表代替密碼又可以稱為單字母密碼：就是明文的一個(gè)字符用相應(yīng)的一個(gè)密文字符代替。著名的愷撒密碼就是一種簡(jiǎn)單的代替密碼。其加密原理就是每一個(gè)明文字符都由其右邊第3個(gè)字符代替，那么3就是這個(gè)算法的密鑰，即A由D代替，B由E代替，…，W由Z代替，X由A代替，Y由B代替，Z由C代替。若明文為student，則對(duì)應(yīng)的密文為VWXGHQW(此時(shí)密鑰為3)。愷撒密碼僅有26個(gè)可能的密鑰，非常的不安全。

由于英文字母中各字母出現(xiàn)的頻率有明顯的固有特征，而單表代替密碼沒(méi)有把明文中的不同字母的出現(xiàn)頻率掩蓋起來(lái)，因此根據(jù)字母頻率表可以很容易對(duì)替換密碼進(jìn)行破譯。代替密碼是對(duì)所有的明文字母都用一個(gè)固定的代替密碼進(jìn)行加密，故也叫單表代替密碼。為了防止字母頻率分析攻擊，隨后產(chǎn)生了多表代替密碼和多字母代替密碼。

(2)多表代替密碼由LeonBattista在1568年發(fā)明，在美國(guó)南北戰(zhàn)爭(zhēng)中使用。多表代替密碼中最著名的一種密碼是維吉尼亞密碼，Vigenere是法國(guó)密碼學(xué)專家。維吉尼亞密碼有多個(gè)單字母密鑰，每一個(gè)密鑰被用來(lái)加密一個(gè)明文字母。第一個(gè)密鑰加密明文的第一個(gè)字母，第二個(gè)密鑰加密明文的第二個(gè)字母，等等。在所有密鑰用完后，密鑰又再循環(huán)使用，其中密鑰的長(zhǎng)度就是密碼的周期，在古典密碼學(xué)中，密碼周期越長(zhǎng)越難破譯。例如，明文為system，密鑰為dog，加密過(guò)程如下：

明文：system密鑰：dogdog密文：vmgwrs其中，密鑰字母a、b、c、d、...、x、y、z對(duì)應(yīng)的數(shù)字為：0、1、2、3、...、24、25。密鑰字母d對(duì)應(yīng)數(shù)字3，所以明文字母s在d作用下右移3位，得到密文字母v，明文字母y在o作用下右移14位可以得到密文字母m，依次類推。解密時(shí)，密文字母在密鑰字母的作用下向前移位即可得到對(duì)應(yīng)的明文字符。多表代替密碼結(jié)果將使得對(duì)單表代替用的字母簡(jiǎn)單頻率分析方法失效，但使用計(jì)算機(jī)可以輕易破譯具有很長(zhǎng)周期的代替密碼。

(3)多字母代替密碼：在前面介紹的兩種算法中，明文中的每一個(gè)字符都是以單個(gè)字母作為代替的對(duì)象，如果用多于一個(gè)字母代替明文字符就是多字母代替密碼，它的優(yōu)點(diǎn)是容易將字母的頻率隱藏，從而抗擊字母統(tǒng)計(jì)分析。這種密碼首先是由Playfair在1854年發(fā)明的，另外一個(gè)使用相對(duì)較多的多字母代替密碼例子是Hill密碼，但這類密碼由于加密過(guò)于復(fù)雜而且不是非常安全，因此未能廣泛應(yīng)用。

2．換位密碼在換位密碼中，明文的字母數(shù)保持相同，但相互之間的順序被打亂了。在簡(jiǎn)單的縱行換位密碼中，明文以固定的寬度水平寫在一張圖表紙上，密文按垂直方向讀出，解密就是將密文按相同的寬度垂直地寫在圖表紙上，然后水平地讀出明文。

2.3對(duì)

稱

密

碼

1．對(duì)稱密碼簡(jiǎn)介 如果一個(gè)加密系統(tǒng)的加密密鑰和解密密鑰相同，或者雖然不相同，但是由其中的任意一個(gè)可以很容易地推導(dǎo)出另一個(gè)，則該系統(tǒng)所采用的就是對(duì)稱密碼體制。對(duì)稱密碼體制的優(yōu)點(diǎn)是具有很高的保密強(qiáng)度，可以達(dá)到經(jīng)受較高級(jí)破譯力量的分析和攻擊。但它的密鑰必須通過(guò)安全可靠的途徑傳遞，密鑰管理成為影響系統(tǒng)安全的關(guān)鍵性因素，使它難以滿足系統(tǒng)的開放性要求。

對(duì)稱密碼體制根據(jù)對(duì)明文加密方式的不同而分為分組密碼和流密碼(又叫序列密碼)。序列密碼則一次只對(duì)明文中的單個(gè)位(有時(shí)也對(duì)字節(jié))加/解密，對(duì)輸入元素進(jìn)行連續(xù)處理，同時(shí)產(chǎn)生連續(xù)單個(gè)輸出元素。而分組密碼是先按一定長(zhǎng)度如64字節(jié)、128字節(jié)等對(duì)明文進(jìn)行分組，然后以組為單位進(jìn)行加/解密，一次處理一塊輸入明文，每個(gè)輸入塊生成一個(gè)輸出塊，各分組分別在密鑰的控制下變換成等長(zhǎng)度的密文分組?，F(xiàn)代計(jì)算機(jī)加/解密典型分組長(zhǎng)度為64位，這個(gè)分組不僅有防止分析破譯的足夠強(qiáng)度，又可以方便使用。數(shù)據(jù)加密標(biāo)準(zhǔn)(DES，DataEncryptionStandard)是一種最通用的計(jì)算機(jī)加密算法，屬于分組密碼的一種。

2．DES加密數(shù)據(jù)加密標(biāo)準(zhǔn)是最通用的算法之一，1973年5月美國(guó)國(guó)家標(biāo)準(zhǔn)局(NBS，NationalBureauofStandyards)公布了一則公告，征求國(guó)家密碼標(biāo)準(zhǔn)方案。1975年3月NBS公布了IBM公司提供的密碼算法，以標(biāo)準(zhǔn)建議的形式在全國(guó)范圍內(nèi)征求意見。在經(jīng)過(guò)大量公開討論之后，該密碼算法于1977年1月15日正式被批準(zhǔn)為美國(guó)聯(lián)邦信息處理標(biāo)準(zhǔn)，并授權(quán)在非密級(jí)的政府通信中使用，同年7月15日生效。

DES是一個(gè)分組加密算法，以64位為分組對(duì)數(shù)據(jù)加密。64位一組的明文從算法的一端輸入，64位的密文從另一端輸出。DES是一個(gè)對(duì)稱算法：加密和解密都用同一個(gè)算法(除密鑰編排不同)。密鑰長(zhǎng)度也是64位，其中每個(gè)第8位都用作奇偶校驗(yàn)，因此實(shí)際有效密鑰長(zhǎng)度為56位，是可以任意改變的56位數(shù)。DES算法是公開的，其安全性依賴于密鑰的保密程度。

DES算法描述，先進(jìn)行64位的明文分組操作，將該分組用初始置換IP進(jìn)行置換，得到一個(gè)亂序的64位明文分組，然后將分組分成左、右等長(zhǎng)的兩邊，各為32位長(zhǎng)，記作L0和R0。在進(jìn)行16輪完全類似的迭代運(yùn)算后(其中F是在運(yùn)算過(guò)程中將數(shù)據(jù)與密鑰結(jié)合在一起的函數(shù))，把所得到的左、右長(zhǎng)度相等的兩半L16和R16交換，從而得到64位數(shù)據(jù)R16L16，最后再用初始逆置換(IP－1)進(jìn)行置換，可以得到64位密文分組。加密算法過(guò)程如圖2-3所示。

圖2-3加密算法過(guò)程

初始置換是在第一輪迭代前執(zhí)行，對(duì)輸入64位分組實(shí)現(xiàn)如圖2-4所示變換。此圖順序?yàn)閺纳系较拢瑥淖蟮接?。例如，初始置換把明文的第58位換到第一位，把50位換到第二位，以次類推。產(chǎn)生子密鑰Ki，如果不考慮每一個(gè)字節(jié)的第八位(即校驗(yàn)位)，DES的密鑰可以由64位減少到56位。在DES加密算法中，將用戶提供的64位初始密鑰經(jīng)過(guò)一系列的處理得到K1、K2、…、K16，分別作為1～16輪運(yùn)算的16個(gè)子密鑰。先將64位密鑰去掉8個(gè)校驗(yàn)位，用密鑰置換(圖2-5)剩下的56位密鑰；再將56位分成兩個(gè)部分，各28位，然后根據(jù)輪數(shù)(圖2-6)，這兩部分分別循環(huán)左移1位或2位。

圖2-4初始置換表IP圖2-5密鑰置換表

圖2-6密鑰每輪移動(dòng)的位數(shù)

移動(dòng)后，將兩部分合并成56位再通過(guò)壓縮置換(如圖2-7所示)，從而得到48位子密鑰。

圖2-7壓縮置換

這樣經(jīng)過(guò)16次運(yùn)算就可以得到迭代運(yùn)算所需的16個(gè)48位子密鑰。

F函數(shù)是由數(shù)據(jù)擴(kuò)展、與子密鑰的異或運(yùn)算、S盒代替、P盒置換組成，輸入是由32位數(shù)據(jù)和48位的子密鑰組成，下面分別介紹這幾種運(yùn)算：數(shù)據(jù)擴(kuò)展也可以稱為E盒擴(kuò)展(如圖2-8)，此運(yùn)算將數(shù)據(jù)的右半部分Ri從32位擴(kuò)展到48位，可以產(chǎn)生與密鑰同長(zhǎng)度的數(shù)據(jù)進(jìn)行異或運(yùn)算，同時(shí)也可以使輸入的一位影響兩個(gè)替換，從而使輸出對(duì)輸入的依賴性傳播得更快。

圖2-8擴(kuò)展置換E異或，就是將擴(kuò)展后的48位輸出數(shù)據(jù)E(Ri)和壓縮后的子密鑰Ki作異或運(yùn)算。

S盒代替，就是將異或得到的48位結(jié)果分成八個(gè)6位的塊，每一塊作為每個(gè)S盒的輸入，同時(shí)每個(gè)S盒產(chǎn)生一個(gè)4位的輸出，這樣8個(gè)S盒就可以產(chǎn)生32位的輸出(如圖2-9所示)。

圖2-9S盒構(gòu)成對(duì)于每一個(gè)Si，由6位輸入中的第1和第6位組成的二進(jìn)制數(shù)確定Si的行，中間其余的4位二進(jìn)制數(shù)用來(lái)確定Si的列。Si中相應(yīng)的行、列位置的十進(jìn)制數(shù)的4位二進(jìn)制數(shù)用來(lái)作為輸出。例如，某個(gè)S2輸入為101001，則行數(shù)和列數(shù)的二進(jìn)制數(shù)分別表示11和0100，即十進(jìn)制數(shù)下的第3行和第4列，而在S盒2中第3行第4列的十進(jìn)制數(shù)為3，用4位二進(jìn)制數(shù)表示為0011，所以S2的輸出為0011，從而可以用值0011代替101001。經(jīng)過(guò)S盒置換，對(duì)8個(gè)4位分組進(jìn)行重新組合，可以形成一個(gè)32位的分組。

P置換，即將S盒代替運(yùn)算后的32位輸出按照P盒表(如圖2-10)進(jìn)行置換，該置換把每輸入位對(duì)應(yīng)到輸出位上，任何一位不能被置換二次，也不能被忽略。例如，將第29位移動(dòng)到第5位處，而把第5位移動(dòng)到第13位處，以次類推。

圖2-10P盒置換

初始逆置換是初始置換的逆過(guò)程，就是將最后一輪迭代所得64位數(shù)據(jù)R16L16用初始逆置換IP－1(如圖2-11)進(jìn)行置換，產(chǎn)生64位密文分組。

圖2-11逆置換

DES解密，明文雖然經(jīng)過(guò)許多輪的代替、置換、異或和循環(huán)移動(dòng)之后，產(chǎn)生對(duì)應(yīng)的密文，但由于經(jīng)過(guò)精心選擇各種操作，因此加密和解密可以使用相同的算法，惟一不同的是各輪密鑰使用的次序相反，比如各輪加密密鑰分別是K1、K2、K3、…、K16，那么，解密密鑰就是K16、K15、…、K3、K2、K1。

DES工作模式有四種：電子密本(ECB)，密碼分組鏈接(CBC)，密文反饋(CFB)和輸出反饋(OFB)。這四種模式中ECB方式比較簡(jiǎn)單，也最容易受到攻擊，但在流行的商業(yè)軟件中，仍然是最常用的方式。

3．DES算法中的關(guān)鍵函數(shù)設(shè)計(jì)

1)函數(shù)F的設(shè)計(jì)函數(shù)F的基本功能就是“擾亂(confusion)”輸入，因此，對(duì)于F來(lái)說(shuō)，其非線性越高越好，也就是說(shuō)，要恢復(fù)F所做的“擾亂”操作越難越好。其他的設(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ù)的“擾亂”功能。

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è)很重要的特性。S盒越大，越容易抵制差分和線性密碼分析。在實(shí)踐當(dāng)中，通常選擇n在8～10之間。

Mister和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ì)尤為重要。

Nyberg提出了以下幾種S盒的設(shè)計(jì)和實(shí)踐原則：

(1)隨機(jī)性：采用某些偽隨機(jī)數(shù)發(fā)生器或隨機(jī)數(shù)表格來(lái)產(chǎn)生S盒的各個(gè)項(xiàng)。

(2)隨機(jī)測(cè)試：隨機(jī)選擇S盒各個(gè)項(xiàng)，然后按照不同準(zhǔn)則測(cè)試其結(jié)果。

(3)數(shù)學(xué)構(gòu)造：根據(jù)某些數(shù)學(xué)原理來(lái)產(chǎn)生S盒。其好處就是可以根據(jù)數(shù)學(xué)上的嚴(yán)格證明來(lái)抵御差分和線性密碼分析，并且可以獲得很好的擴(kuò)散(Diffusion)特性。

2.4公

鑰

密

碼

1.公鑰密碼簡(jiǎn)介在對(duì)稱密鑰密碼體制中，加密運(yùn)算與解密運(yùn)算使用同樣的密鑰。通常使用的加密算法比較簡(jiǎn)便高效、密鑰簡(jiǎn)短、破譯極其困難。但是，在公共的計(jì)算機(jī)網(wǎng)絡(luò)上安全地傳送和保管密鑰是一個(gè)嚴(yán)峻的問(wèn)題。

為了解決上述問(wèn)題，1976年由WhitefieldDiffie和MartinHellman首先提出公開密鑰密碼學(xué)的概念。同時(shí)，RalphMerkle也獨(dú)立地提出了這一體制。它的基本思想是采用一對(duì)密鑰，加密密鑰和解密密鑰(且從加密密鑰推出解密密鑰是不可行的)，在這一對(duì)密鑰中，一個(gè)可以公開(稱為公鑰)，另一個(gè)為私人專用(稱為私鑰)，它是基于陷門單向函數(shù)的概念。如果對(duì)一個(gè)函數(shù)f的定義域上的任意一個(gè)x都容易計(jì)算f(x)，但對(duì)f的值域上的任意一個(gè)y，f-－1(y)在計(jì)算上是不可行的，就稱f是單向函數(shù)。如果進(jìn)一步給定某些輔助信息，計(jì)算f-－1(y)又變得容易，則稱f是陷門單向函數(shù)。這個(gè)輔助信息也就是私人密鑰。

2.RSA密碼系統(tǒng)到目前為止，使用最廣泛的公開密鑰系統(tǒng)是RSA公開密鑰密碼系統(tǒng)，它是由R.Rivest、A.Shamir和L.Adleman提出的。RSA的取名就是來(lái)自于這三位發(fā)明者的姓的第一個(gè)字母，后來(lái)，他們?cè)?982年創(chuàng)辦了以RSA命名的公司RSADataSecurityInc.和RSA實(shí)驗(yàn)室，該公司和實(shí)驗(yàn)室在公開密鑰密碼系統(tǒng)的研究和商業(yè)應(yīng)用推廣方面具有舉足輕重的地位。

RSA密碼系統(tǒng)的安全是基于大整數(shù)分解因子的難度，其公開密鑰(現(xiàn)在一般是1024位甚至更長(zhǎng))和私人密鑰是一對(duì)大素?cái)?shù)的函數(shù)。一般來(lái)說(shuō)，求一對(duì)大素?cái)?shù)的乘積相對(duì)比較容易，但要對(duì)這個(gè)乘積進(jìn)行因式分解則非常困難。因此，可以把一對(duì)大素?cái)?shù)的乘積作為公開密鑰公布，而把素?cái)?shù)作為私鑰，從而從一個(gè)公開密鑰和密文中恢復(fù)出明文的難度等價(jià)于分解兩個(gè)大素?cái)?shù)之積。

建立RSA密碼系統(tǒng)過(guò)程如下：

(1)選取兩個(gè)大素?cái)?shù)p和q，p和q的位數(shù)差不多大小。

(2)計(jì)算乘積n＝pq和Ф(n)＝(p－1)(q－1)。

(3)隨機(jī)選取加密密鑰e，使e和(p－1)(q－1)互素，也即gcd(e,Ф(n))＝1。

(4)計(jì)算解密密鑰d，以滿足ed＝1modФ(n)，即e與d互逆，d與n是互素的。

(5)加密函數(shù)為：E(x)＝memodn，解密函數(shù)為：D(x)＝cdmodn，其中m是明文，c是密文。

(6){e，n}為公開密鑰，d為私人密鑰，p、q不再需要，可以丟棄，但不能泄露。一般n的長(zhǎng)度是1024位或者更長(zhǎng)。

RSA加密消息m時(shí)，首先將消息分成大小合適的數(shù)據(jù)分組，然后對(duì)分組分別進(jìn)行加密，每個(gè)分組的長(zhǎng)度均應(yīng)該比n的位數(shù)要小。舉例，選擇兩個(gè)小的素?cái)?shù)取p＝11，q＝13，p和q的乘積為n＝p×q＝143，算出另一個(gè)數(shù)Ф(n)＝(p－1)(q－1)＝120；再選取一個(gè)與z＝120互質(zhì)的數(shù)，例如e＝7，對(duì)于這個(gè)e值，可以算出另一個(gè)值d＝103滿足e×d＝1modz；其實(shí)7×103＝721除以120確實(shí)余1。(n,e)和(n,d)這兩組數(shù)分別為公開密鑰和私人密鑰。設(shè)想A需要發(fā)送機(jī)密信息(明文，即未加密的報(bào)文)m＝85給B，A已經(jīng)從公開媒體得到了B的公開密鑰(n,e)＝(143,7)，于是A算出加密值c＝me

modn＝857mod143＝123并發(fā)送給B。B在收到“密文”(即經(jīng)加密的報(bào)文)c＝123后，利用只有B自己知道的私人密鑰(n,d)＝(143,123)計(jì)算123123mod143，得到的值就是明文(值)85，實(shí)現(xiàn)了解密。在RSA的加/解密過(guò)程中都涉及到求一個(gè)大整數(shù)的冪，然后模n，所以加/解密的速度會(huì)比較慢，不論在硬件實(shí)現(xiàn)時(shí)還是軟件實(shí)現(xiàn)時(shí)，RSA比DES要慢很多。一般公鑰密碼系統(tǒng)用于以下幾個(gè)方面：通信保密、數(shù)字簽名和密鑰交換。

3．Diffie-Hellman密鑰交換

Diffie-Hellman算法是第一個(gè)公開密鑰算法，發(fā)明于1976年。Diffie-Hellman算法能夠用于密鑰分配，但不能用于加密或解密信息。Diffie-Hellman算法的安全性在于在有限域上計(jì)算離散對(duì)數(shù)非常困難。在此先簡(jiǎn)單介紹一下離散對(duì)數(shù)的概念。定義素?cái)?shù)p的本原根(PrimitiveRoot)為一種能生成1～p－1所有數(shù)的一個(gè)數(shù)，即如果a為p的本原根，則amodp，a2modp，…，ap－1modp兩兩互不相同，構(gòu)成1～p－1的全體數(shù)的一個(gè)排列(例如p＝11，a＝2)。對(duì)于任意數(shù)b及素?cái)?shù)p的本原根a，可以找到一個(gè)惟一的指數(shù)i，滿足：b＝aimodp，0≤i≤p?1稱指數(shù)i為以a為底模p的b的離散對(duì)數(shù)。如果Alice和Bob想在不安全的信道上交換密鑰，他們可以采用如下步驟：

(1)?Alice和Bob協(xié)商一個(gè)大素?cái)?shù)p及其本原根a，a和p可以公開。

(2)?Alice秘密產(chǎn)生一個(gè)隨機(jī)數(shù)x，計(jì)算X＝axmodp，然后把X發(fā)送給Bob。

(3)?Bob秘密產(chǎn)生一個(gè)隨機(jī)數(shù)y，計(jì)算Y＝aymodp，然后把Y發(fā)送給Alice。

(4)?Alice計(jì)算k＝Y(jié)xmodp。

(5)Bob計(jì)算k′＝Xy

modp。

k和k′是恒等的，因?yàn)閗＝Y(jié)xmodp＝(ay)xmodp＝(ax)ymodp＝Xymodp＝k′。線路上的搭線竊聽者只能得到a、p、X和Y的值，除非能計(jì)算離散對(duì)數(shù)，恢復(fù)出x和y，否則就無(wú)法得到k，因此，k為Alice和Bob獨(dú)立計(jì)算的秘密密鑰。下面用一個(gè)例子來(lái)說(shuō)明上述過(guò)程。Alice和Bob需進(jìn)行密鑰交換，則：

(1)二者協(xié)商后決定采用素?cái)?shù)p＝353及其本原根a＝3。

(2)?Alice選擇隨機(jī)數(shù)x＝97，計(jì)算X＝397mod353＝40，并發(fā)送給Bob。

(3)?Bob選擇隨機(jī)數(shù)y＝233，計(jì)算Y＝3233mod353＝248，并發(fā)送給Alice。

(4)?Alice計(jì)算k＝Y(jié)xmodp＝24897mod353＝160。

(5)?Bob計(jì)算k′＝Xymodp＝40233mod353＝160。k和k′即為秘密密鑰。2.5消息驗(yàn)證和數(shù)字簽名

1.Hash函數(shù)公鑰密碼體制最重要的一個(gè)應(yīng)用是數(shù)字簽名，而數(shù)字簽名常常需要和單向散列函數(shù)結(jié)合起來(lái)使用。散列函數(shù)(Hash函數(shù))是把不固定長(zhǎng)度輸入串(M是變長(zhǎng)的消息串)轉(zhuǎn)換成固定長(zhǎng)度輸出串(散列值h)的一種函數(shù)，即h＝H(M)，其中h的長(zhǎng)度是m。單向散列函數(shù)是在一個(gè)方向上工作的散列函數(shù)，其安全性主要在于它的單向性，必須具有如下性質(zhì)：

(1)對(duì)于給定的M，很容易計(jì)算其散列值h。(2)對(duì)于給定的h，根據(jù)H(M)＝h得出M在計(jì)算上是不可行的。(3)對(duì)于給定的M，要找到另一消息M′，并滿足H(M)＝H(M′)在計(jì)算上是不可行的。

(4)尋找任意的M，M′，使得H(M)＝H(M′)在計(jì)算上不可行的(抗碰撞條件)。

為了對(duì)不定長(zhǎng)的輸入產(chǎn)生定長(zhǎng)的輸出，并且最后的結(jié)果要與所有的字節(jié)相關(guān)，許多單向散列函數(shù)都采用了分塊填充鏈接的方式，其結(jié)構(gòu)是迭代漸進(jìn)型的，這種散列函數(shù)將輸入數(shù)據(jù)分成n塊固定長(zhǎng)度(每塊長(zhǎng)度為k)的分組。單向散列函數(shù)建立在壓縮函數(shù)f的基礎(chǔ)上。給定一長(zhǎng)度為k的輸入，單向函數(shù)輸出長(zhǎng)為m散列值，壓縮函數(shù)的輸入是消息分組和文本前一分組的輸出(對(duì)第一個(gè)分組，其輸入為消息分組和初始化向量)，輸出是到該點(diǎn)的所有分組的散列。即分組Mi的散列值為：hi＝f(Mi,hi－1)

該散列值和下一輪的消息分組一起，作為壓縮函數(shù)下一輪的輸入。最后一分組的散列就成為整個(gè)消息的散列。有結(jié)論可以得出，如果壓縮函數(shù)是無(wú)碰撞的，那么上述方法得到的Hash函數(shù)也是無(wú)碰撞的。因此，Hash函數(shù)的核心技術(shù)是設(shè)計(jì)無(wú)碰撞壓縮函數(shù)。同樣，密碼分析對(duì)算法的攻擊重點(diǎn)也是對(duì)f內(nèi)部結(jié)構(gòu)的分析，常常需要先找出f的碰撞。

MD表示消息摘要(MessageDigest)，MD4算法是由RonRivest提出的一個(gè)單向散列函數(shù)，MD5是MD4的改進(jìn)版，該算法對(duì)輸入的任意長(zhǎng)度消息產(chǎn)生128位散列值，MD5曾經(jīng)是使用最普遍的安全散列算法，但從密碼分析角度來(lái)看，MD5被認(rèn)為已經(jīng)不再安全了。因此現(xiàn)在比較流行的算法是散列值長(zhǎng)度160位SHA-1和RIPEMD-160。

2．消息驗(yàn)證與密鑰相關(guān)的單向散列函數(shù)通常稱為MAC，即消息驗(yàn)證碼。MAC具有與前面討論的單向散列函數(shù)相同的特性，但MAC還包括一個(gè)秘密密鑰，即MAC＝fk(M)，散列值是輸入值和密鑰的函數(shù)。其中M是輸入串，k為通信雙方的密鑰，f為單向散列函數(shù)。

MAC可為擁有共享密鑰的雙方在通信中驗(yàn)證消息的完整性，也可以被單個(gè)用戶用來(lái)確定他的文件是否已經(jīng)被改動(dòng)，或是否被感染了病毒。

3．?dāng)?shù)字簽名數(shù)字簽名就是附加在數(shù)據(jù)單元上的一些數(shù)據(jù)，或是對(duì)數(shù)據(jù)單元所作的密碼變換。這種數(shù)據(jù)或變換允許數(shù)據(jù)單元的接收者用以確認(rèn)數(shù)據(jù)單元的來(lái)源和數(shù)據(jù)單元的完整性，并保護(hù)數(shù)據(jù)，防止被人進(jìn)行偽造。它是對(duì)電子形式的消息進(jìn)行簽名的一種方法，一個(gè)簽名消息能在通信網(wǎng)絡(luò)中傳輸。基本要求如下：

(1)簽名是可信的。

(2)簽名不可偽造。

(3)簽名不可重用，簽名是文件的一部分，不能移到別的文件上去。

(4)簽名的文件是不可改變的，在文件上簽名以后就不能改變。

(5)簽名是不可抵賴的。

目前使用比較多的數(shù)字簽名有兩類：一類是使用對(duì)稱密碼系統(tǒng)和需要仲裁者的簽名方法；還有一類是基于公開密鑰體制的數(shù)字簽名，一般目前使用最多的是基于公開密鑰體制的數(shù)字簽名。一般數(shù)字簽名方案由兩部分組成：簽名算法和驗(yàn)證算法。在實(shí)際應(yīng)用中，由于公開密鑰算法的執(zhí)行效率比較低，因此為了節(jié)約時(shí)間，數(shù)字簽名協(xié)議經(jīng)常和單向散列函數(shù)一起使用，發(fā)送方并不對(duì)整個(gè)文件簽名，而只是對(duì)文件的散列值簽名。簽名的過(guò)程如下：

(1)發(fā)送者產(chǎn)生文件的單向散列值。

(2)發(fā)送者用其私人密鑰對(duì)散列加密，以實(shí)現(xiàn)對(duì)發(fā)送文件的簽名。

(3)發(fā)送者將文件和散列簽名發(fā)送給接收者。

(4)接收者根據(jù)發(fā)送者發(fā)送的文件產(chǎn)生文件的單向散列值，然后用數(shù)字簽名算法對(duì)散列值運(yùn)算，同時(shí)用發(fā)送者的公開密鑰對(duì)簽名的散列解密。如果簽名的散列值與其產(chǎn)生的散列值匹配，則簽名是有效的。

前面提到的公開密鑰算法RSA也可以用于數(shù)字簽名。令n＝p1p2，p1和p2是大素?cái)?shù)，令消息為M，選e并計(jì)算出d使ed≡1mod((n)，公開n和e，將p1、p2和d保密。

K＝(n,p,q,e,d)。對(duì)消息M的簽字為：S＝Sigk(M)＝[H(M)]dmodn，簽名過(guò)程如圖2-12所示。

圖2-12RSA算法實(shí)現(xiàn)的數(shù)字簽名過(guò)程

驗(yàn)證簽名過(guò)程如圖2-13所示，對(duì)給定的M和S，可按下式驗(yàn)證：H(M)≡Semodn

圖2-13驗(yàn)證RSA數(shù)字簽名過(guò)程