公鑰密碼(中Elgamal)課件

密碼學(xué)

第十講公鑰密碼

——ELGamalwzy@武漢大學(xué)密碼學(xué)

第十講公鑰密碼

——ELGamal武漢大學(xué)密碼學(xué)

第十講公鑰密碼

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

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

已知Y，求X=f-1(Y)不可行單向函數(shù)單向函數(shù)是滿足下列性質(zhì)的函數(shù)：每個(gè)函數(shù)值都存在唯一的逆，并且單向函數(shù)是滿足下列性質(zhì)的函數(shù)：每個(gè)函數(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ù)單向函數(shù)是求逆困難的函數(shù)，而單向陷門函數(shù)(Trapdoor單向函數(shù)是求逆困難的函數(shù)，而單向陷門函數(shù)(Trapdoor背包問題(Knapsackproblem)已被攻破大整數(shù)分解問題(TheIntegerFactorizationProblem)RSA密碼離散對(duì)數(shù)問題有限域的乘法群上的離散對(duì)數(shù)問題(TheDiscreteLogarithmProblem)——ElGamal密碼定義在有限域的橢圓曲線上的離散對(duì)數(shù)問題(TheEllipticCurveDiscreteLogarithmProblem)——ECC密碼公鑰密碼基于的數(shù)學(xué)難題背包問題(Knapsackproblem)已被攻破公鑰密碼背包問題(Knapsackproblem)已被攻破公鑰密碼理論上：不能證明單向函數(shù)一定存在；實(shí)際上：只要函數(shù)的單向性足夠工程應(yīng)用就行；

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

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

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

c），而對(duì)數(shù)計(jì)算困難(logacb)。單向函數(shù)研究現(xiàn)狀理論上：不能證明單向函數(shù)一定存在；單向函數(shù)研究現(xiàn)狀理論上：不能證明單向函數(shù)一定存在；單向函數(shù)研究現(xiàn)狀理論上：不合數(shù)的因子分解問題單向函數(shù)研究現(xiàn)狀合數(shù)的因子分解問題單向函數(shù)研究現(xiàn)狀合數(shù)的因子分解問題單向函數(shù)研究現(xiàn)狀合數(shù)的因子分解問題單向函數(shù)有限域上的離散對(duì)數(shù)問題例如GF(19)中模19的整數(shù)冪單向函數(shù)研究現(xiàn)狀有限域上的離散對(duì)數(shù)問題單向函數(shù)研究現(xiàn)狀有限域上的離散對(duì)數(shù)問題單向函數(shù)研究現(xiàn)狀有限域上的離散對(duì)數(shù)問題1、基本情況：ELGamal密碼是除了RSA密碼之外最有代表性的公開密鑰密碼。ELGamal密碼建立在離散對(duì)數(shù)的困難性之上。RSA密碼建立在大合數(shù)分解的困難性之上。ELGamal公鑰密碼的基本情況1、基本情況：ELGamal公鑰密碼的基本情況1、基本情況：ELGamal公鑰密碼的基本情況1、基本情況：2、離散對(duì)數(shù)問題：①設(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ù)問題2、離散對(duì)數(shù)問題：離散對(duì)數(shù)問題2、離散對(duì)數(shù)問題：離散對(duì)數(shù)問題2、離散對(duì)數(shù)問題：離散對(duì)數(shù)問題有限域上的離散對(duì)數(shù)問題例如GF(19)中模19的整數(shù)冪離散對(duì)數(shù)問題有限域上的離散對(duì)數(shù)問題離散對(duì)數(shù)問題有限域上的離散對(duì)數(shù)問題離散對(duì)數(shù)問題有限域上的離散對(duì)數(shù)問題離散12離散對(duì)數(shù)問題12離散對(duì)數(shù)問題12離散對(duì)數(shù)問題12離散對(duì)數(shù)問題2、離散對(duì)數(shù)問題：求解對(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ù)問題是相當(dāng)困難的。離散對(duì)數(shù)問題2、離散對(duì)數(shù)問題：離散對(duì)數(shù)問題2、離散對(duì)數(shù)問題：離散對(duì)數(shù)問題2、離散對(duì)數(shù)問題：離散對(duì)數(shù)問題（備注）算法復(fù)雜度：例如：離散對(duì)數(shù)問題（備注）算法復(fù)雜度：離散對(duì)數(shù)問題（備注）算法復(fù)雜度：離散對(duì)數(shù)問題（備注）算法復(fù)雜度：離散對(duì)數(shù)15離散對(duì)數(shù)問題(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ù)問題15離散對(duì)數(shù)問題(DiscreteLogarithmP15離散對(duì)數(shù)問題(DiscreteLogarithmP16離散對(duì)數(shù)問題(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ù)問題16離散對(duì)數(shù)問題(DiscreteLogarithmP16離散對(duì)數(shù)問題(DiscreteLogarithmP171985年，ElGamal在Differ-Hellman密鑰交換協(xié)議基礎(chǔ)上改進(jìn)而來依賴數(shù)學(xué)難題：DLP(DiscreteLogarithmProblem)ELGamal公鑰密碼171985年，ElGamalELGamal公鑰密碼171985年，ElGamalELGamal公鑰密碼17118算法生成密鑰對(duì)GenKeyPair加密Encrypt解密DecryptELGamal公鑰密碼18算法ELGamal公鑰密碼18算法ELGamal公鑰密碼18算法ELGamal公鑰密碼19準(zhǔn)備階段：隨機(jī)地選擇一個(gè)大素?cái)?shù)p，且要求p-1有大素?cái)?shù)因子。再選擇一個(gè)模p的本原元α。將p和α公開。⑴密鑰生成用戶隨機(jī)地選擇一個(gè)整數(shù)d作為自己的秘密的解密鑰，2≤d≤p-2。計(jì)算y=αd

modp，取y為自己的公開的加密鑰。由公開鑰y

計(jì)算秘密鑰d，必須求解離散對(duì)數(shù)，而這是極困難的。ELGamal公鑰密碼19準(zhǔn)備階段：隨機(jī)地選擇一個(gè)大素?cái)?shù)p，且要求p-1有大素?cái)?shù)因19準(zhǔn)備階段：隨機(jī)地選擇一個(gè)大素?cái)?shù)p，且要求p-1有大素?cái)?shù)因20算法GenKeyPair模塊Givensystemparametersα,p(21023<p<21024

)Randomgeneratedy=αd(modp)PublicKey:y

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

C2＝UMmodp；取C＝（C1

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

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

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

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

=c2/

c1d(modp)ELGamal公鑰密碼24算法ELGamal公鑰密碼24算法ELGamal公鑰密碼24算法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公鑰密碼25算法可還原性證明ELGamal公鑰密碼25算法可還原性證明ELGamal公鑰密碼25算法可還原性證26安全性直接破解ElGamal加密機(jī)制的唯一方法是獲取yk，（如果存在其他方法也能破解ElGamal加密機(jī)制得到明文，則等同于獲取了yk

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

攻擊2——由于c1是公開的，計(jì)算yk=c1d需要d，需解DLP：d=logay由于DLP問題是難解的，所以上述兩種方法都無效ELGamal公鑰密碼27安全性ELGamal公鑰密碼27安全性ELGamal公鑰密碼27安全性ELGamal公鑰28安全性針對(duì)k重復(fù)使用的攻擊方法攻擊1（假設(shè)攻擊者掌握k）如果k不是一次性的，時(shí)間長(zhǎng)了就可能被攻擊者獲得。又因y是公開密鑰，攻擊者自然知道。于是攻擊者就可以根據(jù)U＝y(tǒng)kmodp計(jì)算出U，進(jìn)而利用Euclid算法求出U－1。又因?yàn)楣粽呖梢垣@得密文C2，于是可根據(jù)式C2＝UMmodp通過計(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公鑰密碼28安全性ELGamal公鑰密碼28安全性ELGamal公鑰密碼28安全性ELGamal公鑰29安全性其它攻擊方法假如兩個(gè)明文采用相同的隨機(jī)數(shù)k加密，則通過其密文可以容易推導(dǎo)出兩個(gè)明文的相互關(guān)系。所以要保證加密者所使用的隨機(jī)數(shù)發(fā)生器的安全性如果p不夠大，則DLP問題將因?yàn)槊荑€空間太小而變得容易解。所以，要對(duì)p進(jìn)行認(rèn)真的選擇加密者在使用接收者的公鑰時(shí)，應(yīng)設(shè)法確認(rèn)該公鑰是對(duì)應(yīng)著該接收者，否則可能造成應(yīng)該接收的人無法正常接收，而其他人可以解密ELGamal公鑰密碼29安全性ELGamal公鑰密碼29安全性ELGamal公鑰密碼29安全性ELGamal公鑰30安全性由于ELGamal密碼的安全性建立在GF（p）離散對(duì)數(shù)的困難性之上，而目前尚無求解GF（p）離散對(duì)數(shù)的有效算法，所以在p足夠大時(shí)ELGamal密碼是安全的。為了安全p應(yīng)為150位以上的十進(jìn)制數(shù)，而且p-1應(yīng)有大素因子。為了安全加密和簽名所使用的k必須是一次性的。ELGamal公鑰密碼30安全性ELGamal公鑰密碼30安全性ELGamal公鑰密碼30安全性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公鑰密碼31ELGamal密碼的應(yīng)用ELGamal公鑰密碼31ELGamal密碼的應(yīng)用ELGamal公鑰密碼31ELG32ElGamal與RSA比較ELGamal公鑰密碼32ElGamal與RSA比較ELGamal公鑰密碼32ElGamal與RSA比較ELGamal公鑰密碼32El33橢圓曲線密碼的一般情況受ELGamal密碼啟發(fā)，在其它離散對(duì)數(shù)問題難解的群中，同樣可以構(gòu)成ELGamal密碼。于是人們開始尋找其它離散問題難解的群。研究發(fā)現(xiàn)，有限域GF（p）上的橢圓曲線的解點(diǎn)構(gòu)成交換群，而且離散對(duì)數(shù)問題是難解的。于是可在此群上建立ELGamal密碼，并稱為橢圓曲線密碼。橢圓曲線密碼33橢圓曲線密碼的一般情況橢圓曲線密碼33橢圓曲線密碼的一般情況橢圓曲線密碼33橢圓曲線密碼的一般34橢圓曲線密碼的一般情況橢圓曲線密碼已成為除RSA密碼之外呼聲最高的公鑰密碼之一。它密鑰短、簽名短，軟件實(shí)現(xiàn)規(guī)模小、硬件實(shí)現(xiàn)電路省電。普遍認(rèn)為，160位長(zhǎng)的橢圓曲線密碼的安全性相當(dāng)于1024位的RSA密碼，而且運(yùn)算速度也較快。橢圓曲線密碼34橢圓曲線密碼的一般情況橢圓曲線密碼34橢圓曲線密碼的一般情況橢圓曲線密碼34橢圓曲線密碼的一般35RSA和ECC的比較RSA和ECC安全模長(zhǎng)的比較橢圓曲線密碼35RSA和ECC的比較RSA和ECC安全模長(zhǎng)的比較橢圓曲線35RSA和ECC的比較RSA和ECC安全模長(zhǎng)的比較橢圓曲線361985年，NealKoblitz和VictorMiller分別獨(dú)立地提出了橢圓曲線密碼體制多數(shù)公鑰密碼(RSA,DH)使用非常大的數(shù)或多項(xiàng)式，給密鑰和信息的存儲(chǔ)和處理帶來很大的運(yùn)算量橢圓曲線是一個(gè)代替，可以用更小的尺寸得到同樣的安全性ANSI、IEEE、ISO和NIST都制定了ECC標(biāo)準(zhǔn)草案橢圓曲線密碼361985年，NealKoblitz和VictorMi361985年，NealKoblitz和VictorMi37橢圓曲線密碼的一般情況一些國(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)用。橢圓曲線密碼37橢圓曲線密碼的一般情況橢圓曲線密碼37橢圓曲線密碼的一般情況橢圓曲線密碼37橢圓曲線密碼的一般38橢圓曲線橢圓曲線不是橢圓！費(fèi)馬大定理：當(dāng)n>2且xyz≠0時(shí)， xn+yn=zn沒有正整數(shù)解n=2時(shí)，上式有無窮組整數(shù)解，例如勾股定理定義“同余數(shù)”：正整數(shù)n為“同余數(shù)”(CongruentNumber)，如果它是一個(gè)有理直角三角形的面積。如5、6、7都是“同余數(shù)”橢圓曲線密碼38橢圓曲線橢圓曲線密碼38橢圓曲線橢圓曲線密碼38橢圓曲線橢圓曲線密碼39橢圓曲線n為“同余數(shù)”的條件是下列方程組有有理解：a2+b2=c2

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

橢圓曲線密碼39橢圓曲線橢圓曲線密碼39橢圓曲線橢圓曲線密碼39橢圓曲線橢圓曲線密碼40橢圓曲線“勾股定理”->“同余數(shù)”->橢圓曲線橢圓曲線一般形式（Weierstrass方程）當(dāng)特征為2時(shí)，可化簡(jiǎn)為當(dāng)特征大于3時(shí)，可化簡(jiǎn)為橢圓曲線密碼40橢圓曲線橢圓曲線密碼40橢圓曲線橢圓曲線密碼40橢圓曲線橢圓曲線密碼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)，將此二元組描畫到橢圓曲線上便為一個(gè)點(diǎn)，于是又稱其為解點(diǎn)。橢圓曲線密碼41橢圓曲線橢圓曲線密碼41橢圓曲線橢圓曲線密碼41橢圓曲線橢圓曲線密碼復(fù)習(xí)：代數(shù)結(jié)構(gòu)橢圓曲線密碼復(fù)習(xí)：代數(shù)結(jié)構(gòu)橢圓曲線密碼復(fù)習(xí)：代數(shù)結(jié)構(gòu)橢圓曲線密碼復(fù)習(xí)：代數(shù)結(jié)構(gòu)橢圓曲線密碼43橢圓曲線交換群封閉性：結(jié)合律：?jiǎn)挝辉耗嬖航粨Q律：橢圓曲線密碼43橢圓曲線橢圓曲線密碼43橢圓曲線橢圓曲線密碼43橢圓曲線橢圓曲線密碼44橢圓曲線橢圓曲線密碼44橢圓曲線橢圓曲線密碼44橢圓曲線橢圓曲線密碼44橢圓曲線橢圓曲線密碼45橢圓曲線為了利用解點(diǎn)構(gòu)成交換群，需要引進(jìn)一個(gè)O元素，并定義如下的加法運(yùn)算：

①定義單位元引進(jìn)一個(gè)無窮點(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）。橢圓曲線密碼45橢圓曲線橢圓曲線密碼45橢圓曲線橢圓曲線密碼45橢圓曲線橢圓曲線密碼46橢圓曲線定義如下的加法運(yùn)算：

②定義逆元

設(shè)P（x1

，y1）和Q（x2

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

如果x1=x2

且y1=-y2，則

P（x1

，y1）＋Q（x2

，y2）＝0。這說明任何解點(diǎn)R（x，y）的逆就是R（x，-y）。橢圓曲線密碼46橢圓曲線橢圓曲線密碼46橢圓曲線橢圓曲線密碼46橢圓曲線橢圓曲線密碼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）。橢圓曲線密碼47橢圓曲線橢圓曲線密碼47橢圓曲線橢圓曲線密碼47橢圓曲線橢圓曲線密碼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）。橢圓曲線密碼48橢圓曲線橢圓曲線密碼48橢圓曲線橢圓曲線密碼48橢圓曲線橢圓曲線密碼49橢圓曲線定義如下的加法運(yùn)算：作集合E={全體解點(diǎn)，無窮點(diǎn)O}。容易驗(yàn)證，如上定義的集合E和加法運(yùn)算構(gòu)成加法交換群。復(fù)習(xí)：群的定義G是一個(gè)非空集，定義了一種運(yùn)算，且運(yùn)算是自封閉的；運(yùn)算滿足結(jié)合律；G中有單位元；G中的元素都有逆元；橢圓曲線密碼49橢圓曲線橢圓曲線密碼49橢圓曲線橢圓曲線密碼49橢圓曲線橢圓曲線密碼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)。

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

橢圓曲線密碼xy0PQP+Q橢圓曲線解點(diǎn)加法運(yù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的平方剩余。

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

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

xx3+x+6mod11是否模11平方剩余y06No18No25Yes4,733Yes5,648No54Yes2,968No74Yes2,989Yes3,897No104Yes2,9橢圓曲線密碼xx3+x+6mod11是否模11平方xx3+x+6mod11是否模11平方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)。再加上無窮遠(yuǎn)點(diǎn)O，共13的點(diǎn)構(gòu)成一個(gè)加法交換群。由于群的元素個(gè)數(shù)為13，而13為素?cái)?shù)，所以此群是循環(huán)群，而且任何一個(gè)非O元素都是生成元。

橢圓曲線密碼55舉例：橢圓曲線密碼55舉例：橢圓曲線密碼55舉例：橢圓曲線密碼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。

橢圓曲線密碼56舉例：橢圓曲線密碼56舉例：橢圓曲線密碼56舉例：橢圓曲線密碼

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)注意：同階交換群是同構(gòu)的橢圓曲線密碼GF(13)加法群01注意：同階交換群是同構(gòu)的橢圓曲線密碼GF(13)加法群0159橢圓曲線“勾股定理”->“同余數(shù)”->橢圓曲線橢圓曲線一般形式（Weierstrass方程）當(dāng)特征為2時(shí)，可化簡(jiǎn)為當(dāng)特征大于3時(shí)，可化簡(jiǎn)為橢圓曲線密碼59橢圓曲線橢圓曲線密碼59橢圓曲線橢圓曲線密碼59橢圓曲線橢圓曲線密碼60橢圓曲線設(shè)m是正整數(shù)，且b

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

①定義單位元引進(jìn)一個(gè)無窮點(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）。橢圓曲線密碼61橢圓曲線橢圓曲線密碼61橢圓曲線橢圓曲線密碼61橢圓曲線橢圓曲線密碼62橢圓曲線定義如下的加法運(yùn)算：

②定義逆元

設(shè)P（x1

，y1）和Q（x2

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

如果x1=x2

且y2=x1+y1，則

P（x1

，y1）＋Q（x2

，y2）＝0。這說明任何解點(diǎn)R（x，y）的逆是R（x，x+y）。橢圓曲線密碼62橢圓曲線橢圓曲線密碼62橢圓曲線橢圓曲線密碼62橢圓曲線橢圓曲線密碼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）。橢圓曲線密碼63橢圓曲線橢圓曲線密碼63橢圓曲線橢圓曲線密碼63橢圓曲線橢圓曲線密碼64橢圓曲線定義如下的加法運(yùn)算：

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

P（x1

，y1）＋P（x1

，y1）＝2P（x1

，y1）＝R（x3

，y3）。其中

橢圓曲線密碼64橢圓曲線橢圓曲線密碼64橢圓曲線橢圓曲線密碼64橢圓曲線橢圓曲線密碼65舉例：g(x)=x4+x+1是GF（2）上的既約多項(xiàng)式，用g(x)構(gòu)造擴(kuò)域GF（24）。GF（24）的任意元素都可用表5-5中四種形式來表示。取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ò)域

橢圓曲線密碼65舉例：橢圓曲線密碼65舉例：橢圓曲線密碼65舉例：橢圓曲線密碼通過窮舉，求出其全部解點(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)通過窮舉，求出其全部解點(diǎn)如下：橢圓曲線密碼P1=(0000，通過窮舉，求出其全部解點(diǎn)如下：橢圓曲線密碼P1=(0000，通過窮舉，求出其全部解點(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é)果說明，這個(gè)群是循環(huán)群，P5是群的一個(gè)生成元。注意，并不是所有非零元素都是群的生成元，如P12=(1000，0001)的階為11。橢圓曲線密碼通過窮舉，求出其全部解點(diǎn)如下：橢圓曲線密碼通過窮舉，求出其全部解點(diǎn)如下：橢圓曲線密碼通過窮舉，求出其全注意：同階交換群是同構(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)注意：同階交換群是同構(gòu)的橢圓曲線密碼GF(22)加法群01G注意：同階交換群是同構(gòu)的橢圓曲線密碼GF(22)加法群01G69舉例：例1：驗(yàn)證P1=(0000，1011)例2：計(jì)算點(diǎn)加P5+P19=例3：計(jì)算倍點(diǎn)2P5

橢圓曲線密碼69舉例：橢圓曲線密碼69舉例：橢圓曲線密碼69舉例：橢圓曲線密碼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

。橢圓曲線密碼70除了GF(p)上的橢圓曲線外還有定義在GF(2m)上的橢70除了GF(p)上的橢圓曲線外還有定義在GF(2m)上的橢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]。橢圓曲線密碼71美國(guó)信息技術(shù)研究所NIST向社會(huì)推薦了15條橢圓曲線，其71美國(guó)信息技術(shù)研究所NIST向社會(huì)推薦了15條橢圓曲線，其72例如p192=2192-264-1。2192=264+1modp2256=2128+264modp2320+=2128+264+1modp于是

c=c52128+c5264+c5+c42128+c4264+c3264+c3+c22128+c1264+c0modp因此，通過4次192位的整數(shù)c52128+c5264+c5，c42128+c4264，c3264+c3和c22128+c1264+c0相加，并重復(fù)地減p，直到結(jié)果小于p為止，便可得到cmodp。橢圓曲線密碼72例如p192=2192-264-1。橢圓曲線密碼72例如p192=2192-264-1。橢圓曲線密碼72例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）。橢圓曲線密碼73算法模p192=2192-264-1的快速取模橢圓曲73算法模p192=2192-264-1的快速取模橢圓曲74橢圓曲線密碼ELGamal密碼建立在有限域GF（p）的乘法群的離散對(duì)數(shù)問題的困難性之上。而橢圓曲線密碼建立在橢圓曲線群的離散對(duì)數(shù)問題的困難性之上。兩者的主要區(qū)別是其離散對(duì)數(shù)問題所依賴的群不同。因此兩者有許多相似之處。橢圓曲線密碼74橢圓曲線密碼橢圓曲線密碼74橢圓曲線密碼橢圓曲線密碼74橢圓曲線密碼橢圓曲線密碼75橢圓曲線密碼橢圓曲線群上的離散對(duì)數(shù)問題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ù)問題是困難的。橢圓曲線密碼75橢圓曲線密碼橢圓曲線密碼75橢圓曲線密碼橢圓曲線密碼75橢圓曲線密碼橢圓曲線密碼76橢圓曲線密碼橢圓曲線群上的離散對(duì)數(shù)問題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ù)問題，簡(jiǎn)記為ECDLP(EllipticCurveDiscreteLogarithmProblem)。橢圓曲線密碼76橢圓曲線密碼橢圓曲線密碼76橢圓曲線密碼橢圓曲線密碼76橢圓曲線密碼橢圓曲線密碼77橢圓曲線密碼橢圓曲線群上的離散對(duì)數(shù)問題ECDLP除了幾類特殊的橢圓曲線外，對(duì)于一般ECDLP目前尚沒有找到有效的求解方法。于是可以在這個(gè)循環(huán)子群E1中建立任何基于離散對(duì)數(shù)困難性的密碼，并稱這個(gè)密碼為橢圓曲線密碼。橢圓曲線密碼77橢圓曲線密碼橢圓曲線密碼77橢圓曲線密碼橢圓曲線密碼77橢圓曲線密碼橢圓曲線密碼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)系起來。橢圓曲線密碼78橢圓曲線密碼橢圓曲線密碼78橢圓曲線密碼橢圓曲線密碼78橢圓曲線密碼橢圓曲線密碼79橢圓曲線密碼ELGamal橢圓曲線密碼密鑰：用戶的私鑰定義為一個(gè)隨機(jī)數(shù)d， d∈{0,1,2,···,n-1}。用戶的公鑰定義為Q點(diǎn)， Q=dG。橢圓曲線密碼79橢圓曲線密碼橢圓曲線密碼79橢圓曲線密碼橢圓曲線密碼79橢圓曲線密碼橢圓曲線密碼80橢圓曲線密碼ELGamal橢圓曲線密碼設(shè)d為用戶私鑰，Q為公鑰，將Q存入PKDB。設(shè)要加密的明文數(shù)據(jù)為M，將M劃分為一些較小的數(shù)據(jù)塊，M=[m1，m2，···

，mt]，其中0≤mi<n。橢圓曲線密碼80橢圓曲線密碼橢圓曲線密碼80橢圓曲線密碼橢圓曲線密碼80橢圓曲線密碼橢圓曲線密碼81橢圓曲線密碼ELGamal橢圓曲線密碼加密過程：A將M加密發(fā)給BA查PKDB，查到B的公開密鑰QB。A選擇一個(gè)隨機(jī)數(shù)k，且k∈{0,1,2,···,n-1}。A計(jì)算點(diǎn)X1：（x1

，y1）=kG。A計(jì)算點(diǎn)X2：（x2

，y2）=kQB，如果分量x2=O，則轉(zhuǎn)②。A計(jì)算密文C=mix2modn。A發(fā)送加密數(shù)據(jù)（X1，C）給B。橢圓曲線密碼81橢圓曲線密碼橢圓曲線密碼81橢圓曲線密碼橢圓曲線密碼81橢圓曲線密碼橢圓曲線密碼82橢圓曲線密碼ELGamal橢圓曲線密碼解密過程：用戶B用自己的私鑰dB求出點(diǎn)X2： dBX1 =dB（kG） =k(dBG) =kQB =X2：（x2

，y2）對(duì)C解密，得到明文mi=Cx2–1modn。橢圓曲線密碼82橢圓曲線密碼橢圓曲線密碼82橢圓曲線密碼橢圓曲線密碼82橢圓曲線密碼橢圓曲線密碼83橢圓曲線密碼橢圓曲線密碼的實(shí)現(xiàn)由于橢圓曲線密碼所依據(jù)的數(shù)學(xué)基礎(chǔ)比較復(fù)雜，從而使得其具體實(shí)現(xiàn)也比較困難。難點(diǎn)：安全橢圓曲線的產(chǎn)生；倍點(diǎn)運(yùn)算。橢圓曲線密碼83橢圓曲線密碼橢圓曲線密碼83橢圓曲線密碼橢圓曲線密碼83橢圓曲線密碼橢圓曲線密碼1、單向函數(shù)

設(shè)函數(shù)y=f(x)，如果滿足以下兩個(gè)條件，則稱為單向函數(shù)：如果對(duì)于給定的x，要計(jì)算出y很容易；而對(duì)于給定的y，要計(jì)算出x很難。2、單向函數(shù)的應(yīng)用安全HASH函數(shù)操作系統(tǒng)口令總結(jié)：公鑰密碼1、單向函數(shù)總結(jié)：公鑰密碼1、單向函數(shù)總結(jié)：公鑰密碼1、單向函數(shù)總結(jié)：公鑰密碼3、利用單向函數(shù)構(gòu)造密碼用正變換作加密，加密效率高；用逆變換作解密，安全，敵手不可破譯；但是加密后不能還原?？偨Y(jié)：公鑰密碼3、利用單向函數(shù)構(gòu)造密碼總結(jié)：公鑰密碼3、利用單向函數(shù)構(gòu)造密碼總結(jié)：公鑰密碼3、利用單向函數(shù)構(gòu)造密4、單向陷門函數(shù)設(shè)函數(shù)y=f(x)，且f具有陷門，如果滿足以下兩個(gè)條件，則稱為單向陷門函數(shù)：如果對(duì)于給定的x，要計(jì)算出y很容易；而對(duì)于給定的y，如果不掌握陷門要計(jì)算出x很難，而如果掌握陷門要計(jì)算出x就很容易?？偨Y(jié)：公鑰密碼4、單向陷門函數(shù)總結(jié)：公鑰密碼4、單向陷門函數(shù)總結(jié)：公鑰密碼4、單向陷門函數(shù)總結(jié)：公鑰密碼5、單向陷門函數(shù)的應(yīng)用用正變換作加密，加密效率高；用逆變換作解密，安全；

把陷門信息作為密鑰，且只分配給合法用戶。確保合法用戶能夠方便地解密，而非法用戶不能破譯?？偨Y(jié)：公鑰密碼5、單向陷門函數(shù)的應(yīng)用總結(jié)：公鑰密碼5、單向陷門函數(shù)的應(yīng)用總結(jié)：公鑰密碼5、單向陷門函數(shù)的應(yīng)用總理論上：不能證明單向函數(shù)一定存在；實(shí)際上：只要函數(shù)的單向性足夠工程應(yīng)用就行；

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

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

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

c），而對(duì)數(shù)計(jì)算困難(logacb)?？偨Y(jié)：公鑰密碼理論上：不能證明單向函數(shù)一定存在；總結(jié)：公鑰密碼理論上：不能證明單向函數(shù)一定存在；總結(jié)：公鑰密碼理論上：不能二、ELGamal密碼①證明ELGamal密碼的可逆性②為什么ELGamal密碼要求參數(shù)K是一次性的？③設(shè)p=5,m=3,構(gòu)造一個(gè)ELGamal密碼,并用它對(duì)m加密。習(xí)題二、ELGamal密碼習(xí)題二、ELGamal密碼習(xí)題二、ELGamal密碼習(xí)題三、橢圓曲線密碼①證明例5-8中，P12=（1000,0001）的階為11。②取p=29,求出橢圓曲線y2=x3+4x+20的全部解點(diǎn)。

③以例5-5為例,分別以G=（2,7）和G=（5,2）構(gòu)造橢圓曲線密碼,并設(shè)m=3，分別進(jìn)行加密和解密。③以例5-8為例,分別以G=P5=（0010,1111）構(gòu)造橢圓曲線密碼,并設(shè)m=（1010），分別進(jìn)行加密和解密。習(xí)題三、橢圓曲線密碼習(xí)題三、橢圓曲線密碼習(xí)題三、橢圓曲線密碼習(xí)題第十講公鑰密碼結(jié)束第十講公鑰密碼結(jié)束第十講公鑰密碼結(jié)束第十講公鑰密碼結(jié)束密碼學(xué)

第十講公鑰密碼

——ELGamalwzy@武漢大學(xué)密碼學(xué)

第十講公鑰密碼

——ELGamal武漢大學(xué)密碼學(xué)

第十講公鑰密碼

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

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

已知Y，求X=f-1(Y)不可行單向函數(shù)單向函數(shù)是滿足下列性質(zhì)的函數(shù)：每個(gè)函數(shù)值都存在唯一的逆，并且單向函數(shù)是滿足下列性質(zhì)的函數(shù)：每個(gè)函數(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ù)單向函數(shù)是求逆困難的函數(shù)，而單向陷門函數(shù)(Trapdoor單向函數(shù)是求逆困難的函數(shù)，而單向陷門函數(shù)(Trapdoor背包問題(Knapsackproblem)已被攻破大整數(shù)分解問題(TheIntegerFactorizationProblem)RSA密碼離散對(duì)數(shù)問題有限域的乘法群上的離散對(duì)數(shù)問題(TheDiscreteLogarithmProblem)——ElGamal密碼定義在有限域的橢圓曲線上的離散對(duì)數(shù)問題(TheEllipticCurveDiscreteLogarithmProblem)——ECC密碼公鑰密碼基于的數(shù)學(xué)難題背包問題(Knapsackproblem)已被攻破公鑰密碼背包問題(Knapsackproblem)已被攻破公鑰密碼理論上：不能證明單向函數(shù)一定存在；實(shí)際上：只要函數(shù)的單向性足夠工程應(yīng)用就行；

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

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

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

c），而對(duì)數(shù)計(jì)算困難(logacb)。單向函數(shù)研究現(xiàn)狀理論上：不能證明單向函數(shù)一定存在；單向函數(shù)研究現(xiàn)狀理論上：不能證明單向函數(shù)一定存在；單向函數(shù)研究現(xiàn)狀理論上：不合數(shù)的因子分解問題單向函數(shù)研究現(xiàn)狀合數(shù)的因子分解問題單向函數(shù)研究現(xiàn)狀合數(shù)的因子分解問題單向函數(shù)研究現(xiàn)狀合數(shù)的因子分解問題單向函數(shù)有限域上的離散對(duì)數(shù)問題例如GF(19)中模19的整數(shù)冪單向函數(shù)研究現(xiàn)狀有限域上的離散對(duì)數(shù)問題單向函數(shù)研究現(xiàn)狀有限域上的離散對(duì)數(shù)問題單向函數(shù)研究現(xiàn)狀有限域上的離散對(duì)數(shù)問題1、基本情況：ELGamal密碼是除了RSA密碼之外最有代表性的公開密鑰密碼。ELGamal密碼建立在離散對(duì)數(shù)的困難性之上。RSA密碼建立在大合數(shù)分解的困難性之上。ELGamal公鑰密碼的基本情況1、基本情況：ELGamal公鑰密碼的基本情況1、基本情況：ELGamal公鑰密碼的基本情況1、基本情況：2、離散對(duì)數(shù)問題：①設(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ù)問題2、離散對(duì)數(shù)問題：離散對(duì)數(shù)問題2、離散對(duì)數(shù)問題：離散對(duì)數(shù)問題2、離散對(duì)數(shù)問題：離散對(duì)數(shù)問題有限域上的離散對(duì)數(shù)問題例如GF(19)中模19的整數(shù)冪離散對(duì)數(shù)問題有限域上的離散對(duì)數(shù)問題離散對(duì)數(shù)問題有限域上的離散對(duì)數(shù)問題離散對(duì)數(shù)問題有限域上的離散對(duì)數(shù)問題離散103離散對(duì)數(shù)問題12離散對(duì)數(shù)問題103離散對(duì)數(shù)問題12離散對(duì)數(shù)問題2、離散對(duì)數(shù)問題：求解對(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ù)問題是相當(dāng)困難的。離散對(duì)數(shù)問題2、離散對(duì)數(shù)問題：離散對(duì)數(shù)問題2、離散對(duì)數(shù)問題：離散對(duì)數(shù)問題2、離散對(duì)數(shù)問題：離散對(duì)數(shù)問題（備注）算法復(fù)雜度：例如：離散對(duì)數(shù)問題（備注）算法復(fù)雜度：離散對(duì)數(shù)問題（備注）算法復(fù)雜度：離散對(duì)數(shù)問題（備注）算法復(fù)雜度：離散對(duì)數(shù)106離散對(duì)數(shù)問題(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ù)問題15離散對(duì)數(shù)問題(DiscreteLogarithmP106離散對(duì)數(shù)問題(DiscreteLogarithm107離散對(duì)數(shù)問題(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ù)問題16離散對(duì)數(shù)問題(DiscreteLogarithmP107離散對(duì)數(shù)問題(DiscreteLogarithm1081985年，ElGamal在Differ-Hellman密鑰交換協(xié)議基礎(chǔ)上改進(jìn)而來依賴數(shù)學(xué)難題：DLP(DiscreteLogarithmProblem)ELGamal公鑰密碼171985年，ElGamalELGamal公鑰密碼1081985年，ElGamalELGamal公鑰密碼17109算法生成密鑰對(duì)GenKeyPair加密Encrypt解密DecryptELGamal公鑰密碼18算法ELGamal公鑰密碼109算法ELGamal公鑰密碼18算法ELGamal公鑰密110準(zhǔn)備階段：隨機(jī)地選擇一個(gè)大素?cái)?shù)p，且要求p-1有大素?cái)?shù)因子。再選擇一個(gè)模p的本原元α。將p和α公開。⑴密鑰生成用戶隨機(jī)地選擇一個(gè)整數(shù)d作為自己的秘密的解密鑰，2≤d≤p-2。計(jì)算y=αd

modp，取y為自己的公開的加密鑰。由公開鑰y

計(jì)算秘密鑰d，必須求解離散對(duì)數(shù)，而這是極困難的。ELGamal公鑰密碼19準(zhǔn)備階段：隨機(jī)地選擇一個(gè)大素?cái)?shù)p，且要求p-1有大素?cái)?shù)因110準(zhǔn)備階段：隨機(jī)地選擇一個(gè)大素?cái)?shù)p，且要求p-1有大素?cái)?shù)111算法GenKeyPair模塊Givensystemparametersα,p(21023<p<21024

)Randomgeneratedy=αd(modp)PublicKey:y

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

C2＝UMmodp；取C＝（C1

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

=<αk(modp),M*yk(modp)>ELGamal公鑰密碼22算法ELGamal公鑰密碼113算法ELGamal公鑰密碼22算法ELGamal公鑰密114⑶解密將密文（C1

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

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

=c2/

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

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公鑰密碼25算法可還原性證明ELGamal公鑰密碼116算法可還原性證明ELGamal公鑰密碼25算法可還原性117安全性直接破解ElGamal加密機(jī)制的唯一方法是獲取yk，（如果存在其他方法也能破解ElGamal加密機(jī)制得到明文，則等同于獲取了yk

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

攻擊2——由于c1是公開的，計(jì)算yk=c1d需要d，需解DLP：d=logay由于DLP問題是難解的，所以上述兩種方法都無效ELGamal公鑰密碼27安全性ELGamal公鑰密碼118安全性ELGamal公鑰密碼27安全性ELGamal公119安全性針對(duì)k重復(fù)使用的攻擊方法攻擊1（假設(shè)攻擊者掌握k）如果k不是一次性的，時(shí)間長(zhǎng)了就可能被攻擊者獲得。又因y是公開密鑰，攻擊者自然知道。于是攻擊者就可以根據(jù)U＝y(tǒng)kmodp計(jì)算出U，進(jìn)而利用Euclid算法求出U－1。又因?yàn)楣粽呖梢垣@得密文C2，于是可根據(jù)式C2＝UMmodp通過計(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公鑰密碼28安全性ELGamal公鑰密碼119安全性ELGamal公鑰密碼28安全性ELGamal公120安全性其它攻擊方法假如兩個(gè)明文采用相同的隨機(jī)數(shù)k加密，則通過其密文可以容易推導(dǎo)出兩個(gè)明文的相互關(guān)系。所以要保證加密者所使用的隨機(jī)數(shù)發(fā)生器的安全性如果p不夠大，則DLP問題將因?yàn)槊荑€空間太小而變得容易解。所以，要對(duì)p進(jìn)行認(rèn)真的選擇加密者在使用接收者的公鑰時(shí)，應(yīng)設(shè)法確認(rèn)該公鑰是對(duì)應(yīng)著該接收者，否則可能造成應(yīng)該接收的人無法正常接收，而其他人可以解密ELGamal公鑰密碼29安全性ELGamal公鑰密碼120安全性ELGamal公鑰密碼29安全性ELGamal公121安全性由于ELGamal密碼的安全性建立在GF（p）離散對(duì)數(shù)的困難性之上，而目前尚無求解GF（p）離散對(duì)數(shù)的有效算法，所以在p足夠大時(shí)ELGamal密碼是安全的。為了安全p應(yīng)為150位以上的十進(jìn)制數(shù)，而且p-1應(yīng)有大素因子。為了安全加密和簽名所使用的k必須是一次性的。ELGamal公鑰密碼30安全性ELGamal公鑰密碼121安全性ELGamal公鑰密碼30安全性ELGamal公122ELGamal密碼的應(yīng)用由于ELGamal密碼的安全性得到世界公認(rèn)，所以得到廣泛的應(yīng)用。著名的美國(guó)數(shù)字簽名標(biāo)準(zhǔn)DSS，采用了ELGamal密碼的一種變形。為了適應(yīng)不同的應(yīng)用，人們?cè)趹?yīng)用中總結(jié)出1