公鑰密碼體制的密鑰交換課件

第二章密碼學(xué)概論

12．1密碼學(xué)概述2一、保密通信模型

A向B發(fā)送一報文，為了不被E竊聽，A對報文進行加密，然后在通信信道上進行傳輸，B收到報文后進行解密，得到原來的報文。E即使竊聽到密文，由于其沒有密鑰，他也無法還原出明文。

保密通信安全的關(guān)鍵？3二、數(shù)據(jù)加密概念1、基本術(shù)語明文是要加密的報文。密文是加密后的報文。密碼算法是一些函數(shù)、公式、法則或程序，密碼算法分為加密算法和解密算法，前者是將明文變換成密文，后者是將密文變換成明文。

密鑰是密碼算法中的可變參數(shù)，可以是數(shù)字、詞匯或語句。密鑰分為加密密鑰和解密密鑰。42、數(shù)據(jù)加密的數(shù)學(xué)描述一個加密系統(tǒng)數(shù)學(xué)符號描述如下（假設(shè)k1=k2=k）：S=｛M，C，K，E，D｝

其中M是明文空間，C是密文空間，K是密鑰空間，E是加密算法，D是解密算法，當(dāng)給定密鑰k∈K時，加、解密算法分別記作Ek和Dk，并有：

C=Ek(M)

M=Dk(C)=Dk(Ek(M)),

或記為

Dk=Ek–1且Ek=Dk–15三、密碼學(xué)概述密碼學(xué)概念密碼學(xué)是對信息進行編碼實現(xiàn)隱蔽信息的一門學(xué)問。6密碼學(xué)發(fā)展的三個階段階段一：1949年之前，古典密碼學(xué)密碼學(xué)還不是科學(xué),而是藝術(shù)。出現(xiàn)一些密碼算法和加密設(shè)備。密碼算法的基本手段出現(xiàn)，保密針對的是字符。簡單的密碼分析手段出現(xiàn)。階段一密碼學(xué)主要特點：由于數(shù)據(jù)傳遞具有一對一的特點，數(shù)據(jù)的安全基于算法的保密

7階段二：1949年～1976年，現(xiàn)代密碼學(xué)l

密碼學(xué)成為科學(xué)，具有較嚴密的數(shù)學(xué)理論基礎(chǔ)，其安全性可以論證。l

計算機使得基于復(fù)雜計算的密碼算法成為可能。對稱密碼體制成熟應(yīng)用：加密密鑰=解密密鑰。l主要特點：由于數(shù)據(jù)傳遞具有一對多的特點，數(shù)據(jù)的安全基于算法的保密已不再可行。本階段最大特點在于一切秘密寓于密鑰之中，數(shù)據(jù)的安全基于密鑰而不是算法的保密。即在設(shè)計加密系統(tǒng)時，總是假定密碼算法是公開的，真正需要保密的是密鑰。8階段三：1976年以后，公鑰密碼學(xué)l

開辟了現(xiàn)代密碼學(xué)的新方向l公鑰密碼體制發(fā)展起來：一對密鑰，一個公開，另一個保密。l主要特點：公鑰密碼使得發(fā)送端和接收端無密鑰傳輸?shù)谋Ｃ芡ㄐ懦蔀榭赡?；拓展了密碼學(xué)的用途。9四、兩類密碼體制1、對稱密碼體制對稱密碼體制即加密密鑰和解密密鑰相同或一個可由另一個導(dǎo)出。在對稱密鑰中，密鑰的管理極為重要，一旦密鑰丟失，密文將無密可保。1011

2、公鑰密碼體制公鑰密碼體制又稱為非對稱密碼體制，兩個密鑰（加密密鑰和解密密鑰）各不相同。一個密鑰公開，另一個密鑰不公開，從一個推導(dǎo)出另一個是不可行的。公鑰密碼的優(yōu)點是可以適應(yīng)網(wǎng)絡(luò)的開放性要求，且密鑰管理問題也較為簡單，尤其可方便的實現(xiàn)數(shù)字簽名和驗證。1213五、兩類密碼算法1、序列密碼算法如果密文不僅與給定的密碼算法和密鑰有關(guān)，同時也是被處理的明文數(shù)據(jù)段在整個明文（或密文）中所處的位置的函數(shù)，則稱為序列密碼體制。是一個比特一個比特地處理。2、分組密碼算法如果密文僅與給定的密碼算法和密鑰有關(guān)，與被處理的明文數(shù)據(jù)段在整個明文（或密文）中所處的位置無關(guān)，則稱為分組密碼體制。分組密碼體制就是將明文分成固定長度的組，如64bit一組，用同一密鑰和算法對每一組加密，輸出也是固定長度的密文?，F(xiàn)代計算機密碼算法的典型分組長度為64位14六、對密碼算法的要求（1）必須提供高度的安全性，并且能夠被證明；（2）具有相當(dāng)高的復(fù)雜性，使得破譯的開銷超過可能獲得的利益，同時又便于理解和掌握；（3）安全性應(yīng)不依賴于算法的保密，其加密的安全性僅以加密密鑰的保密為基礎(chǔ)；（4）必須適用于不同的用戶和不同的場合；151、密碼分析學(xué)概念密碼分析學(xué)是研究分析破譯密碼的學(xué)問。與密碼學(xué)相互對立、促進。

密碼分析學(xué)是在不知道密鑰的情況下，恢復(fù)出明文的科學(xué)。成功的密碼分析能恢復(fù)出消息的明文或密鑰。密碼分析也可以用來發(fā)現(xiàn)密碼體制的弱點，以對其進行改進。七、密碼分析學(xué)概述16一）、破譯算法的代價不能大于加密數(shù)據(jù)的價值；二）、破譯算法所需的時間不能大于加密數(shù)據(jù)保密的時間。2、密碼分析遵循的兩條基本原則172．2古典密碼體制（略）181、規(guī)則將字母表中的每個字母用該字母后第三個字母代替。字母轉(zhuǎn)換關(guān)系：

ABCDEFGHIJKLMNOPQRSTUVWXYZdefghIjklmnopqrstuvwxyzabc

一、Caesar密碼192、算法描述假設(shè)a=0,b=1,c=2,…z=25則加密算法為

C=E(p)=(p+3)mod26

則解密算法為

p=D(C)=(C-3)mod26203、通用的Caesar算法假設(shè)K（1<=K<=25）表示密鑰

則加密算法為

C=E(p)=(p+K)mod26則解密算法為

p=D(C)=(C-K)mod2621密鑰由25個英文字母（J與I相同）組成的5階方陣。每一對明文字母m1和m2，都根據(jù)下面的6條規(guī)則進行加密。（1）I、J看成是相同字母。（2）明文有奇數(shù)個字母，末尾加一個無效字母。（3）明文字母m1和m2相同。在m1和m2之間加一個特定的無效字母。（4）明文字母m1和m2同行。密文循環(huán)取其右邊字母。（5）明文字母m1和m2同列。密文循環(huán)取其下邊字母。（6）明文字母m1和m2不同行、不同列。則取其同行且與下一字母同列的字母為密文。

二、Playfair密碼22設(shè)密鑰k=k1k2…km，明文M=m1m2…mn（若明文長度不是m的倍數(shù)，則在末尾填充隨機字符），加密變換Ek(M)=c1c2…cn。

其中

ci+l*m=(mi+l*m+ki)mod26i=1,2…m;l=0,1…,n/m

三、維吉尼亞（Vigenere）密碼23

加密算法：

C=KP（mod26）。其中C和P為長度為m的列向量，分別表示密文和明文；K為m*m的矩陣，表示加密密鑰。加密操作要執(zhí)行模26運算。四、Hill密碼24五、轉(zhuǎn)輪技術(shù)轉(zhuǎn)輪密碼機ENIGMA，由ArthurScherbius于1919年發(fā)明，面板前有燈泡和插接板；4輪ENIGMA在1942年裝備德國海軍，使得英國從1942年2月到12月都沒能解讀德國潛艇的信號。25假設(shè)有一個由兩個同心圓所組成的密碼轉(zhuǎn)盤，如下圖所示。

密碼轉(zhuǎn)盤圖旋轉(zhuǎn)后的密碼轉(zhuǎn)盤

26

轉(zhuǎn)動轉(zhuǎn)盤就改變了字母之間的替代關(guān)系，生成一個單字母替代密碼。一個轉(zhuǎn)輪可得26種替代密碼。設(shè)有n個轉(zhuǎn)輪，輸入和輸出依次相接，則可得26n種替代密碼，大大增加了密碼攻擊的難度。272．3對稱密碼體制

28一、DES算法

291、DES概述產(chǎn)生：IBM公司于1971年研制出了一種密碼算法LUCIFER，隨后，在1971至1972年間IBM的W.Tuchman和C.Meyer對該方案進行了改進。美國商業(yè)部的國家標(biāo)準局1973年5月到1974年8月兩次發(fā)布通告，公開征求用于電子計算機的加密算法。經(jīng)評選從一大批算法中采納了IBM的LUCIFER方案。標(biāo)準化：LUCIFER方案于1976年11月被美國政府采用，隨后被美國國家標(biāo)準局和美國國家標(biāo)準協(xié)會(AmericanNationalStandardInstitute，ANSI)承認。1977年1月以數(shù)據(jù)加密標(biāo)準DES（DataEncryptionStandard）的名稱正式向社會公布。該標(biāo)準于1977年7月15日生效。DES的發(fā)展：如衍生出可抗差分分析攻擊的變形DES以及密鑰長度為128比特的三重DES等。302、DES安全性在1977年，人們估計要耗資兩千萬美元才能建成一個專門計算機用于DES的解密，而且需要12個小時的破解才能得到結(jié)果。1997年開始，RSA公司發(fā)起了一個稱作“向DES挑戰(zhàn)”的競技賽。1997年1月，用了96天時間，成功地破解了用DES加密的一段信息；一年之后，在第二屆賽事上，這一記錄為41天；一年之后的“第三屆DES挑戰(zhàn)賽”把破解DES的時間縮短到了只需56個小時；“第四屆DES挑戰(zhàn)賽”把破解DES的時間縮短到了只需22.5小時。

31盡管DES已被AES所取代，但DES對于我們掌握分組密碼的基本理論和設(shè)計思想仍然具有重要的意義。323、DES算法概要利用傳統(tǒng)的換位和置換加密。DES是一個分組加密算法，它以64位為分組對數(shù)據(jù)加密。64位一組的明文從算法的一端輸入，64位的密文從另一端輸出。DES是一個對稱密碼算法：加密和解密用的是同一密鑰。密鑰的長度為56位。（密鑰通常表示為64位的數(shù)，但每個第8位都用作奇偶校驗，可以忽略。）密鑰可以是任意的56位的數(shù)，且可在任意的時候改變。其中極少量的數(shù)被認為是弱密鑰，但能容易地避開它們。所有的保密性依賴于密鑰。33DES算法框架34假定信息空間由{0,1}組成的字符串，信息被分成64比特的塊，密鑰是56比特。經(jīng)過DES加密的密文也是64比特的塊。明文：m=m1m2…m64mi=0,1i=1,2,…64

密鑰：k=k1k2…k64

ki

=0,1i=1,2,…64其中k8，k16，…，k64是奇偶校驗位，起作用的僅為56位。加密算法

Ek(m)=IP-1·T16·T15……T1·IP(m)

其中IP為初始置換，IP-1是IP的逆，Ti，i=1,2,…16是一系列的變換。解密算法Ek-1(c)=IP-1·T1·T2……T16·IP(c)

353．1、初始變換IP

位序號363．2逆初始變換P-1

逆初始變換IP-1和IP互逆。例如，第58位經(jīng)過初始置換后，處于第1位，而通過逆置換，又將第1位換回到第58位。可見輸入分組m和IP(IP-1(m))是一樣的。

373.3中間各級乘積邊換算法TiLi-1LiRi-1RiLi-1⊕

f(Ri-1,Ki)按位異或383．3．1加密函數(shù)?(A,Ki)A(32位)加密時A=Ri-1擴展置換E擴展置換E48位結(jié)果48位Ki+S-盒代替(S1~S8)32位結(jié)果32位結(jié)果iP-盒置換32位按位異或393．4擴展置換r1(i)r2(i)r3(i)r4(i)

r5(i)r6(i)r7(i)r8(i)…r29(i)r30(i)r31(i)r32(i)r32(i)r1(i)r2(i)r3(i)r4(i)

r5(i)r4(i)r5(i)r6(i)r7(i)r8(i)

r9(i)…r28(i)r29(i)r30(i)r31(i)r32(i)

r1(i)把R（i）視為由8個4位二進制的塊組成把它們再擴充為8個6位二進制的塊（左右各增加一列）40A32位3212345456789891011121312131415161716171819202120212223242524252627282928293031321選擇運算E擴展置換E的結(jié)果48位41S盒實質(zhì)上是用硬件實現(xiàn)若干比特的替換壓縮后的密鑰與擴展分組異或以后，將48位的結(jié)果送入，進行代替運算。替代由8個S盒完成。每一個S盒都有6位輸入，4位輸出，且這8個S盒是不同的。48位的輸入被分為8個6位的分組，每一分組對應(yīng)一個S盒代替操作：分組1由S-盒1操作，分組2由S-盒2操作，依此類推。3．5S-盒代替42每個S盒是一個4行、16列的表。盒中的每一項都是一個4位二進制數(shù)的十進制表示，其值在0-15之間。S盒的6個位輸入確定了其對應(yīng)的輸出在哪一行哪一列。下面列出所有的8個S盒。

4344454647將以上第j個(1≤j≤8)二進制的塊（記為Zj=zj1zj2zj3zj4zj5zj6）輸入第j個選擇函數(shù)Sj。各選擇函數(shù)Sj的功能是把6位數(shù)變換成4位數(shù)，做法是以zj1zj6為行號，zj2zj3zj4zj5為列號，查找Sj，行列交叉處即是要輸出的4位數(shù)。在此以S1為例說明其功能，我們可以看到：在S1中，共有4行數(shù)據(jù)，命名為0，1、2、3行；每行有16列，命名為0、1、2、3，......，14、15列?，F(xiàn)設(shè)輸入為：D＝101100

令：行＝10列＝0110坐標(biāo)為（2，6），然后在S1表中查得對應(yīng)的數(shù)為2，以4位二進制表示為0010，此即選擇函數(shù)S1的輸出。

48012345678910111213141501441312151183106125907101574142131106121195382411481362111512973105031512824917511314100613S11011001020010輸入6位輸出4位49P盒實質(zhì)上是用硬件實現(xiàn)變位，改變輸入序列。S盒代替運算后的32位輸出依照P盒進行置換。該置換把每輸入位映射到輸出位，任意一位不能被映射兩次，也不能被略去，下表給出了每位移到的位置。3．6P盒置換位序號503.7密鑰產(chǎn)生

64位密鑰置換選擇1C0(28位)D0(28位)Ci(28位)Di(28位)置換選擇2Ki(48位)(56位)16個子密鑰的生成算法循環(huán)左移：1191211023211242122521326214264位密鑰置換選擇1密鑰置換C0(28位)D0(28位)循環(huán)左移循環(huán)左移Ci(28位)Di(28位)置換選擇2壓縮置換Ki(48位)(56位)16個子密鑰的生成算法循環(huán)左移：1191211023211242122521326214272152821615157494133251791585042342618102595143352719113605244366355473931331576254463830221466153453729211352820124不考慮各字節(jié)第8位密鑰（64位）C0(28位)D0(28位)密鑰置換位序號52Ci(28位)Di(28位)1417112415328156211023191242681672720132415231374755304051453348444939563453464250362932Ki(48位)壓縮置換去掉第9，18，22，25，35，38，43，54位，56位變成48位位序號534、DES解密在經(jīng)過所有的代替、置換、異或和循環(huán)移動之后，獲得了這樣一個非常有用的性質(zhì)：加密和解密可使用相同的算法和密鑰。DES使得用相同的函數(shù)來加密或解密每個分組成為可能，二者的唯一不同之處是子密鑰的次序相反。545、分組密碼運行模式（略）

5．1、ECB（電碼本）模式555．2CBC（密碼分組鏈接）模式Vi565．3CFB（密碼反饋）模式Xi+1SVEi575．4OFB（輸出反饋）模式

SV586、DES算法的脆弱性591）二重DES（二個密鑰，長度112位）：加密：C=Ek2[Ek1(P)]解密：P=Dk1[Dk2(C)]2）三重DES（二個密鑰）加密：C=Ek1[Dk2[Ek1(P)]]解密：P=Dk1[Ek2[Dk1(C)]]

7、多重DES60AES的算法屬對稱密碼體制；算法為分組密碼算法，分組長度是128bit;密鑰長度為128，192和256bit三種，可選；比三重DES快，至少和三重DES一樣安全；AES被開發(fā)用于替代DES作為對稱密碼算法的標(biāo)準。三、高級加密標(biāo)準（AES）AES算法概要61

AES算法的設(shè)計目標(biāo)能抗擊所有的已知攻擊；能在多種平臺上快速實現(xiàn)，并且代碼簡潔；設(shè)計簡單。

622．4公鑰密碼體制

631、對稱密碼體制的缺陷密鑰傳輸帶來的不安全性。密鑰管理的麻煩，n個用戶保存n*(n-1)/2個密鑰。不能提供法律證據(jù)解決糾紛，因為只有通訊雙方知道密鑰。一、概述64是對對稱密碼的重要補充；是密碼學(xué)一次偉大的革命；擴展了密碼學(xué)的用途。使用兩個密鑰：公密鑰、私密鑰。加解密的非對稱性。利用數(shù)論的方法。2、公鑰密碼體制簡介65（1）通信保密：此時將公鑰作為加密密鑰，私鑰作為解密密鑰，通信雙方不需要交換密鑰就可以實現(xiàn)保密通信。這時，通過公鑰或密文分析出明文或私鑰是不可行的。（2）數(shù)字簽名：將私鑰作為加密密鑰，公鑰作為解密密鑰，可實現(xiàn)由一個用戶對數(shù)據(jù)加密而使多個用戶解讀。（3）密鑰交換：通信雙方使用公鑰密碼體制加密傳輸會話密鑰，該會話密鑰用以加密通信雙方后續(xù)連接所傳輸?shù)男畔?。每次邏輯連接使用一把新的會話密鑰，用完就丟棄。

3、公鑰密碼學(xué)用途66A向B發(fā)消息X，B的公鑰為KUb,私鑰為KRb。A加密Y=EKUb(X)B解密X=DKRb(Y)

公鑰密碼體制的加密功能信道明文密文加密算法解密算法明文接收方采用公鑰算法生成一對密鑰用自己的私鑰解密發(fā)送方用對方的公鑰加密公鑰傳送給對方密文67A向B發(fā)送消息X，A的公鑰為KUa，私鑰為KRa.。A“加密”：Y=EKRa(X)（數(shù)字簽名）B“解密”：X=DKUa(Y)

注意：不能保證消息的保密性。公鑰密碼體制的數(shù)字簽名信道明文密文加密算法解密算法明文發(fā)送方采用公鑰算法生成一對密鑰用對方的公鑰解密發(fā)送方用自己的私鑰加密密文將公鑰發(fā)送給對方68明文密文密文信道解密算法信道加密算法解密算法接收方用自己的私鑰解密數(shù)字信封發(fā)送方用對方的公鑰加密DES密鑰形成數(shù)字信封明文加密算法發(fā)送方用自己的DES密鑰加密明文得到發(fā)送方的DES密鑰用于解密密文密鑰交換技術(shù)也稱為數(shù)字信封技術(shù)，應(yīng)用非常廣泛。公鑰密碼體制的密鑰交換69僅根據(jù)密碼算法和加密密鑰來確定解密密鑰在計算上不可行。兩個密鑰中的任何一個都可用來加密，另一個用來解密。

4、公鑰密碼重要特點70對稱密碼非對稱密碼

5、對稱密碼體制與非對稱密碼體制的比較711、RSA概述由MIT的Rivest,Shamir&Adleman

在1977提出。最著名的且被廣泛應(yīng)用的公鑰加密體制。明文、密文是0到n-1之間的整數(shù)，通常n的大小為1024位或309位十進制數(shù)。二、RSA算法722、RSA的數(shù)論基礎(chǔ)1、互素：若gcd(a,b)=1，則整數(shù)a和b互素。

注：gcd為歐幾里得算子2、Euler函數(shù)：a)φ(n)表示與n互素的、小于n的正整數(shù)的個數(shù)，n>1。b)若n是素數(shù)，則φ(n)=n-1c)若n=p*q，p、q是素數(shù)，則φ(n)=(p-1)*(q-1)3、Euler定理：對于任何互素的整數(shù)g和n，有g(shù)

φ(n)modn=1

注：mod為模運算算子4、Euler定理的一個推論：對于任何互素的M和n，存在k，有Mk?(n)＋1=Mmodn。(證明略)733、RSA算法過程

1．取兩個隨機大素數(shù)p和q（保密）。2．計算公開的模數(shù)n=p*q(公開)。3．計算秘密的歐拉函數(shù)φ(n)=（p-1）*(q-1)（保密），丟棄p和q，不要讓任何人知道。4．隨機選取整數(shù)e,滿足gcd(e,φ(n))=1(公開e)。5．計算d滿足de=1(modφ(n))(保密d)。6．將明文M按模為n自乘e次冪以完成加密操作，從而產(chǎn)生密文C。C=Memodn

注意要保證C、M值在0到n-1范圍內(nèi)

747．解密：將密文C按模為n自乘d次冪M=Cd

modn

因為ed＝1（mod?(n)）

因此存在k使得e.d=1+k?(n)

因此Cd=(Me)d=Med=M1+k?(n)=Mmodn754、RSA算法舉例1.

選擇兩個互異素數(shù)：p=17&q=112.

計算n=pq=17×11=1873.

計算?(n)=(p–1)(q