現(xiàn)代密碼學(xué)(第四章)

1、2022-6-91第四章：第四章：公鑰密碼一、公鑰密碼的基本概念一、公鑰密碼的基本概念二、公鑰密碼二、公鑰密碼RSA三、背包公鑰密碼三、背包公鑰密碼四、公鑰密碼四、公鑰密碼Rabin五、五、 ElGamal公鑰密碼公鑰密碼六、公鑰密碼六、公鑰密碼NTRU七、橢圓曲線(xiàn)公鑰密碼七、橢圓曲線(xiàn)公鑰密碼ECC八、八、 McEliece公鑰密碼公鑰密碼2022-6-92一、公鑰密碼的基本概念一、公鑰密碼的基本概念雙鑰密碼體制雙鑰密碼體制(公鑰密碼體制公鑰密碼體制) 于1976年由W. Diffie和M. Hellman1976提出，同時(shí)R. Merkle1978也獨(dú)立提出了這一體制?？捎糜诒Ｃ芡ㄐ牛部捎?/p>

2、于數(shù)字簽字。這一體制的出現(xiàn)在密碼學(xué)史上是劃時(shí)代的事件，它為解決計(jì)算機(jī)信息網(wǎng)中的安全提供了新的理論和技術(shù)基礎(chǔ)。公鑰體制的基本原理是陷門(mén)單向函數(shù)陷門(mén)單向函數(shù)。2022-6-93一、公鑰密碼的基本概念一、公鑰密碼的基本概念一個(gè)函數(shù)f：AB，若它滿(mǎn)足： 1o 對(duì)所有xA，易于計(jì)算f(x)。 2o 對(duì)“幾乎所有xA”，由f(x)求x“極為困難”，以至于實(shí)際上不可能做到。則稱(chēng)f為一單向(One-way)函數(shù)。定義中的“極為困難”是對(duì)現(xiàn)有的計(jì)算資源和算法而言。陷門(mén)單向函數(shù)(Trapdoor one-way function)，是這樣的單向函數(shù)：n在不知陷門(mén)信息下，由f(x)求x“極為困難”， ；n當(dāng)知道陷門(mén)

3、信息后，由f(x)求x是易于實(shí)現(xiàn)的。2022-6-94單向函數(shù)舉例單向函數(shù)舉例離散對(duì)數(shù)離散對(duì)數(shù)DL。給定一大素?cái)?shù)p（比如， p在21024數(shù)量級(jí)），p1含另一大素?cái)?shù)因子。稱(chēng)log2p為素?cái)?shù)p的長(zhǎng)度。1, 2, , p-1關(guān)于modp乘法構(gòu)成了一乘群Zp*，它是一個(gè)p1階循環(huán)群。該循環(huán)群的生成元一共有(p-1)個(gè)。n設(shè)一個(gè)生成元為整數(shù)g，1gp1。n設(shè)一個(gè)整數(shù)x，1xp1。n設(shè)y滿(mǎn)足y=gxmodp。2022-6-95單向函數(shù)舉例單向函數(shù)舉例已知x，g，p， 求y=gxmodp容易。這是因?yàn)?，采用折半相乘，只需要不超過(guò)2log2p次的modp乘法運(yùn)算。（實(shí)際上只需要不超過(guò)2log2x次的modp

4、乘法運(yùn)算。如x=15=11112，g15 modp=(g)2g)2g)2g modp，要用6次modp乘法 ）2022-6-96單向函數(shù)舉例單向函數(shù)舉例若已知y，g，p，求x滿(mǎn)足y=gxmodp，稱(chēng)為求解離散對(duì)數(shù)問(wèn)題。記為x=logg y mod p。求解離散對(duì)數(shù)問(wèn)題的“最笨的方法”當(dāng)然就是窮舉，對(duì)每一個(gè)x0, 1, 2, , p1檢驗(yàn)是否y=gxmodp。窮舉求解法的運(yùn)算次數(shù)約為( p1)/2。許多求解離散對(duì)數(shù)問(wèn)題的算法比窮舉快得多，比如Shanks算法，Pohlig-Hellman算法等。最快求解法的運(yùn)算次數(shù)約為數(shù)量級(jí))ln)(ln(ln(exp(ppO2022-6-97單向函數(shù)舉例單向函

5、數(shù)舉例這個(gè)計(jì)算量稱(chēng)為亞指數(shù)計(jì)算量。這是什么概念呢？我們知道p的長(zhǎng)度是log2p?？匆韵碌牟坏仁健．?dāng)log2p1024時(shí)，亞指數(shù)計(jì)算量不小于2100數(shù)量級(jí)。至少在在當(dāng)前的計(jì)算水平之下是不能實(shí)現(xiàn)的。 .logln) )ln)(lnln(lnexp() )ln)(ln(lnexp(;2) )(ln(lnexp() )ln)(ln(lnexp(2log2pppppppppppp2022-6-98單向函數(shù)舉例單向函數(shù)舉例大整數(shù)分解大整數(shù)分解FAC。設(shè)有二大素?cái)?shù)p和q。設(shè)n=pq。若已知p和q，求n=pq只需一次乘法。但若已知n，求p和q滿(mǎn)足n=pq，則稱(chēng)為大整數(shù)分解問(wèn)題。迄今為止，已知的各種算法的漸近運(yùn)

6、行時(shí)間約為：試除法：n/2。二次篩(QS)：橢圓曲線(xiàn)(EC)：數(shù)域篩(NFS)：)lnlnln(expnnO)lnlnln2(expppO)ln(ln)(ln92. 1(exp(3231nnO2022-6-99單向函數(shù)舉例單向函數(shù)舉例背包問(wèn)題。背包問(wèn)題。已知向量A=( a1, a2, , aN)， ai為正整數(shù)， 稱(chēng)其為背包向量背包向量，稱(chēng)每個(gè)ai為物品重量。給定向量x=(x1, x2, xN)， xi0, 1，求和式（稱(chēng)為背包重量）S= a1x1+ a2x2+ +aNxN容易，只需要不超過(guò)N1次加法。但已知A和S，求x則非常困難，稱(chēng)其為背包問(wèn)題，又稱(chēng)作子集和子集和(Subset-Sum)問(wèn)題

7、。一般只能用窮舉搜索法，有2N種可能。N大時(shí)，相當(dāng)困難。2022-6-910單向函數(shù)舉例單向函數(shù)舉例背包問(wèn)題的特例：超遞增背包問(wèn)題。背包問(wèn)題的特例：超遞增背包問(wèn)題。將物品重量從小到大排列：a1，a2，a3，aN。稱(chēng)該背包問(wèn)題為超遞增背包問(wèn)題，如果：a1a2；a1+a2a3；a1+a2+a3a4；a1+a2+a3+aN-1aN。（超遞增背包問(wèn)題是容易解決的。）2022-6-911單向函數(shù)舉例單向函數(shù)舉例定理定理 設(shè)超遞增背包重量為S。如果k滿(mǎn)足akSak+1，則ak是背包中的最大物品重量。定理的證明定理的證明 首先，背包中沒(méi)有大于ak的物品重量。其次，背包中確有等于ak的物品重量。證明完畢。注意

8、到，尋找k滿(mǎn)足akSak+1只需要對(duì)比N次。2022-6-912單向函數(shù)舉例單向函數(shù)舉例超遞增背包問(wèn)題的解決方法超遞增背包問(wèn)題的解決方法解決方法是可行的。設(shè)背包重量S，步驟如下。（1）窮舉：找k滿(mǎn)足akS0，則令S:=S-ak，返回（1）。如果w=0，則到（4）。（4）輸出前面存儲(chǔ)的所有的k，停止。2022-6-913單向函數(shù)舉例單向函數(shù)舉例格的最小向量問(wèn)題格的最小向量問(wèn)題(SVP)。若干個(gè)N維向量組成的集合，如果滿(mǎn)足“集合中任何若干個(gè)向量的整數(shù)線(xiàn)性組合仍是集合中的一個(gè)向量?！眲t該結(jié)合稱(chēng)為一個(gè)格。關(guān)于格有以下的性質(zhì)和概念。n如果格中存在這樣的幾個(gè)向量，滿(mǎn)足它們（實(shí)數(shù)）線(xiàn)性無(wú)關(guān)；格中的任何其它向

9、量都能唯一地表示為這幾個(gè)向量的整數(shù)線(xiàn)性組合。則這幾個(gè)向量構(gòu)成的向量組稱(chēng)為基。n基中的向量的個(gè)數(shù)稱(chēng)為格的維數(shù)。n格的維數(shù)總是不超過(guò)N。2022-6-914單向函數(shù)舉例單向函數(shù)舉例給定一個(gè)格的一組基。尋找格中的“尺寸最小”的向量（即模最小的向量），稱(chēng)為格的最小向量問(wèn)題（shortest vector problem；SVP）。又稱(chēng)為格歸約。實(shí)際上，格歸約的傳統(tǒng)算法為L(zhǎng)LL算法，以后又有各種改進(jìn)的算法。當(dāng)格的維數(shù)比較大時(shí)（比如，維數(shù)大于200），當(dāng)前的所有格歸約算法都不是有效算法。2022-6-915二、公鑰密碼二、公鑰密碼RSA公鑰密碼公鑰密碼RSARSA19771977年由美國(guó)麻省理工學(xué)院的三位

10、教授年由美國(guó)麻省理工學(xué)院的三位教授 Ronald Ronald R Rivestivest Adi Adi S Shamirhamir Leonard Leonard A Adlemandleman聯(lián)合發(fā)明聯(lián)合發(fā)明2022-6-916二、公鑰密碼二、公鑰密碼RSARSA的密鑰生成的密鑰生成選擇兩個(gè)大的素?cái)?shù)p和q。選擇兩個(gè)正整數(shù)e和d，滿(mǎn)足：ed是(p-1)(q-1)的倍數(shù)加1。計(jì)算n=pq。Bob的公鑰是（n，e），對(duì)外公布。Bob的私鑰是d ，自己私藏。至于（p，q ），可以是Bob的另一部分私鑰，也可以是對(duì)所有人（包括Bob ）都保密的。2022-6-917二、公鑰密碼二、公鑰密碼RSA基

11、本基本RSA的加密過(guò)程：的加密過(guò)程：Alice欲發(fā)送明文m給Bob，其中0mn 。Alice用Bob的公鑰（n，e），計(jì)算密文c為c=me(modn)?；净綬SA的解密過(guò)程：的解密過(guò)程：Bob 收到密文c后，用自己的公鑰（n，e）和私鑰d，計(jì)算cd(modn)=med(modn)=m。（因?yàn)閑d是(p-1)(q-1)的倍數(shù)加1，所以med(modn)=m。這是數(shù)論中的一個(gè)基本結(jié)論）2022-6-918二、公鑰密碼二、公鑰密碼RSA基本基本RSA的安全性的安全性攻擊者Eve已經(jīng)知道了Bob的公鑰是（n，e）。n如果Eve還知道（p，q），則他容易知道Bob的私鑰d。此時(shí)Eve只需要用推廣的輾

12、轉(zhuǎn)相除法尋找d，滿(mǎn)足ed=1(mod(p-1)(q-1)。n由n的值求解（p，q）的值，即求解n的大整數(shù)分解n=pq，是一個(gè)公認(rèn)的數(shù)學(xué)難題（雖然至今并沒(méi)有證明），暫時(shí)還沒(méi)有有效的算法。2022-6-919二、公鑰密碼二、公鑰密碼RSA目前普遍使用的參數(shù)范圍是2511p2512，2511qa1+a2+a3+an；MU；Ua1M；M與U互素，因此可以用輾轉(zhuǎn)相除法計(jì)算出U關(guān)于(modM)的逆元U-1。2022-6-928三、背包公鑰密碼三、背包公鑰密碼計(jì)算：b1=Ua1(modM)，b2=Ua2(modM) ，b3=Ua3(modM) ，bn=Uan(modM) 。（此時(shí)a1=U-1b1(modM)

13、， a2=U-1b2(modM)， a3=U-1b3(modM)， ，an=U-1bn(modM) 。 ）2022-6-929三、背包公鑰密碼三、背包公鑰密碼b1，b2，b3，bn是n個(gè)物品重量。因?yàn)閁a1MUa1(modM)=b1，Ua2Ua1MUa2(modM)=b2，Ua3Ua1MUa3(modM)=b3，UanUa1MUan(modM)=bn，所以通常b1，b2，b3，bn不具有超遞增性。b1，b2，b3，bn是公鑰。a1，a2，a3，an ， M，U都是私鑰。2022-6-930三、背包公鑰密碼三、背包公鑰密碼背包公鑰密碼的加密背包公鑰密碼的加密設(shè)明文m=(m1, m2, m3, ,

14、 mn)是長(zhǎng)度為n的比特串。使用公鑰b1，b2，b3，bn計(jì)算密文c ：c=m1b1+m2b2+m3b3+mnbn。密文c是一個(gè)正整數(shù)。（密文c是背包重量，由n個(gè)物品重量b1，b2，b3，bn中的某些物品重量相加而成。若截獲了密文c，又知道n個(gè)物品重量b1，b2，b3，bn，求解明文m就是背包問(wèn)題。 ）2022-6-931三、背包公鑰密碼三、背包公鑰密碼背包公鑰密碼的解密背包公鑰密碼的解密使用私鑰a1，a2，a3，an ， M，U，計(jì)算變換課文C：C=U-1c(modM)=U-1(m1b1+m2b2+m3b3+mnbn )(modM)=m1a1+m2a2+m3a3+mnan(modM) =m1

15、a1+m2a2+m3a3+mnan。根據(jù)定理中的方法，容易解出明文m。2022-6-932三、背包公鑰密碼三、背包公鑰密碼變換課文C是背包重量，由n個(gè)物品重量a1，a2，a3，an中的某些物品重量相加而成。若已知變換課文C ，又知道n個(gè)物品重量a1，a2，a3，an，求解明文m就是超遞增背包問(wèn)題。2022-6-933四、公鑰密碼四、公鑰密碼RabinRabin的密鑰生成的密鑰生成選擇兩個(gè)大的素?cái)?shù)p和q，要求p和q都是4的倍數(shù)加3。計(jì)算n=pq。Bob的公鑰是n，對(duì)外公布。Bob的私鑰是（p，q），自己私藏。2022-6-934四、公鑰密碼四、公鑰密碼RabinRabinRabin的加密過(guò)程的加

16、密過(guò)程Alice欲發(fā)送明文m給Bob，其中0mn 。Alice用Bob的公鑰n，計(jì)算：c=m2(modn)。c為密文。2022-6-935四、公鑰密碼四、公鑰密碼RabinRabinRabin的解密過(guò)程的解密過(guò)程Bob 收到密文c后，用自己的私鑰（p，q）計(jì)算).(mod);(mod4141qcmpcmpqpp2022-6-936四、公鑰密碼四、公鑰密碼Rabin計(jì)算4個(gè)數(shù)m(1,1)， m(1,2)， m(2,1)， m(2,2)，滿(mǎn)足：0m(1,1)n；0m(1,2)n；0m(2,1)n； 0m(2,2)n；m(1,1)(modp)=mp； m(1,1)(modq)=mq；m(1,2)(m

17、odp)=mp； m(1,2)(modq)=q-mq；m(2,1)(modp)=p-mp； m(2,1)(modq)=mq；m(2,2)(modp)=p-mp； m(2,2)(modq)=q-mq 。2022-6-937四、公鑰密碼四、公鑰密碼Rabin（4個(gè)數(shù)的計(jì)算使用孫子定理（中國(guó)剩余定理）。）于是，真正的明文m一定就是4個(gè)數(shù)m(1,1)， m(1,2)， m(2,1)， m(2,2)之中的一個(gè)。觀察4個(gè)數(shù)，排除那些沒(méi)有意義的“亂碼課文”。哪個(gè)是有意義的課文，哪個(gè)就是真正的明文m。解密完畢。2022-6-938四、公鑰密碼四、公鑰密碼RabinRabinRabin的解密原理的解密原理因?yàn)閚

18、=pq是兩個(gè)不同的素?cái)?shù)的乘積，所以，關(guān)于未知數(shù)x的二次方程c=x2(modn)恰好有4個(gè)不同的根x，分別有以下形狀：一個(gè)根的(modp)、(modq)值是mp、mq；一個(gè)根的(modp)、(modq)值是mp、q-mq；一個(gè)根的(modp)、(modq)值是p-mp、mq；一個(gè)根的(modp)、(modq)值是p-mp、q-mq 。2022-6-939四、公鑰密碼四、公鑰密碼Rabin4個(gè)根中有一個(gè)是明文m。如果把(modp)、(modq)值為mp、mq的根叫做m，則(modp)、(modq)值為p-mp、q-mq的根就是n-m。另外兩個(gè)根的和也等于n。即如果把一個(gè)叫做m，則另一個(gè)就是n-m。

19、那么， 4個(gè)不同的根怎樣計(jì)算呢？如果僅僅知道n，而不知道分解式n=pq，則無(wú)法計(jì)算mp和mq，因而無(wú)法計(jì)算這4個(gè)不同的根。2022-6-940四、公鑰密碼四、公鑰密碼Rabin如果知道了n的分解式n=pq，則能夠計(jì)算mp和mq。再由mp和mq計(jì)算4個(gè)根，使用的是著名的孫子定理（中國(guó)剩余定理）（略）。最后，要判斷哪一個(gè)根是真正的明文。一般，真正的明文都具有語(yǔ)言含義，而其它的根則是沒(méi)有語(yǔ)言含義的“亂碼課文”。當(dāng)然也有例外，比如當(dāng)明文是一副圖象的編碼時(shí)，明文也是沒(méi)有語(yǔ)言含義的“亂碼課文”。2022-6-941四、公鑰密碼四、公鑰密碼RabinRabinRabin的安全性原理的安全性原理攻擊者Eve截

20、獲了密文c。 Eve還知道Bob的公鑰n，也知道明文m滿(mǎn)足方程c=m2(modn)。但是他不知道n的分解式n=pq，無(wú)法計(jì)算mp和mq，進(jìn)一步無(wú)法計(jì)算4個(gè)根。求n的分解式n=pq是大數(shù)分解問(wèn)題。2022-6-942四、公鑰密碼四、公鑰密碼RabinRSARSA與與RabinRabin比較比較比較項(xiàng)目RSARabin公鑰(n, e)n私鑰d(p, q)加密算法c=me(modn)c=m2(modn)解密算法m=cd(modn)若干步安全基礎(chǔ)大數(shù)分解問(wèn)題的困難性大數(shù)分解問(wèn)題的困難性2022-6-943五、五、 ElGamal公鑰密碼公鑰密碼ElGamal的密鑰生成的密鑰生成選擇一個(gè)大的素?cái)?shù)p。選擇

21、g，1g p。選擇x，1x p-1。計(jì)算y=gxmod p。Bob的公鑰是(p, g, y)，對(duì)外公布。Bob的私鑰是x，自己私藏。2022-6-944五、五、 ElGamal公鑰密碼公鑰密碼ElGamal的加密過(guò)程的加密過(guò)程Alice欲發(fā)送明文m給Bob，其中0mp 。Alice選擇隨機(jī)數(shù)k，(k,p1)=1，計(jì)算：y1=g kmodp (隨機(jī)數(shù)k被加密)。再用Bob的公鑰y，計(jì)算：y2=mykmod p(明文被隨機(jī)數(shù)k和公鑰y加密)密文由y1、y2級(jí)連構(gòu)成，即密文c=y1|y2。2022-6-945五、五、 ElGamal公鑰密碼公鑰密碼ElGamal的解密過(guò)程：的解密過(guò)程：Bob 收到密

22、文c后，用自己的私鑰x計(jì)算m=y2/y1x=myk/gkx=mgxk/gxk modp 。特點(diǎn)特點(diǎn)：密文由明文和所選隨機(jī)數(shù)k來(lái)定，因而是非確定性非確定性加密，一般稱(chēng)之為隨機(jī)化隨機(jī)化加密，對(duì)同一明文由于不同時(shí)刻的隨機(jī)數(shù)k不同而給出不同的密文。代價(jià)是使數(shù)據(jù)擴(kuò)展一倍。安全性：安全性：基于離散對(duì)數(shù)的困難性。2022-6-946六、公鑰密碼六、公鑰密碼NTRUNTRU的密鑰生成的密鑰生成要用到三個(gè)公開(kāi)參數(shù)(N, q, p)，其中N是正整數(shù)，p是小的奇素?cái)?shù)，p與q互素，且pq/2。 要使用三種模運(yùn)算(modq)、(modp)、(modxN-1)。關(guān)于(modq)運(yùn)算的結(jié)果限制在區(qū)間(-q/2, q/2內(nèi)，

23、而不是區(qū)間0, q)內(nèi)。關(guān)于(modp)運(yùn)算的結(jié)果限制在區(qū)間(-p/2, p/2內(nèi)，而不是區(qū)間0, p)內(nèi)。域GF(p)中的元素也在區(qū)間(-p/2, p/2內(nèi)，而不是區(qū)間0, p)內(nèi)。 2022-6-947六、公鑰密碼六、公鑰密碼NTRUn選擇兩個(gè)多項(xiàng)式f(x)和g(x)， 滿(mǎn)足：它們的次數(shù)均不超過(guò)N-1，它們的系數(shù)均屬于0, 1 。n分別驗(yàn)證f(x)和g(x)關(guān)于(modp, modxN-1)和(modq, modxN-1) 是否可逆。2022-6-948六、公鑰密碼六、公鑰密碼NTRUn如果可逆，則計(jì)算f(x)-1(modp, modxN-1)，h(x)=f(x)-1g(x) (modq,

24、 modxN-1)，存儲(chǔ)f(x), g(x), f(x)-1(modp, modxN-1), h(x)。n如果不全可逆，則重新選擇f(x), g(x)。Bob的公鑰是h(x) ，對(duì)外公布。Bob的私鑰是f(x), g(x) ，自己私藏。 2022-6-949六、公鑰密碼六、公鑰密碼NTRUNTRU的加密過(guò)程的加密過(guò)程Alice欲發(fā)送明文m(x)給Bob，其中m(x)為域GF(p)上的次數(shù)不超過(guò)N-1的多項(xiàng)式。Alice隨機(jī)地選取r(x)為域GF(p)上的次數(shù)不超過(guò)N-1的多項(xiàng)式，稱(chēng)r(x)為工作密鑰。密文c(x)如下計(jì)算： c(x)=pr(x)h(x)+m(x) (modq, modxN-1)

25、。2022-6-950六、公鑰密碼六、公鑰密碼NTRUNTRU的解密過(guò)程的解密過(guò)程Bob計(jì)算d(x)=f(x)c(x)(modq, modxN-1)=pg(x)r(x)+f(x)m(x) (modq, modxN-1)。注意到由于f(x)和pg(x) 的系數(shù)相對(duì)于q很小，因此希望pg(x)r(x)+f(x)m(x) (modxN-1)的每個(gè)系數(shù)都不超出區(qū)間(-q/2, q/2。若果真如此，則d(x)=pg(x)r(x)+f(x)m(x) (modxN-1)。（無(wú)modq ）2022-6-951六、公鑰密碼六、公鑰密碼NTRU（若果真如此，） Bob繼續(xù)計(jì)算f(x)-1d(x) (modp, m

26、odxN-1)=f(x)-1f(x)m(x) (modp, modxN-1)=m(x)。（由此看來(lái)，要保證正確解密首先要保證： pg(x)r(x)+f(x)m(x) (modxN-1)的每個(gè)系數(shù)都不超出區(qū)間(-q/2, q/2。 ）2022-6-952六、公鑰密碼六、公鑰密碼NTRU一、若f(x)和pg(x) 的系數(shù)絕對(duì)值之和不超過(guò)(q-1)/p，則對(duì)任何明文m(x)都保證：pg(x)r(x)+f(x)m(x) (modxN-1)的每個(gè)系數(shù)都不超出區(qū)間(-q/2, q/2。二、一般， f(x)和pg(x) 的系數(shù)恰當(dāng)?shù)卦O(shè)計(jì)，可以對(duì)絕大多數(shù)明文m(x)都保證： pg(x)r(x)+f(x)m(x

27、) (modxN-1)的每個(gè)系數(shù)都不超出區(qū)間(-q/2, q/2。2022-6-953六、公鑰密碼六、公鑰密碼NTRUNTRU的安全性的安全性設(shè)h(x)是NTRU的公鑰。如果t(x)=h(x)s(x) (modq, modxN-1)，且多項(xiàng)式pt(x)r(x)+s(x)m(x) (modxN-1) 的每個(gè)系數(shù)都在區(qū)間(-q/2, q/2內(nèi)，則此t(x), s(x)就是能夠?qū)⒋藃(x), m(x)進(jìn)行解密的一個(gè)局部有效私鑰。這是因?yàn)閔(x)=t(x)s-1(x) (modq, modxN-1)，因此2022-6-954六、公鑰密碼六、公鑰密碼NTRUc(x)=pr(x)h(x)+m(x) (mo

28、dq, modxN-1)；d(x)=s(x)c(x)(modq, modxN-1)=pt(x)r(x)+s(x)m(x) (modq, modxN-1)=pt(x)r(x)+s(x)m(x) (modxN-1)；s(x)-1d(x) (modp, modxN-1)=s(x)-1s(x)m(x) (modp, modxN-1)=m(x)。2022-6-955六、公鑰密碼六、公鑰密碼NTRUn當(dāng)t(x), s(x)的“尺寸”比較小，就可能有r(x), m(x) 使pt(x)r(x)+s(x)m(x) (modxN-1) 的每個(gè)系數(shù)都在區(qū)間(-q/2, q/2內(nèi)，因而t(x), s(x)能夠作為有效

29、私鑰對(duì)r(x), m(x) 成功解密。nt(x), s(x)的“尺寸”越小， t(x), s(x)能夠成功解密的r(x), m(x) 越多。n尋找滿(mǎn)足方程t(x)=h(x)s(x) (modq, modxN-1)、且“尺寸”足夠小的t(x), s(x)是攻破NTRU的關(guān)鍵。2022-6-956六、公鑰密碼六、公鑰密碼NTRUn方程t(x)=h(x)s(x) (modq, modxN-1)的全部解t(x), s(x)構(gòu)成了一個(gè)格，稱(chēng)為CS格。n真正的私鑰g(x), f(x)屬于此CS格。nCS 格歸約被用來(lái)尋找“尺寸”足夠小的t(x), s(x) ，來(lái)作為NTRU的有效私鑰或局部有效私鑰。n C

30、S 格歸約的方法主要是LLL算法和各種改進(jìn)算法。n只要N足夠大（N251），在當(dāng)前CS 格歸約還不能成功。2022-6-957七、橢圓曲線(xiàn)公鑰密碼七、橢圓曲線(xiàn)公鑰密碼ECC1. 簡(jiǎn)要?dú)v史簡(jiǎn)要?dú)v史n橢圓曲線(xiàn)橢圓曲線(xiàn)(Elliptic curve)作為代數(shù)幾何中的重要問(wèn)題已有100多年的研究歷史n1985年，N. Koblitz和V. Miller獨(dú)立將其引入密碼學(xué)中，成為構(gòu)造雙鑰密碼體制的一個(gè)有力工具。n利用有限域GF(2n )上的橢圓曲線(xiàn)上點(diǎn)集所構(gòu)成的群上定義的離散對(duì)數(shù)系統(tǒng)，可以構(gòu)造出基于有限域上離散對(duì)數(shù)的一些雙鑰體制-橢圓曲線(xiàn)離散對(duì)數(shù)密碼體制橢圓曲線(xiàn)離散對(duì)數(shù)密碼體制(ECDLC )，如Dif

31、fie-Hellman，ElGamal，Schnorr，DSA等。n10余年的研究，尚未發(fā)現(xiàn)明顯的弱點(diǎn)。2022-6-958七、橢圓曲線(xiàn)公鑰密碼七、橢圓曲線(xiàn)公鑰密碼ECC橢圓曲線(xiàn)橢圓曲線(xiàn)有限域上滿(mǎn)足方程y2+axy+by=x3+cx2+dx+e的所有點(diǎn)P=(x, y)，加上一個(gè)“無(wú)窮遠(yuǎn)點(diǎn)”，構(gòu)成的集合稱(chēng)為一個(gè)“橢圓曲線(xiàn)”。（其中方程中的常數(shù)a、b、c、d、e需要滿(mǎn)足一些簡(jiǎn)單的條件。）該“橢圓曲線(xiàn)”上的所有點(diǎn)之間可以定義一種特殊的“加法”，記為“+” ：P+Q=R。 “橢圓曲線(xiàn)”上的點(diǎn)關(guān)于此“加法”構(gòu)成交換群（Abel群）。2022-6-959七、橢圓曲線(xiàn)公鑰密碼七、橢圓曲線(xiàn)公鑰密碼ECCn橢圓

32、曲線(xiàn)上一個(gè)點(diǎn)P的k倍表示表示P+P+（k個(gè)點(diǎn)P “相加”），記為kP。n橢圓曲線(xiàn)上一個(gè)點(diǎn)P的所有倍數(shù)點(diǎn)組成了橢圓曲線(xiàn)的子集，該子集是該橢圓曲線(xiàn)關(guān)于該“加法”的循環(huán)子群。n給定“橢圓曲線(xiàn)”上的點(diǎn)P，給定整數(shù)k，計(jì)算“kP=？”是容易的。（折半相加）n給定“橢圓曲線(xiàn)”上的兩個(gè)點(diǎn)P和Q，求整數(shù)“？P=Q”是困難的。這個(gè)問(wèn)題稱(chēng)為橢圓曲線(xiàn)上的離散對(duì)數(shù)問(wèn)題。2022-6-960七、橢圓曲線(xiàn)公鑰密碼七、橢圓曲線(xiàn)公鑰密碼ECC根據(jù)這個(gè)數(shù)學(xué)難題，可以構(gòu)造豐富的公鑰密碼體制，稱(chēng)為橢圓曲線(xiàn)公鑰密碼（ECC，略）。 Certicom 公司對(duì)ECC和RSA進(jìn)行了對(duì)比，在實(shí)現(xiàn)相同的安全性下，ECC 所需的密鑰量比RSA少得多，如下表所示。其中MIPS表示用每秒完成100萬(wàn)條指令的計(jì)算機(jī)所需工作的年數(shù)，m表示ECC的密鑰由2 m點(diǎn)構(gòu)成。以40 MHz的鐘頻實(shí)現(xiàn)155 bits