密碼學(xué)課件：八、公鑰密碼體制

1、公鑰密碼體制主要內(nèi)容概述公鑰密碼的應(yīng)用RSA公鑰密碼體制ElGamal公鑰密碼體制橢圓曲線密碼體制概述公鑰密碼體制提出的背景（1）在對稱密碼體制中，密鑰分發(fā)過程復(fù)雜，代價高。安全信道的建立是突出問題。（2）密鑰量增大造成密鑰管理困難。當(dāng)用戶增多，密鑰量增加，密鑰管理復(fù)雜化。如n個用戶兩兩保密通信，則每個用戶需要獲取并保管(n-1)個密鑰，總密鑰量為n(n-1)/2，當(dāng)n=100時，密鑰量是4995個；當(dāng)n=5000時，密鑰量是增加到超過1200萬個。概述公鑰密碼體制提出的背景（3）保密通信系統(tǒng)的開放性差。如果收發(fā)雙方素不相識，或沒有可靠的密鑰傳遞渠道，則無法通信。（4）存在數(shù)字簽名的困難性。當(dāng)

2、用對稱密碼算法實現(xiàn)數(shù)字簽名時，由于通信雙方擁有相同的密鑰，使得接收方可以偽造數(shù)字簽名，發(fā)送方可以抵賴發(fā)送過的消息。概述公鑰密碼體制的發(fā)展是密碼學(xué)歷史上的一次革命，有著極其重要的歷史里程碑意義。公鑰密碼體制出現(xiàn)之前的幾乎所有的密碼系統(tǒng)都建立在基本的代替和換位基礎(chǔ)上（如DES、AES等）公鑰密碼體制與以前的方法不同，基于一種特殊的數(shù)學(xué)函數(shù)而不是代替和換位操作公開密鑰體制不對稱，有兩個密鑰，一個公鑰，一個私鑰。概述基本思想所有用戶的公開密鑰可以被其他所有用戶訪問，每一個用戶的解密密鑰將由用戶保存并嚴(yán)格保密。一般公鑰密碼體制的示意圖：KUB為公鑰，KRB為私鑰。概述基本思想公鑰密碼體制的要求：（1）D

3、KRB(c)是EKUB(m)的逆變換DKRB(c)= DKRB(EKUB(m)=m（2）在已知加密密鑰或解密密鑰時，相應(yīng)的加密或解密計算是容易的（3）如果不知道私鑰KRB，那么即使知道公鑰KUB 、具體的加密與解密算法以及密文，確定明文是計算上不可行的。單向函數(shù)定義：設(shè)定義域為X，值域為Y，函數(shù)y=f(x)稱為單向函數(shù)：如果對于所有xX計算f(x)都是“容易的”，而對于“基本上所有yY”發(fā)現(xiàn)任意一個xX滿足f(x)=y都是“計算不可能的”。xf(x)HardEasy單向陷門函數(shù)定義：單向陷門函數(shù)是單向函y=f(x)再附加如下特性：如果給定一些附加信息，這些附加信息稱為陷門信息K，那么，就對任意

4、yY求解xX滿足fK(x)=y都變得“容易了”。xf(x)HardEasyEasyK概述因此設(shè)計公鑰密碼體制就變成了尋找單向陷門函數(shù)，目前基于的單向函數(shù)設(shè)計的公鑰密碼體制：（1）大整數(shù)分解問題（公鑰密碼體制RSA）（2）有限域上的離散對數(shù)問題（公鑰密碼體制ElGamal）（3）橢圓曲線上的離散對數(shù)問題（公鑰密碼體制ECC）公鑰密碼的應(yīng)用1. 用于數(shù)據(jù)加密實現(xiàn)機密性要求對數(shù)據(jù)進行加密：發(fā)送方用接收方的公鑰加密消息，接收方用自己的私鑰解密。2. 用于數(shù)字簽名發(fā)送方用自己的私鑰簽名消息，接收方通過發(fā)送方對應(yīng)的公鑰來鑒別消息，并且發(fā)送方不能對自己的簽名進行否認(rèn)。公鑰密碼的應(yīng)用3. 用于密鑰分發(fā)和協(xié)商在

5、公開信道上進行大規(guī)模的密鑰分發(fā)和協(xié)商。公鑰密碼算法運算量大，相對而言，對稱加密算法運算量小。如AES在256個元素的范圍內(nèi)運算，基本的運算如乘法、求逆可通過“查表”來完成，效率非常高。故一般不直接用公鑰密碼系統(tǒng)來加密量大的數(shù)據(jù)。一般采用混合體制：用公鑰密碼體制加密對稱密碼體制短期所需的一個密鑰來進行分發(fā)，用對稱體制加密數(shù)據(jù)。RSA公鑰密碼體制對稱密碼體制# 加密密鑰與解密密鑰同：K1=K2在通信前，由發(fā)送方生成密鑰，通過安全信道送到接收方。非對稱密碼體制# 加密密鑰與解密密鑰不同：K1K2在通信前，每個用戶都有一對用于加密和解密的密鑰對，公鑰可以發(fā)布，私鑰自己保管。RSA由MIT的Ron Ri

6、vest、Adi Shamirh和LenAdleman在1978年提出。RSA取名來自開發(fā)他們?nèi)叩拿?。已成為公鑰密碼的國際標(biāo)準(zhǔn)數(shù)學(xué)基礎(chǔ)是歐拉定理，安全性建立在大整數(shù)因子分解的困難性之上。基于數(shù)論事實：將兩個大素數(shù)相乘很容易，反過來對乘積進行因式分解非常困難。RSA算法描述初等數(shù)論中的三個定理和兩個定義：歐拉函數(shù)的定義：設(shè)nZ且n1，將小于n且與n互素的正整數(shù)的個數(shù)稱為n的歐拉函數(shù)，記為(n)。定理1：設(shè)m1,m2N，gcd(m1,m2)=1，則(m1m2)=(m1)(m2)。定理2：如果p為素數(shù)，則(p)=p-1歐拉定理：設(shè)m是正整數(shù)，且gcd(a,m)=1，則a(m)1 mod m乘法逆

7、元的定義：設(shè)a，nZ且n1，如果存在bZ使得ab1 mod n，則a,b稱為互為模n的乘法逆元，記為ba-1 mod n。1.密鑰生成（1）選擇兩個隨機的大素數(shù)p和q，并計算n=pq和(n)=(p-1)(q-1)（2）選擇一個隨機數(shù)e,1e(n)，滿足gcd(e,(n)=1，并計算d=e-1 mod (n)（3）公鑰為(e, n)，私鑰為d。RSA算法描述RSA算法描述2.加密對明文mn，其對應(yīng)的密文為c=me mod n3.解密對密文c，其對應(yīng)的明文為m=cd mod nRSA算法描述對算法的說明：RSA密碼體制中用到兩個群：群(Z(n), )和群(Zn, )（1）群(Z(n), )密鑰對(

8、e,d)的產(chǎn)生的乘法運算是在群(Z(n), )中，此時， ed=1 mod (n)即，在群(Z(n), )中，元素d是元素e的逆元。（2）群(Zn, )加密運算c=me mod n與解密運算m=cd mod n中的乘法運算是在群(Zn, )中，n=pq。RSA算法描述進一步說明：因在群中運算，必須滿足群運算的條件如下。（1）1e(n)：若e1e2 mod (n)，則對所有的明文x，有xe1xe2 mod n，因此公鑰e的只需在范圍(1e(n)中選擇。（2）e與(n)互素：保證e模(n)的乘法逆d存在，e、d互為乘法逆，所以d也與(n)互素。（3）規(guī)定明文mn，則(m-tn)e mod n=me

9、 mod n，tZ即m-tn與m的加密結(jié)果相同，這樣使得解密結(jié)果唯一。RSA算法描述下面證明加密和解密是逆運算。m必與p和q中至少一個互素。否則，若與p和q都不互素，因p和q都是素數(shù)，則m必是p和q的倍數(shù)，故也是n的倍數(shù)，這與mn矛盾。另： de=1 mod (n)故存在整數(shù)k滿足： de=k(n)+1分兩種情況討論：RSA算法描述（1）m僅與p和q兩者之一互素，不凡設(shè)僅與p互素，則m是q的倍數(shù)，那么存在整數(shù)a使得m=aq，由歐拉定理：mk(n)mk(p)(q)(m(p)k(q)1 mod p于是存在整數(shù)t使得：mk(n)=tp+1兩邊同乘 m=aq得： mk(n)+1=tapq+m=tan+

10、m由此得： cd=med=mk(n)+1=tan+mm mod nRSA算法描述（2）如果m與p和q都互素，那么m也和n互素，有cd=med=mk(n)+1=m(m(n)km mod n證畢。RSA算法描述第二種方法證明加密和解密是逆運算。先介紹模運算的兩個性質(zhì)：（1）p和q互素，若x mod p=0，且x mod q=0，則x mod pq=0（2）p和q互素，若y mod p=x，且y mod q=x，則y mod pq=x。RSA算法描述第二種方法證明加密和解密是逆運算。由于： de=1 mod (n)故存在整數(shù)k滿足： de=k(n)+11.當(dāng)gcd(m,p)=1，由費爾馬小定理有mp

11、-1=1 mod p故有med=mk(n)+1=mk(p-1)(q-1)+1=m(m(p-1)k(q-1)m mod p2.當(dāng)gcd(m,p)=p時，medm mod p顯然成立。RSA算法描述同樣可推出：med=mk(n)+1 m mod q故有：cdmed=mk(n)+1 m mod nRSA算法描述例，用戶B取p=47，q=71，n=pq=4771=3337，(n)=4670=3220。設(shè)e=79,用擴展歐幾里得算法：d=e-1 mod (p-1)(q-1)=79-1 mod 3220=1019因此B的公鑰為(3337,79)，私鑰為1019.假定用戶A將消息688加密后發(fā)給B，A首先獲

12、得B的公鑰(3337,79) ，然后計算出密文c=68879 mod 3337=1570并把密文發(fā)給B。B收到密文后，用私鑰進行解密m=15701019 mod 3337=688思考題：公鑰為(e, n)，私鑰為d，設(shè)m=(n)=(p-1)(q-1),有ed1 mod m針對給定的n，滿足條件的密鑰對(e,d)有多少？說明：e與(n)互素，且1e(n)，所以e的數(shù)量最多有(n)= (p-1)(q-1)個。對每個選定的e，其乘法逆d即是同余方程ex1 mod m的解。方程的解的數(shù)量是滿足條件的同余類的數(shù)量，模m的同余類最多有m個。因此在1e,de(e+1)/2時，運用低指數(shù)攻擊法便可求出m。選型

13、e為16位的素數(shù)，是一種可加速加密運算并同時可以避免低指數(shù)攻擊法的選擇。為避免第3種攻擊，e應(yīng)選擇在其模(n)時的階最大，即ei=1 mod (n)中最小的i為i=(p-1)(q-1)/2。RSA在應(yīng)用中的問題6.私鑰d長度應(yīng)大于n長度的1/4在許多應(yīng)用場合，人們常常使用位數(shù)較短的私鑰d，以降低解密或簽名的時間，尤其是在智能卡的應(yīng)用中，因其CPU的處理能力低。若d的長度很小，則猜測d的空間變小。1990年Wiener提出一種針對d長度較小的攻擊方法，證明了若d的長度小于n長度的1/4，利用連分?jǐn)?shù)算法，可以求出正確的d?？紤]實際使用和安全性，一般盡量降低e的長度而不應(yīng)降低d的長度。RSA在應(yīng)用中

14、的問題7.不可使用公共的模nRSA使用公共模n有很多優(yōu)點：密鑰管理簡單，節(jié)省公鑰的存儲空間，但存在風(fēng)險。相同的明文分別發(fā)送給兩個不同的人i，j，公鑰為ei，ej，且互素，ci=mei mod n，cj=mej mod n。由擴展歐幾里得算法可求得兩個整數(shù)r及s使得rei+sej=1，顯然r和s一定有一個負數(shù)。假設(shè)r為負，若ci與n互素，則ci乘法逆元存在，并輕易求得ci-1，因此易得明文m：(ci-1)|r|(cj)s=(mei)-|r|(mej)s=mrei+sej=m mod n。若ci與n不互素，則可以利用最大公因子方法求出ci與n的最大公因子，即為p或q，進而分解n。RSA在應(yīng)用中的問

15、題8.不僅要注意私鑰d和大素數(shù)p、q的保密，還要保密(n)（1）若(n)已知，則能確定e模(n)的乘法逆元，即d=e-1 mod (n)（2）(n)=(p-1)(q-1)=pq-p-q+1=n-(p+q)+1(p+q)=n+1-(n)(p-q)2=(p+q)2-4pq=(p+q)2-4n從而求出p+q和p-q，進而可以求出p、q。RSA在應(yīng)用中的問題9.避免不動點問題每個RSA系統(tǒng)都存在不動點，即存在特定的明文m1）成立的最小正整數(shù)n為a模p的階。如果a模p的階n=(p)，則稱a為p的本原根。概述設(shè)p為素數(shù)，a是p的本原根，則在模p下a mod p, a2 mod p, a3 mod p, a

16、p-1 mod p產(chǎn)生1到p-1之間的所有值，且每個值僅出現(xiàn)一次。因此：對任意bZp*=1,p-1，都存在唯一正整數(shù)kZp*，使bak mod p。這樣，模指數(shù)函數(shù)yax mod p是Zp*到Zp*的一一映射。概述對映射yax mod p， xZp*進行變換，使得y作為自變量，x作為因變量，表示成：xlogay mod p。上式稱x為模p下以a為底y的對數(shù)。由于運算定義在Zp*上，所以稱為離散對數(shù)運算。概述在實數(shù)域上，設(shè)a,b,cR，如果a=bc，則稱c是以b為底a的對數(shù)，記作c=logba，a0。如果a,b為實數(shù)，計算c容易，如果a,b為有限域中的元素，求正整數(shù)n，使a=bn，則是一個很困難

17、的問題。概述針對函數(shù)yax mod p和xlogay mod p：如果已知a、x、p，使用快速指數(shù)算法容易計算得到y(tǒng)，反過來，如果僅知a、p和y，當(dāng)p較大時（如p的長度在150位以上）計算xlogay mod p非常困難。ElGamal密碼體制基本以上計算的困難性之上。密鑰的生成選取一個大素數(shù)p，aZp*是p的一個本原根。隨機生成一個整數(shù)x，2xp-2，并計算：y=ax mod p。以（p,a,y）作為公鑰，x作為私鑰。加密設(shè)用戶想加密的明文為m3的素數(shù))上的一條橢圓曲線產(chǎn)生的循環(huán)群，對于Ep(a,b)上任意兩點P和Q，尋找一個整數(shù)k3的素數(shù))上的一條橢圓曲線產(chǎn)生的循環(huán)群，任取gEp(a,b)

18、，再取正整數(shù)xp，計算y=xg。公鑰為g、y、p，私鑰為x。（因Ep(a,b)為循環(huán)群，故任意元素g是其生成元，即Ep(a,b)=gk|kZ。）橢圓曲線密碼算法加密變換對于明文m，隨機選取正整數(shù)kp，計算c1=kg和c2=mky。密文為c=(c1,c2)解密變換m=c2(-xc1)加解密互逆驗證：c2(-xc1)=(mky)(-xkg)=(mkxg)(-xkg)=m密文依賴于明文和隨機數(shù)k，因此一個明文對于多個密文，即密文具有“非確定性”。橢圓曲線密碼算法總結(jié)對任意素數(shù)p構(gòu)造一個有限域GF(p)即（Zp,+p,p），Zp=0,1,2,p-1。任取a,bZp，定義a+pb=(a+b) mod p

19、, apb=(ab)mod p。構(gòu)造循環(huán)群(E,)，集合E中的元素除無窮遠點O之外，都由序偶(x,y)構(gòu)成，且x和y都來自于有限域GF(p)，兩者之間的關(guān)系由橢圓曲線方程： y2x3+ax+b (mod p)（ 4a3+27b20 mod p，a,bZp）進行約束。根據(jù)橢圓曲線的特性，可得(x1,y2)(x1,y2)運算的具體實現(xiàn)方法。在循環(huán)群(E,)上數(shù)乘的逆運算即是離散對數(shù)難題。例：取g=(2,7)為E11(1,6)的生成元，假設(shè)某用戶的私鑰是x=7，那么y=7g=(7,2)，公鑰(g,y,p)=(2,7), (7,2),11)。假設(shè)有一明文消息m=(10,9)，取k=3，密文計算如下：c

20、=(c1,c2)=(kg,mky)=(3g,(10,9)3(7,2)=(8,3),(10,9)(3,5)=(8,3),(10,2)解密：m=c2(-xc1)=(10,2)(-7(8,3)=(10,2)(-(3,5)=(10,2)(3,6)=(10,9)算法中的運算都是群Ep(a,b)上元素的加法運算，因此要用某種編碼方式將原始的明文消息m嵌入到Ep(a,b)的點上，然后才能使用群Ep(a,b)的運算規(guī)則進行運算。明文信息嵌入橢圓曲線明文信息嵌入橢圓曲線一個算法設(shè)橢圓曲線E：y2x3+ax+b (mod p)，p為素數(shù)。數(shù)字明文m將被植入一個點G(x,y)的x坐標(biāo)。設(shè)x=mK+j，0jK，其中K

21、表示一個大整數(shù)。明文信息嵌入橢圓曲線(1)計算G(x,y)的x坐標(biāo)step 1：取整數(shù)K，使m滿足(m+1)K2160）曲線階的大素數(shù)因子不能整除pk-1(1k20)對于二進制域F(2m)，m不能為合數(shù)。公鑰密碼體制總結(jié)單向函數(shù)定義：設(shè)定義域為X，值域為Y，函數(shù)y=f(x)稱為單向函數(shù)：如果對于所有xX計算f(x)都是“容易的”，而對于“基本上所有yY”發(fā)現(xiàn)任意一個xX滿足f(x)=y都是“計算不可能的”。xf(x)HardEasy單向陷門函數(shù)定義：單向陷門函數(shù)是單向函y=f(x)再附加如下特性：如果給定一些附加信息，這些附加信息稱為陷門信息K，那么，就對任意yY求解xX滿足fK(x)=y都變得“容易了”。xf(x)HardEasyEasyKRSA算法基于大整數(shù)分解問題的難解已知公鑰(e,n)和明文m，加密計算c=me mod n很容易；但是已知c、n、e，解密計算m很難