橢圓曲線、雙線性對(duì)與群簽名

9.1橢圓曲線★橢圓曲線并非橢圓，之所以稱為橢圓曲線是因?yàn)樗那€方程與計(jì)算橢圓周長(zhǎng)的方程類似。在數(shù)學(xué)上，橢圓曲線的曲線方程是以下形式的三次方程：

y2=x3+ax+b

因?yàn)椋?a/3)3+(b/2)2=(4a3+27b2)/108是方程x3+ax+b＝0的判別式，當(dāng)4a3+27b2

＝0時(shí)方程有重根，設(shè)為x0，則點(diǎn)Q0＝(x0,0)是橢圓曲線的重根即x3+ax+b＝(x-x0)3，重根使一階導(dǎo)數(shù)3x2＋a在該Q0點(diǎn)為0令F(x,y)=y2－x3－ax－b，則

F/x|Q0=F/y|Q0=0所以dy/dx=－(F/x)/(F/y)＝(3x2＋a)/2y在Q0點(diǎn)無(wú)定義，即曲線y2≡x3+ax+b在Q0點(diǎn)的切線無(wú)定義，因此點(diǎn)Q0的倍點(diǎn)運(yùn)算無(wú)定義所以要求判別式

=4a3+27b20第一頁(yè)2024/1/91第二頁(yè)，共47頁(yè)。9.1橢圓曲線★

實(shí)數(shù)域上的橢圓曲線對(duì)于固定的a和b，滿足形如方程y2=x3+ax+b

的所有點(diǎn)（x，y）集合，外加一個(gè)無(wú)窮遠(yuǎn)點(diǎn)O，其中，a、b是實(shí)數(shù),x和y在實(shí)數(shù)域上取值。

★

有限域GF(p)上的橢圓曲線對(duì)于固定的a和b，滿足形如方程y2≡x3+ax+b(modp)(a,b,x,y

GF(p),4a3+27b2(modp)≠0)的所有點(diǎn)（x，y）集合，外加一個(gè)零點(diǎn)或無(wú)窮遠(yuǎn)點(diǎn)O

，其中，a、b、x和y均在有限域GF(p)上取值，即在{0,1,2,…p-1}上取值。P是素?cái)?shù)。第二頁(yè)2024/1/92第三頁(yè)，共47頁(yè)。9.1橢圓曲線★一般來(lái)說(shuō)，Ep(a,b)由以下方式產(chǎn)生：

①對(duì)每一個(gè)x(0

x<p且x為整數(shù)），計(jì)算x3+ax+b(modp)。②在①中求得的值在模p下是否有平方根，如果沒(méi)有，則曲線上沒(méi)有與這一x相對(duì)應(yīng)的點(diǎn)；如果有，則求出兩個(gè)平方根y和-ymodp(y=0時(shí)只有一個(gè)平方根)?！镉邢抻騁F(2^m)上的橢圓曲線對(duì)于固定的a和b，滿足形如方程y2≡x3+ax+b(modp)的所有點(diǎn)（x，y）集合，外加一個(gè)零點(diǎn)或無(wú)窮遠(yuǎn)點(diǎn)O，其中，a、b、x，y

GF(2^m)GF(2^m)上的點(diǎn)是m位比特串。第三頁(yè)2024/1/93第四頁(yè)，共47頁(yè)。9.1.1橢圓曲線的加法運(yùn)算法則★Ep(a,b)上的加法定義如下：設(shè)P，Q

Ep(a,b)，則①P+O=P；②若P=(x,y)，那么(x,y)+(x,-y)=O，即(x,-y)是P的加法逆元，記為-P。顯然任一點(diǎn)P和其逆元-P都是Ep(a,b)中的點(diǎn)，如P=(1,11)和-P=(1,-11)=(1,12)

E23(1,4)③設(shè)P=(x1,y1)，Q=(x2,y2)，P≠-Q，則P+Q=(x3,y3)由以下確定：

x3≡λ2－x1－x2(modp)y3≡λ(x1－x3)－y1(modp)其中λ＝

切線，倍乘第四頁(yè)2024/1/94第五頁(yè)，共47頁(yè)。9.1.1橢圓曲線的加法運(yùn)算法則★兩相異點(diǎn)相加：P,Q為橢圓曲線上相異兩點(diǎn)，有P+Q=R，點(diǎn)R是經(jīng)過(guò)P、Q兩點(diǎn)的直線與曲線相交點(diǎn)的唯一負(fù)點(diǎn)（逆元）?！锉冻诉\(yùn)算：P的倍點(diǎn)2P是經(jīng)過(guò)點(diǎn)P的切線與橢圓曲線相交點(diǎn)的負(fù)點(diǎn)（逆元）。若存在最小正整數(shù)n使nP=0成立，則點(diǎn)P的階(周期)為n。★倍乘運(yùn)算仍定義為重復(fù)加法，如4P=P+P+P+P★Ep(a,b)是一個(gè)Abel群對(duì)一般的Ep(a,b)，其上的加法運(yùn)算是封閉的，滿足交換律、結(jié)合律，其上的加法逆元運(yùn)算也是封閉的，有單位元O，所以Ep(a,b)是一個(gè)Abel群。第五頁(yè)2024/1/95第六頁(yè)，共47頁(yè)。9.1.2橢圓曲線的應(yīng)用

★

橢圓曲線群中的離散對(duì)數(shù)問(wèn)題是指已知群中的P和Q，求解方程：

kP=Q中k值的問(wèn)題。由k和P易求Q，但由P、Q求k則是困難的，這就是橢圓曲線上的離散對(duì)數(shù)問(wèn)題，可應(yīng)用于公鑰密碼體制。

★例：對(duì)基于GF(23)的橢圓群y2＝x3+9x+17(mod23)，求Q=(4，5)對(duì)于P=(16，5)的離散對(duì)數(shù)。

P＝(16，5)，2P=(20，20)，3P＝(14，14),4P=(19，20)，5P＝(13，10)，6P＝(7，3)，

7P＝(8，7)，8P＝(12，17)，9P＝(4，5)因此k關(guān)于Q的離散對(duì)數(shù)是9，點(diǎn)P稱為基點(diǎn)。

第六頁(yè)2024/1/96第七頁(yè)，共47頁(yè)。明文到橢圓曲線上的嵌入★使用橢圓曲線構(gòu)造密碼體制前，需將明文嵌入到橢圓曲線上，作為橢圓曲線上的點(diǎn)。設(shè)明文消息為m，令k為一個(gè)大整數(shù)，滿足(m+1)k<p，如下計(jì)算一系列x：x＝{mk+j,j=0,1,2,…k-1}，直到是x3+ax+b(modp)是平方剩余，即得到橢圓曲線上的點(diǎn)(x,)。因?yàn)樵?到p的整數(shù)中，有一半是模p的平方剩余，一半是模p的非平方剩余。所以k次找到x，使得x3+ax+b(modp)是平方根的概率不小于1－1/2k。反之，從橢圓曲線上點(diǎn)(x,y)得到明文消息m，只須求m＝

x/k

第七頁(yè)2024/1/97第八頁(yè)，共47頁(yè)。橢圓曲線上的密碼★利用橢圓曲線實(shí)現(xiàn)ElGamal密碼體制首先選取一條橢圓曲線，并得Ep(a,b)，將明文消息m通過(guò)編碼嵌入到曲線上點(diǎn)Pm，再對(duì)點(diǎn)Pm做加密變換。取Ep(a,b)的一個(gè)生成元G，G的階為素?cái)?shù)n，Ep(a,b)、G和n作為公開(kāi)參數(shù)。用戶A在[1,n-1]上選隨機(jī)整數(shù)kA作為私鑰，并以PA=kAG作為公鑰任一用戶B若想向A發(fā)送消息Pm，可在[1,n-1]選取一隨機(jī)正整數(shù)k，產(chǎn)生以下點(diǎn)對(duì)作為密文：Cm={kG，Pm+kPA}A解密時(shí)，以密文點(diǎn)對(duì)中的第二個(gè)點(diǎn)減去用自己的秘密鑰與第一個(gè)點(diǎn)倍乘，即

(Pm+kPA)－kAkG=Pm+k(kAG)－kAkG=Pm攻擊者若想由Cm得到Pm，就必須知道k。而要得到k，只有通過(guò)橢圓曲線上的兩個(gè)已知點(diǎn)G和kG，這意味著必須求橢圓曲線上的離散對(duì)數(shù)，因此不可行。第八頁(yè)2024/1/98第九頁(yè)，共47頁(yè)。橢圓曲線上的密碼★利用橢圓曲線實(shí)現(xiàn)Diffie-Hellman密鑰交換第1步：選取一個(gè)基域GF(p)和兩個(gè)參數(shù)a、b，則得橢圓曲線上的點(diǎn)及無(wú)窮遠(yuǎn)點(diǎn)構(gòu)成Abel群Ep(a,b)。第2步:取Ep(a,b)的一個(gè)生成元G＝(x1,y1)，G的階是素?cái)?shù)n。Ep(a,b),G,n作為公開(kāi)參數(shù)。第3步:用戶A和B之間的密鑰交換如下進(jìn)行：①A隨機(jī)選整數(shù)kA<n，保密kA，計(jì)算PA=kAG產(chǎn)生Ep(a,b)上的一點(diǎn)發(fā)給B②B類似地選取秘密的kB并計(jì)算PB發(fā)給A③A、B分別由K=kAPB和K=kBPA產(chǎn)生出雙方共享的秘密鑰

事實(shí)上K=kAPB=kA(kBG)=kB(kAG)=kBPA攻擊者若想獲取K，則必須由PA和G求出kA，或由PB和G求出kB，即需要求橢圓曲線上的離散對(duì)數(shù)，因此是不可行的。如果將這一密鑰用作傳統(tǒng)密碼中的會(huì)話密鑰，可簡(jiǎn)單地取點(diǎn)坐標(biāo)中的一個(gè)，如取x坐標(biāo)，或取x坐標(biāo)的某一簡(jiǎn)單函數(shù)。第九頁(yè)2024/1/99第十頁(yè)，共47頁(yè)。橢圓曲線密碼體制的優(yōu)點(diǎn)★與基于有限域上離散對(duì)數(shù)問(wèn)題的公鑰體制相比，橢圓曲線密碼體制有如下優(yōu)點(diǎn):(1)安全性高攻擊有限域上的離散對(duì)數(shù)問(wèn)題可以用指數(shù)積分法對(duì)橢圓曲線上的離散對(duì)數(shù)問(wèn)題并不有效。目前攻擊橢圓曲線上的離散對(duì)數(shù)問(wèn)題的方法只有適合攻擊任何循環(huán)群上離散對(duì)數(shù)問(wèn)題的大步小步法，其運(yùn)算復(fù)雜度高。

(2)密鑰量小在實(shí)現(xiàn)相同安全性能條件下，橢圓曲線密碼體制所需的密鑰量遠(yuǎn)比基于有限域上的離散對(duì)數(shù)問(wèn)題的公鑰體制的密鑰量小。第十頁(yè)2024/1/910第十一頁(yè)，共47頁(yè)。橢圓曲線密碼體制的優(yōu)點(diǎn)(3)靈活性好有限域GF(P)一定的情況下，其上的循環(huán)群是確定的GF(P)上的橢圓曲線可以通過(guò)改變曲線參數(shù)，得到不同的曲線，形成不同的循環(huán)群?？稍诤蚏SA/DSA體制同樣安全性能的前提下大大縮短密鑰長(zhǎng)度(目前160比特足以保證安全性)，因而在密碼領(lǐng)域有著廣闊的應(yīng)用前景下表給出了橢圓曲線密碼體制和RSA/DSA體制所需的密鑰的長(zhǎng)度第十一頁(yè)2024/1/911第十二頁(yè)，共47頁(yè)。9.2雙線性對(duì)

Menezes、Okamota和Vanstones在1983年，在有限域上定義了一種特殊的橢圓曲線,即超奇異曲線，并指出了這些橢圓曲線上利用橢圓曲線離散對(duì)數(shù)問(wèn)題構(gòu)建密碼體制較標(biāo)準(zhǔn)的離散對(duì)數(shù)問(wèn)題可使用較小的有限域的優(yōu)勢(shì)不存在了。

但Joux首先利用橢圓曲線中的Weil配對(duì)構(gòu)造了一個(gè)一輪三方密鑰交換協(xié)議，隨后Boneh和Franklin用Weil配對(duì)構(gòu)造了一個(gè)基于身份的加密體制。從此以Weil配對(duì)技術(shù)為基礎(chǔ)的各種密碼學(xué)算法層出不窮，成為近年來(lái)的一個(gè)研究熱點(diǎn)。第十二頁(yè)2024/1/912第十三頁(yè)，共47頁(yè)。9.2.1雙線性映射

第十三頁(yè)2024/1/913第十四頁(yè)，共47頁(yè)。9.2.2雙線性對(duì)在密碼學(xué)中的應(yīng)用在數(shù)字化的信息社會(huì)里，數(shù)字簽名代替了傳統(tǒng)的手寫(xiě)簽名和印簽，是手寫(xiě)簽名的電子模擬。在使用數(shù)字簽名的過(guò)程中，仍然會(huì)遇到需要將簽名權(quán)委托給其他人的情況。比如，某公司的經(jīng)理由于業(yè)務(wù)需要到外地出差。在他出差期間，很可能有人給他發(fā)來(lái)電子郵件，其中有些郵件需要及時(shí)回復(fù)。然而，他出差的地方很偏僻，沒(méi)有覆蓋互聯(lián)網(wǎng)，因此，該經(jīng)理不得不委托他的秘書(shū)代表他處理這些電子郵件，包括代表他在回復(fù)這些電子郵件時(shí)在回信上生成數(shù)字簽名。

那么如何以安全、可行、有效的方法實(shí)現(xiàn)數(shù)字簽名權(quán)利的委托？第十四頁(yè)2024/1/914第十五頁(yè)，共47頁(yè)。9.2.2雙線性對(duì)在密碼學(xué)中的應(yīng)用1996年，Mambo、Usuda和Okamoto首先提出代理簽名的概念。所謂代理簽名是指在一個(gè)代理簽名方案中，代理簽名人代表原始簽名人生成的有效的簽名。由初始化過(guò)程，數(shù)字簽名權(quán)力的委托過(guò)程，代理簽名的生成過(guò)程和代理簽名的驗(yàn)證過(guò)程四部分組成。

1982年，Chaum首次提出了盲簽名的概念。所謂盲簽名，就是先將要隱藏的文件放進(jìn)信封里，當(dāng)文件在一個(gè)信封中時(shí)，任何人都不能讀它。對(duì)文件簽名就是通過(guò)在信封中放一張復(fù)寫(xiě)紙，當(dāng)簽名者在信封上簽名時(shí)，他的簽名便會(huì)透過(guò)復(fù)寫(xiě)紙簽到文件上。盲簽名是一種特殊的數(shù)字簽名，它與通常的數(shù)字簽名的不同之處在于，簽名者并不知道他所要簽發(fā)文件的具體內(nèi)容。正是這一點(diǎn)，使得盲簽名這種技術(shù)可廣泛應(yīng)用于許多領(lǐng)域，如電子投票系統(tǒng)和電子現(xiàn)金系統(tǒng)等。第十五頁(yè)2024/1/915第十六頁(yè)，共47頁(yè)。基于雙線性對(duì)的代理簽名方案

第十六頁(yè)2024/1/916第十七頁(yè)，共47頁(yè)?；陔p線性對(duì)的代理簽名方案

第十七頁(yè)2024/1/917第十八頁(yè)，共47頁(yè)?；陔p線性對(duì)的代理簽名方案

第十八頁(yè)2024/1/918第十九頁(yè)，共47頁(yè)。基于雙線性對(duì)的代理盲簽名方案

第十九頁(yè)2024/1/919第二十頁(yè)，共47頁(yè)。基于雙線性對(duì)的代理盲簽名方案

第二十頁(yè)2024/1/920第二十一頁(yè)，共47頁(yè)?；陔p線性對(duì)的代理盲簽名方案

第二十一頁(yè)2024/1/921第二十二頁(yè)，共47頁(yè)。9.3群簽名方案

群簽名（groupsignature）的概念由Chaum和Heyst于1991年首次提出。在群簽名方案中,群體中的任意一個(gè)成員可以以匿名的方式代表整個(gè)群體對(duì)消息進(jìn)行簽名。與其它數(shù)字簽名一樣,群簽名是可以公開(kāi)驗(yàn)證的,而且可以只用單個(gè)群公鑰來(lái)驗(yàn)證。群簽名與一般的數(shù)字簽名的最大區(qū)別是，一般的數(shù)字簽名只涉及簽名者和用戶，而群簽名還要涉及一個(gè)群管理員且所產(chǎn)生的簽名代表著一個(gè)群體。群簽名方案由群、群成員、群管理員和簽名接受者（或驗(yàn)證者）組成。群簽名方案的特點(diǎn)如下：只有群成員才能為消息簽名，并產(chǎn)生群簽名；簽名接收者可以驗(yàn)證簽名的有效性，但是不能識(shí)別簽名者的身份；一旦發(fā)生爭(zhēng)議，群管理員（或群中成員合謀）可以識(shí)別簽名者的身份。第二十二頁(yè)2024/1/922第二十三頁(yè)，共47頁(yè)。9.3群簽名方案

群簽名方案是一個(gè)包含以下過(guò)程的數(shù)字簽名方案：初始化過(guò)程（創(chuàng)建過(guò)程）。系統(tǒng)參數(shù)選取，包括產(chǎn)生群公鑰和群私鑰的算法。成員加入過(guò)程。制定用戶加入到群中成為正式成員，用戶與管理員之間的交互式協(xié)議，執(zhí)行該協(xié)議，產(chǎn)生群成員的私鑰和成員證書(shū)，并使群管理員掌握群成員的秘密的成員管理秘鑰。簽名過(guò)程。輸入待簽名的信息和成員私鑰，產(chǎn)生群簽名的簽名算法。驗(yàn)證過(guò)程。驗(yàn)證群簽名是否有效的驗(yàn)證算法。打開(kāi)過(guò)程。輸入群簽名和群私鑰，產(chǎn)生識(shí)別簽名者身份的打開(kāi)算法。圖9-3群簽名方案第二十三頁(yè)2024/1/923第二十四頁(yè)，共47頁(yè)。9.3群簽名方案群簽名方案的安全性要求：匿名性。給定一個(gè)群簽名后，對(duì)除了唯一的群管理員之外的任何人來(lái)說(shuō)，確定簽名人的身份在計(jì)算上都是不可行的。不可偽造性。只有群成員才能產(chǎn)生有效的群簽名，其他任何人都不可能偽造有效的群簽名?？筛櫺浴?/p>

群管理員在必要時(shí)可以打開(kāi)群簽名以確定簽名人的身份，而且群成員不能阻止一個(gè)合法群簽名的打開(kāi)?？购现\攻擊。

即使群成員串通在一起也不能產(chǎn)生一個(gè)合法的不能被跟蹤的群簽名。不關(guān)聯(lián)性。

在不打開(kāi)群簽名的情況下，確定兩個(gè)不同的群簽名是否為同一個(gè)群成員所簽在計(jì)算上是困難的。群簽名方案的效率：一個(gè)群簽名方案的效率依賴于以下參數(shù):

1)群公鑰的大??；2)群簽名的長(zhǎng)度；3)群簽名算法和驗(yàn)證算法的效率；4)創(chuàng)建，加入以及打開(kāi)過(guò)程的效率。

第二十四頁(yè)2024/1/924第二十五頁(yè)，共47頁(yè)。9.3.1基于離散對(duì)數(shù)的群簽名方案

第二十五頁(yè)2024/1/925第二十六頁(yè)，共47頁(yè)。9.3.1基于離散對(duì)數(shù)的群簽名方案

安全性分析（1）在群中成員誠(chéng)實(shí)時(shí)，雖然可以識(shí)別簽名者，但當(dāng)成員偽造或合謀偽造時(shí)，仍能生成有效的簽名，因此不符合不可偽造性和抗合謀攻擊性。（2）GA可以將群成員的有效群簽名轉(zhuǎn)化為群中其他成員的有效群簽名，因此，不符合不可偽造性。（3）GA在簽名過(guò)程中可以冒充群成員A偽造任意消息的有效群簽名。（4）GA在打開(kāi)過(guò)程中偽造，無(wú)法驗(yàn)證群成員A進(jìn)行了群簽名，不滿足可追蹤性。第二十六頁(yè)2024/1/926第二十七頁(yè)，共47頁(yè)。9.3.1基于離散對(duì)數(shù)的群簽名方案

第二十七頁(yè)2024/1/927第二十八頁(yè)，共47頁(yè)。9.3.1基于離散對(duì)數(shù)的群簽名方案

第二十八頁(yè)2024/1/928第二十九頁(yè)，共47頁(yè)。9.3.1基于離散對(duì)數(shù)的群簽名方案

第二十九頁(yè)2024/1/929第三十頁(yè)，共47頁(yè)。9.3.1基于離散對(duì)數(shù)的群簽名方案

第三十頁(yè)2024/1/930第三十一頁(yè)，共47頁(yè)。9.3.1基于離散對(duì)數(shù)的群簽名方案

第三十一頁(yè)2024/1/931第三十二頁(yè)，共47頁(yè)。9.3.1基于離散對(duì)數(shù)的群簽名方案

第三十二