公鑰密碼(中Elgamal)課件

密碼學(xué)

第十講公鑰密碼

——ELGamalwzy@武漢大學(xué)2第十講公鑰密碼單向陷門函數(shù)ELGamal密碼橢圓曲線密碼橢圓曲線橢圓曲線密碼單向函數(shù)是滿足下列性質(zhì)的函數(shù)：每個(gè)函數(shù)值都存在唯一的逆，并且計(jì)算函數(shù)值是容易的但求逆卻是不可行的：

已知X，求Y=f(X)容易

已知Y，求X=f-1(Y)不可行單向函數(shù)單向函數(shù)是求逆困難的函數(shù)，而單向陷門函數(shù)(Trapdoorone-wayfunction)，是在不知陷門信息下求逆困難的函數(shù)，當(dāng)知道陷門信息后，求逆是易于實(shí)現(xiàn)的。單向限門函數(shù)是一族可逆函數(shù)fk，滿足1.y=fk(x)易于計(jì)算（當(dāng)k和x已知）2.x=fk-1(y)易于計(jì)算（當(dāng)k和y已知）3.x=fk-1(y)計(jì)算上不可行（y已知但k未知）研究公鑰密碼算法就是找出合適的單向限門函數(shù)單向陷門函數(shù)背包問(wèn)題(Knapsackproblem)已被攻破大整數(shù)分解問(wèn)題(TheIntegerFactorizationProblem)RSA密碼離散對(duì)數(shù)問(wèn)題有限域的乘法群上的離散對(duì)數(shù)問(wèn)題(TheDiscreteLogarithmProblem)——ElGamal密碼定義在有限域的橢圓曲線上的離散對(duì)數(shù)問(wèn)題(TheEllipticCurveDiscreteLogarithmProblem)——ECC密碼公鑰密碼基于的數(shù)學(xué)難題理論上：不能證明單向函數(shù)一定存在；實(shí)際上：只要函數(shù)的單向性足夠工程應(yīng)用就行；

實(shí)際上已找到的單向性足夠的函數(shù)有：

①合數(shù)的因子分解問(wèn)題

大素?cái)?shù)的乘積容易計(jì)算（pqn），而大合數(shù)的因子分解困難(npq)。②有限域上的離散對(duì)數(shù)問(wèn)題有限域上大素?cái)?shù)的冪乘容易計(jì)算（ab

c），而對(duì)數(shù)計(jì)算困難(logacb)。單向函數(shù)研究現(xiàn)狀合數(shù)的因子分解問(wèn)題單向函數(shù)研究現(xiàn)狀有限域上的離散對(duì)數(shù)問(wèn)題例如GF(19)中模19的整數(shù)冪單向函數(shù)研究現(xiàn)狀1、基本情況：ELGamal密碼是除了RSA密碼之外最有代表性的公開(kāi)密鑰密碼。ELGamal密碼建立在離散對(duì)數(shù)的困難性之上。RSA密碼建立在大合數(shù)分解的困難性之上。ELGamal公鑰密碼的基本情況2、離散對(duì)數(shù)問(wèn)題：①設(shè)p為素?cái)?shù)，則模p的剩余構(gòu)成域：

Fp={0,1,2,…,p-1}Fp的非零元構(gòu)成循環(huán)群Fp*Fp*={α，α2，α3，，αp-1}，則稱α為Fp*的生成元或模p的本原元(根)。②設(shè)p為素?cái)?shù)，α為模p的本原元，α的冪乘運(yùn)算為

Y=αXmodp，1≤X≤p-1,則稱X為以α為底的模p的對(duì)數(shù)。離散對(duì)數(shù)問(wèn)題有限域上的離散對(duì)數(shù)問(wèn)題例如GF(19)中模19的整數(shù)冪離散對(duì)數(shù)問(wèn)題12離散對(duì)數(shù)問(wèn)題2、離散對(duì)數(shù)問(wèn)題：求解對(duì)數(shù)X的運(yùn)算為

X=logαY，1≤X≤p-1由于上述運(yùn)算是定義在模p有限域上的，所以稱為離散對(duì)數(shù)運(yùn)算。③從X計(jì)算Y是容易的?？墒菑腨計(jì)算X就困難得多，利用目前最好的算法O(exp((lnp)1/3ln(lnp)2/3)，對(duì)于安全選擇的p將至少需用p1/2次以上的運(yùn)算，只要p足夠大，求解離散對(duì)數(shù)問(wèn)題是相當(dāng)困難的。離散對(duì)數(shù)問(wèn)題（備注）算法復(fù)雜度：例如：離散對(duì)數(shù)問(wèn)題15離散對(duì)數(shù)問(wèn)題(DiscreteLogarithmProblem)，簡(jiǎn)稱DLPGivenα,y,p,tofindxs.t.αx=y(modp)e.g.α=2

,y=3

,p=23,x=？α=2

,y=97206

,p=136943,x=？離散對(duì)數(shù)問(wèn)題16離散對(duì)數(shù)問(wèn)題(DiscreteLogarithmProblem)，簡(jiǎn)稱DLPGivenα,y,p,tofindxs.t.αx=y(modp)e.g.α=2

,y=3

,p=23,x=8α=2

,y=97206

,p=136943,x=70469離散對(duì)數(shù)問(wèn)題171985年，ElGamal在Differ-Hellman密鑰交換協(xié)議基礎(chǔ)上改進(jìn)而來(lái)依賴數(shù)學(xué)難題：DLP(DiscreteLogarithmProblem)ELGamal公鑰密碼18算法生成密鑰對(duì)GenKeyPair加密Encrypt解密DecryptELGamal公鑰密碼19準(zhǔn)備階段：隨機(jī)地選擇一個(gè)大素?cái)?shù)p，且要求p-1有大素?cái)?shù)因子。再選擇一個(gè)模p的本原元α。將p和α公開(kāi)。⑴密鑰生成用戶隨機(jī)地選擇一個(gè)整數(shù)d作為自己的秘密的解密鑰，2≤d≤p-2。計(jì)算y=αd

modp，取y為自己的公開(kāi)的加密鑰。由公開(kāi)鑰y

計(jì)算秘密鑰d，必須求解離散對(duì)數(shù)，而這是極困難的。ELGamal公鑰密碼20算法GenKeyPair模塊Givensystemparametersα,p(21023<p<21024

)Randomgeneratedy=αd(modp)PublicKey:y

PrivateKey:dELGamal公鑰密碼21⑵加密將明文消息M（0≤M≤p-1)加密成密文的過(guò)程如下：隨機(jī)地選取一個(gè)整數(shù)k，2≤k≤p-2。計(jì)算： U＝y(tǒng)kmodp； C1＝αkmodp；

C2＝UMmodp；取C＝（C1

，C2）作為的密文。ELGamal公鑰密碼22算法Encrypt模塊Givensystemparametersα,pGivenPublicKey:yPlainText:MRandomchoosekCipherText:C

=<αk(modp),M*yk(modp)>ELGamal公鑰密碼23⑶解密將密文（C1

，C2）解密的過(guò)程如下：計(jì)算V＝C1dmodp；計(jì)算M＝C2

V-1modp。ELGamal公鑰密碼24算法Decrypt模塊Givensystemparametersα,pGivenPrivateKey:xCipherText:C=<c1,c2>PlainText:M

=c2/

c1d(modp)ELGamal公鑰密碼25算法可還原性證明

C2

V-1modp ＝(UM)V-1modp

＝UM（C1d）-1modp

＝UM（（αk）d）-1modp

＝UM（（αd）k）-1modp

＝UM（（y）k）-1modp

＝UM（U）-1modp

＝MmodpELGamal公鑰密碼26安全性直接破解ElGamal加密機(jī)制的唯一方法是獲取yk，（如果存在其他方法也能破解ElGamal加密機(jī)制得到明文，則等同于獲取了yk

）ELGamal公鑰密碼27安全性獲取yk的直接攻擊方法攻擊1——由于y是公開(kāi)的，計(jì)算yk需要k，需解DLP：k=logac1

攻擊2——由于c1是公開(kāi)的，計(jì)算yk=c1d需要d，需解DLP：d=logay由于DLP問(wèn)題是難解的，所以上述兩種方法都無(wú)效ELGamal公鑰密碼28安全性針對(duì)k重復(fù)使用的攻擊方法攻擊1（假設(shè)攻擊者掌握k）如果k不是一次性的，時(shí)間長(zhǎng)了就可能被攻擊者獲得。又因y是公開(kāi)密鑰，攻擊者自然知道。于是攻擊者就可以根據(jù)U＝y(tǒng)kmodp計(jì)算出U，進(jìn)而利用Euclid算法求出U－1。又因?yàn)楣粽呖梢垣@得密文C2，于是可根據(jù)式C2＝UMmodp通過(guò)計(jì)算U－1C2得到明文M。攻擊2設(shè)用同一個(gè)k加密兩個(gè)不同的明文M和M’，相應(yīng)的密文為（C1

，C2）和（C1’，C2’）。因?yàn)閥k

不變，所以C2∕C2’＝M∕M’，如果攻擊者知道M，則很容易求出M’。

ELGamal公鑰密碼29安全性其它攻擊方法假如兩個(gè)明文采用相同的隨機(jī)數(shù)k加密，則通過(guò)其密文可以容易推導(dǎo)出兩個(gè)明文的相互關(guān)系。所以要保證加密者所使用的隨機(jī)數(shù)發(fā)生器的安全性如果p不夠大，則DLP問(wèn)題將因?yàn)槊荑€空間太小而變得容易解。所以，要對(duì)p進(jìn)行認(rèn)真的選擇加密者在使用接收者的公鑰時(shí)，應(yīng)設(shè)法確認(rèn)該公鑰是對(duì)應(yīng)著該接收者，否則可能造成應(yīng)該接收的人無(wú)法正常接收，而其他人可以解密ELGamal公鑰密碼30安全性由于ELGamal密碼的安全性建立在GF（p）離散對(duì)數(shù)的困難性之上，而目前尚無(wú)求解GF（p）離散對(duì)數(shù)的有效算法，所以在p足夠大時(shí)ELGamal密碼是安全的。為了安全p應(yīng)為150位以上的十進(jìn)制數(shù)，而且p-1應(yīng)有大素因子。為了安全加密和簽名所使用的k必須是一次性的。ELGamal公鑰密碼31ELGamal密碼的應(yīng)用由于ELGamal密碼的安全性得到世界公認(rèn)，所以得到廣泛的應(yīng)用。著名的美國(guó)數(shù)字簽名標(biāo)準(zhǔn)DSS，采用了ELGamal密碼的一種變形。為了適應(yīng)不同的應(yīng)用，人們?cè)趹?yīng)用中總結(jié)出18種不同的ELGamal密碼的變形。（p173-175）ELGamal公鑰密碼32ElGamal與RSA比較ELGamal公鑰密碼33橢圓曲線密碼的一般情況受ELGamal密碼啟發(fā)，在其它離散對(duì)數(shù)問(wèn)題難解的群中，同樣可以構(gòu)成ELGamal密碼。于是人們開(kāi)始尋找其它離散問(wèn)題難解的群。研究發(fā)現(xiàn)，有限域GF（p）上的橢圓曲線的解點(diǎn)構(gòu)成交換群，而且離散對(duì)數(shù)問(wèn)題是難解的。于是可在此群上建立ELGamal密碼，并稱為橢圓曲線密碼。橢圓曲線密碼34橢圓曲線密碼的一般情況橢圓曲線密碼已成為除RSA密碼之外呼聲最高的公鑰密碼之一。它密鑰短、簽名短，軟件實(shí)現(xiàn)規(guī)模小、硬件實(shí)現(xiàn)電路省電。普遍認(rèn)為，160位長(zhǎng)的橢圓曲線密碼的安全性相當(dāng)于1024位的RSA密碼，而且運(yùn)算速度也較快。橢圓曲線密碼35RSA和ECC的比較RSA和ECC安全模長(zhǎng)的比較橢圓曲線密碼361985年，NealKoblitz和VictorMiller分別獨(dú)立地提出了橢圓曲線密碼體制多數(shù)公鑰密碼(RSA,DH)使用非常大的數(shù)或多項(xiàng)式，給密鑰和信息的存儲(chǔ)和處理帶來(lái)很大的運(yùn)算量橢圓曲線是一個(gè)代替，可以用更小的尺寸得到同樣的安全性ANSI、IEEE、ISO和NIST都制定了ECC標(biāo)準(zhǔn)草案橢圓曲線密碼37橢圓曲線密碼的一般情況一些國(guó)際標(biāo)準(zhǔn)化組織已把橢圓曲線密碼作為新的信息安全標(biāo)準(zhǔn)。如，IEEEP1363/D4，ANSIF9.62，ANSIF9.63等標(biāo)準(zhǔn)，分別規(guī)范了橢圓曲線密碼在Internet協(xié)議安全、電子商務(wù)、Web服務(wù)器、空間通信、移動(dòng)通信、智能卡等方面的應(yīng)用。橢圓曲線密碼38橢圓曲線橢圓曲線不是橢圓！費(fèi)馬大定理：當(dāng)n>2且xyz≠0時(shí)， xn+yn=zn沒(méi)有正整數(shù)解n=2時(shí)，上式有無(wú)窮組整數(shù)解，例如勾股定理定義“同余數(shù)”：正整數(shù)n為“同余數(shù)”(CongruentNumber)，如果它是一個(gè)有理直角三角形的面積。如5、6、7都是“同余數(shù)”橢圓曲線密碼39橢圓曲線n為“同余數(shù)”的條件是下列方程組有有理解：a2+b2=c2

（1）ab/2=n （2）由(1)/4±(2)得:令，則求“同余數(shù)”的問(wèn)題轉(zhuǎn)化為：尋找有理數(shù)x，使得等差數(shù)列x-n，x，x+n都是平方數(shù)。那么也是平方數(shù)，記為

橢圓曲線密碼40橢圓曲線“勾股定理”->“同余數(shù)”->橢圓曲線橢圓曲線一般形式（Weierstrass方程）當(dāng)特征為2時(shí)，可化簡(jiǎn)為當(dāng)特征大于3時(shí)，可化簡(jiǎn)為橢圓曲線密碼41橢圓曲線設(shè)p是大于3的素?cái)?shù)，且4a3+27b2≠0modp，稱 y2=x3+ax+b，a,b∈GF(p)為GF（p）上的橢圓曲線。由橢圓曲線可得到一個(gè)同余方程： y2=x3+ax+bmodp其解為一個(gè)二元組<x,y>，x,y∈GF(p)，將此二元組描畫(huà)到橢圓曲線上便為一個(gè)點(diǎn)，于是又稱其為解點(diǎn)。橢圓曲線密碼復(fù)習(xí)：代數(shù)結(jié)構(gòu)橢圓曲線密碼43橢圓曲線交換群封閉性：結(jié)合律：?jiǎn)挝辉耗嬖航粨Q律：橢圓曲線密碼44橢圓曲線橢圓曲線密碼45橢圓曲線為了利用解點(diǎn)構(gòu)成交換群，需要引進(jìn)一個(gè)O元素，并定義如下的加法運(yùn)算：

①定義單位元引進(jìn)一個(gè)無(wú)窮點(diǎn)O（∞，∞），簡(jiǎn)記為0，作為0元素。

O（∞，∞）＋O（∞，∞）＝0＋0＝0。并定義對(duì)于所有的解點(diǎn)P（x

，y），

P（x

，y）+O＝O+P（x

，y）＝P（x

，y）。橢圓曲線密碼46橢圓曲線定義如下的加法運(yùn)算：

②定義逆元

設(shè)P（x1

，y1）和Q（x2

，y2）是解點(diǎn)，

如果x1=x2

且y1=-y2，則

P（x1

，y1）＋Q（x2

，y2）＝0。這說(shuō)明任何解點(diǎn)R（x，y）的逆就是R（x，-y）。橢圓曲線密碼47橢圓曲線定義如下的加法運(yùn)算：

③定義加法設(shè)P(x1，y1)≠Q(mào)(x2，y2)，且P和Q不互逆，則

P（x1

，y1）＋Q（x2

，y2）＝R（x3

，y3）。其中

x3=λ2-x1-x2，

y3=λ(x1–x3)-y1，

λ=（y2-y1）/(x2-x1）。橢圓曲線密碼48橢圓曲線定義如下的加法運(yùn)算：

③定義加法當(dāng)P≠-P時(shí)

P（x1

，y1）＋P（x1

，y1）＝2P（x1

，y1）＝R（x3

，y3）。其中

x3=λ2-2x1，

y3=λ(x1–x3)-y1，

λ=（3x12+a）/（2y1）。橢圓曲線密碼49橢圓曲線定義如下的加法運(yùn)算：作集合E={全體解點(diǎn)，無(wú)窮點(diǎn)O}。容易驗(yàn)證，如上定義的集合E和加法運(yùn)算構(gòu)成加法交換群。復(fù)習(xí)：群的定義G是一個(gè)非空集，定義了一種運(yùn)算，且運(yùn)算是自封閉的；運(yùn)算滿足結(jié)合律；G中有單位元；G中的元素都有逆元；橢圓曲線密碼50橢圓曲線解點(diǎn)加法運(yùn)算的幾何意義：設(shè)P（x1

，y1）和Q（x2

，y2）是橢圓曲線的兩個(gè)點(diǎn)，則連接P（x1

，y1）和Q（x2

，y2）的直線與橢圓曲線的另一交點(diǎn)關(guān)于橫軸的對(duì)稱點(diǎn)即為P（x1

，y1）+Q（x2

，y2）點(diǎn)。

橢圓曲線密碼xy0PQP+Q橢圓曲線解點(diǎn)加法運(yùn)算的幾何意義：

橢圓曲線密碼52舉例：取p=11，橢圓曲線y2=x3+x+6。由于p較小，使GF(p)也較小，故可以利用窮舉的方法根據(jù)y2=x3+x+6mod11求出所有解點(diǎn)。復(fù)習(xí)：平方剩余設(shè)p為素?cái)?shù)，如果存在一個(gè)正整數(shù)x，使得 x2=amodp,

則稱a是模p的平方剩余。

橢圓曲線密碼53舉例：橢圓曲線y2=x3+x+6

橢圓曲線密碼

xx3+x+6mod11是否模11平方剩余y06No18No25Yes4,733Yes5,648No54Yes2,968No74Yes2,989Yes3,897No104Yes2,9橢圓曲線密碼55舉例：根據(jù)表可知全部解點(diǎn)集為：(2，4),(2，7),(3，5),(3，6),(5，2),(5，9),(7，2),(7，9),(8，3),(8，8),(10，2),(10，9)。再加上無(wú)窮遠(yuǎn)點(diǎn)O，共13的點(diǎn)構(gòu)成一個(gè)加法交換群。由于群的元素個(gè)數(shù)為13，而13為素?cái)?shù)，所以此群是循環(huán)群，而且任何一個(gè)非O元素都是生成元。

橢圓曲線密碼56舉例：由于是加法群，n個(gè)元素G相加，G+G+...+G＝nG。我們?nèi)＝（2，7）為生成元，具體計(jì)算加法表如下：

2G=（2，7）+（2，7）=（5，2）因?yàn)棣?（3×22+1）（2×7）-1mod11=2×3-1mod11=2×4mod11=8。

于是， x3=82-2-2mod11=5， y3=8（2-5）-7mod11=2。

橢圓曲線密碼

G＝（2，7），2G＝（5，2），

3G＝（8，3），4G＝（10，2），

5G＝（3，6），6G＝（7，9），

7G＝（7，2），8G＝（3，5），

9G＝（10，9），10G＝（8，8），

11G＝（5，9），12G＝（2，4）。橢圓曲線密碼

注意：同階交換群是同構(gòu)的

G＝（2，7），2G＝（5，2），

3G＝（8，3），4G＝（10，2），

5G＝（3，6），6G＝（7，9），

7G＝（7，2），8G＝（3，5），

9G＝（10，9），10G＝（8，8），

11G＝（5，9），12G＝（2，4）。橢圓曲線密碼GF(13)加法群0123456789101112橢圓曲線加法群y2=x3+x+6O1G(2,7)2G(5,2)3G(8,3)4G(10,2)5G(3,6)6G(7,9)7G(7,2)8G(3,5)9G(10,9)10G(8,8)11G(5,9)12G(2,4)59橢圓曲線“勾股定理”->“同余數(shù)”->橢圓曲線橢圓曲線一般形式（Weierstrass方程）當(dāng)特征為2時(shí)，可化簡(jiǎn)為當(dāng)特征大于3時(shí)，可化簡(jiǎn)為橢圓曲線密碼60橢圓曲線設(shè)m是正整數(shù)，且b

≠0，稱曲線 y2+xy=x3+ax2+b，a,b∈GF(2m)為GF（2m）上的橢圓曲線。和GF（p）上的橢圓曲線一樣,GF（2m）上的橢圓曲線的全體解點(diǎn)加上無(wú)窮遠(yuǎn)點(diǎn)的集合E構(gòu)成加法交換群。橢圓曲線密碼61橢圓曲線為了利用解點(diǎn)構(gòu)成交換群，需要引進(jìn)一個(gè)O元素，并定義如下的加法運(yùn)算：

①定義單位元引進(jìn)一個(gè)無(wú)窮點(diǎn)O（∞，∞），簡(jiǎn)記為0，作為0元素。

O（∞，∞）＋O（∞，∞）＝0＋0＝0。并定義對(duì)于所有的解點(diǎn)P（x

，y），

P（x

，y）+O＝O+P（x

，y）＝P（x

，y）。橢圓曲線密碼62橢圓曲線定義如下的加法運(yùn)算：

②定義逆元

設(shè)P（x1

，y1）和Q（x2

，y2）是解點(diǎn)，

如果x1=x2

且y2=x1+y1，則

P（x1

，y1）＋Q（x2

，y2）＝0。這說(shuō)明任何解點(diǎn)R（x，y）的逆是R（x，x+y）。橢圓曲線密碼63橢圓曲線定義如下的加法運(yùn)算：

③定義加法設(shè)P(x1，y1)≠Q(mào)(x2，y2)，且P和Q不互逆，則

P（x1

，y1）＋Q（x2

，y2）＝R（x3

，y3）。其中

x3=λ2+λ+x1+x2+a

，

y3=λ(x1+x3)+x3+y1，

λ=（y1+y2）/(x1+x2）。橢圓曲線密碼64橢圓曲線定義如下的加法運(yùn)算：

③定義加法當(dāng)P≠-P時(shí)

P（x1

，y1）＋P（x1

，y1）＝2P（x1

，y1）＝R（x3

，y3）。其中

橢圓曲線密碼65舉例：g(x)=x4+x+1是GF（2）上的既約多項(xiàng)式，用g(x)構(gòu)造擴(kuò)域GF（24）。GF（24）的任意元素都可用表5-5中四種形式來(lái)表示。取a=α3，b=α14，考慮GF（24）上的橢圓曲線多項(xiàng)式y(tǒng)2+xy=x3+ax2+b=x3+α3x2+α14復(fù)習(xí)：AES中S盒由多項(xiàng)式構(gòu)成GF（28）擴(kuò)域

橢圓曲線密碼通過(guò)窮舉，求出其全部解點(diǎn)如下：

橢圓曲線密碼P1=(0000，1011)P8=(0101，0000)P15=(1001，1111)P2=(0001，0000)P9=(0101，0101)P16=(1011，0010)P3=(0001，0001)P10=(0111，1011)P17=(1011，1001)P4=(0010，1101)P11=(0111，1100)P18=(1100，0000)P5=(0010，1111)P12=(1000，0001)P19=(1100，1100)P6=(0011，1100)P13=(1000，1001)P20=(1111，0100)P7=(0011，1111)P14=(1001，0110)P21=(1111，1011)通過(guò)窮舉，求出其全部解點(diǎn)如下：1P5=P5 2P5=P16 3P5=P8 4P5=P13 5P5=P106P5=P217P5=P78P5=P149P5=P210P5=P1811P5=P112P5=P1913P5=P314P5=P1515P5=P616P5=P2017P5=P1118P5=P1219P5=P920P5=P1721P5=P4

22P5=O計(jì)算結(jié)果說(shuō)明，這個(gè)群是循環(huán)群，P5是群的一個(gè)生成元。注意，并不是所有非零元素都是群的生成元，如P12=(1000，0001)的階為11。橢圓曲線密碼注意：同階交換群是同構(gòu)的例：取生成元G=P5=(0010，1111)其中生成元個(gè)數(shù)是歐拉函數(shù)φ(22)=10橢圓曲線密碼GF(22)加法群01G2G3G4G5G6G7G8G9G10G橢圓曲線加法群y2+xy=x3+α3x2+α14OP5=(0010，1111)P16=(1011，0010)P8=(0101，0000)P13=(1000，1001)P10=(0111，1011)P21=(1111，1011)P7=(0011，1111)P14=(1001，0110)P2=(0001，0000)P18=(1100，0000)GF(22)加法群11G12G13G14G15G16G17G18G19G20G21G橢圓曲線加法群y2+xy=x3+α3x+α14P1=(0000，1011)P19=(1100，1100)P3=(0001，0001)P15=(1001，1111)P6=(0011，1100)P20=(1111，0100)P11=(0111，1100)P12=(1000，0001)P9=(0101，0101)P17=(1011，1001)P4=(0010，1101)69舉例：例1：驗(yàn)證P1=(0000，1011)例2：計(jì)算點(diǎn)加P5+P19=例3：計(jì)算倍點(diǎn)2P5

橢圓曲線密碼70除了GF(p)上的橢圓曲線外還有定義在GF(2m)上的橢圓曲線。這兩種橢圓曲線都可以構(gòu)成安全的橢圓曲線密碼。在上例中，由于p較小，使GF(p)或GF(2m)也較小，故可以利用窮舉的方法求出所有解點(diǎn)。但是，對(duì)于一般情況要確切計(jì)算橢圓曲線解點(diǎn)數(shù)N的準(zhǔn)確值比較困難。N滿足以下不等式 P+1-2P1/2≤N≤P+1+2P1/2

。橢圓曲線密碼71美國(guó)信息技術(shù)研究所NIST向社會(huì)推薦了15條橢圓曲線，其中5條素域GF(p)上隨機(jī)選取的橢圓曲線，5條二進(jìn)制域GF(2m)上隨機(jī)選取的橢圓曲線，5條二進(jìn)制域GF(2m)上的Koblits橢圓曲線。例如p192=2192-264-1。令c是一個(gè)0≤c≤p2的整數(shù)。再令c=c52320+c42256+c32192+c22128+c1264+c0是c的264進(jìn)制的表示式，其中ci∈[0，264-1]。橢圓曲線密碼72例如p192=2192-264-1。2192=264+1modp2256=2128+264modp2320+=2128+264+1modp于是

c=c52128+c5264+c5+c42128+c4264+c3264+c3+c22128+c1264+c0modp因此，通過(guò)4次192位的整數(shù)c52128+c5264+c5，c42128+c4264，c3264+c3和c22128+c1264+c0相加，并重復(fù)地減p，直到結(jié)果小于p為止，便可得到cmodp。橢圓曲線密碼73算法

模p192=2192-264-1的快速取模輸入：c=(c5,c4,c3,c2,c1,c0)為264進(jìn)制整數(shù)，0≤c≤p2192；輸出：cmodp192；1.定義192位整數(shù)； s1=(c2,c1,c0)，s2=(0,c3,c3)； s3=(c4,c4,0)，s4=(c5,c5,c5)2.返回（s1+s2+s3+s4modp192）。橢圓曲線密碼74橢圓曲線密碼ELGamal密碼建立在有限域GF（p）的乘法群的離散對(duì)數(shù)問(wèn)題的困難性之上。而橢圓曲線密碼建立在橢圓曲線群的離散對(duì)數(shù)問(wèn)題的困難性之上。兩者的主要區(qū)別是其離散對(duì)數(shù)問(wèn)題所依賴的群不同。因此兩者有許多相似之處。橢圓曲線密碼75橢圓曲線密碼橢圓曲線群上的離散對(duì)數(shù)問(wèn)題ECDLP在上例中橢圓曲線上的解點(diǎn)所構(gòu)成的交換群恰好是循環(huán)群，但是一般并不一定。于是我們希望從中找出一個(gè)循環(huán)子群E1

?？梢宰C明當(dāng)循環(huán)子群E1的階∣E1∣是足夠大的素?cái)?shù)時(shí)，這個(gè)循環(huán)子群中的離散對(duì)數(shù)問(wèn)題是困難的。橢圓曲線密碼76橢圓曲線密碼橢圓曲線群上的離散對(duì)數(shù)問(wèn)題ECDLP

設(shè)P和Q是橢圓曲線上的兩個(gè)解點(diǎn)，t為一正整數(shù)，且0≤t<∣E1∣。對(duì)于給定的P和t，計(jì)算tP＝Q是容易的。但若已知P和Q點(diǎn)，要計(jì)算出t則是極困難的。這便是橢圓曲線群上的離散對(duì)數(shù)問(wèn)題，簡(jiǎn)記為ECDLP(EllipticCurveDiscreteLogarithmProblem)。橢圓曲線密碼77橢圓曲線密碼橢圓曲線群上的離散對(duì)數(shù)問(wèn)題ECDLP除了幾類特殊的橢圓曲線外，對(duì)于一般ECDLP目前尚沒(méi)有找到有效的求解方法。于是可以在這個(gè)循環(huán)子群E1中建立任何基于離散對(duì)數(shù)困難性的密碼，并稱這個(gè)密碼為橢圓曲線密碼。橢圓曲線密碼78橢圓曲線密碼ELGamal橢圓曲線密碼基礎(chǔ)參數(shù)T=<p,a,b,G,n,h>p為大于3素?cái)?shù)，p確定了有限域GF（p）；元素a,b∈GF(p),a和b確定了橢圓曲線；G為循環(huán)子群E1的生成元點(diǎn)，n為素?cái)?shù)且為生成元G的階，G和n確定了循環(huán)子群E1；h=|E|/n，并稱為余因子，h將交換群E和循環(huán)子群聯(lián)系起來(lái)。橢圓曲線密碼79橢圓曲線密碼ELGamal橢圓曲線密碼密鑰：用戶的私鑰定義為一個(gè)隨機(jī)數(shù)d， d∈{0,1,2,···,n-1}。用戶的公鑰定義為Q點(diǎn)， Q=dG。橢圓曲線密碼80橢圓曲線密碼ELGamal橢圓曲線密碼設(shè)d為用戶私鑰，Q為公鑰，將Q存入PKDB。設(shè)要加密的明文數(shù)據(jù)為M，將M劃分為一些較小的數(shù)據(jù)塊，M=[m1，m2，