現(xiàn)代密碼學(xué)公鑰密碼體制課件

1、第6章 公鑰密碼體制 6.1 公鑰密碼的原理及典型公鑰密碼 6.2 橢圓曲線密碼 6.3 超橢圓曲線密碼 6.4 基于身份的公鑰密碼體制 第第6章章 公鑰密碼體制公鑰密碼體制 第6章 公鑰密碼體制 6.1 公鑰密碼的原理及典型公鑰密碼公鑰密碼的原理及典型公鑰密碼6.1.1 公鑰密碼的原理公鑰密碼的原理公鑰密碼的思想最早由Diffie和Hellman在其論文“New Directions in Cryptography”中提出。他們?cè)O(shè)想了一種無(wú)須事先傳遞密鑰的密碼體制，在該體制中，用戶Alice有一對(duì)密鑰：公開(kāi)的加密密鑰(簡(jiǎn)稱公鑰)和保密的解密密鑰(簡(jiǎn)稱私鑰)。向Alice發(fā)送秘密信息時(shí)，用其公

2、鑰加密，Alice收到信息后，用私鑰解密。由于加密密鑰與解密密鑰不同，因此公鑰密碼體制又被稱為非對(duì)稱密碼體制，而傳統(tǒng)密碼(分組密碼、序列密碼)被稱為對(duì)稱密碼體制。第6章 公鑰密碼體制 與對(duì)稱密碼相比，公鑰密碼有以下特點(diǎn)：() 安全性取決于某些困難問(wèn)題的難解性；() 無(wú)須事先傳遞密鑰；() 計(jì)算量通常大于對(duì)稱密碼。公鑰密碼中常用的難解問(wèn)題有分解大整數(shù)、離散對(duì)數(shù)問(wèn)題、橢圓曲線上的離散對(duì)數(shù)問(wèn)題等，其安全性取決于構(gòu)造算法所依賴的數(shù)學(xué)問(wèn)題的計(jì)算復(fù)雜性，所以公鑰密碼在理論上是不安全的，但在實(shí)際應(yīng)用中可以選擇足夠安全的參數(shù)來(lái)保證計(jì)算上的安全性。第6章 公鑰密碼體制 6.1.2 Diffie-Hellman密

3、鑰交換Diffie和Hellman給出了一種通信雙方無(wú)須事先傳遞密鑰也能利用對(duì)稱密碼體制進(jìn)行保密通信的方法，這就是Diffie-Hellman密鑰交換協(xié)議(簡(jiǎn)稱D-H協(xié)議)，在該協(xié)議中，通信雙方通過(guò)協(xié)商可以建立一個(gè)秘密的密鑰。D-H協(xié)議充分體現(xiàn)了公鑰密碼的思想，其安全性基于離散對(duì)數(shù)問(wèn)題。第6章 公鑰密碼體制 設(shè)系統(tǒng)中公開(kāi)的參數(shù)為大素?cái)?shù)p和模p的原根g，用戶Alice和Bob為了協(xié)商一個(gè)公用的秘密密鑰，需要進(jìn)行如下步驟：(1) Alice隨機(jī)選擇整數(shù)xA，計(jì)算 ，將yA傳給Bob；(2) Bob隨機(jī)選擇整數(shù)xB，計(jì)算，將yB傳給Alice；(3) Alice計(jì)算，Bob計(jì)算，易知兩者是相等的，從

4、而可將作為雙方的通信密鑰。D-H協(xié)議的安全性是基于這樣一個(gè)假設(shè)，即已知和，求xB是困難的，Diffie和Hellman假設(shè)此問(wèn)題的困難等價(jià)于離散對(duì)數(shù)問(wèn)題。AAmodxygpBBmodxygpAA BBmodxxxygpBB AAmodx xxygpA BmodxxkgpA BxxgAxg第6章 公鑰密碼體制 6.1.3 RSA1977年，美國(guó)麻省理工學(xué)院的三位數(shù)學(xué)家Ron Rivest、Adi Shamir和Len Adleman成功地設(shè)計(jì)了一個(gè)公鑰密碼算法，該算法根據(jù)設(shè)計(jì)者的名字被命名為RSA，在其后的30年中，RSA成為世界上應(yīng)用最為廣泛的公鑰密碼體制。設(shè)RSA系統(tǒng)中每個(gè)用戶有公開(kāi)的加密密

5、鑰n、e和保密的解密密鑰d，這些密鑰通過(guò)以下步驟確定：(1) 用戶選擇兩個(gè)大素?cái)?shù)p、q，計(jì)算n=pq及(n)=(p1)(q1)；第6章 公鑰密碼體制 (2) 選擇隨機(jī)數(shù)e，要求1e(n)，且gcd(e，(n)=1)；(3) 求出e模(n)的逆d，即ed1 mod (n)；(4) 將n、 e公開(kāi)，d保密。加密時(shí)，首先將明文表示為小于n的整數(shù)，設(shè)m為明文，要將m加密并發(fā)送給用戶Alice時(shí)，利用Alice的公開(kāi)密鑰nA、eA，計(jì)算求出的整數(shù)c即為密文。AAmodecmn第6章 公鑰密碼體制 Alice收到c后，利用自己的解密密鑰dA，計(jì)算求出的m即為明文。AAmoddmcn第6章 公鑰密碼體制 6

6、.1.4 ElGamalElGamal是基于離散對(duì)數(shù)問(wèn)題的最著名的公鑰密碼體制，其系統(tǒng)參數(shù)如下：選擇大素?cái)?shù)p和模p的原根g，隨機(jī)選擇整數(shù)x，計(jì)算y=gx mod p，將p、g、y公開(kāi)，x保密。加密時(shí)，假設(shè)明文被編碼為整數(shù)m，加密者隨機(jī)選擇整數(shù)k，滿足gcd(k，p1)=1，再計(jì)算c1=gk mod pc2=myk mod p則密文為c=(c1，c2)。接收方收到密文組(c1，c2)后，進(jìn)行如下的解密運(yùn)算：11121()()()modxkkxkxkxccmygmggmp第6章 公鑰密碼體制 6.2 橢圓曲線密碼橢圓曲線密碼6.2.1 橢圓曲線橢圓曲線(Elliptic Curve)橢圓曲線的圖像

7、軌跡并不是橢圓，而是一個(gè)平面上的三次曲線，是人們?cè)谘芯咳绾斡?jì)算橢圓的弧長(zhǎng)時(shí)發(fā)現(xiàn)的問(wèn)題。定義定義6-1 由三次威樂(lè)斯特拉斯方程(Weierstrass方程):y2+axy+by=x3+cx2+dx+e所確定的平面曲線稱為橢圓曲線，滿足方程的點(diǎn)稱為曲線上的點(diǎn)。若系數(shù)a，b，c，d，e來(lái)自有限域Fp，則曲線上的點(diǎn)數(shù)目也是有限的，這些點(diǎn)再加上一個(gè)人為定義的無(wú)窮遠(yuǎn)點(diǎn)O，構(gòu)成集合E(Fp)，E(Fp)的點(diǎn)數(shù)記作#E(Fp)。第6章 公鑰密碼體制 Hasse證明了如下結(jié)論： 在構(gòu)造密碼系統(tǒng)時(shí)，我們主要關(guān)心這樣一種橢圓曲線，其方程為y2=x3+ax+b x，y，a，b，F(xiàn)p12#()12pppE Fpp 第6

8、章 公鑰密碼體制 定理定理6-1 橢圓曲線上的點(diǎn)集合E(Fp)對(duì)于如下定義的加法規(guī)則構(gòu)成一個(gè)Abel群：(1) O+O=O；(2) 對(duì)(x，y)E(Fp)，(x，y)+O=(x，y)；(3) 對(duì)(x，y)E(Fp)，(x，y)+(x，y)=O，即點(diǎn)(x，y)的逆為(x，y)；(4) 若x1x2，則(x1，y1)+(x2，y2)=(x3，y3)，其中，231221213131,()xxxyyxxyxxy第6章 公鑰密碼體制 (5) (倍點(diǎn)規(guī)則)對(duì)(x1，y1)E(Fp)，y10，有2(x1，y1)=(x2，y2)，其中,222111212123,2()xxxayyxxy第6章 公鑰密碼體制 以上

9、規(guī)則體現(xiàn)在曲線圖形上，含義為(1) O是加法單位元；(2) 一條與x軸垂直的線和曲線相交于兩個(gè)x坐標(biāo)相同的點(diǎn)，即P1=(x，y)和P2=(x，y)，同時(shí)它也與曲線相交于無(wú)窮遠(yuǎn)點(diǎn)，因此P2=P1；(3) 橫坐標(biāo)不同的兩個(gè)點(diǎn)R和Q相加時(shí)，先在它們之間畫(huà)一條直線并求直線與曲線的第三個(gè)交點(diǎn)P，此時(shí)有R+Q=P；(4) 對(duì)一個(gè)點(diǎn)Q加倍時(shí)，通過(guò)該點(diǎn)畫(huà)一條切線并求切線與曲線的另一個(gè)交點(diǎn)S，Q+Q=2Q=S。第6章 公鑰密碼體制 6.2.2 橢圓曲線公鑰密碼體制橢圓曲線公鑰密碼體制設(shè)PE(Fp)，點(diǎn)Q為P的倍數(shù)，即存在正整數(shù)x，使Q=xP，則橢圓曲線離散對(duì)數(shù)問(wèn)題ECPLP(Elliptic Curve Dis

10、crete Logarithm Problem)是指由給定的P和Q確定出x。從目前的研究成果看，橢圓曲線上的離散對(duì)數(shù)問(wèn)題比有限域上的離散對(duì)數(shù)似乎更難處理，這就為構(gòu)造公鑰密碼體制提供了新的途徑?；跈E圓曲線離散對(duì)數(shù)問(wèn)題，人們構(gòu)造了橢圓曲線密碼體制。定義定義6-2 設(shè)E為橢圓曲線，P為E上的一點(diǎn)，若存在正整數(shù)n，使nP=O，則稱n是點(diǎn)P的階，這里O為無(wú)窮遠(yuǎn)點(diǎn)。第6章 公鑰密碼體制 系統(tǒng)的構(gòu)造系統(tǒng)的構(gòu)造選取基域Fp，橢圓曲線E，在E上選擇階為素?cái)?shù)n的點(diǎn)P(xp，yp)。公開(kāi)信息為：域Fp、曲線方程E、點(diǎn)P及其階n。 密鑰的生成密鑰的生成用戶Alice隨機(jī)選取整數(shù)d，13的有限域，定義該域上的橢圓曲線

11、E，E：y2=x3+ax+b(a，bFp，4a3+27b2(mod q) 0，q為 n bit的素?cái)?shù)，n 190)，PE(Fq) 是一個(gè)公開(kāi)基點(diǎn)，P的階為L(zhǎng)(L160 bit)，#E(Fq)為橢圓曲線的階，至少有50位以上的大素因子。假設(shè)ki(1，2，q1)分別為消息簽名者Bi的私鑰，Ki=kiP為Bi的公鑰，共享的安全散列函數(shù)選擇SHA_1或RIPEMD_160。消息發(fā)送者A預(yù)先設(shè)計(jì)一個(gè)簽名順序B1，B2，Bn，并且將簽名順序發(fā)送給每一位簽名者Bi與驗(yàn)證者C。第6章 公鑰密碼體制 簽名產(chǎn)生過(guò)程簽名產(chǎn)生過(guò)程A將消息m發(fā)送到第一位簽名者B1，規(guī)定此時(shí)的簽名消息s=0。每一位簽名者Bi(i2)收到

12、簽名信息(m，(si1，Ri1)后，先對(duì)簽名進(jìn)行驗(yàn)證，然后執(zhí)行以下步驟：(1) Bi隨機(jī)選取ui(1，2，q1)，計(jì)算:m=SHA_1(m)，Ri=uiP=(xi，yi)0，si=si1+kiximui(mod q)(6-1)第6章 公鑰密碼體制 (2) 將(m，(si，Ri)發(fā)送到下一個(gè)簽名者Bi+1，同時(shí)將Ri發(fā)送給Bi以后的簽名者以及簽名驗(yàn)證者C。簽名驗(yàn)證過(guò)程簽名驗(yàn)證過(guò)程簽名者Bi(i2)要對(duì)B1，B2，Bi1的簽名進(jìn)行驗(yàn)證，驗(yàn)證者C要對(duì)所有簽名者B1，B2，Bn的簽名進(jìn)行驗(yàn)證。Bi驗(yàn)證 (6-2)是否成立。若等式成立，則Bi認(rèn)為B1，B2，Bi1的簽名消息有效；否則判定簽名無(wú)效，拒絕繼

13、續(xù)對(duì)消息簽名。1111iijjjijjx KmRs P第6章 公鑰密碼體制 同樣，C驗(yàn)證(6-3)是否成立。如果等式成立，則認(rèn)為B1，B2，Bn的簽名有效；否則認(rèn)定為無(wú)效簽名。11nnjjjnjjx KmRs P第6章 公鑰密碼體制 簽名驗(yàn)證中，由式(6-1)可得(6-4)因此 這就驗(yàn)證了上述有序多重?cái)?shù)字簽名方案的正確性。111(mod ) ()(mod )iiiiiijjjjssk xm uqk xm uq111111111111()(mod )()(mod )(mod )ijijiijjjjjjijjjjjiijjjjjjmRs pmu pk xm uq pm uk xm uq pk xq

14、 px K式(6-2)右邊等式左邊第6章 公鑰密碼體制 2) 廣播多重?cái)?shù)字簽名方案初始化過(guò)程此方案的系統(tǒng)初始化和參數(shù)設(shè)定與有序多重?cái)?shù)字簽名方案相同，且Bc為簽名收集者。簽名產(chǎn)生過(guò)程A將消息m發(fā)送到每一位簽名者Bi(i=1，2，n)和簽名收集者Bc，規(guī)定此時(shí)的簽名消息s=0。簽名者Bi和收集者Bc收到消息后執(zhí)行以下步驟：(1) Bi隨機(jī)選取ui(1，2，q1)計(jì)算Ri=uiP=(xi，yi)0，將Ri發(fā)送到簽名收集者Bc;第6章 公鑰密碼體制 (2) 簽名收集者Bc收集到所有Ri(i=1，2，n)后，計(jì)算， 隨后Bc將R發(fā)送到每一位簽名者Bi(i=1，2，n);(3) 對(duì)于消息m，簽名者Bi計(jì)算

15、m=RIPEMD_160(m)，然后生成簽名 (6-5)則si作為簽名者Bi對(duì)消息m的子簽名，Bi將簽名消息(m， si)發(fā)送到簽名收集者Bc;niiiRxR1),()(mod)(quxkmsiiii第6章 公鑰密碼體制 (4) 當(dāng)Bc收集到所有(m， si)(i=1，2，n)后，計(jì)算 (6-6)然后將(m，s，R)作為最后簽名信息發(fā)送到簽名驗(yàn)證者C。 njjqss1)(mod第6章 公鑰密碼體制 簽名驗(yàn)證過(guò)程簽名驗(yàn)證過(guò)程C接收到簽名信息(m，s，R)后，首先計(jì)算m=RIPEMD_160(m)，然后驗(yàn)證(6-7)是否成立。如果等式成立，則認(rèn)為B1，B2，Bn 對(duì)消息m的簽名有效；否則認(rèn)定為無(wú)效

16、簽名。1()niim KRsp第6章 公鑰密碼體制 上述驗(yàn)證簽名的等式中，由于因此 式(6-7)右邊=等式左邊上式驗(yàn)證了上述廣播多重?cái)?shù)字簽名方案的正確性。niiiiniiquxkmqss11)(mod)()(mod1111()()()nniiiiiiiniiiiiiniiRspx RmKx Rx RmKx RmK第6章 公鑰密碼體制 3) 方案分析基于ECC的多重?cái)?shù)字簽名方案除體現(xiàn)了現(xiàn)有多重?cái)?shù)字簽名方案的優(yōu)點(diǎn)外，還具有以下特點(diǎn)：(1) 實(shí)現(xiàn)了一類(lèi)透明的協(xié)議過(guò)程。廣播多重簽名中，簽名收集者通過(guò)簽名處理過(guò)程11( , ),()(mod )nniiiiiiiRx Rsmkxuq 第6章 公鑰密碼體制

17、 的引入，隱蔽了各個(gè)簽名者的隨機(jī)中間參數(shù)Ri與單個(gè)子簽名消息si，驗(yàn)證者與攻擊者都無(wú)法將簽名信息與單個(gè)簽名者聯(lián)系起來(lái)，因此方案對(duì)于外部攻擊具有較強(qiáng)的抵抗能力。對(duì)于內(nèi)部攻擊，假定有m(mmax(L0，L1)。H0、 H1、 H2為安全的散列函數(shù)，H0，H1，H20，1 *Zn。ka， kb分別為用戶A和銀行的私鑰，Kb=kbP，Ka=kaP作為兩者的公鑰，密鑰對(duì) (Ka，ka)、 (Kb，kb)作為協(xié)議中的主密鑰。表示是一個(gè)從J(Fq)到有限整數(shù)集=0，1，q2g+11的單射函數(shù)，將其記為(P)x或(P)q。公開(kāi)n，P、 P1和H0、 H1、 H2以及公鑰Kb=kbP，Ka=kaP。設(shè)kA，kB

18、(1，2，n1)分別為A和B的私鑰， KA=kAp，KB=kBp為A和B的公鑰，共享的安全散列函數(shù)為H1和H2。*nZ21gqZ第6章 公鑰密碼體制 2) 委托過(guò)程(1) A隨機(jī)選取u(1，2， n1)，計(jì)算:R=up0，h=H1(R) x)f=hkA+u(mod n) (6-9)并將(R，f)秘密地發(fā)送給B。 (2) B計(jì)算h=H1(R) x)，然后驗(yàn)證:fp=hKA+R是否成立，若成立則計(jì)算f=f+kB(mod n)(6-10)第6章 公鑰密碼體制 3) 代理簽名過(guò)程對(duì)于某個(gè)消息m，B隨機(jī)選取v(1，2， n1)，計(jì)算得到T=vp0，再計(jì)算m=H2(m)s=(T) xfmv(mod n)(

19、6-11)并將(m，s，R，T)發(fā)送給簽名驗(yàn)證者。第6章 公鑰密碼體制 4) 代理簽名驗(yàn)證過(guò)程驗(yàn)證者接收到(m，s，R，T)后，計(jì)算h=H1(R) x)，m=H2(m)驗(yàn)證(T) x(hKA+R+KB)=sp+mT (6-12)是否成立。如果等式成立，則認(rèn)為B代理A的簽名有效；否則認(rèn)定為無(wú)效簽名。第6章 公鑰密碼體制 簽名驗(yàn)證中，由式(6-11)可得式(6-12)右邊=等式左邊這就驗(yàn)證了上述單一代理數(shù)字簽名方案的正確性。ABAB( )( )( ) ()( ) ()xxxxspm TTfm v pm vpTf pThkukpThKRK第6章 公鑰密碼體制 3. 基于基于HCC的多重代理數(shù)字簽名方

20、案的多重代理數(shù)字簽名方案1) 初始化過(guò)程系統(tǒng)初始化和參數(shù)設(shè)定與單一代理數(shù)字簽名的方案相同，假設(shè)ki，kB分別為Ai(i=1，2，n) 和B的私鑰， Ki=kip，KB=kBp為Ai和B的公鑰，共享的安全散列函數(shù)為H1和H2。第6章 公鑰密碼體制 2) 委托過(guò)程(1) Ai隨機(jī)選取ui(1，2， n1)，計(jì)算Ri=uip0，hi=H1(Ri) x)fi=hiki+ui(mod n)(6-13)并將(Ri，fi)秘密地發(fā)送給B。第6章 公鑰密碼體制 (2) B在收到(Ri，fi)(i=1，2，n)后，計(jì)算hi=H1(Ri)x)，然后驗(yàn)證fip=hiKi+Ri是否成立。若成立則認(rèn)為(Ri，fi)是一

21、個(gè)有效的子代理密鑰; 否則B要求Ai重復(fù)(1)或終止協(xié)議過(guò)程。第6章 公鑰密碼體制 3) 代理簽名過(guò)程B在收到所有(Ri，fi)后，計(jì)算出 (6-14)對(duì)于某個(gè)消息m，B隨機(jī)選取v(i=1，2， n1)，計(jì)算T=vp0，m=H2(m)s=f(m+(T) x)v(mod n)(6-15)(s，T，R1，R2， Rn)為B代表Ai(i=1，2，n)生成的多重代理簽名。)(mod1nfkfniiB第6章 公鑰密碼體制 4) 代理簽名驗(yàn)證過(guò)程驗(yàn)證者收到(s，T，R1，R2， Rn)和消息m后，計(jì)算hi=H1(Ri) x)，m=H2(m)驗(yàn)證(6-16)是否成立。如果等式成立，則認(rèn)為B代理Ai生成的多重

22、代理簽名有效；否則認(rèn)定為無(wú)效簽名。TTmspKRKhxBiinii)(?)(1TTmspKRKhxBiinii)(?)(1第6章 公鑰密碼體制 簽名驗(yàn)證中，由式(6-15)可得式(6-16)右邊等式左邊這就驗(yàn)證了上述多重代理數(shù)字簽名方案的正確性。B1B1( ) )( ) ) )( ) )()()xxxniiniiiispmTTfmTv pmTTf pfkphKRK第6章 公鑰密碼體制 4. 代理數(shù)字簽名方案分析代理數(shù)字簽名方案分析(1) 代理簽名方案可具有區(qū)分與身份證實(shí)性。根據(jù)式(6-10)，在單一代理簽名中有f=f+kB(mod n)根據(jù)式(6-14)，在多重代理簽名中有)(mod1nfkf

23、niiB第6章 公鑰密碼體制 所以代理簽名密鑰的產(chǎn)生依賴于原始簽名人的普通簽名密鑰，但不同于原始簽名者的普通簽名密鑰，因此與原始簽名密鑰是可區(qū)分的，而且在存在多個(gè)代理簽名者的情況下，每個(gè)代理簽名者的子代理密鑰(Ri，fi)也是不相同的。所以，原始簽名者可以將不同的代理者區(qū)分開(kāi)，有效地實(shí)現(xiàn)對(duì)代理者的監(jiān)督，防止代理簽名權(quán)力的濫用。在出現(xiàn)問(wèn)題時(shí)，第三方也可以將原始簽名者與代理簽名者、不同的代理者區(qū)分開(kāi)來(lái)。第6章 公鑰密碼體制 (2) 具有較強(qiáng)的防偽造性。除了原始簽名人A以外，任何人(包括代理簽名者)在不知道私鑰kA的情況下，都不能偽造原始簽名人的普通簽名信息。同理，代理簽名者的簽名秘鑰對(duì)于攻擊者(包

24、括原始簽名者)也是安全的。如果原始簽名者委托了多人代理簽名，則根據(jù)式(6-10) 、(6-14)，由于代理簽名秘鑰f中引入了代理簽名者的私鑰kB，各個(gè)代理簽名者之間也不能偽造簽名信息，因?yàn)橐獋卧旌灻仨毠粝鄳?yīng)代理簽名者的私鑰及隨機(jī)數(shù)v，這就使得面對(duì)的都是求解HCDLP問(wèn)題。對(duì)于內(nèi)部攻擊，假定有m(m3，使得p=6q1，E為由Fp上方程y2=x3+1確定的橢圓曲線，在E/Fp上隨機(jī)選取q階點(diǎn)P；Step2：隨機(jī)選擇，令Ppub=sP；Step3：選擇Hash函數(shù)H：0，1 n，G：0，1*Fp，在安全性分析中，將H與G視為隨機(jī)預(yù)言機(jī)(Random Oracle)。*qsZ2pF第6章 公鑰密碼

25、體制 系統(tǒng)的消息空間為M=0，1 n，密文空間為C=E/Fp0，1n，系統(tǒng)參數(shù)為params=p，n，P，Ppub，G，H，主密鑰為。提?。簩?duì)給定的串ID0,1*，算法通過(guò)如下方法生成私鑰d。Step1：利用MapToPoint將ID映射為E/Fp上的q階元QID；Step2：計(jì)算私鑰dID=sQID，其中s為主密鑰。加密：對(duì)消息mM加密時(shí)，進(jìn)行如下步驟。Step1：利用MapToPoint將ID映射為E/Fp上的q階元QID；Step2：隨機(jī)選擇rZq；Step3：計(jì)算密文其中， 。*qsZID,()rcrP mH g2IDIDpub(,)pge QPF第6章 公鑰密碼體制 解密：解密：令c

26、=(U，V)C為利用公鑰ID加密后的密文，如果U不是E/Fp上的q階點(diǎn)，則丟棄此密文，否則，利用私鑰dID進(jìn)行如下計(jì)算來(lái)解密：ID ( (,)VH e dUm第6章 公鑰密碼體制 以下定理表明，在WDH假設(shè)成立的前提下，BasicIdent方案具有單向性。定理定理6-3 令H與G為隨機(jī)預(yù)言機(jī)，假設(shè)存在一個(gè)ID-OWE敵手A，能以優(yōu)勢(shì)攻破BasicIdent，并且假設(shè)A最多進(jìn)行了qE0次私鑰提取詢問(wèn)及qH0次Hash詢問(wèn)，那么存在算法B，能以至少的優(yōu)勢(shì)計(jì)算WDH，其中e2.71，為自然對(duì)數(shù)的底，而B(niǎo)的運(yùn)行時(shí)間是O(time(A)。證明詳見(jiàn)參考文獻(xiàn)5。EHH1(1)2neqqq第6章 公鑰密碼體制 4. 具有選擇密文攻擊安全性的具有選擇密文攻擊安全性的IBE利用Fujisaki-Okamoto在參考文獻(xiàn)13中提供的方法，可以將BasicIdent方案轉(zhuǎn)化為在隨機(jī)預(yù)言模型下具有選擇密文攻擊安全性的IBE。設(shè)E為一個(gè)公鑰加密方案，用Epk(m; r)表示在公鑰pk下利用隨機(jī)比特r對(duì)m加密的結(jié)果，F(xiàn)ujisaki-Okamoto定義了混合方案Ehy如下：其中，為隨機(jī)生成的串; H1，G1為Hash函數(shù)。Fujisaki-Okamoto證明了如果E為單向加密方案，則Ehy是在隨機(jī)預(yù)言模型下選擇密文攻擊安全(IN