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

1、第二章第二章 密碼學(xué)基礎(chǔ)密碼學(xué)基礎(chǔ)目標(biāo)要求目標(biāo)要求 基本要求基本要求 理解密碼系統(tǒng)的理解密碼系統(tǒng)的模型模型 理解對(duì)稱密碼體制和非對(duì)稱密碼體制的原理理解對(duì)稱密碼體制和非對(duì)稱密碼體制的原理 掌握掌握IDEA算法、算法、ECC等公開密碼算法的原理與應(yīng)用等公開密碼算法的原理與應(yīng)用 了解常見的了解常見的加密方式和各自的特點(diǎn)加密方式和各自的特點(diǎn)目標(biāo)要求目標(biāo)要求 重點(diǎn)重點(diǎn) 掌握對(duì)稱密碼體制和非對(duì)稱密碼體制的原理掌握對(duì)稱密碼體制和非對(duì)稱密碼體制的原理 熟悉熟悉IDEA算法、算法、ECC公開密碼算法的原理與應(yīng)用公開密碼算法的原理與應(yīng)用 熟悉各種熟悉各種加密方式和各自的特點(diǎn)加密方式和各自的特點(diǎn) 難點(diǎn)難點(diǎn) 非對(duì)稱密

2、碼體制的原理非對(duì)稱密碼體制的原理本章內(nèi)容本章內(nèi)容2.1 密碼技術(shù)概述密碼技術(shù)概述2.2 密碼算法密碼算法2.3 對(duì)稱密鑰密碼加密模式對(duì)稱密鑰密碼加密模式2.4 網(wǎng)絡(luò)加密方式網(wǎng)絡(luò)加密方式2.1 密碼技術(shù)概述密碼技術(shù)概述2.1.1 密碼學(xué)歷史密碼學(xué)歷史 1000 BC:姜子牙陰陽符姜子牙陰陽符 500-600 BC: 天書天書 100-44 BC: Caesar cipherthe romans arecoming todayCaesar cipher：移位密碼：移位密碼密文表：密文表：abcdefghijklmnopqrstuvwxyz密文表：密文表：defghijklmnopqrstuvwxy

3、zabcAn example: 明文明文-Plaintext: How are you 密文密文-Ciphertext ? 1790: 轉(zhuǎn)輪密碼，轉(zhuǎn)輪密碼，Thomas Jefferson 二戰(zhàn)二戰(zhàn): German Enigma machine 二戰(zhàn)二戰(zhàn): Japanese Purple machine Born: 30 April 1916 in Gaylord, Michigan, USADied: 24 Feb 2001 in Medford, Massachusetts, USA2.1.2 密碼系統(tǒng)密碼系統(tǒng)加密變換加密變換不安全信道不安全信道Plain TextCipher TextC

4、ipher Text解密變換解密變換Plain Text發(fā)送者：發(fā)送者：AliceDecryption KeyEncryption Key接受者：接受者：AliceCipher Text密碼分析密碼分析？竊密者：竊密者：Eve密鑰信道密鑰信道（1）密碼學(xué)基本概念）密碼學(xué)基本概念 密碼學(xué)密碼學(xué)(Cryptology)：研究信息系統(tǒng)安全保密：研究信息系統(tǒng)安全保密 的科學(xué)。它包含兩個(gè)分支：的科學(xué)。它包含兩個(gè)分支： 密碼編碼學(xué)密碼編碼學(xué)(Cryptography)，對(duì)信息進(jìn)行編對(duì)信息進(jìn)行編 碼實(shí)現(xiàn)隱蔽信息的一門學(xué)問；碼實(shí)現(xiàn)隱蔽信息的一門學(xué)問； 密碼分析學(xué)密碼分析學(xué)(Cryptanalysis)，研究分

5、析破譯研究分析破譯 密碼的學(xué)問。密碼的學(xué)問。 明文明文(消息消息)(Plaintext) ：被隱蔽消息，常用被隱蔽消息，常用M表示表示 密文密文(Ciphertext)或密報(bào)或密報(bào)(Cryptogram)：明文經(jīng)明文經(jīng) 密碼變換成的一種隱蔽形式，常用密碼變換成的一種隱蔽形式，常用C表示表示 加密加密(Encryption)：將明文變換為密文的過程將明文變換為密文的過程 解密解密(Decryption)：加密的逆過程，即由密文恢加密的逆過程，即由密文恢 復(fù)出原明文的過程復(fù)出原明文的過程 加密員或密碼員加密員或密碼員(Cryptographer)：對(duì)明文進(jìn)行對(duì)明文進(jìn)行 加密操作的人員。加密操作的人

6、員。 常用常用E（）（） 表示表示 控制加密和解密算法操作的數(shù)據(jù)處控制加密和解密算法操作的數(shù)據(jù)處 理，分別稱作加密密鑰和解密密鑰，常用理，分別稱作加密密鑰和解密密鑰，常用k表示表示 在信息傳輸和處理系統(tǒng)在信息傳輸和處理系統(tǒng) 中的非受權(quán)者，通過搭線竊聽、電磁竊聽、聲音中的非受權(quán)者，通過搭線竊聽、電磁竊聽、聲音 竊聽等來竊取機(jī)密信息。竊聽等來竊取機(jī)密信息。 （2）密碼系統(tǒng)組成）密碼系統(tǒng)組成 明文空間：明文空間：信息本來的原始空間信息本來的原始空間 密文空間：密文空間：明文經(jīng)過加密后得到難以理解和辨明文經(jīng)過加密后得到難以理解和辨 認(rèn)的信息空間認(rèn)的信息空間 密鑰空間：密鑰空間：控制算法的實(shí)現(xiàn)，由信息通

7、信雙方控制算法的實(shí)現(xiàn)，由信息通信雙方 所掌握的專門信息空間所掌握的專門信息空間 密碼算法：密碼算法：規(guī)定了明文和密文之間的一個(gè)復(fù)雜規(guī)定了明文和密文之間的一個(gè)復(fù)雜 的函數(shù)變換方式，包括的函數(shù)變換方式，包括加密函數(shù)加密函數(shù)與與解密函數(shù)解密函數(shù) 加密過程：加密過程：EK(M)=C 加密過程：加密過程：DK(C)=M 密碼系統(tǒng)應(yīng)滿足：密碼系統(tǒng)應(yīng)滿足：DK(EK(M)=)=M 密碼學(xué)的密碼學(xué)的Kerchoff準(zhǔn)則準(zhǔn)則“一切秘密寓于密鑰之中一切秘密寓于密鑰之中”1883年荷蘭密碼學(xué)家年荷蘭密碼學(xué)家A.Kerchoff(18351903)就就給出了密碼學(xué)的一個(gè)基本原則給出了密碼學(xué)的一個(gè)基本原則:密碼的安全必

8、須完全寓密碼的安全必須完全寓于密鑰之中。盡管密碼學(xué)家們大都同意這一看法于密鑰之中。盡管密碼學(xué)家們大都同意這一看法,但直但直到制定到制定DES時(shí)才首次認(rèn)真地遵循這一原則。時(shí)才首次認(rèn)真地遵循這一原則。 2.1.3 密碼體制密碼體制密碼體制：一個(gè)密碼系統(tǒng)采用的基本工作方式密碼體制：一個(gè)密碼系統(tǒng)采用的基本工作方式密碼體制從原理上可以分為兩大類：密碼體制從原理上可以分為兩大類： 對(duì)稱密鑰密碼體制（或單鑰密碼體制）對(duì)稱密鑰密碼體制（或單鑰密碼體制） 非對(duì)稱密鑰密碼體制（或雙鑰密碼體制）非對(duì)稱密鑰密碼體制（或雙鑰密碼體制）2.1.3.1 對(duì)稱密鑰密碼體制對(duì)稱密鑰密碼體制加密：加密：E不安全信道不安全信道Pl

9、ain TextCipher TextCipher Text解密解密:DPlain Text發(fā)送者：發(fā)送者：AliceKK接受者：接受者：Alice密鑰信道密鑰信道密鑰生成器密鑰生成器 加密過程：加密過程：EK(M)=C 加密過程：加密過程：DK(C)=M 對(duì)稱密鑰密碼根據(jù)對(duì)明文加密方式的不同分為：對(duì)稱密鑰密碼根據(jù)對(duì)明文加密方式的不同分為： 序列密碼（序列密碼（Stream Cipher）或流密碼）或流密碼 分組密碼（分組密碼（Block Cipher）或塊密碼）或塊密碼（1） 序列密碼序列密碼對(duì)明文的單個(gè)位（有時(shí)對(duì)字節(jié)）運(yùn)算的算法。對(duì)明文的單個(gè)位（有時(shí)對(duì)字節(jié)）運(yùn)算的算法。 軍事和外交場(chǎng)合使用

10、的主要密碼技術(shù)軍事和外交場(chǎng)合使用的主要密碼技術(shù) 工作原理：工作原理：明文序列：明文序列：m=m0m1m2密文序列：密文序列：c=ccc1c2密鑰序列：密鑰序列：k=k0k1k2序列密碼的加密過程序列密碼的加密過程明文序列：明文序列：m=m0m1m2密文序列：密文序列：c=ccc1c2密鑰序列：密鑰序列：k=k0k1k2序列密碼的解密過程序列密碼的解密過程 加密過程：加密過程：ci=(ki+mi)(mod 2) 加密過程：加密過程：mi=(ki+ci)(mod 2)（2） 分組密碼分組密碼 對(duì)明文信息分割成塊結(jié)構(gòu)，逐塊進(jìn)行加密和解密。對(duì)明文信息分割成塊結(jié)構(gòu)，逐塊進(jìn)行加密和解密。 工作原理：首先將

11、明文分成相同長(zhǎng)度的數(shù)據(jù)塊，工作原理：首先將明文分成相同長(zhǎng)度的數(shù)據(jù)塊， 然后分別對(duì)每個(gè)數(shù)據(jù)塊加密產(chǎn)生一串滅為你數(shù)據(jù)然后分別對(duì)每個(gè)數(shù)據(jù)塊加密產(chǎn)生一串滅為你數(shù)據(jù) 塊；解密時(shí)，第每個(gè)密文數(shù)據(jù)塊進(jìn)行解密后得到相塊；解密時(shí)，第每個(gè)密文數(shù)據(jù)塊進(jìn)行解密后得到相 應(yīng)的明文數(shù)據(jù)塊，將所有的明文數(shù)據(jù)塊合并起來即應(yīng)的明文數(shù)據(jù)塊，將所有的明文數(shù)據(jù)塊合并起來即 得到明文。得到明文。明文序列：明文序列：m=m0m1m2密文序列：密文序列：c=ccc1c2密鑰序列：密鑰序列：k=k0k1k2分組密碼的加密過程分組密碼的加密過程Ek明文序列：明文序列：m=m0m1m2密文序列：密文序列：c=ccc1c2密鑰序列：密鑰序列：k=

12、k0k1k2分組密碼的加密過程分組密碼的加密過程Dk（1）對(duì)稱密鑰密碼體制的問題）對(duì)稱密鑰密碼體制的問題2.1.3.2 非稱密鑰密碼體制非稱密鑰密碼體制ENetwork or Storage明文明文Plain Text密文密文Cipher TextD原明文原明文OriginalPlain TextBob私鑰私鑰Secret KeyAlice私鑰私鑰Secret Key密文密文Cipher Text 若若N個(gè)人相互保密通信，每人必須擁有（個(gè)人相互保密通信，每人必須擁有（N-1）個(gè)）個(gè) 私鑰，私鑰，N很大時(shí)，需要保存的私鑰很多。如何解很大時(shí)，需要保存的私鑰很多。如何解 決？決？ 可信中心分發(fā)：共需

13、要發(fā)可信中心分發(fā)：共需要發(fā)N*(N-1)/2個(gè)私鑰個(gè)私鑰 N =1000時(shí)時(shí), 999 *1000/2 = 499500 雙方事先約定：用戶之間自己秘密會(huì)面雙方事先約定：用戶之間自己秘密會(huì)面 （第一次遠(yuǎn)距離通信如何辦？）（第一次遠(yuǎn)距離通信如何辦？） 加密：加密：E不安全信道不安全信道Plain TextCipher TextCipher Text解密解密:DPlain Text發(fā)送者：發(fā)送者：AliceK2K1接受者：接受者：Alice 1976，由，由Diffie和和Hellman提出，提出，被公認(rèn)為現(xiàn)代被公認(rèn)為現(xiàn)代 密碼學(xué)誕生的標(biāo)志。密碼學(xué)誕生的標(biāo)志。 工作原理：工作原理：每個(gè)用戶都有一對(duì)

14、選定的密鑰（公鑰：每個(gè)用戶都有一對(duì)選定的密鑰（公鑰： K1，私鑰，私鑰K2） K1是可以公開的，可以像電話號(hào)是可以公開的，可以像電話號(hào) 碼一樣進(jìn)行注冊(cè)公布；碼一樣進(jìn)行注冊(cè)公布； K2則是秘密的。則是秘密的。 特點(diǎn)：特點(diǎn)：（1）將加密和解密能力分開；（將加密和解密能力分開；（2）多個(gè)）多個(gè) 用戶加密的消息只能由一個(gè)用戶解讀（秘密通用戶加密的消息只能由一個(gè)用戶解讀（秘密通 信）；（信）；（3）一個(gè)用戶加密的消息而使多個(gè)用戶可）一個(gè)用戶加密的消息而使多個(gè)用戶可 以解讀（認(rèn)證）；（以解讀（認(rèn)證）；（4）不用事先分配秘鑰。）不用事先分配秘鑰。（2）非對(duì)稱密鑰密碼體制）非對(duì)稱密鑰密碼體制2.1.4 密碼分

15、析密碼分析 密碼分析：密碼分析：試圖獲得加密體制細(xì)節(jié)、解密密鑰和試圖獲得加密體制細(xì)節(jié)、解密密鑰和 明文等機(jī)密信息的過程，通常包括：分析統(tǒng)計(jì)截明文等機(jī)密信息的過程，通常包括：分析統(tǒng)計(jì)截 獲的密文材料、假設(shè)、推斷和證實(shí)等步驟。獲的密文材料、假設(shè)、推斷和證實(shí)等步驟。 密碼分析方法有密碼分析方法有傳統(tǒng)破譯方法傳統(tǒng)破譯方法和和物理破譯方法物理破譯方法兩兩 大類。大類。（1） 基本概念基本概念 傳統(tǒng)破譯方法傳統(tǒng)破譯方法包括包括窮舉破譯法窮舉破譯法和和數(shù)學(xué)分析法數(shù)學(xué)分析法兩類。兩類。 數(shù)學(xué)分析法數(shù)學(xué)分析法又分為又分為確定性分析法確定性分析法的和的和統(tǒng)計(jì)分析法統(tǒng)計(jì)分析法。 四種破譯類型：四種破譯類型： 唯密文

16、破譯唯密文破譯（ciphertext only attacks），）， 分析者僅知道有限數(shù)量的密文。分析者僅知道有限數(shù)量的密文。 已知明文破譯已知明文破譯（known plaintext attacks），）， 分析者除了擁有有限數(shù)量的密文外，還有數(shù)量限分析者除了擁有有限數(shù)量的密文外，還有數(shù)量限 定的一些已知定的一些已知“明文明文密文密文”對(duì)。對(duì)。 四種破譯類型（續(xù)）：四種破譯類型（續(xù)）： 選擇明文破譯選擇明文破譯（chosen plaintext attacks），）， 分析者除了擁有有限數(shù)量的密文外，還有機(jī)會(huì)使分析者除了擁有有限數(shù)量的密文外，還有機(jī)會(huì)使 用注入了未知密鑰的加密機(jī)，通過自由選

17、擇明文用注入了未知密鑰的加密機(jī)，通過自由選擇明文 來獲取所希望的來獲取所希望的“明文明文密文密文”對(duì)（集合）。對(duì)（集合）。 選擇密文破譯選擇密文破譯（chosen ciphertext attacks），）， 分析者除了擁有有限數(shù)量的密文外，還有機(jī)會(huì)使分析者除了擁有有限數(shù)量的密文外，還有機(jī)會(huì)使 用注入了未知密鑰的解密機(jī)，通過自由選擇密文用注入了未知密鑰的解密機(jī)，通過自由選擇密文 來獲取所希望的來獲取所希望的“密文密文明文明文”對(duì)（集合）。對(duì)（集合）。（2）防止密碼破譯的措施）防止密碼破譯的措施為防止密碼被破譯，可以采取以下措施：為防止密碼被破譯，可以采取以下措施： 強(qiáng)壯的加密算法；強(qiáng)壯的加密算

18、法； 動(dòng)態(tài)會(huì)話密鑰動(dòng)態(tài)會(huì)話密鑰 保護(hù)關(guān)鍵密鑰保護(hù)關(guān)鍵密鑰2.2 密碼算法密碼算法（1）IDEA的歷史的歷史 1990年，年，瑞士的來學(xué)嘉（瑞士的來學(xué)嘉（Xuejia Lai）和和 James Massey于于1990年公布了年公布了IDEA密碼算法第密碼算法第 一版，稱為一版，稱為PES (Proposed Encryption Standard)； 1991年，為抗擊差分密碼攻擊，他們?cè)鰪?qiáng)了算法的強(qiáng)年，為抗擊差分密碼攻擊，他們?cè)鰪?qiáng)了算法的強(qiáng) 度，稱度，稱IPES（Improved PES)； 1992年，改名為年，改名為IDEA（International Data Encryption A

19、lgorithm）。）。2.2.1 IDEA算法算法（2）IDEA加密過程加密過程 IDEA是一個(gè)分組長(zhǎng)度為是一個(gè)分組長(zhǎng)度為 64bit的分組密碼算法，密的分組密碼算法，密 鑰長(zhǎng)度為鑰長(zhǎng)度為128bit（抗強(qiáng)力攻（抗強(qiáng)力攻 擊能力比擊能力比DES強(qiáng)），同一強(qiáng)），同一 算法既可加密也可解密。算法既可加密也可解密。 IDEA的的“混淆混淆”和和“擴(kuò)散擴(kuò)散” 設(shè)計(jì)原則來自三種運(yùn)算，設(shè)計(jì)原則來自三種運(yùn)算， 它們易于軟、硬件實(shí)現(xiàn)它們易于軟、硬件實(shí)現(xiàn) （加密速度快）：（加密速度快）：Z6F2F1Z5G1G21. 在在IDEA的模乘運(yùn)的模乘運(yùn)算中，為什么將模數(shù)算中，為什么將模數(shù)取為取為216+1，而不是，而

20、不是 216 ？ 2. 在其模加運(yùn)算中，為什么模數(shù)取為在其模加運(yùn)算中，為什么模數(shù)取為216而不是而不是 216+1 ？ IDEA加密的總體方案圖加密的總體方案圖循環(huán)循環(huán)2循環(huán)循環(huán)8循環(huán)循環(huán)1輸出變換輸出變換64位密文位密文64位明文位明文Z1Z6Z7Z12Z43Z48Z49Z52子密鑰生成器子密鑰生成器128bit密鑰密鑰Z1Z5216IDEA加密的單個(gè)循環(huán)圖加密的單個(gè)循環(huán)圖X1X2X3X4Z1Z2Z3Z4Z5Z6W11W12W13W14IDEA的密鑰生成的密鑰生成 56個(gè)個(gè)16bit的子密鑰從的子密鑰從128bit的密鑰中生成前的密鑰中生成前8 個(gè)子密鑰直接從密鑰中取出；個(gè)子密鑰直接從密鑰中

21、取出； 對(duì)密鑰進(jìn)行對(duì)密鑰進(jìn)行25bit的循環(huán)左移，接下來的密鑰的循環(huán)左移，接下來的密鑰 就從中取出；就從中取出； 重復(fù)進(jìn)行直到重復(fù)進(jìn)行直到52個(gè)子密鑰都產(chǎn)生出來。個(gè)子密鑰都產(chǎn)生出來。（3）IDEA的解密的解密 加密解密實(shí)質(zhì)相同，但使用不同的密鑰；加密解密實(shí)質(zhì)相同，但使用不同的密鑰； 解密密鑰以如下方法從加密子密鑰中導(dǎo)出：解密密鑰以如下方法從加密子密鑰中導(dǎo)出： 解密循環(huán)解密循環(huán)I的頭的頭4個(gè)子密鑰從加密循環(huán)個(gè)子密鑰從加密循環(huán)10I 的頭的頭4個(gè)子密鑰中導(dǎo)出；解密密鑰第個(gè)子密鑰中導(dǎo)出；解密密鑰第1、4個(gè)個(gè) 子密鑰對(duì)應(yīng)于子密鑰對(duì)應(yīng)于1、4加密子密鑰的乘法逆元；加密子密鑰的乘法逆元； 2、3對(duì)應(yīng)對(duì)應(yīng)2

22、、3的加法逆元；的加法逆元； 對(duì)前對(duì)前8個(gè)循環(huán)來說，循環(huán)個(gè)循環(huán)來說，循環(huán)I的最后兩個(gè)子密鑰的最后兩個(gè)子密鑰 等于加密循環(huán)等于加密循環(huán)9I的最后兩個(gè)子密鑰；的最后兩個(gè)子密鑰； 使用子分組：使用子分組：16bit的子分組；的子分組； 使用簡(jiǎn)單操作（易于加法、移位等操作實(shí)現(xiàn)）使用簡(jiǎn)單操作（易于加法、移位等操作實(shí)現(xiàn)） ； 加密解密過程類似；加密解密過程類似； 規(guī)則的結(jié)構(gòu)（便于規(guī)則的結(jié)構(gòu)（便于VLSI實(shí)現(xiàn)）。實(shí)現(xiàn)）。（4）實(shí)現(xiàn)上的考慮）實(shí)現(xiàn)上的考慮（5）IDEA的安全性的安全性 IDEA能抗差分分析和相關(guān)分析；能抗差分分析和相關(guān)分析； IDEA似乎沒有似乎沒有DES意義下的弱密鑰；意義下的弱密鑰； ID

23、EA是是PGP的一部分；的一部分； Bruce Schneier 認(rèn)為認(rèn)為IDEA是是DES的最好替代，但的最好替代，但 問題是問題是IDEA太新，許多問題沒解決。太新，許多問題沒解決。2.2.2 ECC公鑰密碼公鑰密碼（1）簡(jiǎn)要?dú)v史）簡(jiǎn)要?dú)v史 橢圓曲線橢圓曲線(Elliptic curve)作為代數(shù)幾何中的重要問題作為代數(shù)幾何中的重要問題 已有已有100多年的研究歷史多年的研究歷史 1985年，年，N. Koblitz和和V. Miller獨(dú)立將其引入密碼學(xué)獨(dú)立將其引入密碼學(xué) 中，成為構(gòu)造公鑰密碼體制的一個(gè)有力工具中，成為構(gòu)造公鑰密碼體制的一個(gè)有力工具。 利用有限域利用有限域GF(2n )上

24、的橢圓曲線上點(diǎn)集所構(gòu)成的群上上的橢圓曲線上點(diǎn)集所構(gòu)成的群上 定義的離散對(duì)數(shù)系統(tǒng)，可以構(gòu)造出基于有限域上離散定義的離散對(duì)數(shù)系統(tǒng)，可以構(gòu)造出基于有限域上離散 對(duì)數(shù)的一些公鑰體制對(duì)數(shù)的一些公鑰體制-橢圓曲線離散對(duì)數(shù)密碼體制橢圓曲線離散對(duì)數(shù)密碼體制 (ECDLC )，如，如Diffie-Hellman，ElGamal， Schnorr，DSA等等 實(shí)數(shù)上的橢圓曲線：實(shí)數(shù)上的橢圓曲線： 其中的其中的 是滿足簡(jiǎn)單條件的實(shí)數(shù)是滿足簡(jiǎn)單條件的實(shí)數(shù) 一些曲線上的點(diǎn)連同無窮遠(yuǎn)點(diǎn)一些曲線上的點(diǎn)連同無窮遠(yuǎn)點(diǎn)O的集合。的集合。232yaxybyxcxdxe,abcde 實(shí)數(shù)上的橢圓曲線例子：實(shí)數(shù)上的橢圓曲線例子： 23

25、1yxx（2） 運(yùn)算定義：運(yùn)算定義： 12121211;,22,OOOO pOpXp pppOOppQRXpQRpOQSQQS 若曲線三點(diǎn)在一條直線上，則其和為 ，用作加法的單位：，一條豎直線交 軸兩點(diǎn)則于是，如果兩個(gè)點(diǎn) 和 的 軸不同，則畫一連線，得到第三個(gè)點(diǎn) ，則，倍，一個(gè)點(diǎn) 的 倍是，找到它的切線與曲線的另一交點(diǎn)于是l有限域上的橢圓曲線：有限域上的橢圓曲線：l模模P橢圓群記為橢圓群記為 群中的元素（群中的元素（x, y)是滿足是滿足 以上方程的小于以上方程的小于P的非負(fù)整數(shù)另外加上無窮遠(yuǎn)點(diǎn)的非負(fù)整數(shù)另外加上無窮遠(yuǎn)點(diǎn)Ol計(jì)算計(jì)算2332mod4270modyxaxbppabp是奇素?cái)?shù)，且,

26、:pEa b30,mod,pxpxaxbpyx yx ypEa b針對(duì)所有的計(jì)算確定是否可以求出有效的 得到曲線上的點(diǎn)其中，記為。,:pEa b 的加法規(guī)則：的加法規(guī)則： ,pEa b 112233231231312121211,modmod,/,3/ 2pPOPPx yPxyOxyPPxyEa bPx yQxyPQxyxxxpyxxypPQyyxxPQxay如果則點(diǎn)是 的負(fù)點(diǎn)，記為。而且也在中如果則為其中，如果則 如果則 ECC的加解密：的加解密：, , ,:,:ppmmmmmmmEa bGGnGnGOnrPrGp a b G PPrMMEa bPkCkG PkPkkGkPOkCPkPr k

27、GPkrGrkGP選擇的元素使得 的階 是一個(gè)大素?cái)?shù)的階是指滿足的最小 值秘密選擇整數(shù) 計(jì)算然后公開為公鑰保密加密先把消息變換成為中的一個(gè)點(diǎn)然后選擇隨機(jī)數(shù)計(jì)算密文如果 使得或者為則重新選擇解密加密消息有擴(kuò)張 ECC加解密例子加解密例子 23751,1,188 ,188,0,376,562,201 ,386201,5386 0,376676,558562,201386 201,5385,328676 558385 328pmBmBpEyxxGABPAkBPkGPkPA取這等價(jià)于曲線假設(shè) 希望發(fā)送一個(gè)報(bào)文給這個(gè)報(bào)文被編碼為橢圓曲線上的點(diǎn)而 選擇隨機(jī)數(shù)的公鑰是我們有因此 發(fā)送密文， ECC特別適用：

28、特別適用： 無線無線Modem的實(shí)現(xiàn)：對(duì)分組交換數(shù)據(jù)網(wǎng)提供加密，在的實(shí)現(xiàn)：對(duì)分組交換數(shù)據(jù)網(wǎng)提供加密，在 移動(dòng)通信器件上運(yùn)行移動(dòng)通信器件上運(yùn)行4 MHz的的68330 CPU，ECC可實(shí)現(xiàn)可實(shí)現(xiàn) 快速快速Diffie-Hellman密鑰交換，并極小化密鑰交換占用密鑰交換，并極小化密鑰交換占用 的帶寬，將計(jì)算時(shí)間從大于的帶寬，將計(jì)算時(shí)間從大于60秒降到秒降到2秒以下。秒以下。 Web服務(wù)器的實(shí)現(xiàn)：在服務(wù)器的實(shí)現(xiàn)：在Web服務(wù)器上集中進(jìn)行密碼計(jì)算會(huì)形成服務(wù)器上集中進(jìn)行密碼計(jì)算會(huì)形成 瓶頸，瓶頸，Web服務(wù)器上的帶寬有限使帶寬費(fèi)用高，采用服務(wù)器上的帶寬有限使帶寬費(fèi)用高，采用ECC可節(jié)可節(jié) 省計(jì)算時(shí)間和

29、帶寬，且通過算法的協(xié)商較易于處理兼容性。省計(jì)算時(shí)間和帶寬，且通過算法的協(xié)商較易于處理兼容性。 集成電路卡的實(shí)現(xiàn)：集成電路卡的實(shí)現(xiàn)：ECC無需協(xié)處理器就可以在標(biāo)準(zhǔn)卡上實(shí)現(xiàn)無需協(xié)處理器就可以在標(biāo)準(zhǔn)卡上實(shí)現(xiàn) 快速、安全的數(shù)字簽名，這是快速、安全的數(shù)字簽名，這是RSA體制難以做到。體制難以做到。ECC可使程可使程 序代碼、密鑰、證書的存儲(chǔ)空間極小化，數(shù)據(jù)幀最短，便于實(shí)序代碼、密鑰、證書的存儲(chǔ)空間極小化，數(shù)據(jù)幀最短，便于實(shí) 現(xiàn)，大大降低了現(xiàn)，大大降低了IC卡的成本?？ǖ某杀?。 Menezes，Okamoto和和Vanstone 指出應(yīng)避免選指出應(yīng)避免選 用超奇異曲線，否則橢圓曲線群上的離散對(duì)數(shù)問用超奇異

30、曲線，否則橢圓曲線群上的離散對(duì)數(shù)問 題退化為有限域低次擴(kuò)域上的離散對(duì)數(shù)問題，從題退化為有限域低次擴(kuò)域上的離散對(duì)數(shù)問題，從 而能在多項(xiàng)式時(shí)間上可解。他們還指出，若所用而能在多項(xiàng)式時(shí)間上可解。他們還指出，若所用 循環(huán)子群的階數(shù)達(dá)循環(huán)子群的階數(shù)達(dá)2160，則可提供足夠的安全性。，則可提供足夠的安全性。 （3）ECC的安全性的安全性 ECC和和RSA對(duì)比：在實(shí)現(xiàn)相同的安全性下，對(duì)比：在實(shí)現(xiàn)相同的安全性下，ECC 所需的密所需的密 鑰量比鑰量比RSA少得多，如下表所示。其中少得多，如下表所示。其中MIPS年表示用每秒年表示用每秒 完成完成100萬條指令的計(jì)算機(jī)所需工作的年數(shù)，萬條指令的計(jì)算機(jī)所需工作的年

31、數(shù)，m表示表示ECC 的密鑰由的密鑰由2 m點(diǎn)構(gòu)成。以點(diǎn)構(gòu)成。以40 MHz的鐘頻實(shí)現(xiàn)的鐘頻實(shí)現(xiàn)155 bits的的 ECC，每秒可完成，每秒可完成40,000次橢園曲線運(yùn)算，其速度比次橢園曲線運(yùn)算，其速度比1024 bits的的DSA和和RSA快快10倍。倍。 ECC的密鑰長(zhǎng)度的密鑰長(zhǎng)度m RSA的密鑰長(zhǎng)度的密鑰長(zhǎng)度 MIPS-年年 160 1024 1012 320 5120 1036 600 21000 1078 1200 120000 101682.3.1 分組密碼的工作模式分組密碼的工作模式2.3 網(wǎng)絡(luò)加密方法網(wǎng)絡(luò)加密方法 分組密碼可以按不同的模式工作，實(shí)際應(yīng)用的環(huán)分組密碼可以按不同

32、的模式工作，實(shí)際應(yīng)用的環(huán)境不同應(yīng)采用不同的工作模式境不同應(yīng)采用不同的工作模式 電碼本電碼本(ECB)模式模式 密碼分組鏈接密碼分組鏈接(CBC)模式模式 密碼反饋密碼反饋(CFB)模式模式 輸出反饋輸出反饋(OFB)模式模式 計(jì)數(shù)器計(jì)數(shù)器(CTR)模式模式 2.3.2 電碼本（電碼本（ECB）模式）模式 最簡(jiǎn)單的運(yùn)行模式，一次對(duì)一個(gè)最簡(jiǎn)單的運(yùn)行模式，一次對(duì)一個(gè)64bit長(zhǎng)的明長(zhǎng)的明文文 分組加密，且每次加密密鑰都相同。分組加密，且每次加密密鑰都相同。 在用于短數(shù)據(jù)（如加密密鑰）時(shí)非常理想，是安在用于短數(shù)據(jù)（如加密密鑰）時(shí)非常理想，是安 全傳遞全傳遞DES密鑰的最合適的模式密鑰的最合適的模式 在

33、給定的密鑰下同一明文組總產(chǎn)生同樣的密文組。在給定的密鑰下同一明文組總產(chǎn)生同樣的密文組。 這會(huì)暴露明文數(shù)據(jù)的格式和統(tǒng)計(jì)特征。這會(huì)暴露明文數(shù)據(jù)的格式和統(tǒng)計(jì)特征。 明文數(shù)據(jù)都有固定的格式，需要以協(xié)議的形式定明文數(shù)據(jù)都有固定的格式，需要以協(xié)議的形式定 義，重要的數(shù)據(jù)常常在同一位置上出現(xiàn)，使密碼義，重要的數(shù)據(jù)常常在同一位置上出現(xiàn)，使密碼 分析者可以對(duì)其進(jìn)行統(tǒng)計(jì)分析、重傳和代換攻擊分析者可以對(duì)其進(jìn)行統(tǒng)計(jì)分析、重傳和代換攻擊2.3.3 密碼分組鏈接（密碼分組鏈接（CBC）模式）模式 一次對(duì)一個(gè)明文分組加密，每次加密使用同一密一次對(duì)一個(gè)明文分組加密，每次加密使用同一密 鑰，加密算法的輸入是當(dāng)前明文分組和前一次

34、密鑰，加密算法的輸入是當(dāng)前明文分組和前一次密 文分組的異或（在產(chǎn)生第文分組的異或（在產(chǎn)生第1個(gè)密文分組時(shí)，需要個(gè)密文分組時(shí)，需要 有一個(gè)初始向量有一個(gè)初始向量IV與第一個(gè)明文分組異或）；與第一個(gè)明文分組異或）； 解密時(shí)，每一個(gè)密文分組被解密后，再與前一個(gè)解密時(shí)，每一個(gè)密文分組被解密后，再與前一個(gè) 密文分組異或（第一個(gè)密文分組解密后和初始向密文分組異或（第一個(gè)密文分組解密后和初始向 量量IV異或恢復(fù)出第一個(gè)明文分組）。異或恢復(fù)出第一個(gè)明文分組）。 為使安全性最高，為使安全性最高，IV應(yīng)像密鑰一樣被保護(hù)。可使用應(yīng)像密鑰一樣被保護(hù)?？墒褂肊CB 加密模式來發(fā)送加密模式來發(fā)送IV； 保護(hù)保護(hù)IV原因是

35、：如果敵手能欺騙接受方使用不同的原因是：如果敵手能欺騙接受方使用不同的IV， 敵手就能夠在明文的第一個(gè)分組中插入自己選擇的比特值；敵手就能夠在明文的第一個(gè)分組中插入自己選擇的比特值； IV的完整性要比其保密性更為重要。在的完整性要比其保密性更為重要。在CBC模式下，最好模式下，最好 是每發(fā)一個(gè)消息，都改變是每發(fā)一個(gè)消息，都改變IV，比如將其值加一；，比如將其值加一； 由于由于CBC模式的鏈接機(jī)制，該模式對(duì)于加密長(zhǎng)于模式的鏈接機(jī)制，該模式對(duì)于加密長(zhǎng)于64bit的消的消 息非常合適；息非常合適； CBC模式除能獲得保密性外，還能用于認(rèn)證。模式除能獲得保密性外，還能用于認(rèn)證。2.3.4 密碼反饋（密

36、碼反饋（CFB）模式）模式 加密算法的輸入是加密算法的輸入是64bit移位寄存器，其初始值為某個(gè)初始向量移位寄存器，其初始值為某個(gè)初始向量IV，加密算法輸出的最左（最高有效位），加密算法輸出的最左（最高有效位）j bit與明文的第一個(gè)單與明文的第一個(gè)單元進(jìn)行異或，產(chǎn)生第一個(gè)密文單元元進(jìn)行異或，產(chǎn)生第一個(gè)密文單元 并傳送該單元。然后將移位并傳送該單元。然后將移位寄存器的內(nèi)容左移寄存器的內(nèi)容左移j位并將位并將 送入移位寄存器最右邊（最低有效位）送入移位寄存器最右邊（最低有效位）j位。這一過程持續(xù)到明文的所有單元都被加密為止位。這一過程持續(xù)到明文的所有單元都被加密為止1C1C 解密時(shí)，將解密時(shí)，將

37、收到的密文收到的密文 單元與加密單元與加密 函數(shù)的輸出函數(shù)的輸出 進(jìn)行異或進(jìn)行異或l為什么此時(shí)仍然使用加密算法為什么此時(shí)仍然使用加密算法而不是解密算法？而不是解密算法？ 利用利用CFB模式或者模式或者OFB模式可將模式可將DES轉(zhuǎn)換為流轉(zhuǎn)換為流 密碼；密碼； 流密碼不需要對(duì)消息進(jìn)行填充，而且運(yùn)行是實(shí)時(shí)流密碼不需要對(duì)消息進(jìn)行填充，而且運(yùn)行是實(shí)時(shí) 的，因此如果傳送字母流，可使用流密碼對(duì)每個(gè)的，因此如果傳送字母流，可使用流密碼對(duì)每個(gè) 字母直接加密進(jìn)行傳送；字母直接加密進(jìn)行傳送； CFB模式除了獲得保密性外，還能用于認(rèn)證。模式除了獲得保密性外，還能用于認(rèn)證。2.3.5 輸出反饋輸出反饋(OFB)模式模式 OFB模式的結(jié)構(gòu)類似于模式的結(jié)構(gòu)類似于CFB，不同之處在于：，不同之處在于： OFB模式將加密算法的輸出反饋到移位寄存器，模式將加密算