現(xiàn)代密碼學(xué)第六章公鑰密碼體制

6.1公鑰密碼的原理及典型公鑰密碼

6.2橢圓曲線密碼

6.3超橢圓曲線密碼

6.4基于身份的公鑰密碼體制第6章公鑰密碼體制6.1公鑰密碼的原理及典型公鑰密碼6.1.1公鑰密碼的原理公鑰密碼的思想最早由Diffie和Hellman在其論文“NewDirectionsinCryptography〞中提出。他們設(shè)想了一種無須事先傳遞密鑰的密碼體制，在該體制中，用戶Alice有一對密鑰：公開的加密密鑰(簡稱公鑰)和保密的解密密鑰(簡稱私鑰)。向Alice發(fā)送秘密信息時，用其公鑰加密，Alice收到信息后，用私鑰解密。由于加密密鑰與解密密鑰不同，因此公鑰密碼體制又被稱為非對稱密碼體制，而傳統(tǒng)密碼(分組密碼、序列密碼)被稱為對稱密碼體制。與對稱密碼相比，公鑰密碼有以下特點：

(１)平安性取決于某些困難問題的難解性；

(２)無須事先傳遞密鑰；

(３)計算量通常大于對稱密碼。

公鑰密碼中常用的難解問題有分解大整數(shù)、離散對數(shù)問題、橢圓曲線上的離散對數(shù)問題

等，其平安性取決于構(gòu)造算法所依賴的數(shù)學(xué)問題的計算復(fù)雜性，所以公鑰密碼在理論上是

不平安的，但在實際應(yīng)用中可以選擇足夠平安的參數(shù)來保證計算上的平安性。6.1.2Diffie-Hellman密鑰交換

Diffie和Hellman給出了一種通信雙方無須事先傳遞密鑰也能利用對稱密碼體制進(jìn)行保密通信的方法，這就是Diffie-Hellman密鑰交換協(xié)議(簡稱D-H協(xié)議)，在該協(xié)議中，通信雙方通過協(xié)商可以建立一個秘密的密鑰。D-H協(xié)議充分表達(dá)了公鑰密碼的思想，其平安性基于離散對數(shù)問題。設(shè)系統(tǒng)中公開的參數(shù)為大素數(shù)p和模p的原根g，用戶Alice和Bob為了協(xié)商一個公用的秘密密鑰，需要進(jìn)行如下步驟：

(1)Alice隨機選擇整數(shù)xA，計算，將yA傳給Bob；

(2)Bob隨機選擇整數(shù)xB，計算，將yB傳給Alice；

(3)Alice計算，Bob計算

，易知兩者是相等的，從而可將

作為雙方的通信密鑰。

D-H協(xié)議的平安性是基于這樣一個假設(shè)，即和，求xB是困難的，Diffie和Hellman假設(shè)此問題的困難等價于離散對數(shù)問題。6.1.3RSA

1977年，美國麻省理工學(xué)院的三位數(shù)學(xué)家RonRivest、AdiShamir和LenAdleman成功地設(shè)計了一個公鑰密碼算法，該算法根據(jù)設(shè)計者的名字被命名為RSA，在其后的30年中，RSA成為世界上應(yīng)用最為廣泛的公鑰密碼體制。

設(shè)RSA系統(tǒng)中每個用戶有公開的加密密鑰n、e和保密的解密密鑰d，這些密鑰通過以下步驟確定：

(1)用戶選擇兩個大素數(shù)p、q，計算n=pq及φ(n)=(p－1)(q－1)；(2)選擇隨機數(shù)e，要求1<e<φ(n)，且gcd(e，φ(n)=1)；

(3)求出e模φ(n)的逆d，即ed≡1modφ(n)；

(4)將n、e公開，d保密。

加密時，首先將明文表示為小于n的整數(shù)，設(shè)m為明文，要將m加密并發(fā)送給用戶Alice時，利用Alice的公開密鑰nA、eA，計算

求出的整數(shù)c即為密文。Alice收到c后，利用自己的解密密鑰dA，計算

求出的m即為明文。6.1.4ElGamal

ElGamal是基于離散對數(shù)問題的最著名的公鑰密碼體制，其系統(tǒng)參數(shù)如下：

選擇大素數(shù)p和模p的原根g，隨機選擇整數(shù)x，計算

y=gxmodp，將p、g、y公開，x保密。

加密時，假設(shè)明文被編碼為整數(shù)m，加密者隨機選擇整數(shù)k，滿足gcd(k，p－1)=1，再計算

c1=gkmodp

c2=mykmodp

那么密文為c=(c1，c2)。

接收方收到密文組(c1，c2)后，進(jìn)行如下的解密運算：

6.2橢圓曲線密碼6.2.1橢圓曲線(EllipticCurve)橢圓曲線的圖像軌跡并不是橢圓，而是一個平面上的三次曲線，是人們在研究如何計算橢圓的弧長時發(fā)現(xiàn)的問題。定義6-1由三次威樂斯特拉斯方程(Weierstrass方程):y2+axy+by=x3+cx2+dx+e所確定的平面曲線稱為橢圓曲線，滿足方程的點稱為曲線上的點。假設(shè)系數(shù)a，b，c，d，e來自有限域Fp，那么曲線上的點數(shù)目也是有限的，這些點再加上一個人為定義的無窮遠(yuǎn)點O，構(gòu)成集合E(Fp)，E(Fp)的點數(shù)記作#E(Fp)。Hasse證明了如下結(jié)論：

在構(gòu)造密碼系統(tǒng)時，我們主要關(guān)心這樣一種橢圓曲線，其方程為

y2=x3+ax+b

x，y，a，b，∈Fp定理6-1橢圓曲線上的點集合E(Fp)對于如下定義的加法規(guī)那么構(gòu)成一個Abel群：

(1)O+O=O；

(2)對(x，y)∈E(Fp)，(x，y)+O=(x，y)；

(3)對(x，y)∈E(Fp)，(x，y)+(x，－y)=O，即點(x，y)的逆為(x，－y)；

(4)假設(shè)x1≠x2，那么(x1，y1)+(x2，y2)=(x3，y3)，其中，

(5)(倍點規(guī)那么)對(x1，y1)∈E(Fp)，y1≠0，有2(x1，y1)=(x2，y2)，其中,

以上規(guī)那么表達(dá)在曲線圖形上，含義為

(1)O是加法單位元；

(2)一條與x軸垂直的線和曲線相交于兩個x坐標(biāo)相同的點，即P1=(x，y)和P2=(x，－y)，同時它也與曲線相交于無窮遠(yuǎn)點，因此P2=－P1；

(3)橫坐標(biāo)不同的兩個點R和Q相加時，先在它們之間畫一條直線并求直線與曲線的第三個交點P，此時有R+Q=－P；

(4)對一個點Q加倍時，通過該點畫一條切線并求切線與曲線的另一個交點S，Q+Q=2Q=－S。6.2.2橢圓曲線公鑰密碼體制

設(shè)P∈E(Fp)，點Q為P的倍數(shù)，即存在正整數(shù)x，使Q=xP，那么橢圓曲線離散對數(shù)問題ECPLP(EllipticCurveDiscreteLogarithmProblem)是指由給定的P和Q確定出x。從目前的研究

成果看，橢圓曲線上的離散對數(shù)問題比有限域上的離散對數(shù)似乎更難處理，這就為構(gòu)造公鑰密碼體制提供了新的途徑?；跈E圓曲線離散對數(shù)問題，人們構(gòu)造了橢圓曲線密碼體制。

定義6-2設(shè)E為橢圓曲線，P為E上的一點，假設(shè)存在正整數(shù)n，使nP=O，那么稱n是點P的階，這里O為無窮遠(yuǎn)點。系統(tǒng)的構(gòu)造

選取基域Fp，橢圓曲線E，在E上選擇階為素數(shù)n的點P(xp，yp)。

公開信息為：域Fp、曲線方程E、點P及其階n。

密鑰的生成

用戶Alice隨機選取整數(shù)d，1<d≤n－1，計算Q=dP，將點Q作為公開密鑰，整數(shù)d作為秘密密鑰。加密與解密

假設(shè)要給Alice發(fā)送秘密信息M，需執(zhí)行以下步驟：

(1)將明文M表示為域Fp中的一個元素m；

(2)在［1，n－1］內(nèi)隨機選擇整數(shù)k；

(3)計算點(x1，y1)=kP；

(4)計算點(x2，y2)=kQ，假設(shè)x2=0，那么重新選擇k；

(5)計算c=mx2；

(6)將(x1，y1，c)發(fā)送給Alice。Alice收到密文后，利用秘密密鑰d，計算:

d(x1，y1)=dkP=k(dP)=kQ=(x2，y2)

再計算，得到明文m。

這里Q=dP是公開的，假設(shè)破譯者能夠解決橢圓曲線上的離散對數(shù)問題，就能從dP中恢復(fù)d，完成解密［21］。6.2.3基于橢圓曲線公鑰密碼體制的密碼協(xié)議

計算機網(wǎng)絡(luò)技術(shù)正以前所未有的速度滲入到我們工作生活的方方面面。由于自身開放與共享的互聯(lián)特性，網(wǎng)絡(luò)在給我們提供方便、快捷、高效的信息效勞的同時，也帶來了各種平安隱患。數(shù)字簽名是對電子文檔做出承諾或保證電子文檔合法性、抗抵賴性的有效手段。在電子商務(wù)與電子政務(wù)中，有時需要多人進(jìn)行聯(lián)合簽名，假設(shè)采用傳統(tǒng)的簽名方式就會產(chǎn)生巨大的簽名驗證計算量及信息通信量，違背了網(wǎng)絡(luò)業(yè)務(wù)廉價、高效的設(shè)計原那么。此時，多重數(shù)字簽名方案就有著不可替代的重要作用。1994年，Harn首次提出了一種播送多重數(shù)字簽名方案，目前又出現(xiàn)了基于離散對數(shù)的ElGamal有序多重數(shù)字簽名方案與播送多重數(shù)字簽名方案，這些方案的平安性都是建立在有限域GF(p)上離散對數(shù)問題的難解性之上的，而且多重數(shù)字簽名本身就是一種多層次、聯(lián)合式的簽名認(rèn)證協(xié)議，因此已有方案存在著密鑰量大、運算復(fù)雜、軟硬件實現(xiàn)時系統(tǒng)開銷大等缺乏。為了保證簽名認(rèn)證協(xié)議的平安性，同時降低實現(xiàn)多重數(shù)字簽名的空間與時間復(fù)雜度，提高系統(tǒng)執(zhí)行效率，基于橢圓曲線公鑰密碼體制提出了一類網(wǎng)絡(luò)通信中的多重數(shù)字簽名方案。這類方案將算法的平安性建立在橢圓曲線離散對數(shù)問題(ECDLP)的難解性之上，在保證系統(tǒng)數(shù)據(jù)信息平安性的根底上，充分發(fā)揮了橢圓曲線密碼系統(tǒng)效率高、平安強度大的特點。在同等平安強度下，方案可以用較小的開銷(所需計算量、存儲量、帶寬、軟件和硬件實現(xiàn)的規(guī)模等)和時延(加密和簽名速度快)實現(xiàn)較高的平安性。1.多重數(shù)字簽名方案及其分類

在網(wǎng)絡(luò)通信中，有時要求多個用戶對同一消息進(jìn)行簽名與認(rèn)證(如幾位領(lǐng)導(dǎo)或當(dāng)事人簽署同一份文件)。能夠?qū)崿F(xiàn)這種多個協(xié)議方對同一消息進(jìn)行簽名的數(shù)字簽名協(xié)議就稱為多重數(shù)字簽名(DigitalMultisignature)。根據(jù)簽名協(xié)議過程的不同，多重數(shù)字簽名又可以分為有序多重數(shù)字簽名(SequentialMultisignature)與播送多重數(shù)字簽名(BroadcastingMultisignature)。

1)有序多重數(shù)字簽名

有序多重數(shù)字簽名協(xié)議過程如圖6-1所示。圖6-1有序多重數(shù)字簽名方案有序多重數(shù)字簽名方案包含消息發(fā)送者(issuer)、消息簽名者(signers)、簽名驗證者(verifier)三個協(xié)議方，消息發(fā)送者規(guī)定消息簽名順序，然后將消息發(fā)給第一個簽名者。除了第一個簽名者以外的每一位簽名者收到簽名消息后，首先驗證上一簽名的有效性，如果有效那么繼續(xù)簽名，然后將簽名消息發(fā)送到下一個簽名者；如果簽名無效那么拒絕對消息進(jìn)行簽名，終止簽名協(xié)議。簽名驗證者最后收到簽名消息，對消息進(jìn)行有效性驗證，如果簽名有效那么通過認(rèn)證，否那么拒絕進(jìn)一步的協(xié)議過程。2)播送多重數(shù)字簽名

播送多重數(shù)字簽名協(xié)議過程如圖6-2所示。

播送多重數(shù)字簽名方案包含消息發(fā)送者、消息簽名者、簽名收集者(signaturecollector)、簽名驗證者四個協(xié)議方。消息發(fā)送者將消息同時發(fā)送給每一位簽名者進(jìn)行簽名；簽名者將簽名消息發(fā)送到簽名收集者；收集者對各個簽名消息進(jìn)行處理并將結(jié)果發(fā)送給簽名驗證者；簽名驗證者完成對多重數(shù)字簽名的有效性驗證工作。圖6-2播送多重數(shù)字簽名方案

2.基于ECC的多重數(shù)字簽名方案

1)有序多重數(shù)字簽名方案

有序多重數(shù)字簽名方案包括系統(tǒng)初始化、簽名產(chǎn)生與簽名驗證過程，方案的協(xié)議方為消息發(fā)送者、消息簽名者與簽名驗證者。

初始化過程設(shè)A為消息發(fā)送者，B1，B2，…，Bn為消息簽名者，C為簽名驗證者。鑒于平安性和執(zhí)行效率的考慮，系統(tǒng)參數(shù)設(shè)定為：Fp為特征值Char(Fq)>3的有限域，定義該域上的橢圓曲線E，E：y2=x3+ax+b(a，b∈Fp，4a3+27b2(modq)≠0，q為nbit的素數(shù)，n≥190)，P∈E(Fq)是一個公開基點，P的階為L(L≥160bit)，#E(Fq)為橢圓曲線的階，至少有50位以上的大素因子。

假設(shè)ki∈(1，2，…，q－1)分別為消息簽名者Bi的私鑰，Ki=kiP為Bi的公鑰，共享的平安散列函數(shù)選擇SHA_1或RIPEMD_160。消息發(fā)送者A預(yù)先設(shè)計一個簽名順序B1，B2，…，Bn，并且將簽名順序發(fā)送給每一位簽名者Bi與驗證者C。

簽名產(chǎn)生過程

A將消息m發(fā)送到第一位簽名者B1，規(guī)定此時的簽名消息s=0。每一位簽名者Bi(i≥2)收到簽名信息(m，(si－1，Ri－1))后，先對簽名進(jìn)行驗證，然后執(zhí)行以下步驟：

(1)Bi隨機選取ui∈(1，2，…，q－1)，計算:

m′=SHA_1(m)，Ri=uiP=(xi，yi)≠0，

si=si－1+kixi－m′ui(modq)

(6-1)(2)將(m，(si，Ri))發(fā)送到下一個簽名者Bi+1，同時將Ri發(fā)送給Bi以后的簽名者以及簽名驗證者C。

簽名驗證過程

簽名者Bi(i≥2)要對B1，B2，…，Bi－1的簽名進(jìn)行驗證，驗證者C要對所有簽名者B1，B2，…，Bn的簽名進(jìn)行驗證。Bi驗證

(6-2)

是否成立。假設(shè)等式成立，那么Bi認(rèn)為B1，B2，…，Bi－1的簽名消息有效；否那么判定簽名無效，拒絕繼續(xù)對消息簽名。同樣，C驗證

(6-3)

是否成立。如果等式成立，那么認(rèn)為B1，B2，…，Bn的簽名有效；否那么認(rèn)定為無效簽名。簽名驗證中，由式(6-1)可得

(6-4)

因此

這就驗證了上述有序多重數(shù)字簽名方案的正確性。式(6-2)右邊＝等式左邊2)播送多重數(shù)字簽名方案

初始化過程

此方案的系統(tǒng)初始化和參數(shù)設(shè)定與有序多重數(shù)字簽名方案相同，且Bc為簽名收集者。

簽名產(chǎn)生過程

A將消息m發(fā)送到每一位簽名者Bi(i=1，2，…，n)和簽名收集者Bc，規(guī)定此時的簽名消息s=0。簽名者Bi和收集者Bc收到消息后執(zhí)行以下步驟：

(1)Bi隨機選取ui∈(1，2，…，q－1)計算Ri=uiP=(xi，yi)≠0，將Ri發(fā)送到簽名收集者Bc;(2)簽名收集者Bc收集到所有Ri(i=1，2，…，n)后，計算

，隨后Bc將R發(fā)送到每一位簽名者Bi(i=1，2，…，n);

(3)對于消息m，簽名者Bi計算m′=RIPEMD_160(m)，然后生成簽名

(6-5)

那么si作為簽名者Bi對消息m的子簽名，Bi將簽名消息(m，si)發(fā)送到簽名收集者Bc;(4)當(dāng)Bc收集到所有(m，si)(i=1，2，…，n)后，計算

(6-6)

然后將(m，s，R)作為最后簽名信息發(fā)送到簽名驗證者C。

簽名驗證過程

C接收到簽名信息(m，s，R)后，首先計算m′=RIPEMD_160(m)，然后驗證

(6-7)

是否成立。如果等式成立，那么認(rèn)為B1，B2，…，Bn對消息m的簽名有效；否那么認(rèn)定為無效簽名。上述驗證簽名的等式中，由于

因此式(6-7)右邊

=等式左邊

上式驗證了上述播送多重數(shù)字簽名方案的正確性。3)方案分析

基于ECC的多重數(shù)字簽名方案除表達(dá)了現(xiàn)有多重數(shù)字簽名方案的優(yōu)點外，還具有以下特點：

(1)實現(xiàn)了一類透明的協(xié)議過程。播送多重簽名中，簽名收集者通過簽名處理過程

的引入，隱蔽了各個簽名者的隨機中間參數(shù)Ri與單個子簽名消息si，驗證者與攻擊者都無法將簽名信息與單個簽名者聯(lián)系起來，因此方案對于外部攻擊具有較強的抵抗能力。對于內(nèi)部攻擊，假定有m(m<n)個內(nèi)部成員要合謀偽造一個簽名，他們必須得到所有簽名者Bi的私鑰及相應(yīng)隨機數(shù)ui，由于這些秘密參數(shù)是獨立且隨機產(chǎn)生的，對于協(xié)同的內(nèi)部攻擊者，除了自己掌握的秘密參數(shù)外，其攻擊能力并不比外部攻擊者更具優(yōu)勢。方案防止了出現(xiàn)由局部成員可決定的系統(tǒng)秘密，所以對于內(nèi)部成員同樣具有較強的抗攻擊能力。(2)具有較強的防偽造性。偽造者B′在不知道各個簽名者Bi的私鑰ki及隨機數(shù)ui的情況下，偽造簽名信息(m，s′，R)(其中s′≠s)滿足播送多重簽名公式(6-7)：

或偽造簽名信息(m,())(其中)滿足有序多重簽名公式(6-3)：

時，都是求解多重的橢圓曲線離散對數(shù)問題。即使對于簽名收集者Bc，方案也具有較強的防偽造性，因為簽名者Bi的私鑰和隨機參數(shù)ui對Bc是保密的，要偽造簽名，面對的是求解橢圓曲線離散對數(shù)問題。(3)具有牢固的抗抵賴性。兩種多重簽名子方案中，簽名驗證者對各個簽名者公鑰進(jìn)行遍歷，完成驗證后，簽名者Bi不能否認(rèn)對消息進(jìn)行了簽名，因為完成簽名協(xié)議過程的前提是掌握Bi的私鑰及相應(yīng)隨機數(shù)ui。

(4)算法簡潔、高效。方案充分發(fā)揮了ECC密鑰短、平安性高的優(yōu)勢，密鑰長度僅需160bit就可以提供與1024bit的RSA或DSA同樣的平安度。因此，該方案特別適用于計算能力和集成電路空間受限(如智能卡smartcard)、帶寬受限(如無線通信和某些計算機網(wǎng)絡(luò))、要求高效率實現(xiàn)的情況。需要特別指出的是，方案中簽名者Bi每次簽名時必須更換隨機產(chǎn)生的秘密參數(shù)ui。例如，在有序多重簽名方案中，如不更換隨機數(shù)且簽名的順序保持不變，那么攻擊者根據(jù)變化了的si與m′的值，依據(jù)式(6-4)，在經(jīng)過2(i－1)次協(xié)議過程后，就可以聯(lián)立2(i－1)個關(guān)系式，從而求解出前面i－1個簽名者的私鑰與相應(yīng)的隨機數(shù)。同理，在播送多重簽名中，可由式(6-5)、(6-6)得到

如不更換隨機數(shù)，那么協(xié)議過程次數(shù)越多私鑰就越不平安，當(dāng)協(xié)議次數(shù)大于2n時，就完全有可能攻破私鑰，偽造簽名。4)方案的軟件實現(xiàn)效率與平安性

橢圓曲線密碼軟件實現(xiàn)時的函數(shù)包括：模一般素整數(shù)運算函數(shù)集，其中有加、減、乘、除、求逆；大素數(shù)域GF(q)中運算函數(shù)集，這其中也有加、減、乘、除、求逆；橢圓曲線根本運算函數(shù)集，其中有點加、倍點、固定點標(biāo)量乘(scalarmultiplication，即求固定點p的k倍)、隨機點標(biāo)量乘；輔助函數(shù)，如平安散列函數(shù)選擇SHA_1或RIPEMD_160。模一般素整數(shù)運算與大素數(shù)域GF(q)中運算是ECC軟件實現(xiàn)中調(diào)用最頻繁的函數(shù)，這些函數(shù)采用匯編語言編寫，其它的函數(shù)與算法用標(biāo)準(zhǔn)C語言編寫。

表6-1列出了運用相關(guān)文獻(xiàn)提出的橢圓曲線軟件實現(xiàn)方法，在PⅢ800MHz128M內(nèi)存的運行環(huán)境下方案的執(zhí)行效率。方案中，橢圓曲線選取192bit二元域上的Koblitz曲線，平安素數(shù)(公開基點P的階)是160bit的素數(shù)。利用目前對一般橢圓曲線離散對數(shù)問題進(jìn)行攻擊的最好方法Pollardρ算法，對于一臺每分鐘能執(zhí)行1百萬條指令的機器(每秒鐘能執(zhí)行4×104次橢圓曲線加法運算，在一年內(nèi)可執(zhí)行(4×104)(60×60×24×365)≈240次橢圓曲線點加運算)，要完成(πn/2)1/2≈280步攻擊運算，至少需要9.6×1011年。到2004年時，可得到的計算能力已為108MIPS(一個MIPS為一臺每分鐘能執(zhí)行1百萬條指令的機器工作一年)，到2021年，可得到的計算能力為1010~1011MIPS，即使此時要實現(xiàn)對此ECDLP的攻擊也分別至少需要9.6×103年和9.6年(不考慮并行Pollardρ攻擊方法)。因此可以得出結(jié)論：對算法進(jìn)行強力攻擊在計算上是不可實現(xiàn)的，同時方案也以較少的存儲空間和較小的通信帶寬與系統(tǒng)開銷實現(xiàn)了較高的平安性。多重數(shù)字簽名是網(wǎng)絡(luò)中常用的一種通信協(xié)議，但由于是通過屢次簽名與認(rèn)證的策略實現(xiàn)聯(lián)合簽名以加強協(xié)議的平安性，因此多重簽名方案存在著協(xié)議過程復(fù)雜、簽名認(rèn)證運算開銷大等缺乏之處。上文中提出的基于橢圓曲線密碼的網(wǎng)絡(luò)通信中的多重數(shù)字簽名方案表達(dá)了低通信消耗(lowcommunicationcosts)與低系統(tǒng)開銷的設(shè)計原那么。6.3超橢圓曲線密碼NealKoblitz和VictorMiller在20世紀(jì)80年代中期提出了橢圓曲線密碼體制(ECC)，經(jīng)過20多年的研究，ECC理論已經(jīng)比較成熟，并且已經(jīng)廣泛應(yīng)用于實際當(dāng)中。作為橢圓曲線的一個推廣，NealKoblitz在1989年提出了超橢圓曲線密碼體制(HCC)，它的平安性基于有限域上超橢圓曲線的Jacobian上的離散對數(shù)問題的難解性。6.3.1超橢圓曲線

定義6-3設(shè)F是域，是其代數(shù)閉域，那么F上虧格為g(g≥1)的超橢圓曲線C是指具有方程形式:

C：v2+h(u)v=f(u)(6-8)

的曲線。這里h(u)∈F［u］是次數(shù)不大于g的多項式，f(u)∈F［u］是一個次數(shù)為2g+1的首一多項式，而且不存在

滿足以下方程組:

如果g=1，那么稱C為橢圓曲線。定義6-4設(shè)K是F上的一個擴域，那么C上的一個K-點P是符號∞(稱為C上的無窮遠(yuǎn)點)或是方程C：v2+h(u)v=f(u)的一個解(x，y)∈K×K。C上的所有K-點記為C(K)。

定義6-5設(shè)P=(x，y)是一條橢圓曲線C：v2+h(u)v=f(u)上的一個有限K-點，那么它的相反點記為。如果P=∞，我們?nèi)?。如果P是一個有限點且滿足

，那么稱P是一個特殊點，否那么稱P是一個普通點。引理6-1設(shè)C是由方程C：v2+h(u)v=f(u)定義的域F上的超橢圓曲線，那么滿足：

(1)如果h(u)=0，那么Char(F)≠2。

(2)如果Char(F)≠2，那么作變換u→u及v→v－h(huán)(u)/2，從而將C的形式變?yōu)関2=f(u)(其中deguf=2g+1)。6.3.2除子與Jacobian群

定義6-6一個除子d是C上假設(shè)干點的一種形式和:

其中只有有限個整數(shù)mP非零。整數(shù)稱為d的度數(shù)，記為degd。d在P點的階是mP，表示為ordP(d)=mP。設(shè)D表示C上所有除子的集合，那么D在如下加法規(guī)定之下是一個加群：

設(shè)D0={d∈D|degd=0}，那么D0是D的一個子群。

定義6-7設(shè)C是域F上的一條超橢圓曲線，域上C的坐標(biāo)環(huán)是定義為

的商環(huán)。中的元素稱為C上的多項式函數(shù)。

對每一個多項式函數(shù)，可以通過重復(fù)地將G(u，v)中的v2替換成f(u)－h(huán)(u)v來降低v的冪次，最終得到G(u，v)的一種唯一形式，可設(shè)為

定義6-8設(shè)是一個非零的多項式函數(shù)，P∈C，那么G在P點的階記為ordP(G)，定義如下：

(1)如果P=(x，y)是一個有限點，那么可設(shè)

G(u，v)=(u－r)r(a0(u)－b0(u)v)，這里r是可同時整除a(u)和b(u)的(u－x)的最高次冪。如果(a0(x)－b0(x)y)≠0，那么設(shè)s=0；否那么，設(shè)s是使(u－x)s整除范數(shù)

的最高次冪。如果P是一個普通點，那么定義ordP(G)=r+s；

如果P是一個特殊點，那么定義ordP(G)=2r+s。(2)如果P=∞，那么定義

ordP(G)=－max{2degu(a)，2g+1+2degu(b)}

對于一個非零的有理函數(shù)及C上的一個點P的階定義為

ordP(R)=ordP(G)－ordP(H)定義6-9設(shè)是一個有理函數(shù)，那么R的除子定義為

例如，如果P是一個普通點，那么有;如果P是一個特殊點，那么有div(u－x)=2P－2∞。

顯然，如果R=G/H，那么

div(R)=div(G)－div(H)

定義6-10設(shè)J(更準(zhǔn)確地說為也可以用F的任何一個擴域代替)表示商域D0/P，J稱為曲線C上的Jacobian群。

設(shè)d1，d2∈D0，如果d1－d2∈P，那么記d1～d2，并稱d1與d2等價。

J中的每一個元素是D0中元素的一個等價類，它可以表示成d+P，或簡單地記為，這里d∈D0是一個除子，并稱為的一個代表元。很顯然，該代表元不唯一。J中元又稱為除子類。6.3.3超橢圓曲線Jacobian群中的運算

定理6-2設(shè)d=∑miPi－∞∑mi是一個半約化除子，這里Pi=(xi，yi)∈C，設(shè)

，那么存在唯一的一對多項式(a(u)，b(u))滿足d=gcd(div(a(u))，div(b(u)－v))。為了簡便，通常將其寫成div(a,b)。因此，J中的每一個元素可唯一地表示成。其中，多項式a(u)、b(u)滿足degub＜degua＜g及a(u)|(b2(u)+b(u)h(u)－f(u))，因此J(Fq)是一個有限Abelian群，且其階＃J(Fq)≤q2g。

設(shè)D*表示所有約化除子div(a，b)組成的集合，a，b∈F(u)，且滿足degub＜degua＜g及a|(b2+bh－f)，那么集合J(F)與集合D*之間存在一個一一映射。在如下的討論中，我們可以將J(F)看成是D*，將看成是div(a，b)，群J(F)的零元那么是div(1，0)。此處定義一種運算，稱為J(F)中的加法，用標(biāo)記，這也被稱為超橢圓曲線Jacobian上的除子加。

設(shè)d1=div(a1，b1)，d2=div(a2，b2)∈D*，規(guī)定d1⊕d2=d(a，b)是由以下算法唯一確定的約化除子：

(1)利用廣義Euclidean算法找出多項式d，s1，s2，s3∈F(u)，滿足:

d=gcd(a1，a2，b1+b2+h)，d=s1a1+s2a2+s3(b1+b2+h)

(2)置(3)置

(4)如果degua＞g，那么作變換a′←a，b′←b，并返回(3)。

(5)輸出div(a，b)即為d。有限域上超橢圓曲線的Jacobian是一個有限交換群，超橢圓曲線的Jacobian上的根本運算包括除子加、倍除子和除子標(biāo)量乘。Jacobian上實用的群運算算法最早是由Cantor提出的，當(dāng)時只是限定在非特征2的域上。之后，NealKoblitz于1988年提出超橢圓曲線密碼體制時將Cantor算法推廣到了任意的域上。Cantor-Koblitz群運算法那么實際上等價于高斯的二元二次型歸約算法。AndreasEnge將歸約算法進(jìn)行了推廣，在除子運算中運用了擴展的Euclidean算法，對幾種除子運算的計算量作了理論上的分析，得到了一次除子加用到有限域GF(qn)中運算的平均值，其數(shù)據(jù)如表6-2所示(超橢圓曲線為C：v2+h(u)v=f(u))。我們以［19］借助Frobenius自同態(tài)提出的一種快速除子標(biāo)量乘算法為例，計算分析快速除子標(biāo)量乘的運算量。Zhang的方法可推廣為一類計算超橢圓曲線除子標(biāo)量乘的方法，實現(xiàn)步驟如下：

(1)輸入一個除子D及一個正整數(shù)m;

(2)計算曲線Jacobian上的Frobenius自同態(tài)的特征多項式P(T);

(3)對于1≤i≤qg－1，預(yù)計算iD;

(4)將m轉(zhuǎn)換成符號q-進(jìn)制：，其中

－qg+1≤i≤qg－1;

(5)令B:=〈1，0〉;

(6)對于i自l－1遞減到0，計算:

B：B+rD假設(shè)ri不為零

(7)輸出B為mD。

下面我們以幾條選定的GF(qn)上的超橢圓曲線為例，比較二元法與Zhang提出的方法計算qnP的運算量，如表6-3所示。(表中，a、m和s分別表示一次除子加、倍加和賦值運算。)6.3.4超橢圓曲線密碼體制(HCC)

設(shè)C是Fq上虧格為g的超橢圓曲線，J(Fq)是它的Jacobian，

，n是160bit的大素數(shù)(h=1，或是較小的余因子)，q約為160bit。p∈J(Fq)是具有大素數(shù)階n的一個約化除子，

在g=2時，

設(shè)，Q=kP=［aq，bq］≠0，那么Q可以作為公鑰公布，k作為密鑰保存，加密時將信息嵌入密鑰當(dāng)中。同時我們需要一個單射，將P對應(yīng)于一個整數(shù)。設(shè)ψ表示該對應(yīng)關(guān)系，那么ψ是一個從J(Fq)到有限整數(shù)集

的單射，將其記為(P)x或(P)q。很顯然，這樣的賦值映射是不唯一的。在實際密碼應(yīng)用中，可以根據(jù)給定的超橢圓曲線規(guī)定一個適當(dāng)?shù)挠成涞闹涤蚍秶Ｏ旅媸抢樱?/p>

(1)設(shè)β＝(c0，c1，…，c2g－1)是集合{a0，…，ag－1，b0，…，bg－1}上的一個置換映射，那么

是一個單的賦值映射。(2)先對每個ai與bi取模q，轉(zhuǎn)換為不大于q－1的非負(fù)的整數(shù)，令

上式表示將所有ai與bi取模q后的非負(fù)數(shù)聯(lián)接而得到的整數(shù)。超橢圓曲線密碼體制的平安性是建立在超橢圓曲線離散對數(shù)問題(HCDLP)的難解性之上的，目前對低虧格(g≤4)的HCC的攻擊是指數(shù)時間的，對虧格小于4的一般超橢圓曲線沒有發(fā)現(xiàn)亞指數(shù)時間攻擊。在與RSA或傳統(tǒng)的離散對數(shù)密碼系統(tǒng)相同的平安強度下，它可以使用更短的操作數(shù)長度。實際中，操作數(shù)長度在50~80之間(依賴于虧格的取值)所建立的密碼體制就足以抗擊目前的攻擊。假設(shè)取虧格為3，那么所基于的有限域的大小可以是60bit，由此所建立的密碼體制的平安性與180bit的ECC等同，遠(yuǎn)遠(yuǎn)大于1024bit的RSA。如果使用的是64bit處理器的計算機，那么超橢圓曲線的運算就可以用單個計算機的字去處理，從而防止了多精度整數(shù)運算，使得存儲和運算更簡單［1］。6.3.5基于超橢圓曲線密碼體制的密碼協(xié)議

分工的社會化、經(jīng)濟的全球化促使經(jīng)濟業(yè)務(wù)更為復(fù)雜多變，單一的經(jīng)營實體經(jīng)常難以處理專業(yè)性強、職能特征突出的交易與事務(wù)，這就不可防止地出現(xiàn)了委托、信托、行寄的經(jīng)營形式。而在經(jīng)營實體規(guī)模不斷擴大的趨勢下，所有權(quán)與經(jīng)營權(quán)的別離也出現(xiàn)了管理經(jīng)營的授權(quán)委托，比較典型的就是合伙制與股份公司制的受托經(jīng)營。在這些運作模式下，處理電子商務(wù)重大事務(wù)的真正決定權(quán)仍在所有者，由其對重大合同、契約等授權(quán)簽字，而又需要由運作者執(zhí)行簽字。這就內(nèi)含一種代理行使簽名權(quán)的機制，即代理簽名。同樣，在B2B模式下的電子交易系統(tǒng)中，代理數(shù)字簽名也成為代理營銷方案保證交易真實性、完整性、有效性與可靠性的關(guān)鍵技術(shù)。1.代理數(shù)字簽名方案及其分類

代理數(shù)字簽名可以分為單個代理簽名與多重代理數(shù)字簽名。

1)單個代理簽名

設(shè)A，B是某個數(shù)字簽名體制(M，S，K，SIG，VER)的兩個用戶，他們的私鑰和公鑰分別是(xA，yA)與(xB，yB)，假設(shè)有以下5個條件成立，那么，就稱A將他的數(shù)字簽名權(quán)力委托給了B，稱A為原始簽名人，B為A的代理簽名人，f為委托密鑰，fAB為代理簽名密鑰。

(1)A利用他的密鑰xA計算出一個數(shù)f，并將f秘密地交給B；(2)任何人(包括B)在試圖求出xA時，f不會對其有任何幫助；

(3)B利用xB和f生成一個新的簽名密鑰fAB；

(4)存在一個公開的驗證算法VERAB，滿足對于任何s∈S和m∈M，都有VER(yA，s，m)=True，等價于s=SIG(fAB,m)；

(5)任何人在試圖求出xA，xB，f或fAB時，任何數(shù)字簽名SIG(fAB，m)都不會對其產(chǎn)生幫助。2)多重代理數(shù)字簽名

假設(shè)Ai(1≤i≤n)是某個數(shù)字簽名體制(M，S，K，SIG，VER)的n個用戶，Ai的秘鑰與公鑰對為(xi，yi)。假假設(shè)對于任意的Ai(1≤i≤n)都將他的簽名權(quán)力委托給了B(設(shè)B得到的代理簽名秘鑰為fi)，B對某個特定的消息m∈M聯(lián)合生成了一個多重簽名s=SIG(f1，f2，…，fn，m)，使得驗證這個多重簽名的有效性時，必須使用所有Ai的公鑰，那么稱S為一個由B代表Ai(1≤i≤n)生成的多重代理簽名［2］。

2.基于HCC的單一代理數(shù)字簽名方案

方案包括系統(tǒng)初始化、委托過程、簽名產(chǎn)生與簽名驗證過程，同時方案的協(xié)議方為原始簽名者、代理簽名者與簽名驗證者。1)初始化過程

設(shè)C是Fq上虧格為g的超橢圓曲線，J(Fq)是它的Jacobian，#J(Fq)=hl，l是190bit的大素數(shù)(h=1，或是較小的余因子)，q約為190/gbit。P，P1∈J(Fq)是具有大素數(shù)階的約化除子，它們的階分別為L0、L1(滿足min(L0，L1)≥190bit)。n為一個大素數(shù)(滿足n>max(L0，L1))。H0、H1、H2為平安的散列函數(shù)，H0，H1，H2{0，1}*→Zn。ka，kb∈分別為用戶A和銀行的私鑰，Kb=kbP，Ka=kaP作為兩者的公鑰，密鑰對(Ka，ka)、(Kb，kb)作為協(xié)議中的主密鑰。ψ表示是一個從J(Fq)到有限整數(shù)集

={0，1，…，q2g+1－1}的單射函數(shù)，將其記為(P)x或(P)q。公開n，P、P1和H0、H1、H2以及公鑰Kb=kbP，Ka=kaP。設(shè)kA，kB∈(1，2，…，n－1)分別為A和B的私鑰，KA=kAp，KB=kBp為A和B的公鑰，共享的平安散列函數(shù)為H1和H2。2)委托過程

(1)A隨機選取u∈(1，2，…，n－1)，計算:

R=up≠0，h=H1((R)x)

f=hkA+u(modn) (6-9)

并將(R，f)秘密地發(fā)送給B。

(2)B計算h=H1((R)x)，然后驗證:

fp=hKA+R

是否成立，假設(shè)成立那么計算

f′=f+kB(modn) (6-10)3)代理簽名過程

對于某個消息m，B隨機選取v∈(1，2，…，n－1)，計算得到T=vp≠0，再計算

m′=H2(m)

s=(T)xf′－m′v(modn) (6-11)

并將(m，s，R，T)發(fā)送給簽名驗證者。4)代理簽名驗證過程

驗證者接收到(m，s，R，T)后，計算

h=H1((R)x)，m′=H2(m)

驗證

(T)x(hKA+R+KB)=sp+m′T (6-12)

是否成立。如果等式成立，那么認(rèn)為B代理A的簽名有效；否那么認(rèn)定為無效簽名。簽名驗證中，由式(6-11)可得

式(6-12)右邊

=等式左邊

這就驗證了上述單一代理數(shù)字簽名方案的正確性。3.基于HCC的多重代理數(shù)字簽名方案

1)初始化過程

系統(tǒng)初始化和參數(shù)設(shè)定與單一代理數(shù)字簽名的方案相同，假設(shè)ki，kB分別為Ai(i=1，2，…，n)和B的私鑰，Ki=kip，KB=kBp為Ai和B的公鑰，共享的平安散列函數(shù)為H1和H2。2)委托過程

(1)Ai隨機選取ui∈(1，2，…，n－1)，計算

Ri=uip≠0，hi=H1((Ri)x)

fi=hiki+ui(modn) (6-13)

并將(Ri，fi)秘密地發(fā)送給B。(2)B在收到(Ri，fi)(i=1，2，…，n)后，計算hi=H1((Ri)x)，然后驗證

fip=hiKi+Ri

是否成立。假設(shè)成立那么認(rèn)為(Ri，fi)是一個有效的子代理密鑰;否那么B要求Ai重復(fù)(1)或終止協(xié)議過程。3)代理簽名過程

B在收到所有(Ri，fi)后，計算出

(6-14)

對于某個消息m，B隨機選取v∈(i=1，2，…，n－1)，計算

T=vp≠0，m′=H2(m)

s=f′－(m′+(T)x)v(modn) (6-15)

(s，T，R1，R2，…，Rn)為B代表Ai(i=1，2，…，n)生成的多重代理簽名。4)代理簽名驗證過程

驗證者收到(s，T，R1，R2，…，Rn)和消息m后，計算

hi=H1((Ri)x)，m′=H2(m)

驗證

(6-16)

是否成立。如果等式成立，那么認(rèn)為B代理Ai生成的多重代理簽名有效；否那么認(rèn)定為無效簽名。簽名驗證中，由式(6-15)可得

式(6-16)右邊

＝等式左邊

這就驗證了上述多重代理數(shù)字簽名方案的正確性。

4.代理數(shù)字簽名方案分析

(1)代理簽名方案可具有區(qū)分與身份證實性。根據(jù)式(6-10)，在單一代理簽名中有

f′=f+kB(modn)

根據(jù)式(6-14)，在多重代理簽名中有

所以代理簽名密鑰的產(chǎn)生依賴于原始簽名人的普通簽名密鑰，但不同于原始簽名者的普通簽名密鑰，因此與原始簽名密鑰是可區(qū)分的，而且在存在多個代理簽名者的情況下，每個代理簽名者的子代理密鑰(Ri，fi)也是不相同的。所以，原始簽名者可以將不同的代理者區(qū)分開，有效地實現(xiàn)對代理者的監(jiān)督，防止代理簽名權(quán)力的濫用。在出現(xiàn)問題時，第三方也可以將原始簽名者與代理簽名者、不同的代理者區(qū)分開來。(2)具有較強的防偽造性。除了原始簽名人A以外，任何人(包括代理簽名者)在不知道私鑰kA的情況下，都不能偽造原始簽名人的普通簽名信息。同理，代理簽名者的簽名秘鑰對于攻擊者(包括原始簽名者)也是平安的。如果原始簽名者委托了多人代理簽名，那么根據(jù)式(6-10)、(6-14)，由于代理簽名秘鑰f′中引入了代理簽名者的私鑰kB，各個代理簽名者之間也不能偽造簽名信息，因為要偽造簽名必須攻擊相應(yīng)代理簽名者的私鑰及隨機數(shù)v，這就使得面對的都是求解HCDLP問題。對于內(nèi)部攻擊，假定有m(m<n)個原始簽名人要合謀偽造一個簽名，那么他們必須得到所有原始簽名者Ai的私鑰及相應(yīng)隨機數(shù)ui，由于這些秘密參數(shù)是獨立隨機產(chǎn)生的，因此對于協(xié)同的內(nèi)部攻擊者，除了知道自己的秘密參數(shù)外，其攻擊能力并不比外部攻擊者更具優(yōu)勢。方案防止了由局部成員可決定的系統(tǒng)秘密，所以對于內(nèi)部成員同樣具有較強的抗攻擊能力。(3)具有牢固的抗抵賴性。由于代理簽名密鑰與普通簽名密鑰具有較強的防偽造性與身份證實性，因此簽名驗證者對各個原始簽名者的公鑰進(jìn)行遍歷，完成驗證

或

(T)x(hKA+R+KB)=sp+m′T

后，原始簽名者Ai不能否認(rèn)將代理簽名權(quán)委托給了B，代理簽名者B也不能否認(rèn)對消息進(jìn)行了簽名，因為完成委托與代理簽名協(xié)議過程的前提是掌握相應(yīng)的私鑰及協(xié)議中產(chǎn)生的隨機數(shù)。(4)代理簽名權(quán)撤銷靈活。當(dāng)原始簽名人想撤消代理簽名者Bi的代理簽名權(quán)時，他可以通過媒體公開宣布原有委托信息(Ri，fi)不再有效，注銷代理簽名密鑰f′。但是這種播送方式必須要有簽名機制，以防止攻擊者發(fā)布偽造的撤銷消息進(jìn)行中間入侵攻擊(intruder-in-middleattack)。(5)算法簡潔、高效。方案充分發(fā)揮了HCC密鑰短、平安性高的優(yōu)勢。當(dāng)超橢圓曲線虧格為3時，方案所基于的有限域僅需60bit就可以提供與180bit的ECC相同的平安強度。

需要特別指出的是，簽名者B每次簽名時必須更換隨機產(chǎn)生的秘密參數(shù)v，否那么攻擊者根據(jù)si與m′值的變化，從單一代理簽名式(6-9)、(6-10)、(6-11)可得

s=(T)x(hkA+u+kB)－m′v(modn)

經(jīng)過四次協(xié)議過程就可以聯(lián)立四個關(guān)系式，解出原始簽名者與代理簽名者的私鑰與相應(yīng)的隨機數(shù)。同理，在多重代理簽名中，依據(jù)式(6-13)~(6-15)可得

如不更換隨機數(shù)，那么協(xié)議過程越多私鑰就越不平安，當(dāng)協(xié)議次數(shù)大于2(n+1)時，就完全能夠攻破私鑰，破壞整個簽名系統(tǒng)。6.4基于身份的公鑰密碼體制6.4.1基于身份的密碼體制簡介基于身份的密碼體制最早于1984年由Shamir提出［8］，針對公鑰根底設(shè)施利用向用戶分發(fā)證書實現(xiàn)密鑰管理而造成的使用上的不便，Shamir提出了用任意字符串作為密鑰的思想，即IBE(IdentityBasedEncryption)，其主要思路是利用用戶的身份信息(ID、郵箱等)生成公鑰，從而信息的發(fā)送方無須訪問任何證書機構(gòu)或可信第三方就能得到接收方的公鑰。Shamir通過郵件加密來闡述IBE的工作過程，當(dāng)用戶Alice要向Bob發(fā)送郵件時，假設(shè)Bob的郵箱為//，那么Alice直接用公開的字符串加密信息即可，無須從任何證書管理機構(gòu)獲得Bob的公鑰證書。Bob收到密文時，與稱為私鑰生成器(PKG，PrivateKeyGenerator)的第三方聯(lián)系，通過認(rèn)證后，得到自己的私鑰，從而可以解密信息。這樣做可以大大簡化郵件系統(tǒng)中的密鑰管理，從而使公鑰密碼的應(yīng)用變得極為方便。IBE的思想提出后，人們用各種數(shù)學(xué)工具設(shè)計了許多實現(xiàn)方案，但這些方法都有一定的局限性，因此，長期以來，設(shè)計實用的IBE方案被視為一個公開的難題。2001年，Boneh和Franklin利用代數(shù)曲線上的雙線性對實現(xiàn)了第一個既實用又平安的IBE方案［9］。他們還利用隨機預(yù)言機模型(ROM，RandomOracleModel)證明，該方案能抵抗不可區(qū)分的自適應(yīng)選擇密文攻擊。此后，大量基于雙線性對技術(shù)的加密和簽名機制被提出，基于身份的密碼學(xué)研究成為學(xué)者們關(guān)注的熱點。目前，基于身份的方案包括基于身份的加密體制、可鑒別身份的加密和簽密體制、簽名體制、密鑰協(xié)商體制、鑒別體制、門限密碼體制和層次密碼體制等。一個基于身份的密碼體制由四個隨機算法構(gòu)成。

初始化(Setup)：給定平安參數(shù)k，輸出系統(tǒng)參數(shù)params和主密鑰，系統(tǒng)參數(shù)包括消息空間M、密文空間C。系統(tǒng)參數(shù)是公開的，而主密鑰只有“私鑰生成器〞PKG知道。

密鑰提取(Extract)：輸入系統(tǒng)參數(shù)params，主密鑰和任意的ID∈{0，1}*，輸出私鑰d，其中ID為用戶公鑰，d為相應(yīng)的私鑰，提取算法由給定的公鑰生成私鑰d。

加密(Encrypt)：輸入系統(tǒng)參數(shù)params、ID，以及m∈M，輸出密文c∈C。

解密(Decrypt)：輸入系統(tǒng)參數(shù)params、ID，私鑰d以及c∈C，輸出m∈M。這些算法必須滿足一致性條件，即當(dāng)d為由提取算法產(chǎn)生的相對于ID的私鑰時，對任意m∈M，有

Decrypt(params，ID，c，d)=m

其中，c=Encrypt(params，ID，m)。

基于身份的密碼體制建立在橢圓曲線密碼學(xué)(ECC，EllipticCurveCryptography)的根底之上，ECC體制的平安根底是有限域中橢圓曲線上的點群中的離散對數(shù)問題(ECDLP，EllipticCurveDiscreteLogarithmProblem)。目前的研究結(jié)果說明，解決橢圓曲線離散問題比有限域上的離散對數(shù)問題更加困難。對橢圓曲線密碼體制的研究與應(yīng)用極大地促進(jìn)了基于身份密碼體制的研究。以下我們詳細(xì)介紹Boneh和Franklin提出的IBE體制(BF方案)。

6.4.2BF方案及其平安性

1.平安模型

在公鑰密碼體制中，由于加密密鑰公開，因此認(rèn)為攻擊者擁有所有用戶的公鑰，并且可以任意選擇明文進(jìn)行加密，此外攻擊者還有時機獲得密文，而且可能利用各種途徑來獲得解密。因此，足夠平安的公鑰密碼體制應(yīng)該能夠抵抗選擇密文攻擊。公鑰密碼體制按照攻擊者所掌握的條件及攻擊目標(biāo)的不同，可以分為

單向性(OW)平安：由密文不能恢復(fù)相應(yīng)的明文；

不可區(qū)分性(IND)平安：對給定的兩個明文，加密者隨機選擇其中一個進(jìn)行加密，攻擊者無法從密文中獲知是對哪個明文的加密；

非延展性(NM)平安：攻擊者無法構(gòu)造與已給密文相關(guān)的新密文。

以上平安性概念是依次加強的，NM比IND平安，IND比OW平安。此外，公鑰密碼體制還可按照可能的攻擊模型分為

選擇明文(CPA)攻擊：攻擊者可以先適應(yīng)性選擇明文，獲得相應(yīng)的密文；

非適應(yīng)性選擇密文(CCA1)攻擊：攻擊者除了可以適應(yīng)性選擇明文攻擊外，在給定目標(biāo)密文前，還可以任意選擇密文并獲得相應(yīng)的解密；

適應(yīng)性選擇密文(CCA2)攻擊：攻擊者的唯一限制就是不能直接獲得與目標(biāo)密文相對應(yīng)的明文，即攻擊者可以在給定目標(biāo)密文后，任意選擇密文并獲得相應(yīng)的解密。

同時考慮攻擊目標(biāo)和攻擊模型，可以獲得不同的平安性，其中最重要的是IND-CCA2和NM-CCA2平安，而二者被證明是等價的，所以通常意義上的選擇密文攻擊平安性是指IND-CCA2平安。1)IND-ID-CCA

IND-CCA是一種被普遍接受的公鑰密碼平安性標(biāo)準(zhǔn)，在一般情況下，對于攻擊者所掌握的條件可以定義為得到了某個公鑰ID相對應(yīng)的私鑰，而在IBE中，選擇密文攻擊平安性的定義必須有所加強。這是因為攻擊者在攻擊時，可以任意選擇系統(tǒng)中任何一個用戶的ID。因此應(yīng)該定義為允許攻擊者任意選擇公鑰IDi，并得到與之相應(yīng)的私鑰。這個條件被稱為私鑰提取詢問(PrivateKeyExtractionQuery)，而參加了私鑰提取詢問條件的IND-CCA記作IND-ID-CCA。在定義IND-ID-CCA平安的IBE系統(tǒng)時，Boneh和Franklin設(shè)計了如下攻擊游戲：

初始化：挑戰(zhàn)者選擇平安參數(shù)k，運行IBE中的初始化算法，將系統(tǒng)參數(shù)送給敵手，而將主密鑰保密。

階段1：敵手發(fā)出m個詢問q1，q2，…，qm。其中，qi可以是以下二者之一：

(1)提取詢問〈IDi〉，此時挑戰(zhàn)者的響應(yīng)是運行IBE中的密鑰提取算法，產(chǎn)生相應(yīng)于公鑰IDi的私鑰di并將其送給敵手。(2)解密詢問〈IDi，ci〉，此時挑戰(zhàn)者的響應(yīng)是運行密鑰提取算法，產(chǎn)生私鑰di，然后運行解密算法，利用di對密文解密，將明文送給敵手。

敵手可以根據(jù)q1，q2，…，qi－1的結(jié)果自適應(yīng)地選擇qi為何種詢問。

挑戰(zhàn)：階段1結(jié)束后，挑戰(zhàn)者輸出兩個明文m0，m1∈M，以及要挑戰(zhàn)的公鑰ID，唯一的限制條件是ID不出現(xiàn)在階段1的任何詢問中。挑戰(zhàn)者隨機選擇1比特b∈{0，1}，設(shè)置C=Encrypt(params，ID，Mb)，將C作為挑戰(zhàn)發(fā)送給敵手。階段2：敵手發(fā)出更多的詢問qm+1，…，qn。其中，qi為以下二者之一：

(1)提取詢問〈IDi〉，其中IDi≠ID，挑戰(zhàn)者的響應(yīng)如階段1。

(2)解密詢問〈IDi，ci〉≠〈ID，c〉，挑戰(zhàn)者的響應(yīng)如階段1。

猜測：敵手輸出一個猜測b′∈{0，1}，如果b′=b，那么獲勝。

進(jìn)行以上攻擊的敵手A被稱為一個IND-ID-CCA攻擊者，其優(yōu)勢定義為

如果不存在敵手A，能以不可忽略的優(yōu)勢在上述攻擊游戲中獲勝，那么說一個IBE系統(tǒng)在IND-ID-CCA下是語義平安的?！安豢珊雎缘膬?yōu)勢〞理解為存在某個多項式f，使得

，其中k為系統(tǒng)的平安參數(shù)。2)OWE

為了證明IBE系統(tǒng)的平安性，需要采用一個弱化的平安概念，稱為單向加密(OWE，One-WayEncryption)。OWE是針對標(biāo)準(zhǔn)公鑰體制而定義的，其含義為：假設(shè)敵手A掌握了一個隨機的公鑰Kpub和密文c，c是利用Kpub對隨機明文m加密的結(jié)果，攻擊者的目標(biāo)是恢復(fù)相應(yīng)的明文，其優(yōu)勢定義為

Pr［A(Kpub，c)=m］。

如果不存在多項式時間攻擊者，能夠以不可忽略的優(yōu)勢攻破該體制，那么稱一個公鑰體制是單向加密體制。在IBE中，Boneh和Franklin對該定義進(jìn)行了強化，即如果不存在多項式時間的敵手，能以不可忽略的優(yōu)勢在以下的攻擊

中獲勝，那么稱一個IBE體制是基于身份的單向加密體制(ID-OWE)。攻擊包括四個步驟：

初始化：挑戰(zhàn)者選擇平安參數(shù)k，運行IBE中的初始化算法，將系統(tǒng)參數(shù)給敵手，而將主密鑰保密。階段1：敵手發(fā)出私鑰提取詢問ID1，…，IDr，挑戰(zhàn)者運行密鑰提取算法，輸出每個公鑰IDi對應(yīng)的私鑰di，并將其傳給敵手；

挑戰(zhàn)：階段1結(jié)束后，挑戰(zhàn)者輸出公鑰ID≠ID1，…，IDr。ID為其要挑戰(zhàn)的公鑰，隨機選擇m∈M，并用ID對m加密，將密文c送給敵手。

階段2：敵手發(fā)出更多的詢問IDr+1，…，IDn，要求IDi≠ID，挑戰(zhàn)者的響應(yīng)如階段1。

猜測：最后敵手輸出消息m′∈M，如果m′=m，那么獲勝。2.數(shù)學(xué)工具

1)雙線性映射

定義6-11令G1和G2為兩個階為素數(shù)q的循環(huán)群，P為G1的生成元，如果映射e：G1×G1→G2滿足如下性質(zhì)，那么稱e為雙線性映射：

(1)可計算性：給定P，Q∈G1，存在一個多項式時間算法計算e(P，Q)∈G2；

(2)雙線性性：對任意P，Q∈G1，a，b∈Zp，有e(aP，bQ)=e(P，Q)ab；

(3)非退化性：存在P∈G1，使得e(P，P)≠1。此時，稱G1為雙線性群，如果其中的群運算以及雙線性映射都是可以有效計算的。注意，映射e是對稱的，因為

e(Pa，Pb)=e(P，P)ab=e(Pb，Pa)在加法群G1上，有如下一些數(shù)學(xué)難題：

(1)離散對數(shù)問題(DLP)：對P，Q∈G1，找到一個整數(shù)n∈，使Q=nP成立；

(2)Difie-Hellman判定問題(DDHP，DecisionalDiffie-HellmanProblem)：對于a，b，c∈，給定P，aP，bP，cP∈G1，判定c=abmodp是否成立；

(3)Difie-Hellman計算問題(CDHP，ComputationalDiffie-HellmanProblem)：對a，b∈，給定P，aP，bP∈G1，計算abP。2)Weil對及其性質(zhì)

令p為素數(shù)，滿足p=2mod3，且存在素數(shù)q，使得

p=6q－1，令E/Fp為由Fp上方程y2=x3+1確定的橢圓曲線，這種曲線滿足如下性質(zhì)：

(1)由于x3+1是Fp上的置換多項式，因而E/Fp中包含p+1個點，令O表示無窮遠(yuǎn)點，P∈E/Fp為階群Gq中的生成元；

(2)對任意y0∈Fp，存在唯一的點(x0，y0)∈E/Fp。從而假設(shè)(x，y)隨機地取遍E/Fp上的非零點，那么y隨機地取遍Fp上的所有點；(3)假設(shè)ζ∈，ζ≠1，為x3－1=0modp的根，那么映射φ(x，y)=(ζx，y)為曲線E上的自同構(gòu)，注意到P=(x，y)∈E/Fp,從而有，但φ(P)E/Fp，因此P∈E/Fp與φ(P)線性無關(guān)；

(4)由于點P與φ(P)線性無關(guān)，它們可以生成一個與Zq×Zq同構(gòu)的群，將該群記作E［q］。

令μq為中由所有階點構(gòu)成的子群，曲線上的Weil對定義為映射

e：E［q］×E［q］→μq

定義修正后的Weil對為

(6-17)修正后的Weil對滿足以下性質(zhì)：

(1)雙線性性：對任意P，Q∈Gq，a，b∈Z，有

；

(2)非退化性：

是q階元素，事實上，它是μq的生成元；

(3)可計算性：給定P，Q∈Gq，存在一種有效的算法計算

。3)WeilDiffie-Hellman(WDH)假設(shè)

在雙線性群中，BDHP問題是指P，aP，bP，cP∈G1，計算W=e(P，P)abc。在現(xiàn)有條件下，不存在多項式算法解決BDHP問題。

Jouxt和Nguyen指出［12］，在群Gq中，CDHP問題是困難的，而DDH(DecisionalDiffie-Hellman)問題容易解決。因為給定P，aP，bP，cP∈Gq，易知

從而修正后的Weil對提供了一種簡單的方法來驗證Diffie-Hellman向量，所以，不能利用DDH問題在群Gq上構(gòu)建公鑰密碼體制，而必須依賴于以下的CDH假設(shè)的變體，即WDH(WeilDiffie-Hellman)假設(shè)。

WDH假設(shè)：令