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

1、2022-6-91第四章：第四章：公鑰密碼一、公鑰密碼的基本概念一、公鑰密碼的基本概念二、公鑰密碼二、公鑰密碼RSA三、背包公鑰密碼三、背包公鑰密碼四、公鑰密碼四、公鑰密碼Rabin五、五、 ElGamal公鑰密碼公鑰密碼六、公鑰密碼六、公鑰密碼NTRU七、橢圓曲線公鑰密碼七、橢圓曲線公鑰密碼ECC八、八、 McEliece公鑰密碼公鑰密碼2022-6-92一、公鑰密碼的基本概念一、公鑰密碼的基本概念雙鑰密碼體制雙鑰密碼體制(公鑰密碼體制公鑰密碼體制) 于1976年由W. Diffie和M. Hellman1976提出，同時R. Merkle1978也獨(dú)立提出了這一體制。可用于保密通信，也可用

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

3、信息后，由f(x)求x是易于實現(xiàn)的。2022-6-94單向函數(shù)舉例單向函數(shù)舉例離散對數(shù)離散對數(shù)DL。給定一大素數(shù)p（比如， p在21024數(shù)量級），p1含另一大素數(shù)因子。稱log2p為素數(shù)p的長度。1, 2, , p-1關(guān)于modp乘法構(gòu)成了一乘群Zp*，它是一個p1階循環(huán)群。該循環(huán)群的生成元一共有(p-1)個。n設(shè)一個生成元為整數(shù)g，1gp1。n設(shè)一個整數(shù)x，1xp1。n設(shè)y滿足y=gxmodp。2022-6-95單向函數(shù)舉例單向函數(shù)舉例已知x，g，p， 求y=gxmodp容易。這是因為，采用折半相乘，只需要不超過2log2p次的modp乘法運(yùn)算。（實際上只需要不超過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滿足y=gxmodp，稱為求解離散對數(shù)問題。記為x=logg y mod p。求解離散對數(shù)問題的“最笨的方法”當(dāng)然就是窮舉，對每一個x0, 1, 2, , p1檢驗是否y=gxmodp。窮舉求解法的運(yùn)算次數(shù)約為( p1)/2。許多求解離散對數(shù)問題的算法比窮舉快得多，比如Shanks算法，Pohlig-Hellman算法等。最快求解法的運(yùn)算次數(shù)約為數(shù)量級)ln)(ln(ln(exp(ppO2022-6-97單向函數(shù)舉例單向函

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

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

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

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

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

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

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

12、轉(zhuǎn)相除法尋找d，滿足ed=1(mod(p-1)(q-1)。n由n的值求解（p，q）的值，即求解n的大整數(shù)分解n=pq，是一個公認(rèn)的數(shù)學(xué)難題（雖然至今并沒有證明），暫時還沒有有效的算法。2022-6-919二、公鑰密碼二、公鑰密碼RSA目前普遍使用的參數(shù)范圍是2511p2512，2511qa1+a2+a3+an；MU；Ua1M；M與U互素，因此可以用輾轉(zhuǎn)相除法計算出U關(guān)于(modM)的逆元U-1。2022-6-928三、背包公鑰密碼三、背包公鑰密碼計算：b1=Ua1(modM)，b2=Ua2(modM) ，b3=Ua3(modM) ，bn=Uan(modM) 。（此時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個物品重量。因為Ua1MUa1(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)是長度為n的比特串。使用公鑰b1，b2，b3，bn計算密文c ：c=m1b1+m2b2+m3b3+mnbn。密文c是一個正整數(shù)。（密文c是背包重量，由n個物品重量b1，b2，b3，bn中的某些物品重量相加而成。若截獲了密文c，又知道n個物品重量b1，b2，b3，bn，求解明文m就是背包問題。 ）2022-6-931三、背包公鑰密碼三、背包公鑰密碼背包公鑰密碼的解密背包公鑰密碼的解密使用私鑰a1，a2，a3，an ， M，U，計算變換課文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個物品重量a1，a2，a3，an中的某些物品重量相加而成。若已知變換課文C ，又知道n個物品重量a1，a2，a3，an，求解明文m就是超遞增背包問題。2022-6-933四、公鑰密碼四、公鑰密碼RabinRabin的密鑰生成的密鑰生成選擇兩個大的素數(shù)p和q，要求p和q都是4的倍數(shù)加3。計算n=pq。Bob的公鑰是n，對外公布。Bob的私鑰是（p，q），自己私藏。2022-6-934四、公鑰密碼四、公鑰密碼RabinRabinRabin的加密過程的加

16、密過程Alice欲發(fā)送明文m給Bob，其中0mn 。Alice用Bob的公鑰n，計算：c=m2(modn)。c為密文。2022-6-935四、公鑰密碼四、公鑰密碼RabinRabinRabin的解密過程的解密過程Bob 收到密文c后，用自己的私鑰（p，q）計算).(mod);(mod4141qcmpcmpqpp2022-6-936四、公鑰密碼四、公鑰密碼Rabin計算4個數(shù)m(1,1)， m(1,2)， m(2,1)， m(2,2)，滿足：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個數(shù)的計算使用孫子定理（中國剩余定理）。）于是，真正的明文m一定就是4個數(shù)m(1,1)， m(1,2)， m(2,1)， m(2,2)之中的一個。觀察4個數(shù)，排除那些沒有意義的“亂碼課文”。哪個是有意義的課文，哪個就是真正的明文m。解密完畢。2022-6-938四、公鑰密碼四、公鑰密碼RabinRabinRabin的解密原理的解密原理因為n

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

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

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

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

22、文c后，用自己的私鑰x計算m=y2/y1x=myk/gkx=mgxk/gxk modp 。特點特點：密文由明文和所選隨機(jī)數(shù)k來定，因而是非確定性非確定性加密，一般稱之為隨機(jī)化隨機(jī)化加密，對同一明文由于不同時刻的隨機(jī)數(shù)k不同而給出不同的密文。代價是使數(shù)據(jù)擴(kuò)展一倍。安全性：安全性：基于離散對數(shù)的困難性。2022-6-946六、公鑰密碼六、公鑰密碼NTRUNTRU的密鑰生成的密鑰生成要用到三個公開參數(shù)(N, q, p)，其中N是正整數(shù)，p是小的奇素數(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選擇兩個多項式f(x)和g(x)， 滿足：它們的次數(shù)均不超過N-1，它們的系數(shù)均屬于0, 1 。n分別驗證f(x)和g(x)關(guān)于(modp, modxN-1)和(modq, modxN-1) 是否可逆。2022-6-948六、公鑰密碼六、公鑰密碼NTRUn如果可逆，則計算f(x)-1(modp, modxN-1)，h(x)=f(x)-1g(x) (modq,

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

25、。2022-6-950六、公鑰密碼六、公鑰密碼NTRUNTRU的解密過程的解密過程Bob計算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ù)相對于q很小，因此希望pg(x)r(x)+f(x)m(x) (modxN-1)的每個系數(shù)都不超出區(qū)間(-q/2, q/2。若果真如此，則d(x)=pg(x)r(x)+f(x)m(x) (modxN-1)。（無modq ）2022-6-951六、公鑰密碼六、公鑰密碼NTRU（若果真如此，） Bob繼續(xù)計算f(x)-1d(x) (modp, m

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

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

29、私鑰對r(x), m(x) 成功解密。nt(x), s(x)的“尺寸”越小， t(x), s(x)能夠成功解密的r(x), m(x) 越多。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)成了一個格，稱為CS格。n真正的私鑰g(x), f(x)屬于此CS格。nCS 格歸約被用來尋找“尺寸”足夠小的t(x), s(x) ，來作為NTRU的有效私鑰或局部有效私鑰。n C

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

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

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