第四章公鑰密碼體制4.1公鑰密碼體制的基本原理4.2RSA算法4.3ElGamal密碼體制4.4橢圓曲線密碼（ECC）體制1公鑰密碼體制的起源?公鑰密碼又稱為雙鑰密碼和非對稱密碼，是1976年由Diffie和Hellman在其“密碼學新方向”一文中提出的，這在密碼學的發展史上具有里程碑的意義，并在1978年由Rivest、Shamire和Adleman提出了第一個比較完善的公鑰密碼體制算法，即著名的RSA算法。后來陸續出現了ElGalam、ECC等公鑰密碼體制。解決了對稱密碼體制中密鑰分配、消息認證、加密、數字簽名等問題。特別適合于計算機網絡系統的應用。主要有以下算法：–Diffie-Hellman密鑰交換算法–背包算法–RSA算法–ElGamal算法2公開密鑰算法

公開密鑰算法是非對稱算法，即密鑰分為公鑰和私鑰，因此稱雙密鑰體制雙鑰體制的公鑰可以公開，因此也稱公鑰算法公鑰算法的出現，給密碼的發展開辟了新的方向。公鑰算法雖然已經歷了20多年的發展，但仍具有強勁的發展勢頭，在鑒別系統和密鑰交換等安全技術領域起著關鍵的作用公鑰密碼是現代密碼體制的一種公鑰密碼體制的編碼系統是基于數學中的單項陷門函數3對稱算法的不足（1）密鑰管理量的困難傳統密鑰管理：兩兩分別用一個密鑰時，則n個用戶需要C(n,2)=n(n-1)/2個密鑰，當用戶量增大時，密鑰空間急劇增大。如:n=100時，C(100,2)=4,995n=5000時，C(5000,2)=12,497,500（2）密鑰必須通過某一信道協商，對這個信道的安全性的要求比正常的傳送消息的信道的安全性要高4.1公鑰密碼體制的基本原理4（3）數字簽名的問題傳統加密算法無法實現抗抵賴的需求。(4)在進行保密通信時，發送者與接收者需要使用一個安全信道來建立會話密鑰。會話密鑰的取得可以通過兩種方式實現：其一、通過共享密鑰加密傳輸會話密鑰（人工方式獲得）其二、通過密鑰分配中心獲得會話密鑰，分配成本很高。5基本概念公鑰密碼體制：指一個加密系統的加密密鑰和解密密鑰匙不一樣的，或者說不能由一個推導出另一個。其中一個稱為公鑰用于加密，是公開的，另一個稱為私鑰用于解密，是保密的。公鑰密碼體制是基于單項陷門函數單向函數：設f是一個函數，如果對任意給定的x，計算y，使得y=f(x)是容易計算的，但對于任意給定的y，計算x，使得x=f-1(y)是難解的，即求f的逆函數是難解的，則稱f是一個單項函數。在密碼學中，最常用的單項函數有兩類：公鑰密碼體制中的單項陷門函數和消息摘要中的單項散列函數單向陷門函數：設f是一個函數，t是與f有關的一個參數。對任意給定的x，計算y，使得y=f(x)是容易計算的,如果當不知參數t時，計算f的逆函數是難解的，但當知道參數t時，計算函數f的逆函數是容易的，則稱f是一個單項陷門函數，參數t成為陷門。6注意：單向函數不能用于加密在公鑰密碼體制中，計算f(x)相當于加密，陷門y相當于私鑰，而利用陷門y，求f(x)中的x則相當于解密。公鑰密碼體制最初的目標是解決DES算法中密鑰管理的問題，而實際結果不但很好地解決了這個難題，還利用公鑰密碼體制完成了對消息的數字簽名以防對消息的抵賴行為；同時，還可以用數字簽名發現攻擊者對消息的非法篡改，以保護數據信息的完整性。7公開密鑰密碼的重要特性

加密與解密由不同的密鑰完成加密:X

Y:Y=EKU(X)解密:Y

X:X=DKR(Y)=DKR(EKU(X))

知道加密算法,從加密密鑰得到解密密鑰在計算上是不可行的

兩個密鑰中任何一個都可以用作加密而另一個用作解密(不是必須的)X=DKR(EKU(X))8基于公開密鑰的加密過程Alices向Bob發送加密信9基于公開密鑰的鑒別過程Alices與Bob通信，Bob進行驗證10用公鑰密碼實現保密?用戶擁有自己的密鑰對(KU,KR)?公鑰KU公開,私鑰KR保密?A

B:Y=EKUb(X)?B:DKRb(Y)=DKRb(EKUb(X))=X用公鑰密碼實現鑒別?條件:兩個密鑰中任何一個都可以用作加密而另一個用作解密?數字簽名:A

ALL:Y=DKRa(X)ALL:EKUa(Y)=EKUa(DKRa(X))=X?數字簽名+保密:A

B:Z=EKUb(DKRa(X))B:EKUa(DKRb(Z))=X11加密/解密?數字簽名(身份鑒別)?密鑰交換公鑰密鑰的應用范圍12基本思想和要求?涉及到各方：發送方、接收方、攻擊者?涉及到數據：公鑰、私鑰、明文、密文?公鑰算法的條件：–產生一對密鑰是計算可行的–已知公鑰和明文，產生密文是計算可行的–接收方利用私鑰來解密密文是計算可行的–對于攻擊者，利用公鑰來推斷私鑰是計算不可行的–已知公鑰和密文，恢復明文是計算不可行的–(可選)加密和解密的順序可交換13常用的公開密鑰算法公鑰算法的種類很多，具有代表性的三種密碼：基于整數分解難題（IFP）的算法體制(RSA)

基于離散對數難題（DLP）算法體制(ElGamal)基于橢圓曲線離散對數難題（ECDLP）的算法體制(ECC)14Diffie-Hellman密鑰交換算法Diffie和Hellman在其里程碑意義的文章中，雖然給出了密碼的思想，但是沒有給出真正意義上的公鑰密碼實例，也既沒能找出一個真正帶陷門的單向函數然而，他們給出單向函數的實例，并且基于此提出Diffie-Hellman密鑰交換算法15Diffie-Hellman密鑰交換算法的原理基于有限域中計算離散對數的困難性問題之上：設F為有限域，g∈F是F的乘法群F*=F\{0}=<g>，并且對任意正整數x，計算gx是容易的；但是已知g和y求x使y=gx，是計算上幾乎不可能的這個問題稱為有限域F上的離散對數問題。公鑰密碼學中使用最廣泛的有限域為素域FP16Diffie-Hellman密鑰交換協議描述當Alice和Bob要進行保密通信時，他們可以按如下步驟來做：(1)Alice選取大的隨機數x，并計算X=gx(modP)(2)Bob選取大的隨機數x

，并計算X

=gx

(modP)(3)Alice將X傳送給Bob；Bob將X

傳送給Alice(4)Alice計算K=(X

)X(modP);Bob計算K

=（X)X

(modP),

易見，K=K

=g

xx

(modP)由(4)知，Alice和Bob已獲得了相同的秘密值K雙方以K作為加解密鑰以傳統對稱密鑰算法進行保密通信174.2RSA算法184.2RSA算法最早實現Diffie和Hellman的想法的美國麻省理工學院的Rivest、Shamie

和Adleman3人。他們于1977年研制并于1978年發表了一種密碼算法，一般稱為RSA算法，實現了公鑰密碼的基本思想。19RSA安全性是基于大整數分解因子的困難性204.2.1RSA算法描述1.RSA密碼體制的建立（1）選擇兩個大素數p和q，p≠q（2）計算乘積n=pq,n的Euler數φ(n)=(p-1)(q-1)（3）選擇隨機數e,(1<e<φ(n)),使gcd(e，φ(n))=1（4）使用Euclidean算法計算de=1modφ(n)（5）對每一個密鑰k=(n，p，q，d，e)，定義加密變換為

Ek(x)=xemodn,解密變換為Dk(x)=ydmodn，（6）公鑰:KU={e,n},私鑰:KR={d,p,q}密碼分析者攻擊RSA體制的關鍵點在于如何分解n。若分解成功使n=pq，則可以算出φ(n)＝（p-1)(q-1)，然后由公開的e，解出秘密的d。212.RSA算法舉例1.設p=7,q=17,2.計算n=7*17=119；參數T={n=119};φ(n)=(7-1)(17-1)=96;3.選擇隨機數e=5,gcd(5,96)=1;公鑰=5;4.計算d,(d*e)mod96=1;d=77;私鑰=77;5.設:明文m=19

加密：C=（19）5mod119=66

脫密：m=（66）77mod119=19計算d的過程如下：96=5*19+11=96-5*19mod96=96-5*(-96+19)mod96==96+5*77mod96d=7722RSA實例已知p=11，q=13，e=7,M=85，求解d，c解：n=p*q=143;φ(n)=(p-1)*(q-1)=10*12=120計算d，使得de=1mod120120=7*17+11=120-7*17mod120=120-7*(-120+17)mod120==120+7*103mod120d=10323RSA算法的安全性分析密碼分析者攻擊RSA體制的關鍵點在于如何分解n若分解成功使n=pq，則可以算出φ(n)＝（p-1)(q-1)，然后由公開的e，解出秘密的d若使RSA安全，p與q必為足夠大的素數，使分析者沒有辦法在多項式時間內將n分解出來24RSA算法的安全性分析建議選擇p和q大約是100位的十進制素數,按每秒109次運算的高速計算機也要計算106年,估計對200位十進制數的因數分解,在上億次的計算機上要進行55萬年。模n的長度要求至少是512比特EDI攻擊標準使用的RSA算法