第2章-密碼學(xué)基礎(chǔ)(8課時(shí))

第2章密碼學(xué)基礎(chǔ)

電子商務(wù)安全2023/2/52第2章密碼學(xué)基礎(chǔ)問題的提出國(guó)內(nèi)第一起電子郵件侵權(quán)案2023/2/53第2章密碼學(xué)基礎(chǔ)如果電子郵件的發(fā)送附加了數(shù)字簽名，也許本案就不會(huì)發(fā)生了。第2章密碼學(xué)基礎(chǔ)

▅2.1密碼學(xué)概述

▅2.2傳統(tǒng)對(duì)稱密碼體制

▅2.3公鑰密碼體制

▅2.4量子密碼體制

電子商務(wù)安全2023/2/55第2章密碼學(xué)基礎(chǔ)2.1密碼學(xué)概述2.1.1密碼學(xué)起源與發(fā)展2.1.2什么是密碼學(xué)2.1.3密碼體制分類2.1.4密碼系統(tǒng)設(shè)計(jì)的基本原則2.1.5密碼系統(tǒng)攻擊及分析2023/2/56第2章密碼學(xué)基礎(chǔ)2.1.1密碼學(xué)起源與發(fā)展密碼學(xué)的雛形始于古希臘人在戰(zhàn)場(chǎng)上加密寫有“戰(zhàn)爭(zhēng)機(jī)密”的信件2023/2/57第2章密碼學(xué)基礎(chǔ)2.1.1密碼學(xué)起源與發(fā)展1.古典密碼學(xué)

1949年之前，密碼學(xué)是一門藝術(shù)2.近代密碼學(xué)

1949～1975年：密碼學(xué)成為科學(xué)3.現(xiàn)代密碼學(xué)

1976年以后：密碼學(xué)的新方向——公鑰密碼學(xué)2023/2/58第2章密碼學(xué)基礎(chǔ)隱寫術(shù)(steganography):

通過隱藏消息的存在來保護(hù)消息.隱形墨水字符格式的變化圖象圖像

2.1.1密碼學(xué)起源與發(fā)展2023/2/59第2章密碼學(xué)基礎(chǔ)象形文字的修改(ModifiedHieroglyphics)c.1900B.C.

密碼學(xué)的第一個(gè)例子是對(duì)標(biāo)準(zhǔn)書寫符號(hào)的修改我去君留十載中愛無南北與西東萬株松樹青山上潔白孤高生不同2023/2/510第2章密碼學(xué)基礎(chǔ)example-ii2023/2/511第2章密碼學(xué)基礎(chǔ)2.1.1密碼學(xué)起源與發(fā)展傳說，古時(shí)候有一對(duì)夫妻，男的名叫李石匠，女的叫張小花。李石匠靠手藝賺錢，張小花在家紡紗織布。一年，李石匠參加修建石橋，因工程緊張，十一個(gè)月也沒回家一次。張小花獨(dú)自在家只有紡車做伴。一天石匠工地回來一個(gè)工友路過她家，她托這個(gè)工友給丈夫帶去一封書信。2023/2/512第2章密碼學(xué)基礎(chǔ)公元前400年斯巴達(dá)人使用密碼棍(scytale)2023/2/513第2章密碼學(xué)基礎(chǔ)2.1.1密碼學(xué)起源與發(fā)展加密:將要傳遞的信息隱藏例如：清末大儒紀(jì)曉嵐贈(zèng)送的對(duì)聯(lián)鳳遊禾蔭鳥飛去馬走蘆邊草不生禾下加鳳去掉鳥字得禿字馬置蘆邊去掉草頭得驢字

2023/2/514第2章密碼學(xué)基礎(chǔ)Phaistos(范斯特)圓盤，一種直徑約為160mm的粘土圓盤，始于公元前17世紀(jì)。表面有明顯字間空格的字母，至今還沒有破解2023/2/515第2章密碼學(xué)基礎(chǔ)轉(zhuǎn)輪密碼機(jī)ENIGMA，1944年裝備德國(guó)海軍2023/2/516第2章密碼學(xué)基礎(chǔ)20世紀(jì)早期密碼機(jī)2023/2/517第2章密碼學(xué)基礎(chǔ)2.1.1密碼學(xué)起源與發(fā)展這樣的數(shù)字毫無意義么？2023/2/518第2章密碼學(xué)基礎(chǔ)16世紀(jì)意大利數(shù)學(xué)家卡爾達(dá)諾發(fā)明的一種保密通信方法，史稱“卡爾達(dá)諾漏格板”．漏格板是一張用硬質(zhì)材料(如硬紙、羊皮、金屬等)做成的板，上面挖了一些長(zhǎng)方形的孔，即漏格．2.1.1密碼學(xué)起源與發(fā)展2023/2/519第2章密碼學(xué)基礎(chǔ)2.1.1密碼學(xué)起源與發(fā)展大約在1793年，當(dāng)時(shí)的美國(guó)總統(tǒng)托馬斯杰斐遜發(fā)明了一種輪子密碼機(jī)。2023/2/520第2章密碼學(xué)基礎(chǔ)2.1.1密碼學(xué)起源與發(fā)展以二戰(zhàn)時(shí)期真實(shí)歷史為背景的，關(guān)于電報(bào)密文竊聽和密碼破解的故事2023/2/521第2章密碼學(xué)基礎(chǔ)2.1.2什么是密碼學(xué)1.密碼學(xué)概念2.密碼系統(tǒng)構(gòu)成3.密碼系統(tǒng)數(shù)學(xué)模型

2023/2/522第2章密碼學(xué)基礎(chǔ)1.密碼學(xué)概念密碼學(xué)（Cryptology）：是研究如何保護(hù)信息安全性的一門科學(xué)。它包含兩個(gè)分支：密碼編碼學(xué)和密碼分析學(xué)。密碼編碼學(xué)（Cryptography）：主要研究密碼方案的設(shè)計(jì)，即尋找對(duì)信息編碼的方法從而實(shí)現(xiàn)隱藏信息的一門學(xué)問。密碼分析學(xué)（Cryptanalytics），：主要是從攻擊者的角度來看問題，研究如何破解被隱藏信息的一門學(xué)問。兩個(gè)分支：是既相互對(duì)立，又相互依存的科學(xué)。2023/2/523第2章密碼學(xué)基礎(chǔ)2.密碼系統(tǒng)構(gòu)成

密碼系統(tǒng)主要包括以下幾個(gè)基本要素：明文（PlainText），指的是希望得到保密的原始信息。通常用P或M表示。用某種方法偽裝信息以隱藏它的內(nèi)容的過程稱為加密(Encryption)經(jīng)過加密處理后得到的隱藏信息稱為密文(CipherText)，通常用C表示。

而把密文轉(zhuǎn)變?yōu)槊魑牡倪^程稱為解密(Decryption)。2023/2/524第2章密碼學(xué)基礎(chǔ)2023/2/525第2章密碼學(xué)基礎(chǔ)加密算法(EncryptionAlgorithm)。通常用E表示。是指通過一系列的變換、替代或其他各種方式將明文信息轉(zhuǎn)化為密文的方法。解密算法(DecryptionAlgorithm)。通常用D表示。指通過一系列的變換、替代或其他各種方法將密文恢復(fù)為明文的方法。2023/2/526第2章密碼學(xué)基礎(chǔ)舉例說明上述概念商人賈某要給他兒子發(fā)一份密碼電報(bào)，電文四個(gè)字：“拋售布匹”（原文）。按照電報(bào)碼手冊(cè)，這四個(gè)漢字對(duì)應(yīng)：2141078615800572，然后把每個(gè)四位數(shù)都加上100（加密密鑰），四個(gè)四位數(shù)就變成了：2241088616800672，此刻這四個(gè)電報(bào)碼對(duì)應(yīng)變?yōu)椋骸皰噜釓R叵”（密文）。兒子收到電報(bào)“掄噌廟叵”后，根據(jù)相應(yīng)的電報(bào)碼手冊(cè)得到：2241088616800672，按照事先的約定，分別減去100（解密密鑰），就得到“拋售布匹”的信息。2023/2/527第2章密碼學(xué)基礎(chǔ)2.密碼系統(tǒng)構(gòu)成

加解密算法通常都是在一組密鑰的控制下進(jìn)行的，分別稱為加密密鑰和解密密鑰。加密和解密過程如下圖所示。明文明文密文加密算法解密算法加密密鑰解密密鑰2023/2/528第2章密碼學(xué)基礎(chǔ)3.密碼系統(tǒng)數(shù)學(xué)模型

以五元組（M，C，K，E，D）表示密碼系統(tǒng)，其中M是明文信息空間，C是密文信息空間，K是密鑰信息空間，E是加密算法，D是解密算法。各元素之間有如下的關(guān)系：E：MK->C，表示E是M與K到C的一個(gè)映射；D：CK->M，表示D是C與K到M的一個(gè)映射。2023/2/529第2章密碼學(xué)基礎(chǔ)3.密碼系統(tǒng)數(shù)學(xué)模型

在最早的愷撒密碼體制中明文信息空間是26個(gè)英文字母集合，即M={a,b,c,d……z,A,B……Z}；密文信息空間也是26個(gè)英文字母集合，即C={a,b,c,d…..z,A,B…..Z}密鑰信息空間是正整數(shù)集合，即

K={N|N=1,2…..}；因此Ek=(M+K)mod26；與之對(duì)應(yīng)的解密算法是Dk

，Dk=（C-K）mod26。2023/2/530第2章密碼學(xué)基礎(chǔ)3.密碼系統(tǒng)數(shù)學(xué)模型

例如：愷撒密碼體制解密算法：(C-K)mod262023/2/531第2章密碼學(xué)基礎(chǔ)3.密碼系統(tǒng)數(shù)學(xué)模型

發(fā)送信息的一方使用密鑰K加密明文M，通過加密算法得到密文C，即C=EK（M）；接收信息的一方使用密鑰K’解密密文C，通過解密算法得到明文M，即M=DK’(C)；。K與K’可能相等，也可能不等，具體取決于所采用的密碼體制。

2023/2/532第2章密碼學(xué)基礎(chǔ)3.密碼系統(tǒng)數(shù)學(xué)模型

明文m加密算法：密文c=Ek1(m)加密密鑰源解密密鑰源解密算法：m=Dk2(c)明文mmmk1k2cc2023/2/533第2章密碼學(xué)基礎(chǔ)2.1.3密碼體制分類

按不同的劃分標(biāo)準(zhǔn)或者方式，密碼體制可以分為多種形式。我們主要從加密方式、所采用的密鑰方式以及保密程度來劃分。

2023/2/534第2章密碼學(xué)基礎(chǔ)1.按加密方式劃分

（1）流密碼體制。也稱為序列密碼，它是將明文信息一次加密一個(gè)比特形成密文字符串，典型的流密碼體制是一次一密密碼體制，其密鑰長(zhǎng)度與明文長(zhǎng)度相等。

（2）分組密碼體制。

也稱為塊密碼體制，分組密碼則是將明文信息分成各組或者說各塊，每組具有固定的長(zhǎng)度，然后將一個(gè)分組作為整體通過加密算法產(chǎn)生對(duì)應(yīng)密文的處理方式。2023/2/535第2章密碼學(xué)基礎(chǔ)1.按加密方式劃分

⑴流密碼明文m寫成連續(xù)的符號(hào)m=m1m2…，密鑰流k=k1k2…第i個(gè)元素ki對(duì)明文中的第i個(gè)元素mi進(jìn)行加密，加密后的密文c=Ek(m)=Ek1(m1)Ek2(m2)…Eki(mi)…。解密后：m=Dk(c)=Dk1(Ek1(m1))Dk2(Ek2(m2))…=m1m2…。2023/2/536第2章密碼學(xué)基礎(chǔ)1.按加密方式劃分

⑴流密碼加密算法E解密算法D明文mi密文ci=Eki(mi)明文mi=Dki(ci)密鑰ki密鑰ki2023/2/537第2章密碼學(xué)基礎(chǔ)⑴分組密碼2023/2/538第2章密碼學(xué)基礎(chǔ)2.按使用的密鑰方式劃分

（1）單密鑰體制。也稱為對(duì)稱密碼機(jī)制，在該體制下，密碼系統(tǒng)只有一個(gè)密鑰，加密算法和解密算法使用統(tǒng)一的一個(gè)密鑰，擁有密鑰的用戶既可以加密信息也可以解密信息。（2）雙密鑰體制。也稱為非對(duì)稱密碼體制或者公鑰密碼體制，在該體制下，密碼系統(tǒng)有兩個(gè)密鑰，分別是公開密鑰和私有密鑰，公開密鑰是對(duì)外公開的，即所有的人都可知，私有密鑰是只有特定的用戶方能擁有。2023/2/539第2章密碼學(xué)基礎(chǔ)3.按保密程度劃分

（1）實(shí)際上保密的密碼體制。是指在理論上可破解，但是在現(xiàn)有的客觀條件下以及有限的時(shí)間內(nèi)，無法通過計(jì)算從密文破譯出明文或者密鑰的密碼體制。（2）絕對(duì)保密的密碼體制。是指無論在理論上還是實(shí)際上，都不可破解的密碼體制。2023/2/540第2章密碼學(xué)基礎(chǔ)2.1.4密碼系統(tǒng)設(shè)計(jì)的基本原則

（1）簡(jiǎn)單實(shí)用原則。（2）抗攻擊性原則。（3）算法公開化原則。2023/2/541第2章密碼學(xué)基礎(chǔ)2.1.5密碼系統(tǒng)攻擊及分析

對(duì)密碼系統(tǒng)的攻擊分為被動(dòng)攻擊和主動(dòng)攻擊被動(dòng)攻擊是指通過竊取密文試圖了解明文或者密鑰的內(nèi)容；主動(dòng)攻擊是指篡改和偽造密文，以達(dá)到修改或者偽造明文的目的。被動(dòng)攻擊的主要方法有：通過竊聽通信信道上傳輸?shù)拿芪?，?duì)其進(jìn)行分析破譯出明文為或者密鑰；

主動(dòng)攻擊的主要方法有：攻擊者截取通信信道上傳輸?shù)拿芪?，然后?duì)其篡改（如添加、刪除某些內(nèi)容）再發(fā)送2023/2/542第2章密碼學(xué)基礎(chǔ)2.2傳統(tǒng)對(duì)稱密碼體制

在公鑰密碼體制出現(xiàn)以前，無論是古典密碼還是近現(xiàn)代密碼都屬于對(duì)稱密碼體制，也就是說加密和解密使用同一個(gè)密鑰。2.2.1加解密的基本原理

2.2.2數(shù)據(jù)加密標(biāo)準(zhǔn)DES

2.2.3高級(jí)加密標(biāo)準(zhǔn)AES2023/2/543第2章密碼學(xué)基礎(chǔ)2.2.1加解密的基本原理基于對(duì)明文信息的“置換”和“替代”完成的，或者是通過對(duì)兩者的組合運(yùn)用即乘積的方式完成。2023/2/544第2章密碼學(xué)基礎(chǔ)1.置換置換又稱“換位”方法，是指變換明文中各元素的相對(duì)位置，但保持其內(nèi)容不變的方法，即通過對(duì)明文元素重新排列組合來達(dá)到隱藏明文原始內(nèi)容所表達(dá)含義的加密方法。最典型的置換密碼體制是柵欄密碼技術(shù)。2023/2/545第2章密碼學(xué)基礎(chǔ)1.置換柵欄加密算法步驟如下：①將明文的元素按照兩行的方式書寫，并按照從上到下，從左到右的方式排列；②按從上到下的順序依次讀出每一行的元素所得到的組合就是密文。2023/2/546第2章密碼學(xué)基礎(chǔ)1.置換柵欄解密算法步驟如下：①將接收到的密文按照從左到右的順序?qū)憺閮尚校绻芪脑氐膫€(gè)數(shù)為偶數(shù)n，則每一行寫n/2個(gè)元素；如果密文元素個(gè)數(shù)為奇數(shù)，則第一行排列[n+1]/2個(gè)元素，第二行排列[n-1]/2個(gè)元素；②按照加密算法的規(guī)則，依次從上到下，從左到右的規(guī)則讀取各元素，所得到的字母序列即獲得所需要的明文。2023/2/547第2章密碼學(xué)基礎(chǔ)1.置換2023/2/548第2章密碼學(xué)基礎(chǔ)1.置換一種改進(jìn)的方案是將明文元素以矩陣的方式排列，假設(shè)明文可以寫成nm的n行m階的矩陣，矩陣法:①按照nm的矩陣格式從左到右依次寫出明文元素；②根據(jù)密鑰的內(nèi)容指示，讀出相應(yīng)各列的明文元素；③所有讀出的元素按一行的順序排列，得到的結(jié)果即為密文。

2023/2/549第2章密碼學(xué)基礎(chǔ)1.置換例如：2023/2/550第2章密碼學(xué)基礎(chǔ)1.置換矩陣法解密算法是：①根據(jù)密鑰長(zhǎng)度將密文寫成矩陣形式，但書寫的格式是按照逐列寫，各列之間的排列順序參照密鑰內(nèi)容的編號(hào)；②依次讀取排列好的矩陣逐行元素，得到的結(jié)果就是明文。2023/2/551第2章密碼學(xué)基礎(chǔ)1.置換2023/2/552第2章密碼學(xué)基礎(chǔ)1.置換置換法破譯:通過字母的使用頻率破譯2023/2/553第2章密碼學(xué)基礎(chǔ)2.替代替代方法是將明文各元素的內(nèi)容用新的符號(hào)或者符號(hào)組合代替，替換之后形成的新的元素符號(hào)集合便是密文。ABCDEFGH……VWXYZFGHIJKLM……ABCDE2023/2/554第2章密碼學(xué)基礎(chǔ)2.替代——密碼分析給定加密信息：PHHWPHDIWHUWKHSDUWB由于：①加密算法已知②可能嘗試的密鑰只有26個(gè)通過強(qiáng)力攻擊得到明文：Meetmeaftertheparty替代法容易受到攻擊!2023/2/555第2章密碼學(xué)基礎(chǔ)2.2.1加解密的基本原理將置換和替換兩者交替使用的密碼編碼方法稱為乘積密碼Feistel密碼結(jié)構(gòu)就是乘積密碼Feistel密碼結(jié)構(gòu)經(jīng)過多輪循環(huán)的置換與替代操作現(xiàn)在普遍使用的分組密碼體制設(shè)計(jì)原理幾乎都遵循Feistel密碼結(jié)構(gòu)，如經(jīng)典的數(shù)據(jù)加密標(biāo)準(zhǔn)DES。2023/2/556第2章密碼學(xué)基礎(chǔ)2.2.2數(shù)據(jù)加密標(biāo)準(zhǔn)DES2023/2/557第2章密碼學(xué)基礎(chǔ)1.DES的產(chǎn)生

1972年，美國(guó)標(biāo)準(zhǔn)局NBS（現(xiàn)在的NIST）公開征求用于計(jì)算機(jī)通信數(shù)據(jù)保密的方案，其要求為：①算法必須提供高度的安全性；②算法必須有詳細(xì)的說明，并易于理解；③算法的安全性取決于密鑰，不依賴于算法；④算法適用于所有用戶；⑤算法適用于不同應(yīng)用場(chǎng)合；⑥算法必須高效、經(jīng)濟(jì)；⑦算法必須能被證實(shí)有效；⑧算法必須可出口。2023/2/558第2章密碼學(xué)基礎(chǔ)1.DES的產(chǎn)生IBM公司的W.Tuchman和C.Meyers等研究人員提交了一個(gè)數(shù)據(jù)加密算法Lucifer該算法被美國(guó)標(biāo)準(zhǔn)局采用，在經(jīng)過一系列的研究討論和簡(jiǎn)單的修改于1977年正式批為數(shù)據(jù)加密標(biāo)準(zhǔn)DES。2023/2/559第2章密碼學(xué)基礎(chǔ)2.DES算法基本原理

DES屬于典型的分組密碼體制。DES將明文信息按64比特大小分組，密鑰長(zhǎng)度也是64比特，但是實(shí)際使用過程中密鑰長(zhǎng)度是56比特，另外8比特用作奇偶校驗(yàn)位（即每個(gè)字節(jié)的最后一位用作奇偶校驗(yàn)）。64比特的明文分組在密鑰的作用下經(jīng)過多次的置換和替代組合操作，最終形成攻擊者難以破譯的64比特密文。2023/2/560第2章密碼學(xué)基礎(chǔ)2.DES算法基本原理

置換和替代的多次組合過程多輪循環(huán)加密來擾亂和擴(kuò)散明文信息

2023/2/561第2章密碼學(xué)基礎(chǔ)2.DES算法基本原理

DES算法加密的基本原理：⑴加密過程中輸入64比特的明文，首先經(jīng)過初始矩陣IP置換；⑵在56比特的輸入密鑰控制下，進(jìn)行16輪迭代加密處理過程；⑶通過簡(jiǎn)單的換位和逆置換算法，得到64比特的輸出密文。2023/2/562第2章密碼學(xué)基礎(chǔ)2.DES算法基本原理

DES算法加密的基本原理：2023/2/563第2章密碼學(xué)基礎(chǔ)2.DES算法基本原理

DES算法解密的基本原理：解密處理過程與加密處理過程順序完全一樣加密過程：K1=K’16解密過程：K’1=K162023/2/564第2章密碼學(xué)基礎(chǔ)3.算法加密具體過程DES加密算法主要由4個(gè)元素組成：初始置換矩陣IP、加密函數(shù)F、S-盒子、逆初始置換矩陣IP-1。

2023/2/565第2章密碼學(xué)基礎(chǔ)3.算法加密具體過程初始置換：初始置換矩陣IP

2023/2/566第2章密碼學(xué)基礎(chǔ)3.算法加密具體過程初始置換：由置換矩陣可知置換規(guī)則：將原先處在第58位置的比特置換后放在第1個(gè)位置，第50位置的比特置換后放在第2個(gè)位置，第7個(gè)位置的比特置換后放在第64個(gè)位置。如果明文M分組是序列m1m2m3

….m64，則經(jīng)過IP置換后變成序列m58m50m42

….m7。2023/2/567第2章密碼學(xué)基礎(chǔ)3.算法加密具體過程初始置換：舉例，假設(shè)64比特明文M是：按照初始置換矩陣IP的變換規(guī)則，將M變換為M1，M1序列是：2023/2/568第2章密碼學(xué)基礎(chǔ)3.算法加密具體過程M寫成88的矩陣，如表2-7所示。初始置換后如表2-8所示2023/2/569第2章密碼學(xué)基礎(chǔ)3.算法加密具體過程通過比較表2-7與表2-8，可以發(fā)現(xiàn)，M由置換矩陣IP變換到M1遵循一定的規(guī)律：矩陣M1的第1行是矩陣M的第2列的倒置，第2行是矩陣M的第4列倒置，第5行是矩陣M的第1列的倒置。概括的說，置換后的矩陣M1前4行是明文矩陣M各偶數(shù)列的倒置，后4行是明文矩陣M各奇數(shù)列的倒置。2023/2/570第2章密碼學(xué)基礎(chǔ)3.算法加密具體過程再次對(duì)照逆初始矩陣IP-1（如表2-6所示）可發(fā)現(xiàn)，將M1前4行各行的倒置作為新矩陣M2的偶數(shù)列，后4行各行的倒置作為新矩陣M2的奇數(shù)列，會(huì)得到結(jié)果M=M2。也就是說將任何明文M經(jīng)過初始矩陣IP置換，然后再經(jīng)過逆初始矩陣IP-1的置換，M的值保持不變

2023/2/571第2章密碼學(xué)基礎(chǔ)3.算法加密具體過程每輪迭代加密處理過程：

DES算法加密過程需要16輪迭代處理，每一輪迭代的處理步驟是一樣的，只是輸入的信息和控制密鑰不同，第i輪加密處理過程如圖2-3所示。2023/2/572第2章密碼學(xué)基礎(chǔ)3.算法加密具體過程2023/2/573第2章密碼學(xué)基礎(chǔ)3.算法加密具體過程F函數(shù)是DES算法的精髓，它是多個(gè)置換函數(shù)和替代函數(shù)的組合函數(shù)，該函數(shù)以密鑰和上一輪加密得到的部分結(jié)果作為輸入，通過多次擴(kuò)展、置換和替代達(dá)到真正“擾亂”明文信息的目的。F函數(shù)分為擴(kuò)展、異或運(yùn)算、S盒替代以及置換四個(gè)步驟。2023/2/574第2章密碼學(xué)基礎(chǔ)3.算法加密具體過程⑴擴(kuò)展

F函數(shù)首先將32比特的數(shù)據(jù)Ri-1預(yù)擴(kuò)展為48比特，其方法是：將Ri-1從左到右分成8塊，每塊4比特，然后將每塊從4比特?cái)U(kuò)展到6比特。擴(kuò)展的規(guī)則是：每一塊向左擴(kuò)展一位，同時(shí)向右擴(kuò)展一位，也就是說，第n塊向左擴(kuò)展一位，與第n-1塊未擴(kuò)展前的最后一位相同，同時(shí)向右擴(kuò)展一位，與第n+1塊未擴(kuò)展前的最后一位相同；2023/2/575第2章密碼學(xué)基礎(chǔ)3.算法加密具體過程例如由表2-8所知的序列M1，得到加密時(shí)的L0和R0分別是：首先將R0

分為8塊，得到數(shù)據(jù)：1001011101010110101110011100000，如圖2-4所示，2023/2/576第2章密碼學(xué)基礎(chǔ)3.算法加密具體過程2023/2/577第2章密碼學(xué)基礎(chǔ)3.算法加密具體過程⑵異或運(yùn)算：由圖2-3所示，經(jīng)過擴(kuò)展后的48比特Ri-1

將與第i輪加密密鑰Ki進(jìn)行異或運(yùn)算，密鑰Ki

也是48位，由原始密鑰經(jīng)過循環(huán)左移以及置換排列的方式產(chǎn)生，具體的生成過程后面將詳細(xì)描述。

48位的Ki同Ri-1

一樣，也分成8塊，每塊6比特，然后與擴(kuò)展后的Ri-1

對(duì)應(yīng)的各塊做異或運(yùn)算后，同樣生成8個(gè)6位比特塊，其輸出是S盒子的輸入。

2023/2/578第2章密碼學(xué)基礎(chǔ)3.算法加密具體過程假設(shè)密鑰Ki的第1塊6比特?cái)?shù)據(jù)為：110111，圖2-4所示的第一塊擴(kuò)展比特是010010，則兩者異或的結(jié)果是1001012023/2/579第2章密碼學(xué)基礎(chǔ)3.算法加密具體過程⑶S盒替代

DES算法中的S盒子由8個(gè)子盒S1、S2、S3

、S4

、S5、S6、S7、S8組成，每個(gè)盒子構(gòu)成4行16階的416矩陣，表2-9列出了其中一個(gè)子盒S1的定義。

2023/2/580第2章密碼學(xué)基礎(chǔ)3.算法加密具體過程2023/2/581第2章密碼學(xué)基礎(chǔ)3.算法加密具體過程S盒子的輸入是上述所講的由Ri-1與Ki

兩者異或運(yùn)算得到的結(jié)果，其中第j個(gè)子盒Sj的輸入是第j塊異或運(yùn)算的結(jié)果，輸出是根據(jù)Sj盒子定義得到的4比特?cái)?shù)據(jù)。2023/2/582第2章密碼學(xué)基礎(chǔ)3.算法加密具體過程對(duì)于每個(gè)盒子Sj

（j=1,2….8）其輸入與輸出之間的映射關(guān)系是：將Sj輸入的第一位與最后一位兩個(gè)二進(jìn)制組合起來，得到某個(gè)十進(jìn)制數(shù)m，m用來選擇矩陣Sj的行；Sj輸入的中間四比特?cái)?shù)據(jù)組合，得到十進(jìn)制數(shù)n，n用來選擇矩陣Sj的列。已知行m與列n，查找已經(jīng)定義好的矩陣Sj

的m行n列對(duì)應(yīng)的值，該值就是Sj的輸出。2023/2/583第2章密碼學(xué)基礎(chǔ)3.算法加密具體過程對(duì)應(yīng)前面敘述的例子，S1盒子的輸入是F函數(shù)第二步異或運(yùn)算所得結(jié)果，為數(shù)據(jù)100101，S1盒子的輸出通過表2-9確定，具體的方法是：將輸入的第1位“1”與第6位“1”構(gòu)成二進(jìn)制數(shù)“11”，“11”表示十進(jìn)制數(shù)3，即要選擇矩陣S1的第3行，輸入的中間四位二進(jìn)制數(shù)“0010”，表示十進(jìn)制數(shù)2，即要選擇矩陣S1的第2列，在表2-4中，第3行第2列對(duì)應(yīng)的二進(jìn)制數(shù)是10002023/2/584第2章密碼學(xué)基礎(chǔ)3.算法加密具體過程⑷置換F函數(shù)的最后一步是對(duì)S盒子輸出的32比特?cái)?shù)據(jù)進(jìn)行置換，目的是使得S盒的輸出對(duì)下一輪多個(gè)Si子盒產(chǎn)生影響，以增強(qiáng)DES的安全性。F函數(shù)的輸出結(jié)果與上一輪加密處理的左半部分?jǐn)?shù)據(jù)Li-1異或，得到第i輪加密處理的右半部分32位數(shù)據(jù)Ri。然后Li與Ri又作為第i+1輪加密處理時(shí)的輸入數(shù)據(jù)，這樣，經(jīng)過16輪迭代加密處理之后，得到L16

與R16。

2023/2/585第2章密碼學(xué)基礎(chǔ)3.算法加密具體過程將R16

與L16

左右換位，即將R16的32比特?cái)?shù)據(jù)移到左邊，L16的32比特?cái)?shù)據(jù)移到右邊。換位之后，再次經(jīng)過逆初始矩陣IP-1置換，最終得到的結(jié)果就是密文。2023/2/586第2章密碼學(xué)基礎(chǔ)4.DES算法解密過程

DES的解密算法與加密算法除了在每一輪循環(huán)迭代時(shí)所使用的控制密鑰不同之外，其他的完全一樣。并且，輸出的64比特密文經(jīng)過解密處理過程，所得結(jié)果就是所需的明文。2023/2/587第2章密碼學(xué)基礎(chǔ)5.密鑰的生成DES算法定義的分組長(zhǎng)度是64比特，其主密鑰長(zhǎng)度與明文分組長(zhǎng)度一樣，也是64比特，不過在實(shí)際使用中，只用到56比特，還有8比特用作奇偶校驗(yàn)位。每輪迭代所使用的密鑰Ki（i=1,2….16）都是從主密鑰生成的，Ki的長(zhǎng)度是48比特。密鑰的具體生成方法如圖2-5所示：2023/2/588第2章密碼學(xué)基礎(chǔ)5.密鑰的生成2023/2/589第2章密碼學(xué)基礎(chǔ)6.DES算法安全性分析關(guān)于DES算法的安全性，在最初公布的時(shí)候，曾受到很多人的置疑。攻擊者會(huì)很容易的破譯DES算法密鑰更多的人擔(dān)心保密設(shè)計(jì)的S盒子的安全性很多用戶擔(dān)心S盒子存在隱藏的弱點(diǎn)2023/2/590第2章密碼學(xué)基礎(chǔ)6.DES算法安全性分析DES算法為什么需要16次循環(huán)迭代？而不是15次或者更多的20次呢？不能一味的為了防止攻擊者破譯密碼，不斷增加循環(huán)迭代次數(shù)，否則算法的效率與性能將會(huì)受到影響較少的迭代次數(shù)又會(huì)導(dǎo)致攻擊者容易分析密碼算法，從而破譯出密鑰。2023/2/591第2章密碼學(xué)基礎(chǔ)6.DES算法安全性分析DES算法使用56位密鑰是否安全?上世紀(jì)70年代,DES被廣泛使用在安全級(jí)別要求不高的場(chǎng)合。但是20世紀(jì)90年代以來，從計(jì)算上講，56位密鑰的DES不能再認(rèn)為是安全的。

2023/2/592第2章密碼學(xué)基礎(chǔ)2.2.3高級(jí)加密標(biāo)準(zhǔn)AES1.

AES的起源2.

AES的設(shè)計(jì)原則2023/2/593第2章密碼學(xué)基礎(chǔ)1.AES的起源1997年9月，NIST征集AES方案，以替代DES。1999年8月，以下5個(gè)方案成為最終候選方案：MARS,RC6,Rijndael,Serpent,Twofish。2000年10月，由比利時(shí)的JoanDaemen和VincentRijmen提出的算法最終勝出。（Rijndael讀成RainDoll。）2000年12月，美國(guó)國(guó)家標(biāo)準(zhǔn)局NIST正式確認(rèn)新一代數(shù)據(jù)加密標(biāo)準(zhǔn)是高級(jí)加密標(biāo)準(zhǔn)AES(AdvancedEncryptionStandard)。2023/2/594第2章密碼學(xué)基礎(chǔ)2.AES的設(shè)計(jì)原則能抵抗所有已知的攻擊；在各種平臺(tái)上易于實(shí)現(xiàn)，速度快；設(shè)計(jì)簡(jiǎn)單，是一種分組密碼體制，加密和解密使用相同的密鑰，屬于對(duì)稱密碼體制；與DES分組密碼體制不同的是，AES中明文或密文分組長(zhǎng)度以及密鑰長(zhǎng)度不是固定的，而是可變的，它們可以是128比特、192比特、256比特。2023/2/595第2章密碼學(xué)基礎(chǔ)2.3公鑰密碼體制2.3.1

公鑰密碼體制的基本原理2.3.2

RSA算法2.3.3有限域上橢圓曲線密碼算法ECC2.3.4公鑰密碼體制的應(yīng)用2023/2/596第2章密碼學(xué)基礎(chǔ)古老的密碼學(xué)問題

很久以前，分別有兩個(gè)國(guó)家的公主和王子，公主要通過一位信使送給王子一樣不愿被別人看見的信物，所以公主用加鎖的箱子放信物。這位信使只愿意跑一趟，而且在這段路程中，只要一有機(jī)會(huì)（鑰匙）就會(huì)偷看信物。問題：公主如何才能把信物安全的送到王子的手中？2023/2/597第2章密碼學(xué)基礎(chǔ)解決辦法：讓兩個(gè)國(guó)家的每一個(gè)人都具有兩副鎖和鑰匙，每幅各有一把鎖和一把鑰匙。每一把鎖和它不配套的鑰匙放在一起，這樣每個(gè)人就有兩副不配套的鑰匙和鎖了。將其中的一幅秘密留在家里（秘密鎖鑰）；另一幅拿到鎖廠，復(fù)制60億副，讓國(guó)家人人都能從市場(chǎng)上買到它（公開鎖鑰）。2023/2/598第2章密碼學(xué)基礎(chǔ)首先假設(shè)：公主的秘密鎖鑰（Ab）,公開鎖鑰（Ba）

王子的秘密鎖鑰（Cd）,公開鎖鑰（Dc）公主：送的箱子上共鎖著兩把鎖（DA）王子：（Ba）——（A）（Cd）——（D）2023/2/599第2章密碼學(xué)基礎(chǔ)2.3.1公鑰密碼體制的基本原理1976年，狄菲和海爾曼提出了密碼體制的新概念—公鑰密碼。使用兩個(gè)密鑰：公密鑰、私密鑰加解密的非對(duì)稱性，是對(duì)對(duì)稱密碼的重要補(bǔ)充利用數(shù)論與其他數(shù)學(xué)難題的方法2023/2/5100第2章密碼學(xué)基礎(chǔ)2.3.1公鑰密碼體制的基本原理重要特點(diǎn)僅根據(jù)加密算法和加密密鑰來確定解密密鑰在計(jì)算上不可行兩個(gè)密鑰中的任何一個(gè)都可用來加密，另一個(gè)用來解密。六個(gè)組成部分：明文、密文；公鑰、私鑰；加密、解密算法2023/2/5101第2章密碼學(xué)基礎(chǔ)序號(hào)對(duì)稱密碼公鑰密碼1加密和解密使用相同的密鑰加密和解密使用不同密鑰2密鑰必須保密存放私鑰保密存放，公鑰公開存放3通信前，收發(fā)雙方必須實(shí)現(xiàn)密鑰共享通信前，收發(fā)雙方無需實(shí)現(xiàn)密鑰共享4應(yīng)用于數(shù)據(jù)加解密、可以實(shí)現(xiàn)數(shù)據(jù)保密性、認(rèn)證等安全服務(wù)應(yīng)用于數(shù)據(jù)加解密、數(shù)字簽名、密鑰交換等方面，實(shí)現(xiàn)數(shù)據(jù)保密、認(rèn)證、數(shù)據(jù)完整性、不可否認(rèn)性等安全服務(wù)2023/2/5102第2章密碼學(xué)基礎(chǔ)2.3.1公鑰密碼體制的基本原理1.公鑰密碼體制依賴的基礎(chǔ)2.公鑰密碼系統(tǒng)的特征3.公鑰密碼體制加解密過程2023/2/5103第2章密碼學(xué)基礎(chǔ)1.公鑰密碼體制依賴的基礎(chǔ)經(jīng)典的公鑰密碼算法RSA、橢圓曲線密碼算法ECC等都是依賴某類數(shù)學(xué)問題的，它們共同的特點(diǎn)是基于某個(gè)單向陷門函數(shù)。2023/2/5104第2章密碼學(xué)基礎(chǔ)單向陷門函數(shù)y=fk(x)是指同時(shí)滿足下列條件的一類可逆函數(shù)：⑴函數(shù)是一一映射關(guān)系，一個(gè)y對(duì)應(yīng)唯一的一個(gè)x；⑵給定x與關(guān)鍵參數(shù)k,函數(shù)y=fk(x)很容易計(jì)算；2023/2/5105第2章密碼學(xué)基礎(chǔ)1.公鑰密碼體制依賴的基礎(chǔ)⑶給定y，存在某個(gè)關(guān)鍵參數(shù)k’，在未知k’時(shí)，逆函數(shù)x=f-1(y)的計(jì)算相當(dāng)復(fù)雜，實(shí)際上是不可行的；在已知k’時(shí)，則逆函數(shù)x=f-1k’(y)很容易計(jì)算；⑷給定y和參數(shù)k，無法從函數(shù)y=fk(x)推導(dǎo)出影響其逆函數(shù)f-1的關(guān)鍵參數(shù)k’。2023/2/5106第2章密碼學(xué)基礎(chǔ)2.公鑰密碼系統(tǒng)的特征根據(jù)密碼系統(tǒng)的組成以及公鑰密碼體制自身的特點(diǎn)，一個(gè)公鑰密碼系統(tǒng)可以表示為：加密算法E、解密算法D、公鑰/私鑰(PK/SK)對(duì)、明文M、密文C六個(gè)元素，且各元素必須要滿足以下條件：2023/2/5107第2章密碼學(xué)基礎(chǔ)2.公鑰密碼系統(tǒng)的特征⑴密鑰要滿足三點(diǎn)要求：公鑰/私鑰(PK/SK)對(duì)容易產(chǎn)生，且私鑰除了生成密鑰的用戶自己知道之外，其他任何人都不可知；PK和SK中的任何一個(gè)都可以用于加密，相應(yīng)的另一個(gè)用于解密；從公開密鑰PK無法通過計(jì)算得到私有密鑰SK。2023/2/5108第2章密碼學(xué)基礎(chǔ)2.公鑰密碼系統(tǒng)的特征⑵

加密算法E要滿足兩點(diǎn)要求：已知公鑰PK，對(duì)任何明文M，由E計(jì)算出密文C非常容易，即C=EPK(M)易計(jì)算已知私鑰SK，對(duì)任何信息M，由E計(jì)算數(shù)字簽名也非常容易，即C=ESK(M)易計(jì)算。2023/2/5109第2章密碼學(xué)基礎(chǔ)2.公鑰密碼系統(tǒng)的特征⑶解密算法D要求：

僅知道解密算法以及加密密鑰，推導(dǎo)明文和解密密鑰都是計(jì)算不可行的。2023/2/5110第2章密碼學(xué)基礎(chǔ)3.公鑰密碼體制加解密過程假設(shè)網(wǎng)絡(luò)上的兩個(gè)用戶Alice和Bob需要進(jìn)行秘密通信，為了防止攻擊者Eve竊聽信息，Alice和Bob選擇使用公鑰密碼體制加密傳輸?shù)男畔?。Alice是信息的發(fā)送方；Bob是信息的接收方。⑴Alice與Bob產(chǎn)生公鑰/私鑰對(duì)：PKA/SKA，PKB/SKB。2023/2/5111第2章密碼學(xué)基礎(chǔ)3.公鑰密碼體制加解密過程⑵Alice與Bob通過某種機(jī)制公布各自的公鑰PKA與PKB，例如將公鑰放到一個(gè)公共的服務(wù)器，供其他用戶查詢。2023/2/5112第2章密碼學(xué)基礎(chǔ)3.公鑰密碼體制加解密過程⑶Alice通過查詢公共服務(wù)器獲得Bob的公鑰PKB。如果Alice欲給Bob發(fā)送報(bào)文M，他就用Bob的公鑰PKB加密報(bào)文。已知待加密的明文M以及Bob的公鑰PKB，Alice很容易通過加密算法E計(jì)算出密文，即C=EPKB(M)。2023/2/5113第2章密碼學(xué)基礎(chǔ)3.公鑰密碼體制加解密過程接收方Bob收到Alice發(fā)送的信息之后，使用自己的私鑰SKB解密報(bào)文。已知密文C私鑰SKB，Bob很容易通過解密算法計(jì)算出明文M，即M=DSKB(C)。2023/2/5114第2章密碼學(xué)基礎(chǔ)如果反過來呢？Bob發(fā)送給Alice信息該如何加密信息呢？2023/2/5115第2章密碼學(xué)基礎(chǔ)用公鑰進(jìn)行加密2Alice產(chǎn)生一對(duì)密鑰，用于加密和解密3Alice將一個(gè)密鑰公開，另一個(gè)密鑰私有BobAlice1Bob要發(fā)送消息給Alice4Bob用Alice的公鑰對(duì)消息加密，發(fā)送給Alice。只有Alice能解密2023/2/5116第2章密碼學(xué)基礎(chǔ)2.3.2RSA算法1.RSA算法依賴的數(shù)學(xué)問題2.RSA算法密鑰產(chǎn)生過程3.RSA算法加解密過程4.RSA算法安全性及性能分析2023/2/5117第2章密碼學(xué)基礎(chǔ)RSA算法由MIT的Rivest,Shamir&Adleman在1977提出最著名的且被廣泛應(yīng)用的公鑰加密體制明文、密文是0到n-1之間的整數(shù)，通常n的大小為1024位二進(jìn)制或309位十進(jìn)制數(shù)2023/2/5118第2章密碼學(xué)基礎(chǔ)2023/2/5119第2章密碼學(xué)基礎(chǔ)1.RSA算法依賴的數(shù)學(xué)問題⑴模運(yùn)算的性質(zhì)：正整數(shù)n是素?cái)?shù)，集合Zn={0，1，2….，(n-1)}表示小于n的所有非負(fù)整數(shù)集合，則對(duì)于集合Zn中的每一個(gè)整數(shù)wZn，均存在一個(gè)z，滿足公式w×z=1modn，我們稱z是w的乘法逆元，且n是它們的模。2023/2/5120第2章密碼學(xué)基礎(chǔ)1.RSA算法依賴的數(shù)學(xué)問題⑵費(fèi)馬定理：如果p是素?cái)?shù)，a是不能整除p的正整數(shù)，則：ap-1≡1modp例如：P=7，a=2，則27-1=26=64，64mod7=12023/2/5121第2章密碼學(xué)基礎(chǔ)1.RSA算法依賴的數(shù)學(xué)問題⑶歐拉函數(shù)：正整數(shù)n的歐拉函數(shù)是指小于n且與n互素的正整數(shù)個(gè)數(shù)，通常記為?(n)。對(duì)于任一素?cái)?shù)p，顯然有：?(p)＝p–1，例如：設(shè)p=3，小于3且與3互素的正整數(shù)為1，2，因此?(3)=2；類似地，當(dāng)p=7時(shí)，小于7且與7互素的正整數(shù)為1，2，3，4，5，6，因此?(7)=62023/2/5122第2章密碼學(xué)基礎(chǔ)1.RSA算法依賴的數(shù)學(xué)問題假定有兩個(gè)不同的素?cái)?shù)p和q，n是p與q之積，即

n=p×q，則有如下公式關(guān)系：?(n)=?(pq)=?(p)×?(q)=(p-1)×(q-1)

例如：取n=21，?(21)=?(3)×?(7)=(3-1)×(7-1)=2×6=12，其中這12個(gè)整數(shù)是{1，2，4，5，8，10，11，13，16，17，19，20}2023/2/5123第2章密碼學(xué)基礎(chǔ)1.RSA算法依賴的數(shù)學(xué)問題⑷歐拉定理：任何兩個(gè)互素的整數(shù)a和n，有如下關(guān)系：

a?(n)=1modn例如：a=3；n=8；由(3)歐拉函數(shù)的定義，?(8)=4；則a?(n)=34=81=10×8+1≡1mod8≡1modn

2023/2/5124第2章密碼學(xué)基礎(chǔ)1.RSA算法依賴的數(shù)學(xué)問題歐幾里德(Elucid)算法：該算法主要的思想是：用一個(gè)簡(jiǎn)單的方法確定兩個(gè)正整數(shù)的最大公因子，并且如果這兩個(gè)整數(shù)互素，通過擴(kuò)展該算法能確定它們各自的逆元

2023/2/5125第2章密碼學(xué)基礎(chǔ)2.RSA算法密鑰產(chǎn)生過程(1)隨機(jī)選擇兩個(gè)大素?cái)?shù)p與q，且p×q=n。建議p與q長(zhǎng)度應(yīng)該只差幾個(gè)數(shù)字，且p與q應(yīng)該位于區(qū)間[1075..10100]內(nèi)(2)計(jì)算n的歐拉函數(shù)值：

?(n)=(p-1)×(q-1)

(3)隨機(jī)選擇一個(gè)大的正整數(shù)e，e滿足小于n且與?(n)互素的條件，即e與?(n)的最大公因子是12023/2/5126第2章密碼學(xué)基礎(chǔ)2.RSA算法密鑰產(chǎn)生過程(4)根據(jù)e，?(n)，計(jì)算另外一個(gè)值d，d是e的乘法逆元，且?(n)是它們的模，由模運(yùn)算的及乘法逆元的性質(zhì)，d×e=1mod?(n)則兩個(gè)二元組(e,n)、(d,n)構(gòu)成RSA的密鑰對(duì)，選擇其中任意一個(gè)二元組作為公鑰，則另外一個(gè)就為私鑰，在此，我們定義(e,n)為公鑰，(d,n)為私鑰。2023/2/5127第2章密碼學(xué)基礎(chǔ)2.RSA算法密鑰產(chǎn)生過程例如：1)令p=7，q=11，則n=77；2)計(jì)算n的歐拉函數(shù)值?(n)=(7-1)×(11-1)=60；3)選擇e=17，e符合小于77，且于歐拉函數(shù)值?(n)（?(n)=60）的最大公因子是1的條件；4）計(jì)算e的逆元d，因?yàn)?3×17=15×60+1≡1mod60，所以當(dāng)e=17時(shí)，d=53。

因此(17，77)/(53，77)構(gòu)成一個(gè)RSA的公鑰/私鑰對(duì)。

2023/2/5128第2章密碼學(xué)基礎(chǔ)3.RSA算法加解密過程RSA算法屬于分組加密方案，也就是說明文以分組為單位加密分組的大小取決于所選的模n的值，明文塊每個(gè)分組的長(zhǎng)度可以相同也可以不同，但是，各分組大小必須小于或等于log2(n)的值。2023/2/5129第2章密碼學(xué)基礎(chǔ)已知明文的某塊分組報(bào)文M，公鑰(e，n)，私鑰(d，n)，則加密過程如下：對(duì)M的e次方冪指數(shù)運(yùn)算結(jié)果再做模n運(yùn)算，所得結(jié)果即為密文C，即由M計(jì)算C用公式表示為：C=EpK(M)=Memodn（公式2.1）

2023/2/5130第2章密碼學(xué)基礎(chǔ)3.RSA算法加解密過程RSA算法加密和解密過程是等價(jià)的，解密過程如下：對(duì)C的d次方冪運(yùn)算結(jié)果再做模n運(yùn)算，所得結(jié)果即為明文M，即由C推導(dǎo)M可用公式表示為：M=DSK(M)=Cdmodn（公式2.2）2023/2/5131第2章密碼學(xué)基礎(chǔ)4.RSA算法安全性及性能分析RSA算法的安全性基于大整數(shù)因子分解的困難性，即給定大整數(shù)n，將n分解為兩個(gè)素?cái)?shù)因子p與q，在數(shù)學(xué)上已證明是難題，至今沒有有效的方法予以解決。RSA密碼方案的優(yōu)點(diǎn)在于原理簡(jiǎn)單，易于使用

2023/2/5132第2章密碼學(xué)基礎(chǔ)4.RSA算法安全性及性能分析缺點(diǎn)：RSA的性能比較低。硬件實(shí)現(xiàn)的效率是DES的1/1000，軟件實(shí)現(xiàn)的效率是DES的1/100，2023/2/5133第2章密碼學(xué)基礎(chǔ)RSA與DESRSA不適用于對(duì)長(zhǎng)的明文信息加密它常常與對(duì)稱密碼體制結(jié)合使用RSA用來加密通信雙方的會(huì)話密鑰對(duì)稱密碼體制如DES用來加密傳輸?shù)膱?bào)文2023/2/5134第2章密碼學(xué)基礎(chǔ)4.RSA算法安全性及性能分析為了安全起見，RSA方案中要求模數(shù)n越來越大RSA密鑰長(zhǎng)度要求大于1024比特才有安全保障密鑰長(zhǎng)度的增加提高了安全性，但是進(jìn)一步影響了算法的性能在選擇RSA密鑰時(shí)，在系統(tǒng)的安全性和性能之間需要找到一個(gè)平衡點(diǎn)2023/2/5135第2章密碼學(xué)基礎(chǔ)2.3.3有限域上橢圓曲線密碼算法ECC1985年NealKobiltz和Victormiller提出橢圓曲線密碼算法ECC（EllipticCurveCryptosystem）1.ECC算法依賴的數(shù)學(xué)問題2.ECC算法密鑰的選擇3.ECC算法的加解密過程4.ECC算法的安全性分析

2023/2/5136第2章密碼學(xué)基礎(chǔ)1.ECC算法依賴的數(shù)學(xué)問題⑴橢圓曲線定義：設(shè)K表示一個(gè)域,橢圓曲線E(K)用二元方程表示：y2+axy+by=x3+cx2+dx+e其中

a,b,c,d,e均屬于K域。在實(shí)際的密碼學(xué)研究中，主要應(yīng)用的是基于有限域上的橢圓曲線。具有q個(gè)元素的有限域上的橢圓曲線滿足下列方程關(guān)系：

y2=x3+ax+b2023/2/5137第2章密碼學(xué)基礎(chǔ)1.ECC算法依賴的數(shù)學(xué)問題⑵橢圓曲線上的點(diǎn)加運(yùn)算：設(shè)P、Q是E上任意兩點(diǎn)，R’是連接P,Q的直線L與E相交點(diǎn)，R’關(guān)于X軸的對(duì)稱節(jié)點(diǎn)是R，如圖2-6所示。根據(jù)橢圓曲線的對(duì)稱性，R必定在橢圓曲線E上定義：R=P+Q，R就是P與Q點(diǎn)加的和

2023/2/5138第2章密碼學(xué)基礎(chǔ)1.ECC算法依賴的數(shù)學(xué)問題2023/2/5139第2章密碼學(xué)基礎(chǔ)1.ECC算法依賴的數(shù)學(xué)問題如果P和Q相同，即P與Q是橢圓曲線的某一點(diǎn)，如圖2-7所示，則過P做橢圓的切線，該切線同E相交點(diǎn)為M’，M’關(guān)于X軸的對(duì)稱點(diǎn)M就是P+P的點(diǎn)加和，即M=P+P，我們將P+P記做M=[2]P，以此類推，n個(gè)P相加P+P+P…..+P記做[n]P，[n]P也稱為倍乘。根據(jù)橢圓曲線的性質(zhì)，[2]P、[3]P…..[n]P都是E上的點(diǎn)。2023/2/5140第2章密碼學(xué)基礎(chǔ)1.ECC算法依賴的數(shù)學(xué)問題2023/2/5141第2章密碼學(xué)基礎(chǔ)1.ECC算法依賴的數(shù)學(xué)問題⑶橢圓曲線離散對(duì)數(shù)問題給定橢圓曲線E及該橢圓曲線上的一點(diǎn)P，[k]P表示k個(gè)P相加，k為某整數(shù)，如果橢圓曲線上存在一點(diǎn)Q，能夠滿足方程Q=[k]P，那么橢圓曲線離散對(duì)數(shù)問題就是給定點(diǎn)P和點(diǎn)Q，求解k的問題，在數(shù)學(xué)上該問題是同時(shí)涉及整數(shù)因式分解和離散對(duì)數(shù)的難題。2023/2/5142第2章密碼學(xué)基礎(chǔ)1.ECC算法依賴的數(shù)學(xué)問題ECC算法就是基于“橢圓曲線離散對(duì)數(shù)問題”難以求解而設(shè)計(jì)的給定P和k容易通過方程Q=[k]P計(jì)算Q；但是反過來，給定Q和P，求k在計(jì)算上是不可行的，因此我們可以設(shè)定k為私鑰。

2023/2/5143第2章密碼學(xué)基礎(chǔ)2.ECC算法密鑰的選擇基于橢圓曲線密碼體制的ECC算法在加解密之前，首先要給出橢圓曲線域的一些參數(shù)，如基點(diǎn)P，階n，以確定具體的橢圓曲線。

ECC算法密鑰的產(chǎn)生是都是建立在某個(gè)有限域的橢圓曲線上，設(shè)給定一個(gè)具有q個(gè)元素有限域的橢圓曲線E，E的基點(diǎn)是P，P的階為n。2023/2/5144第2章密碼學(xué)基礎(chǔ)2.ECC算法密鑰的選擇（1）密鑰的產(chǎn)生者在區(qū)間[2，n-1]隨機(jī)選取某整數(shù)k；（2）

計(jì)算Q=[k]P。則Q就是公鑰，私鑰是k。2023/2/5145第2章密碼學(xué)基礎(chǔ)3.ECC算法的加解密過程假設(shè)網(wǎng)絡(luò)上的用戶Alice和Bob要進(jìn)行保密通信，它們選擇ECC算法加密通信的報(bào)文。Alice與Bob知道同一條橢圓曲線E，并已分別產(chǎn)生公鑰/私鑰對(duì)kA/QA，kB/QB，Alice欲發(fā)送明文m送給Bob，并且已獲知Bob的公鑰QB。2023/2/5146第2章密碼學(xué)基礎(chǔ)3.ECC算法的加解密過程

Alice加密過程如下：（1）首先要將明文m編碼成橢圓曲線上的點(diǎn)Pm，Pm為(Xm，Ym)；（2）

Alice隨機(jī)選擇整數(shù)k[2,n-1]；（3）計(jì)算[k]P=R1(X1，Y1)，（[k]QB=R2(X2，Y2）；如果X2=0；則返回到（2）；則密文C由{R1，Pm+R2}組成；2023/2/5147第2章密碼學(xué)基礎(chǔ)3.ECC算法的加解密過程

Bob收到密文C后，解密過程如下：（1）計(jì)算[kB]R1=[kB][k]P=[k][kB]P=[k]QB（2）Bob利用密文C的第二點(diǎn)的值R2+Pm

減去由（1）計(jì)算得到的結(jié)果[k]QB，即Pm+R2

[k]QB=

Pm+[k]QB

–[k]QB=Pm；（3）Bob得到橢圓曲線上點(diǎn)Pm，然后按照某種解碼方法從點(diǎn)Pm獲取明文m。2023/2/5148第2章密碼學(xué)基礎(chǔ)4.ECC算法的安全性分析

ECC算法的安全性依賴于橢圓曲線離散對(duì)數(shù)問題計(jì)算的困難性，如果離散對(duì)數(shù)問題容易計(jì)算，從用戶的公鑰能夠推導(dǎo)出私鑰，那么整個(gè)密碼體制就會(huì)坍塌。2023/2/5149第2章密碼學(xué)基礎(chǔ)4.ECC算法的安全性分析相對(duì)于RSA，ECC具有一定的優(yōu)勢(shì)：安全性高

解決橢圓曲線上的離散對(duì)數(shù)問題，其時(shí)間復(fù)雜度是完全指數(shù)階的，而RSA所依賴的大整數(shù)因子分解問題，其時(shí)間復(fù)雜度是子指數(shù)階的，因此攻擊ECC的復(fù)雜度比RSA要高得多；2023/2/5150第2章密碼學(xué)基礎(chǔ)4.ECC算法的安全性分析相對(duì)于RSA，ECC具有一定的優(yōu)勢(shì)：密鑰短

ECC算法中所使用的密鑰長(zhǎng)度比RSA中要短很多，一般加解密時(shí)使用160位長(zhǎng)度密鑰，據(jù)統(tǒng)計(jì)，160位密鑰ECC與1024位RSA安全強(qiáng)度相同性能高

ECC算法的性能比RSA算法要高，其加解密速度比RSA要快得多。2023/2/5151第2章密碼學(xué)基礎(chǔ)4.ECC算法的安全性分析2023/2/5152第2章密碼學(xué)基礎(chǔ)4.ECC算法的安全性分析RSA算法因?yàn)樵砗?jiǎn)單被廣泛使用ECC算法在實(shí)際應(yīng)用中相對(duì)比較少ECC算法理論不斷完善，會(huì)被應(yīng)用到實(shí)際系統(tǒng)中2023/2/5153第2章密碼學(xué)基礎(chǔ)2.3.4公鑰密碼體制的應(yīng)用1.用于加解密信息2.用于數(shù)字簽名2023/2/5154第2章密碼學(xué)基礎(chǔ)2.4量子密碼體制2.4.1概述2.4.2量子密碼原理2.4.3量子密鑰分配2.4.4量子密鑰分配協(xié)議BB842.4.5量子密碼體制的發(fā)展與現(xiàn)狀2.4.6三大密碼體制的比較2023/2/5155第2章密碼學(xué)基礎(chǔ)2.4.1概述對(duì)稱密碼體制與公鑰密碼體制絕大部分算法都是實(shí)際上保密的密碼體制，理論上并不保密。理論上唯一能確保不可破譯的密碼體制是一次一密密碼。該體制在實(shí)際應(yīng)用中是不可行的。

156現(xiàn)代密碼學(xué)中“不可破譯”的密碼

“一次一密”加密方式明文011010XOR110010

XOR=Exclusive-OR101000密文通道101000密文XOR110010011010明文如果 1）密鑰的長(zhǎng)度=信息的長(zhǎng)度

2）密鑰只使用一次“一次一密”原理上絕對(duì)安全

(Shannon1949)如何在發(fā)送者與接收者間建立密鑰？密鑰分配問題發(fā)送者Alice竊聽者Eve接收者Bob密鑰密鑰2023/2/5157第2章密碼學(xué)基礎(chǔ)2.4.1概述1996年，Bell試驗(yàn)室的LovGrover發(fā)現(xiàn)了一種量子搜索算法，該算法可以對(duì)現(xiàn)有的DES算法中的密鑰進(jìn)行快速窮舉，從而破譯出密鑰。因此不論是對(duì)稱密碼體制還是公鑰密碼體制，在量子計(jì)算環(huán)境下，安全性受到極大的威脅。為此，從事密碼學(xué)研究的專家就考慮到：利用量子通信中量子的性質(zhì)重新建立新的密碼體制，即量子密碼體制。2023/2/5158第2章密碼學(xué)基礎(chǔ)2.4.1概述1970年，美國(guó)科學(xué)家威斯納首次提出量子密碼技術(shù)，威斯納當(dāng)時(shí)的想法是利用單量子態(tài)制造不可偽造的“電子鈔票”。1984年，貝內(nèi)特和布拉薩德兩位學(xué)者提出了第一個(gè)量子密鑰分配方案BB84協(xié)議，標(biāo)志著量子密碼體制研究真正的開始。2023/2/5159第2章密碼學(xué)基礎(chǔ)2.4.1概述量子密碼是以量子力學(xué)和密碼學(xué)為基礎(chǔ)，利用量子物理學(xué)中的原理實(shí)現(xiàn)密碼體制的一種新型密碼體制。量子密碼利用信息載體的物理屬性實(shí)現(xiàn)。目前，量子密碼中用于承載信息的載體包括光子、壓縮態(tài)光信號(hào)、相干態(tài)光信號(hào)等。當(dāng)前量子密碼實(shí)驗(yàn)中，大多采用光子作為信息的載體。利用光子的偏振進(jìn)行編碼2023/2/5160第2章密碼學(xué)基礎(chǔ)2.4.1概述量子密碼體制的理論基礎(chǔ)是量子物理定理，理論上，依賴于這些物理定理的量子密碼也是不可攻破的，量子密碼體制是一種絕對(duì)保密的密碼體制。2023/2/5161第2章密碼學(xué)基礎(chǔ)2.4.2量子密碼原理

量子密碼利用測(cè)不準(zhǔn)原理和量子不可克隆原理，建立量子密鑰，該密鑰不會(huì)被任何攻擊者竊聽到，因?yàn)橥ㄐ烹p方在確定密鑰之前可以檢測(cè)信息是否被干擾過。1.海森堡測(cè)不準(zhǔn)原理2.量子不可克隆定理3.量子糾纏4.量子密碼安全性分析162信息與測(cè)量信息的獲取涉及測(cè)量過程；測(cè)量精度決定可獲取的信息量；經(jīng)典物理測(cè)量過程可以不改變被測(cè)物體狀態(tài)；竊聽者可以獲取信息而不被發(fā)現(xiàn)。量子物理測(cè)量過程一般會(huì)改變被測(cè)物體狀態(tài)（測(cè)不準(zhǔn)原理）；量子力學(xué)提供了探測(cè)竊聽的手段。2023/2/5163第2章密碼學(xué)基礎(chǔ)1.海森堡測(cè)不準(zhǔn)原理對(duì)任何量子系統(tǒng)都不可能進(jìn)行精確的測(cè)量而不改變其原有的狀態(tài)，即對(duì)量子系統(tǒng)的任何測(cè)量都會(huì)改變其量子態(tài)，并且這種轉(zhuǎn)變是不可預(yù)測(cè)、無法逆轉(zhuǎn)的。2023/2/5164第2章密碼學(xué)基礎(chǔ)2.量子不可克隆定理量子不可克隆定理的最初表述是Wootters和Zurek兩位學(xué)者于1982年提出來的，當(dāng)時(shí)，他們?cè)凇蹲匀弧冯s志上發(fā)表的一篇paper里提出了這樣的問題：是否存在一個(gè)物理過程，實(shí)現(xiàn)對(duì)一個(gè)未知量子態(tài)的精確復(fù)制，使得每個(gè)復(fù)制態(tài)與初始的量子態(tài)完全相同呢？Wootters和Zurek證明了不存在這樣的物理過程2023/2/5165第2章密碼學(xué)基礎(chǔ)2.量子不可克隆定理量子不可克隆原理是海森堡測(cè)不準(zhǔn)原理的推論，它是指在不知道量子態(tài)的情況下精確復(fù)制單個(gè)量子是不可能的，即未知態(tài)的單量子是不可精確復(fù)制的。2023/2/5166第2章密碼學(xué)基礎(chǔ)2.量子不可克隆定理量子不可克隆定理是量子力學(xué)的固有特性，量子力學(xué)以量子態(tài)作為信息載體，量子態(tài)不可精確復(fù)制是量子密碼體制的重要前提，它確保了量子密碼的“絕對(duì)保密”特性。2023/2/5167第2章密碼學(xué)基礎(chǔ)3.量子糾纏量子糾纏也是量子密碼學(xué)基本原理之一。所謂“量子糾纏”是指不論兩個(gè)粒子間距離有多遠(yuǎn)，一個(gè)粒子的變化總會(huì)影響另一個(gè)粒子的變化，即兩個(gè)粒子之間不論相距多遠(yuǎn)，從根本上講它們還是相互聯(lián)系的。2023/2/5168第2章密碼學(xué)基礎(chǔ)4.量子密碼安全性分析發(fā)送方與接收方在信息交互中通過比較各自的量子態(tài)，判斷通信信道上存在攻擊者2023/2/5169第2章密碼學(xué)基礎(chǔ)4.量子密碼安全性分析攻擊者利用物理上可行的量子復(fù)制機(jī)克隆發(fā)送方發(fā)送的量子態(tài)，仍無法獲得所需的量子比特信息。2023/2/5170第2章密碼學(xué)基礎(chǔ)2.4.3量子密鑰分配在傳統(tǒng)的通信信道上，不可能通過通信信道直接傳輸雙方共享的密鑰。量子密碼體制能為通信雙方提供可靠的密鑰分配手段。2023/2/5171第2章密碼學(xué)基礎(chǔ)2.4.3量子密鑰分配量子密碼學(xué)以量子態(tài)作為密鑰的編碼方式在實(shí)際實(shí)驗(yàn)操作中，光子常被用作量子密鑰的信息載體。172量子力學(xué)：測(cè)量過程對(duì)量子態(tài)產(chǎn)生擾動(dòng)量子密鑰分配的基本原理…10111000001101…10011010001101AliceBobEve量子編碼Errors隨機(jī)數(shù)發(fā)生器過高的比特誤碼率竊聽者的存在2023/2/5173第2章密碼學(xué)基礎(chǔ)2.4.3量子密鑰分配主要有以下三類量子密鑰的分配方案：1.基于兩種共軛基的量子密鑰分配方案2.基于兩個(gè)非正態(tài)的兩態(tài)量子密鑰分配方案3.基于EPR佯謬的糾纏態(tài)量子密鑰分配方案2023/2/5174第2章密碼學(xué)基礎(chǔ)2.4.4量子密鑰分配協(xié)議BB841984年，IBM公司的C.H.Bennett和蒙特利爾大學(xué)的GBrassard兩人共同提出量子密鑰分配協(xié)議BB84，1991年該協(xié)議通過實(shí)驗(yàn)得到了證實(shí)。主要介紹以下幾點(diǎn)內(nèi)容：1.物理學(xué)原理2.BB84協(xié)議具體工作過程3.BB84協(xié)議舉例2023/2/5175第2章密碼學(xué)基礎(chǔ)1.物理學(xué)原理根據(jù)物理學(xué)現(xiàn)象，光子有四個(gè)不同的偏振方向，分別是：水平方向、垂直方向、與水平成45°夾角、與水平成135°夾角。<，>構(gòu)成一組基，稱為線偏振，<，>構(gòu)成一組基，稱為斜偏振。線偏振和斜偏振是互補(bǔ)的，對(duì)某個(gè)光子，不可能同時(shí)用線偏振和斜偏振測(cè)量它，稱線偏振與斜偏振為共軛基。

2023/2/5178第2章密碼學(xué)基礎(chǔ)1.物理學(xué)原理同一基內(nèi)的兩個(gè)量子態(tài)是正交的，且其中的兩個(gè)偏振方向是可以區(qū)分的，即<，>中的兩個(gè)量子態(tài)是正交的，使用線偏振基測(cè)量時(shí)，能夠區(qū)分光子的水平偏振方向與垂直偏振方向；同理，<，>中的兩個(gè)量子態(tài)也是正交的。

2023/2/5179第2章密碼學(xué)基礎(chǔ)1.物理學(xué)原理假設(shè)發(fā)送者Alice發(fā)送的是偏振方向?yàn)榫€偏振光子，如果接收者Bob使用的是線偏振基<，>測(cè)量，那么測(cè)量結(jié)果就是水平偏振方向，換句話說，Bob選擇正確的測(cè)量基能得到所需的結(jié)果；如果接收者Bob使用的是斜偏振基<，>測(cè)量，那么Bob測(cè)得結(jié)果是隨機(jī)的，50%概率是與水平成45°夾角方向，50%概率是與水平成135°夾角方向。但是Bob自身并不得知其測(cè)量結(jié)果是正確的還是錯(cuò)誤的，除非他和Alice進(jìn)一步通信確認(rèn)其測(cè)量基的選擇是否正確。

180要點(diǎn)1利用單個(gè)量子態(tài)編碼：例如單個(gè)光子的偏振態(tài)。！Eve可以進(jìn)行“截取-測(cè)量-再發(fā)送”攻擊實(shí)例：BB84協(xié)議（1）101101“1”“0”AliceBob900偏振

比特值偏振分光鏡

單光子探測(cè)器181Alice

Bob

90101101“1”“0”基一101101“1”“0”基二/20135°45°實(shí)例：BB84協(xié)議（2）要點(diǎn)2:兩組非對(duì)易“基”Alice/Bob隨機(jī)改變“發(fā)送基”/“測(cè)量基”Alice/Bob只保留“相同基”的數(shù)據(jù)2023/2/5182第2章密碼學(xué)基礎(chǔ)2.BB84協(xié)議具體工作過程BB84協(xié)議主要思路分為兩個(gè)階段：第一階段在量子信道上單向的信息傳輸；第二階段在傳統(tǒng)公共信道上雙向的信息傳輸。如圖2-8所示，假設(shè)通信雙方分別是Alice和Bob，其中Alice是信息的發(fā)送方、Bob是信息的接收方，Eve是攻擊方。2023/2/5183第2章密碼學(xué)基礎(chǔ)2.BB84協(xié)議具體工作過程2023/2/5184第2章密碼學(xué)基礎(chǔ)2.BB84協(xié)議具體工作過程Alice和Bob事先要約定好各偏振方向所表示的二進(jìn)制比特，即表示的0還是1。在BB84協(xié)議中，一般規(guī)定水平偏振方向、斜偏振方向45°角表示比特“0”；線偏振垂直方向、斜偏振方向135°角表示比特“1”。Alice和Bob選擇的測(cè)量共軛基是（,），使用只能檢測(cè)到水平與垂直方向上的光子，使用只能檢測(cè)到與水平成45°度方向以及與水平成135°度方向。

2023/2/5185第2章密碼學(xué)基礎(chǔ)2.BB84協(xié)議具體工作過程第一階段：量子信道上的通信，Alice在量子信道上發(fā)送信息給Bob，量子信道一般是光纖，也可以是自由空間，比如利用空氣傳輸，具體操作步驟如下：

⑴在發(fā)送端和接收端均放置偏振方向分別為水平方向、與水平成45°度夾角、與水平成90°夾角、與水平成135°夾角的四個(gè)偏振儀。

2023/2/5186第2章密碼學(xué)基礎(chǔ)2.BB84協(xié)議具體工作過程⑵Alice選擇一串光子脈沖隨機(jī)的通過各偏振儀。不同的偏振儀產(chǎn)生不同的偏振方向，分別代表不同的量子態(tài)。例如某個(gè)光子通過偏振方向是垂直方向的偏振儀，則發(fā)送的光子偏振方向就是。Alice同時(shí)要記錄發(fā)送的光子序列偏振方向。

⑶Bob隨機(jī)選擇一組測(cè)量基序列接收單光子。由于Bob事先并不知道Alice使用的是什么測(cè)量基序列，它只好將自己的測(cè)量基以及測(cè)量結(jié)果保存好，并且不對(duì)外公開。

2023/2/5187第2章密碼學(xué)基礎(chǔ)2.BB84協(xié)議具體工作過程第二階段：傳統(tǒng)公共信道上的通信：⑴Bob將它隨機(jī)選擇的測(cè)量基序列通過公共信道發(fā)送給Alice，此通信過程不存在任何安全措施，所發(fā)的測(cè)量基序列Eve可以竊取到；⑵Alice收到Bob測(cè)量基之后，將它與自己所發(fā)的光子序列偏振方向做比較，確定Bob在哪些位上用的是正確的測(cè)量基，并將比較結(jié)果通過公共信道返回給Bob；

2023/2/5188第2章密碼學(xué)基礎(chǔ)2.BB84協(xié)議具體工作過程⑶Alice和Bob同時(shí)確定了正確的測(cè)量基，由此雙方根據(jù)測(cè)量基產(chǎn)生原始密鑰；⑷雙方比較部分原始密鑰。這里要分兩種情況考慮，無噪聲的量子通信信道和有噪聲的量子通信信道，在有噪聲的量子通信信道上，即使沒有攻擊者，光子的偏振方向也會(huì)受到影響，因此影響雙方的測(cè)量結(jié)果。

2023/2/5189第2章密碼學(xué)基礎(chǔ)2.BB84協(xié)議具體工作過程我們先考慮Alice和Bob通信的量子信道上無任何噪聲干擾，Alice和Bob從原始密鑰中選出相同的隨機(jī)序列m位，通過公共信道傳送給對(duì)方做比較，如果彼此比較結(jié)果發(fā)現(xiàn)不一致的現(xiàn)象，則證明存在竊聽者Eve；如果比較的結(jié)果一致，表明Eve存在概率的可能性非常小，因?yàn)镋ve存在但是不被發(fā)現(xiàn)的概率是非常小的；2023/2/5190第2章密碼學(xué)基礎(chǔ)2.BB84協(xié)議具體工作過程4.1)如果判定沒有Eve竊聽，Alice與Bob從原始密鑰中刪除剛才用于比較的m