1、第6章 公 鑰 密 碼 6.1 公鑰密碼的理論基礎(chǔ) 6.2 RSA公鑰密碼 6.3 ElGamal公鑰密碼 6.4 橢圓曲線上的M-V公鑰密碼 6. 5 對(duì)稱鑰公鑰密碼體制的比較常規(guī)加密的缺陷 主要在于其密鑰的管理：進(jìn)行安全通信前需要以安全方式進(jìn)行密鑰交換。這一步驟，在某種情況下是可行的，但在某些情況下會(huì)非常困難，甚至無(wú)法實(shí)現(xiàn)。密鑰規(guī)模復(fù)雜。舉例來(lái)說(shuō)，A與B兩人之間的密鑰必須不同于A和C兩人之間的密鑰，否則給B的消息的安全性就會(huì)受到威脅。在有1000個(gè)用戶的團(tuán)體中，A需要保持至少999個(gè)密鑰（更確切的說(shuō)是1000個(gè)，如果她需要留一個(gè)密鑰給他自己加密數(shù)據(jù)）。對(duì)于該團(tuán)體中的其它用戶，此種情況同樣存

2、在。這樣，這個(gè)團(tuán)體一共需要將近50萬(wàn)個(gè)不同的密鑰！推而廣之，n個(gè)用戶的團(tuán)體需要n2/2個(gè)不同的密鑰 1976年，W. Diffie和N.E.Hellman發(fā)表的著名論文“密碼學(xué)的新方向”，奠定了公鑰密碼的基礎(chǔ)。公鑰密碼系統(tǒng)提出了一系列新穎的概念和思想，開(kāi)創(chuàng)了密碼學(xué)的新時(shí)代。 其特點(diǎn)是：（1）加密鑰和解密鑰本質(zhì)是不同的，知道其中一個(gè)，不存在一個(gè)有效地推導(dǎo)出另一個(gè)密鑰的算法，所以公鑰密碼系統(tǒng)常又被稱為雙鑰密碼系統(tǒng)或非對(duì)稱密碼系統(tǒng)；（2）不需要分發(fā)密鑰的額外信道，我們可以公開(kāi)加密鑰，這樣無(wú)損于整個(gè)系統(tǒng)的保密性，需要保密的僅僅是解密鑰。（3）公鑰密碼系統(tǒng)還帶來(lái)認(rèn)證性的好處。6.1、 公鑰密碼的理論基礎(chǔ)

3、公開(kāi)鑰明文密文私鑰明文秘密鑰秘密鑰明文密文明文密鑰建立加密/解密基本步驟 接收方加密算法明文解密算法密文明文發(fā)送方Bob的公開(kāi)密鑰Bob的私有密鑰公鑰密碼的優(yōu)點(diǎn)通信雙方事先不需要通過(guò)保密信道交換密鑰。密鑰持有量大大減少。在n個(gè)用戶的團(tuán)體中進(jìn)行通信，每一用戶只需要持有自己的私鑰，而公鑰可放置在公共數(shù)據(jù)庫(kù)上，供其它用戶取用。這樣，整個(gè)團(tuán)體僅需擁有n對(duì)密鑰，就可以滿足相互之間進(jìn)行安全通信的需求。（實(shí)際中，因安全方面的考慮，每一用戶可能持有多個(gè)密鑰，分別用于數(shù)字簽名、加密等用途。此種情況下，整個(gè)團(tuán)體擁有的密鑰對(duì)數(shù)為n的倍數(shù)。但即使如此，與使用對(duì)稱密碼技術(shù)時(shí)需要n2/2個(gè)不同的密鑰相比，需要管理的密鑰數(shù)

4、量仍顯著減少。）非對(duì)稱密碼技術(shù)還提供了對(duì)稱密碼技術(shù)無(wú)法或很難提供的服務(wù)：如與哈希函數(shù)聯(lián)合運(yùn)用可生成數(shù)字簽名（下面介紹），可證明的安全偽隨機(jī)數(shù)發(fā)生器的構(gòu)造，零知識(shí)證明等。公鑰密碼系統(tǒng)提供的安全服務(wù) 加密/解密：發(fā)送方可以用接收方的公鑰加密消息。數(shù)字簽名：發(fā)送方用其私鑰“簽署”消息，通過(guò)對(duì)消息或作為消息函數(shù)的小塊數(shù)據(jù)應(yīng)用加密算法來(lái)進(jìn)行簽署。密鑰交換：兩方互相合作可以進(jìn)行會(huì)話密鑰的交換。 建立一個(gè)公鑰密碼系統(tǒng)，有兩個(gè)基本條件：（1）加密和解密變換必須是計(jì)算上容易的，即應(yīng)該屬于P問(wèn)題；（2）密碼分析必須是計(jì)算上困難的，如屬于NP完全問(wèn)題。 我們?nèi)绾芜x擇計(jì)算困難的問(wèn)題呢？ Deffie and Hell

5、man建立了陷門(mén)單向函數(shù)（trapdoor one-way function）的概念，從而指出了解決這一問(wèn)題的一種途徑。 大數(shù)分解問(wèn)題RSA公鑰密碼有限域上的離散對(duì)數(shù)問(wèn)題Elgamal公鑰密碼橢圓曲線上離散對(duì)數(shù)問(wèn)題單向函數(shù)：計(jì)算F(m, Kp)c 容易，但由 c 計(jì)算 m 不容易。陷門(mén)單向函數(shù)：如果已知 Ks，則由 c 計(jì)算 m 是容易的。什么樣的函數(shù)是單向函數(shù)？如何利用單向函數(shù)、公開(kāi)鑰進(jìn)行加密？計(jì)算難易計(jì)算復(fù)雜性理論為基礎(chǔ)計(jì)算上不可行 計(jì)算復(fù)雜性與單向函數(shù)的概念PKC體制賴以建立的基礎(chǔ)在于公鑰k 私鑰k” 在此，計(jì)算上可行與不可行是如何界定的？為此必須了解一些算法復(fù)雜性方面的知識(shí)。 1. 問(wèn)

6、題(Problem):是指需要回答的一般性提問(wèn)題。 它的描述包括兩個(gè)方面：(1)給出進(jìn)行一般性描述所需參數(shù)的定義；(2)陳述“答案”或“解”必須滿足的性質(zhì)。 若給一個(gè)問(wèn)題的所有未定參數(shù)指定了具體的值，就得到該問(wèn)題的一個(gè)實(shí)例(Instance)。問(wèn)題：一般線性方程組求解；實(shí)例：一個(gè)具體線性方程組求解。2. 算法(Algorithm)是指求解相應(yīng)問(wèn)題的一系 列步驟。 通常可以理解為求解相應(yīng)問(wèn)題的通用計(jì)算機(jī)程序。算法總是針對(duì)某個(gè)問(wèn)題而言，且針對(duì)一個(gè)問(wèn)題的算法可以有好多種。如果一個(gè)算法能解答相應(yīng)問(wèn)題的任何實(shí)例，則說(shuō)這個(gè)算法能解答這個(gè)問(wèn)題。如果針對(duì)一個(gè)問(wèn)題至少有一個(gè)算法可解答之，則說(shuō)這個(gè)問(wèn)題是可解的(R

7、esolvable)，否則就說(shuō)這個(gè)問(wèn)題是不可解的(Unresolvable)。算法的時(shí)間/空間復(fù)雜度 一個(gè)針對(duì)某問(wèn)題的算法，其用于各個(gè)實(shí)例所需的最大時(shí)間T/空間S總是被表示成實(shí)例規(guī)模(即該實(shí)例所需的輸入數(shù)據(jù)的最大長(zhǎng)度)n的函數(shù)T(n)/S(n)，但人們往往不去關(guān)心詳細(xì)的T(n)/S(n)，只是僅僅度量出它們的數(shù)量級(jí)(為此使用記號(hào)“O”：f(n)=O(g(n)常數(shù)c0與自然數(shù)n0,f(n)c|g(n)|, nn0)，稱為該算法的時(shí)間/空間復(fù)雜度。 當(dāng)今大型計(jì)算是在計(jì)算機(jī)上實(shí)現(xiàn)的，而計(jì)算機(jī)需要把所有數(shù)字都轉(zhuǎn)化為二進(jìn)制形式，在二進(jìn)制表示中每位上的數(shù)字稱為bit。實(shí)際上，計(jì)算機(jī)的任何一個(gè)計(jì)算工作最終都

8、歸結(jié)為按bit進(jìn)行。涉及到存儲(chǔ)bit的總量即這一計(jì)算工作所需的空間；而該計(jì)算工作所需的時(shí)間基本上正比于其進(jìn)行bit計(jì)算的數(shù)量(比例常數(shù)取決于計(jì)算機(jī)系統(tǒng))。因此，考察一個(gè)算法的(時(shí)/空)復(fù)雜度即在于估計(jì)出其所需的bit計(jì)算量與bit存儲(chǔ)量。設(shè)自然數(shù)a和b，ab。將a,b用二進(jìn)制 表示的長(zhǎng)度分別記為n和m，即：n=log2a+1,m=log2b+1,nm。ab所需bit計(jì)算量至多是n=O(n)。ab所需bit計(jì)算量至多是(n+m)(m-1)2nm2n2=O(n2)。ab(帶余數(shù))所需bit計(jì)算量至多是(n-m+1)mnmn2=O(n2)。我們計(jì)算一下a與b輾轉(zhuǎn)相除到最后所 需的bit計(jì)算量：設(shè)c0

9、=a，c1=b，ci=qici+1+ci+2 (0ci+2ci+1, i=0,1,k-2; ck+1=0) 顯然，各步帶余除法所需的bit計(jì)算量都 不超過(guò)第1步(即ab)的O(n2)；以下我們只 需弄清楚一共要做多少次帶余除法。我們有ci+2 ci事實(shí)上，若ci+1 ci，則ci+2 ci，則ci=ci+1+ci+22ci+2,從而也有ci+20為 常數(shù))的算法；指數(shù)時(shí)間算法(Exponential time algorithm)：時(shí)間復(fù)雜度為O(2h(n)(h(n) 為大于常數(shù)的多項(xiàng)式)的算法； 此外，還有如時(shí)間復(fù)雜度為 ， 等的算法，稱為超多項(xiàng)式時(shí)間算法，或亞指 數(shù)時(shí)間算法。4. 圖靈機(jī)(

10、Turing machine) 這是一種假想的計(jì)算機(jī)，它具有有限狀態(tài)與無(wú)限的讀寫(xiě)能力，并且可以做無(wú)限的并行操作（從這些方面來(lái)說(shuō)，圖靈機(jī)是人類(lèi)不斷追求的關(guān)于計(jì)算機(jī)的最終理想模型）。圖靈機(jī)分為確定型與非確定型兩種。確定型圖靈機(jī)是指其每一步的操作結(jié)果是唯一確定的。非確定型圖靈機(jī)是指其每一步的操作結(jié)果及下一步操作都有多種選擇，不是唯一確定的。在非確定型圖靈機(jī)上求解一個(gè)問(wèn)題分兩個(gè)階段：猜測(cè)階段和驗(yàn)證階段，因而這“求解”并非真正意義上的求解，因?yàn)椴荒鼙ＷC機(jī)器可猜出正確的答案。（以求解線性方程組為例說(shuō)明）一個(gè)問(wèn)題的實(shí)例若在確定型圖靈機(jī)上于多項(xiàng)式時(shí)間內(nèi)可解，則稱之求解在計(jì)算上可行；若在確定型圖靈機(jī)上找不出多項(xiàng)

11、式時(shí)間的求解算法，則稱之求解在計(jì)算上不可行。一個(gè)問(wèn)題稱為易處理的(Tractable)，是指其所有各個(gè)實(shí)例的求解在計(jì)算上都可行；否則就稱之為難處理的(Intractable)。易處理的問(wèn)題全體稱為確定性多項(xiàng)式時(shí)間可解類(lèi)，記為P。稱一個(gè)問(wèn)題在非確定型圖靈機(jī)上多項(xiàng)式時(shí)間可解，是指對(duì)該問(wèn)題的任何一個(gè)實(shí)例，機(jī)器若猜測(cè)一個(gè)解，則就可在多項(xiàng)式時(shí)間內(nèi)驗(yàn)證其是否正確。在非確定型圖靈機(jī)上多項(xiàng)式時(shí)間可解的問(wèn)題稱為NP問(wèn)題，NP問(wèn)題全體構(gòu)成的類(lèi)稱為非確定性多項(xiàng)式時(shí)間可解類(lèi)，記為NP。顯然，PNP（在確定型圖靈機(jī)上多項(xiàng)式時(shí)間可解的任何問(wèn)題在非確定型圖靈機(jī)上也是多項(xiàng)式時(shí)間可解的，此時(shí)無(wú)需猜測(cè)階段）。雖然NP中許多問(wèn)題都

12、似乎比P中的問(wèn)題“難”得多，但還沒(méi)有人證明PNP。在確定型圖靈機(jī)上，系統(tǒng)地求解NP中一些問(wèn)題似乎都需要指數(shù)時(shí)間。稱一個(gè)NP問(wèn)題是NP-完全的，是指NP中任何問(wèn)題都可通過(guò)多項(xiàng)式時(shí)間轉(zhuǎn)化為該問(wèn)題。NP-完全問(wèn)題的全體記為NPC。顯然，NPC具有下述性質(zhì)：若其中任何一個(gè)問(wèn)題屬于P，則所有的NP問(wèn)題都屬于P，從而P=NP。因此，NP-完全問(wèn)題是NP中“最難”的問(wèn)題。舉例. 背包(Knapsack)問(wèn)題（又稱子集和(Subset sum)問(wèn)題）：給定n個(gè)整數(shù)的集合A=a1,a2,an和一個(gè)整數(shù)S，是否存在A的一個(gè)子集A0，使得 ？上述問(wèn)題是一個(gè)NP問(wèn)題（對(duì)于A的任一給定子集，容易在多項(xiàng)式時(shí)間內(nèi)驗(yàn)證其中全

13、部元素的和是否等于S）；其實(shí)，人們也證明了上述問(wèn)題是一個(gè)NP-完全問(wèn)題。6. 單向函數(shù) 單向函數(shù)的概念是：計(jì)算起來(lái)相對(duì)容易，但求逆卻非常困難（即在正方向上易于計(jì)算而反方向卻難于計(jì)算）。 也就是說(shuō)，已知x，我們很容易計(jì)算f（x）。但已知f（x），卻難于計(jì)算出x。在這里，難的定義是計(jì)算復(fù)雜性意義的（不確定圖靈機(jī)能解的）：即使世界上所有的計(jì)算機(jī)都用來(lái)計(jì)算，從f（x）計(jì)算出x也要花費(fèi)數(shù)百萬(wàn)年的時(shí)間。 用單向函數(shù)加密的信息是毫無(wú)用處的，無(wú)人能解開(kāi)它。所以需要陷門(mén)單向函數(shù)，它是有一個(gè)秘密陷門(mén)的一類(lèi)特殊單向函數(shù)。 考慮加密消息和公鑰，單向函數(shù)為yf（x，k），即知道x，k，求 y 是容易的。反之，知道y 求

14、 k 和 x 是困難的。但是如果你知道陷門(mén)秘密，你也能很容易在反方向計(jì)算單向函數(shù)。也就是說(shuō)有一些秘密信息d（k），一旦給出d（k）和 y，就很容易計(jì)算x。 可以用陷門(mén)單向函數(shù)來(lái)解釋公鑰密碼系統(tǒng)： 數(shù)學(xué)上，公鑰加密過(guò)程是基于上面討論的陷門(mén)單向函數(shù)。 加密是容易的，加密指令就是公開(kāi)密鑰 k，任何人都能加密信息（正向計(jì)算f（x，k），x對(duì)應(yīng)消息M）；解密是困難的（反向計(jì)算f（x，k），它做得非常困難，以致于不知道陷門(mén)秘密d（k），即使用Cray計(jì)算機(jī)和幾百萬(wàn)年的時(shí)間都不能解開(kāi)這個(gè)信息。這個(gè)秘密或陷門(mén)就是私鑰d（k）。持有這個(gè)秘密，解密就和加密一樣容易。 著名的RSA方案 （以發(fā)明者R. Rivest

15、, A. Shamir, and L. Adleman開(kāi)頭字母命名，第一個(gè)安全的公鑰密碼方案。）是基于大數(shù)分解困難問(wèn)題的，即np q； Elgamal方案（發(fā)明者T. Elgamal）是基于離散對(duì)數(shù)問(wèn)題的，即 還有Rabin方案是基于平方根問(wèn)題的。 （第一個(gè)RSA方案是基于背包問(wèn)題的，但背包問(wèn)題基本已被破譯）。 公鑰密碼與對(duì)稱鑰密碼的比較：公鑰密碼：不需共享密鑰；理論基礎(chǔ)堅(jiān)實(shí)；產(chǎn)生數(shù)字簽名; 速度慢、密鑰長(zhǎng).對(duì)稱鑰密碼：速度快，密鑰短，可作為基本單元構(gòu)建 各種密碼工具如偽隨機(jī)數(shù)產(chǎn)生器、Hash函數(shù)； 需要實(shí)現(xiàn)共享密鑰、密鑰管理困難； 沒(méi)有可證明安全性；公鑰密碼有效的數(shù)字簽名和密鑰管理；少量數(shù)據(jù)

16、的加密 公鑰常用于加密對(duì)稱密鑰。這樣的系統(tǒng)稱為 混合密碼系統(tǒng)。 對(duì)稱鑰密碼有效的大量數(shù)據(jù)加密和一些數(shù)據(jù)完整性應(yīng)用。 6.2、RSA 公鑰密碼 RSA公開(kāi)密鑰密碼系統(tǒng)是由R.Rivest、A.Shamir和L.Adleman于1977年提出的。RSA的 取名就是來(lái)自于這三位發(fā)明者的姓的第一個(gè)字母,后來(lái),他們?cè)?982年創(chuàng)辦了以RSA命名的 公司RSA Data Security Inc.和RSA實(shí)驗(yàn)室,該公司和實(shí)驗(yàn)室在公開(kāi)密鑰密碼系統(tǒng)的研究和 商業(yè)應(yīng)用推廣方面具有舉足輕重的地位。 (2) 令 npq，用戶公布n。 計(jì)算 并保密。6.2、RSA 公鑰密碼一、RSA密碼體制 (Rivest-Sham

17、ir-Adelman) (1) 選擇一對(duì)不同的大素?cái)?shù)p和q，將p和q保密。(3) 選取正整數(shù) e ，使其滿足 e 是公開(kāi)鑰。(4) 計(jì)算 d，滿足 ，d是私鑰。(5) 加密過(guò)程為：(6) 解密過(guò)程為：當(dāng)gcd(m,n)1時(shí)，因?yàn)閚=pq，且p和q都是素?cái)?shù)，所以gcd(m,n)一定為p或q，假設(shè)gcd(m,n)=p，則m一定是p的倍數(shù)，設(shè)m=cp解密過(guò)程的正確性：對(duì)任意明文 ，當(dāng)gcd(m,n)=1時(shí)，根據(jù)Euler定理，所以存在一個(gè)整數(shù)s，使得用m=cp乘以兩邊，有例：(1) p11, q=23, (2) n=pq=1123=253,(3) 取e=3，gcd(3,220)=1，e為公鑰；(4)

18、 由擴(kuò)展歐幾里的算法求出3 mod 220的逆為 d=147。(5) 明文空間為對(duì)于明文m=165，則密文(6) 解密過(guò)程例：模冪算法：147128163 10010011 模逆算法：根據(jù)擴(kuò)展的歐幾里得算法 gcd(a,b)=sa+tb , s 和 t 為整數(shù)二、RSA的安全性1、RSA的安全性建立在大合數(shù)n的分解是困難的基礎(chǔ)上， 如果分解已知，則就能求出密鑰d； 2、如果已知 ，則可得到n的分解p和q；所以p和q以上方程的解，此方程是容易解的。 3、p和q應(yīng)為安全素?cái)?shù)或強(qiáng)素?cái)?shù)。 p=2p1+1的素?cái)?shù)為安全素?cái)?shù)，其中p1為素?cái)?shù)。強(qiáng)素?cái)?shù)是p-1、p+1都有大素因子p1、p2，并且p11，p2 1

19、還有大素因子。 4、e和d的選擇 e不能太小，應(yīng)使其在模的階最大。d應(yīng)大于n的長(zhǎng)度的1/4。 6、單純的RSA不能抵抗選擇密文攻擊。5、隨著計(jì)算能力的不斷增加和因子分解算法能力不斷提高， p和q的選擇越來(lái)越大。目前較安全的RSA的 n 一般為 1024 bit 或 2048 bit。需要更多的數(shù)論和密碼學(xué)知識(shí)RSA的安全性RSA公開(kāi)密鑰密碼體制的安全性取決于從公開(kāi)密鑰(n,e)計(jì)算出秘密密鑰(n,d)的困難 程度 .RSA實(shí)驗(yàn)室認(rèn)為,512比特的n已不夠 安全,在1997年或1998年后應(yīng)停止使用。他們建議,現(xiàn)在的個(gè)人應(yīng)用需要用768比特的n,公 司要用1024比特的n,極其重要的場(chǎng)合應(yīng)該用2

20、048比特的n。RSA實(shí)驗(yàn)室還認(rèn)為,768比特的n 可望到2004年仍保持安全。 1977年,科學(xué)的美國(guó)人雜志懸賞征求分解一個(gè)129位十進(jìn)數(shù)(426比特),直至1994年 3月,才由Atkins等人在因特網(wǎng)上動(dòng)用了1600臺(tái)計(jì)算機(jī),前后花了八個(gè)月的時(shí)間,才找出了答 案。然而,這種困難性在理論上至今未能?chē)?yán)格證明,但又無(wú)法否定。對(duì)于許多密碼研究分 析人員和數(shù)學(xué)家而言,因數(shù)分解問(wèn)題的困難性仍是一種信念,一種有一定根據(jù)的合理的信 念。 6.3、ElGamal公鑰密碼一、離散對(duì)數(shù)問(wèn)題群的階：有限群中元素的個(gè)數(shù)。群元素的階：乘法群中滿足 的最小正整數(shù)m。 稱為g在群中的階。是乘法群，群的階為 6。循環(huán)群：

21、群G的每一個(gè)元都是G的某一個(gè)固定元g的乘方。 g稱為G的生成元。 本原元：循環(huán)群 中的生成元稱為域 的本原元。是域，3和5是它的本原元。有限域上的離散對(duì)數(shù)問(wèn)題： 給定一個(gè)素?cái)?shù) p 和 Zp 的一個(gè)本原元 ，對(duì)于 找一個(gè)唯一整數(shù) 使得通常記為例：已知求對(duì)于一般離散對(duì)數(shù)問(wèn)題，沒(méi)有其它有效算法，只有窮搜索，所以是指數(shù)時(shí)間的算法，是困難的.加密變換：對(duì)于任意明文 ，秘密隨機(jī)選取一個(gè)整數(shù) ，密文為（2）隨機(jī)選擇整數(shù) ，計(jì)算 ， 是公鑰，d 是私鑰；二、ElGamal密碼體制 （1）選擇大素?cái)?shù)p， 是一個(gè)本原元，p和 是公開(kāi)的；（3） 明文空間為 ，密文空間為 （4）解密變換：對(duì)任意密文 明文為（3）用戶

22、A想秘密地發(fā)送明文M11給用戶B，A選擇 一個(gè)隨機(jī)數(shù) ，并計(jì)算（2）用戶B選擇整數(shù)d10，作為自己的私鑰，計(jì)算 作為自己的公鑰；解密變換的正確性：例：（1）選取素?cái)?shù)p19，生成元 ；A將（14，17）發(fā)送給B； （4）B 計(jì)算 三、ElGamal密碼體制的安全性 （書(shū)中例6.5，p2579 較大。）1、ElGamal是基于有限域上的離散對(duì)數(shù)困難性；2、素?cái)?shù)p至少為150位十進(jìn)制數(shù)；3、p-1至少有一個(gè)大素因子。6.4 橢圓曲線上的M-V公鑰密碼6.4、橢圓曲線上的M-V公鑰密碼一、有限域上的橢圓曲線 橢圓曲線就是方程所確定的平面曲線。經(jīng)過(guò)坐標(biāo)變換可轉(zhuǎn)化為 有限域上的橢圓曲線就是方程的系數(shù)和取值

23、都為有限域的元素。有限域 （p為大于3的素?cái)?shù)）上的橢圓曲線的點(diǎn)再加上一個(gè)無(wú)窮遠(yuǎn)點(diǎn)所組成的集合E。是滿足同余方程，其中保證有三個(gè)根橢圓曲線的圖象 對(duì)于三次方程可以在橢圓曲線上定義加法運(yùn)算：對(duì)于任意點(diǎn) 可以證明：橢圓曲線E關(guān)于加法構(gòu)成一個(gè)交換群。 |E|表示有限域上的橢圓曲線E中的點(diǎn)的數(shù)目。要精確 計(jì)算該值是困難的，有Hasse定理給出上界和下屆。 Hasse定理： 例：書(shū)中例6. 9Euler準(zhǔn)則：如果 p 是一個(gè)奇素?cái)?shù)，則 z 是模 p 的 平方剩余 當(dāng)且僅當(dāng) 橢圓曲線上的點(diǎn)對(duì)于所定義的加法運(yùn)算構(gòu)成阿貝爾群。 P是橢圓曲線E上的一點(diǎn)，若存在最小的正整數(shù)N，使得nPO，其中O是無(wú)窮遠(yuǎn)點(diǎn)，則稱n為

24、P點(diǎn)的階。我們一般要求n為有限的。 若我們能找到一橢圓曲線E，將明文通過(guò)編碼嵌入到E的點(diǎn)，然后在E上進(jìn)行加密。加密變換也是一種編碼，但從明文通過(guò)編碼嵌入到E上的點(diǎn)的編碼結(jié)果不是密碼，我們假定嵌入變換已解決。那么，橢圓曲線上的加密，就是將熟知的加密運(yùn)算移植到橢圓曲線上。例如 DiffieHellman密碼交換系統(tǒng)已知q和GF（q）是大家共同確定的。用戶A任意選取一個(gè)整數(shù)a， ，將a保密，將 公開(kāi)，g 是GF（q）上一固定元素。用戶B任選一整數(shù)b，將b保密，將 公開(kāi)。A和B的共享密鑰為第三方無(wú)法知道這個(gè)密鑰，這是離散對(duì)數(shù)問(wèn)題。如果在橢圓曲線上實(shí)現(xiàn)上述體制，則：假定橢圓曲線E定義在GF（q）域上。設(shè)

25、 ， 要求由P產(chǎn)生的群的元素足夠多，P的作用相當(dāng)于上述的g。A和B分別選a和b予以保密，但將 公開(kāi)。A，B之間通信用的密鑰為abP，這是第三方無(wú)法知道的。 （1） 設(shè)p3是一個(gè)素?cái)?shù)，E是有限域 上的橢圓曲線， 是橢圓曲線上的一個(gè)點(diǎn)，并且 階足夠大， 使得由 生成的循環(huán)子群中離散對(duì)數(shù)問(wèn)題是難解的。 p和E以及 都公開(kāi)。橢圓曲線上的離散對(duì)數(shù)問(wèn)題： 設(shè)p3是一個(gè)素?cái)?shù)，E是有限域 上的橢圓曲線，設(shè)G是 E的一個(gè)循環(huán)子群，二、Menezes-Vanstone公鑰密碼體制 (93年提出)是G的一個(gè)生成元，求滿足已知的唯一整數(shù)n。M-V 公鑰密碼體制（2）隨機(jī)選取整數(shù)d， ，計(jì)算是公開(kāi)鑰，d是保密的私鑰。（

26、3）明文空間為 密文空間為 加密時(shí)，對(duì)于任意明文 秘密隨機(jī)選取一個(gè)整數(shù)k，密文為（4） 解密時(shí)，明文為 三、橢圓曲線上公鑰密碼的特點(diǎn) 優(yōu)點(diǎn)：同樣安全強(qiáng)度下密鑰短；速度快。 可以應(yīng)用于計(jì)算和存儲(chǔ)能力小的智能卡等場(chǎng)合。 解密過(guò)程的正確性： 橢圓曲線密碼體制與RSA/DSA密碼體制的計(jì)算量比較 橢圓曲線密碼體制 RSA/DSA密碼體制密鑰長(zhǎng)度/bitMIPS/y 密鑰長(zhǎng)度/bit MIPS/y 150 3.81010 5123104 2057.11018 7682108 2341.61028 102431011 128011014 1536310166.5、對(duì)稱鑰密碼和公鑰密碼體制的比較 對(duì)稱鑰和公

27、開(kāi)鑰各有長(zhǎng)處，也各有短處，有些是共有的。 1、對(duì)稱鑰密碼系統(tǒng) 優(yōu)點(diǎn):* 速度快（硬件幾百M(fèi)megabytes/每秒，軟件M/每秒）* 密鑰短( 64bit或128bit)；* 可作為基本單元構(gòu)建各種密碼機(jī)制如偽隨機(jī)數(shù) 產(chǎn)生器、Hash函數(shù)、計(jì)算有效的數(shù)字簽名等；* 弱對(duì)稱鑰密碼可以組合成更強(qiáng)的密碼；* 有比較豐富的歷史； 缺點(diǎn)：* 密鑰管理困難（在兩方通信，各方需保有密 鑰；在網(wǎng)絡(luò)通信，需要大量的密鑰對(duì)，因此 需要無(wú)條件可信TTPtrusted third party）；* 密鑰必須經(jīng)常變化；* 協(xié)議需要無(wú)條件可信的TTP；* 由對(duì)稱鑰構(gòu)造的數(shù)字簽名或者需要大的密鑰 以便公開(kāi)驗(yàn)證或者需要TTP

28、。2、公鑰密碼系統(tǒng) 優(yōu)點(diǎn)是：* 只有私鑰保密；* 在網(wǎng)絡(luò)中密鑰管理只需要功能TTP或離線TTP （ TTP無(wú)條件的是對(duì)所有事情都被信任；功能可信 的被假設(shè)是誠(chéng)實(shí)和公正的，但不能進(jìn)入用戶的密鑰 或私鑰）有效密鑰管理；* 公私鑰對(duì)可以使用較長(zhǎng)時(shí)間(long term key);* 許多公鑰方案可以產(chǎn)生有效的數(shù)字簽名機(jī)制，用于 驗(yàn)證方程的密鑰比對(duì)稱鑰的短得多；* 在大網(wǎng)絡(luò)環(huán)境需要的密鑰數(shù)量比對(duì)稱鑰小得多。缺點(diǎn)：* 速度慢（求模冪運(yùn)算費(fèi)時(shí)，比對(duì)稱鑰慢幾個(gè)數(shù)量 級(jí)，1001000）；* 密鑰長(zhǎng)度長(zhǎng)，約10倍（如RSA中1024bit ; 數(shù)字簽名 長(zhǎng)度比用對(duì)稱鑰實(shí)現(xiàn)數(shù)據(jù)源認(rèn)證的Tag要大）；* 目前沒(méi)有

29、公開(kāi)鑰方案被證明是安全的（分組密碼 也是同樣），最有效的加密方案的安全性建立在 少量假設(shè)的數(shù)論問(wèn)題的困難性上；* 與對(duì)稱鑰相比歷史不長(zhǎng)（1970s）。（并且確定（一對(duì)一）的公鑰加密算法容易受到選擇明文攻擊。所以出現(xiàn)概率加密算法，就是密文和密文不是一一對(duì)應(yīng)的。）3、總結(jié) 公鑰的長(zhǎng)處恰好是對(duì)稱鑰的短處，反之依然，所以二者可以取長(zhǎng)補(bǔ)短。所以公鑰常用于加密對(duì)稱密鑰。這樣的系統(tǒng)成為混合密碼系統(tǒng)。例如當(dāng)兩方需要會(huì)話時(shí)，雙方利用公鑰密碼系統(tǒng)，建立對(duì)稱的會(huì)話鑰，之后利用對(duì)稱密碼體制進(jìn)行會(huì)話，之后銷(xiāo)毀會(huì)話鑰，這樣大大減小了會(huì)話鑰管理的風(fēng)險(xiǎn)。 在許多密碼系統(tǒng)中對(duì)稱鑰塊密碼是最主要和重要的單元。單獨(dú)使用時(shí)它們提供保

30、密性。作為一個(gè)組成塊，它們普遍用于構(gòu)建偽隨機(jī)數(shù)產(chǎn)生器、流密碼、MACs和hash函數(shù)。它們進(jìn)一步可以作為消息認(rèn)證技術(shù)、數(shù)據(jù)完整性機(jī)制、身份認(rèn)證協(xié)議和數(shù)字簽名（對(duì)稱鑰）的中央元件。 公鑰加密的主要目的是提供保密性或機(jī)密性,但目前計(jì)算效率不如對(duì)稱鑰。由于A的加密變換是公開(kāi)的，公鑰加密單獨(dú)不能提供數(shù)據(jù)源認(rèn)證或數(shù)據(jù)完整性。這種確認(rèn)必須利用附加的性質(zhì)，包括消息認(rèn)證和數(shù)字簽名。 所以實(shí)用中，公鑰密碼學(xué)可提供有效的數(shù)字簽名（特別是不可否認(rèn)nonrepudiation的）和密鑰管理；對(duì)稱鑰密碼學(xué)提供有效地加密和一些數(shù)據(jù)完整性應(yīng)用。 公開(kāi)密鑰密碼分析 攻擊公開(kāi)密鑰密碼系統(tǒng)的方法有如下幾種：窮舉法 對(duì)此防范措施應(yīng)

31、為：使用長(zhǎng)的密鑰。但是由于公鑰算法依賴于單向陷門(mén)函數(shù)，計(jì)算函數(shù)的復(fù)雜性與密鑰的長(zhǎng)度的關(guān)系可能會(huì)增長(zhǎng)得更快。因而密鑰大小必須足夠大，以保證安全性，但是又要足夠小以便加密解密使用。根據(jù)公鑰計(jì)算私鑰 在數(shù)學(xué)上證明，對(duì)任何公鑰算法，這種分析可能成功。因而對(duì)任何公鑰算法，對(duì)這種攻擊方法都需要測(cè)試。EFS初步介紹利用EFS，用戶可以按加密格式將他們的數(shù)據(jù)存儲(chǔ)在硬盤(pán)上，保證它們的機(jī)密性。EFS具有下面幾個(gè)關(guān)鍵的功能特征： 1. 它在后臺(tái)運(yùn)行，對(duì)用戶和應(yīng)用程序來(lái)說(shuō)是透明的。 2. 只有被授權(quán)的用戶才能訪問(wèn)加密的文件。EFS自動(dòng)解密該文件，以供使用，然后在保存該文件時(shí)再次對(duì)它進(jìn)行加密。管理員可以恢復(fù)被另一個(gè)用戶加密的數(shù)據(jù)。 3. 它提供內(nèi)置的數(shù)據(jù)恢復(fù)支持功能。 4. 它要求至少有一個(gè)恢復(fù)代理，用以恢復(fù)加密的文件。可以指定多個(gè)恢復(fù)代理，來(lái)管理的 EFS恢復(fù)程序。各個(gè)恢復(fù)代理都需要有 EFS恢復(fù)代理證書(shū)。注意：加密操作和壓縮操作是互斥的。因此，建議或者采用加密技術(shù)，或者對(duì)文件進(jìn)行壓縮，二者不能同時(shí)采用。對(duì)文件夾或者文件進(jìn)行加密EFS加密功能是NTFS文件系統(tǒng)的功能之一。文件的加密是利用文件加密密鑰實(shí)現(xiàn)的。加密操作： 打開(kāi)一個(gè)NTFS分區(qū)的文