5.1公鑰密碼體制的基本原理5.2背包算法5.3RSA算法*5.4Rabin算法5.5ElGamal算法5.6橢圓曲線算法習(xí)題5.1公鑰密碼體制的基本原理5.1.1公鑰密碼的基本思想運(yùn)用諸如DES等經(jīng)典密碼系統(tǒng)進(jìn)行保密通信時(shí)，通信雙方必須擁有一個(gè)共享的秘密密鑰來實(shí)現(xiàn)對(duì)消息的加密和解密，而密鑰具有的機(jī)密性使得通信雙方如何獲得一個(gè)共同的密鑰變得非常困難。通常采用人工傳送的方式分配各方所需的共享密鑰，或借助一個(gè)可靠的密鑰分配中心來分配所需要的共享密鑰。但在具體實(shí)現(xiàn)過程中，這兩種方式都面臨很多困難，尤其是在計(jì)算機(jī)網(wǎng)絡(luò)化時(shí)代更為困難。

1976年兩位美國密碼學(xué)者W.Diffie和M.Hellman在該年度的美國國家計(jì)算機(jī)會(huì)議上提交了一篇名為“密碼學(xué)的新方向（NewDirectionsinCryptography）”的論文，文中首次提出了公鑰密碼體制的新思想，它為解決傳統(tǒng)經(jīng)典密碼學(xué)中面臨的諸多難題提供了一個(gè)新的思路。其基本思想是把密鑰分成兩個(gè)部分：公開密鑰和私有密鑰（簡稱公鑰和私鑰），分別用于消息的加密和解密。公鑰密碼體制又被稱為雙鑰密碼體制（AsymmetricCryptographySystem，非對(duì)稱密碼體制），與之對(duì)應(yīng)，傳統(tǒng)的經(jīng)典密碼體制被稱為單鑰密碼體制（SymmetricCryptographySystem，對(duì)稱密碼體制）。公鑰密碼體制中的公開密鑰可被記錄在一個(gè)公共數(shù)據(jù)庫里或者以某種可信的方式公開發(fā)放，而私有密鑰必須由持有者妥善地秘密保存。這樣，任何人都可以通過某種公開的途徑獲得一個(gè)用戶的公開密鑰，然后進(jìn)行保密通信，而解密者只能是知道相應(yīng)私鑰的密鑰持有者。用戶公鑰的這種公開性使得公鑰體制的密鑰分配變得非常簡單，目前常用公鑰證書的形式發(fā)放和傳遞用戶公鑰(見7.3節(jié))，而私鑰的保密專用性決定了它不存在分配的問題(但需要用公鑰來驗(yàn)證它的真實(shí)性，以防止欺騙)。公鑰密碼算法的最大特點(diǎn)是采用兩個(gè)具有一一對(duì)應(yīng)關(guān)系的密鑰對(duì)k=(pk，sk)使加密和解密的過程相分離。當(dāng)兩個(gè)用戶希望借助公鑰體制進(jìn)行保密通信時(shí)，發(fā)信方Alice用收信方Bob的公開密鑰pk加密消息并發(fā)送給接收方，而接收方Alice使用與公鑰相對(duì)應(yīng)的私鑰sk進(jìn)行解密。根據(jù)公、私鑰之間嚴(yán)格的一一對(duì)應(yīng)關(guān)系，只有與加密時(shí)所用公鑰相對(duì)應(yīng)的用戶私鑰才能夠正確解密，從而恢復(fù)出正確的明文。由于這個(gè)私鑰是通信中的收信方獨(dú)有的，其他用戶不可能知道，因此只有該收信方Bob才能正確地恢復(fù)出明文消息，其他有意或無意獲得消息密文的用戶都不能解密出正確的明文，達(dá)到了保密通信的目的。圖5-1給出了公鑰密碼體制的基本流程。圖5-1公鑰密碼體制的基本流程5.1.2公鑰密碼算法應(yīng)滿足的要求

基于圖5-1給出的公鑰密碼體制的基本流程，一個(gè)實(shí)際可用的公鑰密碼體制(M，C，K，E，D)的基本要求如下：

(1)對(duì)于K中的每一個(gè)公私鑰對(duì)k=(pk，sk)，都存在E中的一個(gè)加密變換Epk:M→C和D中的一個(gè)解密變換Dsk:C→M，使得任意明文消息m∈M都能找到一個(gè)惟一的c∈C滿足c=Epk［m］，且m=Dsk［c］=Dsk［Epk［m］］；

(2)對(duì)于任意的公私鑰對(duì)k=(pk，sk)∈K，加密變換Epk和解密變換Dsk都是多項(xiàng)式時(shí)間可計(jì)算的函數(shù)，但由加密變換Epk推出解密變換Dsk在計(jì)算上是不可行的，或者說在知道公鑰pk的情況下推知私鑰sk是計(jì)算上不可行的。由上面的基本要求可以看出，公鑰密碼體制的核心在于加密變換與解密變換的設(shè)計(jì)。在密碼算法中，加解密變換是互逆的，但條件(2)說明在公鑰密碼體制中加解密變換不能簡單地直接互推。上述條件表明公鑰密碼體制的加解密變換類似于陷門單向函數(shù)，因此可以利用陷門單向函數(shù)來構(gòu)造公鑰密碼體制。所謂的陷門單向函數(shù)是一個(gè)可逆函數(shù)f(x)，滿足對(duì)于定義域中的任何x，計(jì)算函數(shù)值y=f(x)都是容易的，但對(duì)幾乎所有的x要由y=f(x)求x在計(jì)算上不可行(即使已經(jīng)知道函數(shù)f(x))，除非知道某些輔助信息(稱為陷門信息)。這里所說的“容易計(jì)算”是指函數(shù)值能在其輸入長度的多項(xiàng)式時(shí)間內(nèi)計(jì)算出來，比如若輸入長度為n比特，求函數(shù)值的計(jì)算時(shí)間是na的某個(gè)倍數(shù)，則稱此函數(shù)是容易計(jì)算的，否則就是不可行的，這里a是一個(gè)固定常數(shù)。針對(duì)公鑰密碼體制(M，C，K，E，D)的基本要求，一個(gè)可行的公鑰密碼算法應(yīng)該滿足如下要求：

(1)接收方Bob產(chǎn)生密鑰對(duì)k=(pkB，skB)在計(jì)算上是容易的；

(2)發(fā)送方Alice用收信方Bob的公鑰pkB加密消息m產(chǎn)生密文

在計(jì)算上是容易的；

(3)接收方Bob用自己的私鑰skB解密密文c，還原明文消息

在計(jì)算上是容易的；

(4)不僅攻擊者由密文c和Bob的公鑰pkB恢復(fù)明文m是計(jì)算上不可行的，而且攻擊者由Bob的公鑰pkB求解對(duì)應(yīng)的私鑰skB也是計(jì)算上不可行的；

(5)一般情況下，加解密的次序可交換，即

。公鑰密碼體制的思想完全不同于單鑰密碼體制，公鑰密碼算法的基本操作不再是單鑰密碼體制中使用的代換和置換，公鑰密碼體制通常將其安全性建立在某個(gè)尚未解決(且尚未證實(shí)能否有效解決)的數(shù)學(xué)難題的基礎(chǔ)上，并經(jīng)過精心設(shè)計(jì)來保證其具有非常高的安全性。公鑰密碼算法以非對(duì)稱的形式使用兩個(gè)密鑰，不僅能夠在實(shí)現(xiàn)消息加/解密基本功能的同時(shí)簡化了密鑰分配任務(wù)，而且還對(duì)密鑰協(xié)商與密鑰管理、數(shù)字簽名與身份認(rèn)證等密碼學(xué)問題產(chǎn)生了深刻的影響?？梢哉f公鑰密碼思想為密碼學(xué)的發(fā)展提供了新的理論和技術(shù)基礎(chǔ)，是密碼學(xué)發(fā)展史上的一次革命。下面分別給出常用公鑰密碼算法：背包算法、RSA公鑰算法、Rabin算法、ElGamal算法、橢圓曲線密碼的原理和算法分析。5.2背包算法當(dāng)W.Diffie和M.Hellman提出公鑰密碼體制的設(shè)想時(shí)，并沒有給出一個(gè)具體的實(shí)例。直到兩年后的1978年，由R.Merkle和M.Hellman給出了第一個(gè)公鑰密碼算法，這就是基于組合數(shù)學(xué)中背包問題(或者說是子集和問題)的背包公鑰密碼算法，也稱為MH背包算法，簡稱背包算法。5.2.1背包問題

在組合數(shù)學(xué)中有一個(gè)背包問題：假設(shè)有一堆物品，體積各不相同，問能否從這堆物品中找出幾個(gè)正好裝滿一個(gè)給定容量的背包？(假定物品之間不留空隙)

記物品的體積分別為v1，v2，…，vn，背包的容量為C，則背包問題可表示為

b1v1+b2v2+…+bnvn=C

其中，bi(i=1，2，…，n)等于1或者0。bi=1表示第i個(gè)物品在背包中，bi=0表示第i個(gè)物品不在背包中，稱物品體積的序列(v1，v2，…，vn)為背包向量。理論上講，通過檢查背包向量V的所有子集，計(jì)算出每個(gè)子集的元素之和，總可找出一個(gè)子集作為背包問題的解，因此背包問題又稱為子集和問題。然而長度為n的背包向量V的全體子集共有2n個(gè)，當(dāng)n很大時(shí)，對(duì)全部2n個(gè)子集進(jìn)行窮舉式搜索是不可能的。事實(shí)上，背包問題是一類NP完全(NPC)問題，而目前還沒有發(fā)現(xiàn)比窮舉式搜索更好的NPC問題求解方法。幸運(yùn)的是并非所有的背包問題都沒有有效算法，有一類特殊的背包問題是容易求解的，這就是超遞增背包問題。設(shè)V=(v1，v2，…，vn)是一個(gè)背包向量，若V滿足

即V中每一項(xiàng)都大于它前面所有項(xiàng)之和，則稱V是一個(gè)超遞增向

量，或者稱序列v1，v2，…，vn是一個(gè)超遞增序列，以V為背包向量的背包問題被稱做超遞增背包問題。比如，序列1，2，4，…，2n就是一個(gè)超遞增序列。超遞增背包問題的解很容易通過以下過程找到：設(shè)背包容量為C，從右向左(從大到小)依次檢查超遞增背包向量V中的每個(gè)元素，以確定問題的解。若C≥vn，則vn在解中，對(duì)應(yīng)的bn應(yīng)為1，并將C的值更新為C-vn；否則如果C<vn，則vn不在解中，對(duì)應(yīng)的bn應(yīng)為0，C的值保持不變。然后對(duì)vn-1，vn-2，…，v2，v1依次重復(fù)上述過程，并判斷C是否減少到0。若C最終變成0，則問題的解存在，否則解不存在。

例5.1

設(shè)V=(1，2，4，8，16，32)，C=43，那么求解

超遞增序列的過程如下：

C=43>32，得b6=1，更新C為43-32=11；

C=11<16，得b5=0；

C=11>8，得b4=1，更新C為11-8=3；

C=3<4，得b3=0；

C=3>2，得b2=1，更新C為3-2=1；

C=1得b1=1，最后C減小到0。

所以問題的解為110101。超遞增背包問題是很容易求解的。下面給出利用數(shù)論中的模乘運(yùn)算將超遞增序列變?yōu)榉浅f增序列的方法。選擇滿足如下條件的模數(shù)k和乘數(shù)t：

即t與k互素，確保t在模k下的乘法逆元t-1存在。令

U≡tVmodk≡t(v1，v2，…，vn)modk

=(tv1modk，tv2modk，…，tvnmodk)

那么U是一個(gè)非超遞增向量。5.2.2背包算法的描述

借助于背包問題中的超遞增向量和相應(yīng)的非超遞增向量，可以構(gòu)造一個(gè)公鑰密碼算法：背包算法。具體如下：私有密鑰設(shè)置為將一個(gè)超遞增向量V轉(zhuǎn)換為非超遞增向量U的參數(shù)t、t-1和k，公開密鑰設(shè)置為非超遞增向量U。具體的加/解密過程如下：

(1)加密變換：首先將二進(jìn)制明文消息劃分成長度與非超遞增向量U長度相等的明文分組b1b2…bn；然后計(jì)算明文分組向量B=(b1,b2,…,bn)與非超遞增向量U=(u1,u2,…,un)的內(nèi)積B·U=b1u1+b2u2+…+bnun，所得結(jié)果為密文。

(2)解密變換：先還原出超遞增背包向量V=t-1Umodk

≡t-1tVmodk，再將密文B·U模k乘以t-1的結(jié)果作為超遞增背包問題的背包容量，求解超遞增背包問題，得到消息明文。

例5.2

設(shè)V=(1，3，7，13，26，65，119，267)是一個(gè)超遞增背包向量，取模數(shù)k=523，乘數(shù)t=467，則t-1=28mod523。對(duì)V模k乘以t，計(jì)算出公鑰：

U≡t×Vmodk≡467×(1,3,7,13,26,65,119,267)mod523

≡(467,355,131,21,135,215)

并對(duì)外公布U。假設(shè)發(fā)送方有一明文消息m=10101100，用公鑰U對(duì)m加密得到密文：

c=m×U=(1,0,1,0,1,1,0,0)×(467,355,131,318,113,21,135,215)

=467+131+113+21

=732

接收方利用公鑰U與私鑰t-1和k還原出超遞增背包V，對(duì)密文c=732模k乘以t-1，得到c×t-1modk≡732×28mod523≡20496mod523=99

以99作為背包的容量去解超遞增背包問題：由99<267得m8=0；由99<119得m7=0；由99>65得m6=1；由99-65=34>26得m5=1；由34-26=8<13得m4=0；由8>7得m3=1；由8-7=1<3得m2=0，m1=1。解密得到明文分組為10101100，即為原來的m。

要解決類似例5.2這樣的背包向量僅有8個(gè)分量的背包問題并不困難，甚至對(duì)非超遞增的背包向量也是如此。但實(shí)用的背包向量至少應(yīng)包含250個(gè)以上的分量，每個(gè)分量的大小一般要在200到400位，模數(shù)也應(yīng)在100到200位之間。這些值可以使用隨機(jī)序列發(fā)生器來生成。對(duì)于這樣的背包算法，試圖用窮舉式搜索攻擊來破譯是無用的。5.2.3背包算法的安全性

背包算法利用難解的一般背包問題作為公開密鑰，可以方便地對(duì)明文進(jìn)行加密；而私有密鑰則利用易解的超遞增背包問題給出一個(gè)解密的簡單方法。那些不知道私鑰的攻擊者要想破譯密文就不得不求解一個(gè)困難的背包問題，這在計(jì)算上看似是不可行的。背包算法提出兩年后即被破解。破解的基本思想是不必找出真正的模數(shù)k和乘數(shù)t，也不用窮舉式搜索背包向量的所有子集，而是找出一對(duì)任意的k′和t′，使得用公開的背包向量U模k′乘t′后能得到一個(gè)超遞增向量。究其原因是Merkle-Hellman背包體制的公開密鑰是由超遞增向量變換而來的，雖然經(jīng)過模乘置亂，但超遞增向量內(nèi)在的規(guī)律性并不能完全被隱藏，這就給攻擊者留下了可乘之機(jī)。隨后Merkle又提出了多次迭代背包體制，但最終也被破解。1984年Brickell最終證明了Merkle-Hellman背包體制的不安全性，并發(fā)現(xiàn)了一種算法可將難解的背包問題轉(zhuǎn)化為易解的背包問題。背包算法是第一個(gè)使公鑰密碼體制成為現(xiàn)實(shí)的密碼算法，它說明了如何將數(shù)學(xué)難題應(yīng)用于公鑰密碼算法的設(shè)計(jì)。背包體制的優(yōu)勢是加解密速度很快，但它存在的不安全性使其不能用于商業(yè)目的。5.3RSA算法數(shù)論里有一個(gè)大數(shù)分解問題：計(jì)算兩個(gè)素?cái)?shù)的乘積非常容易，但分解該乘積卻異常困難，特別是在這兩個(gè)素?cái)?shù)都很大的情況下?；谶@個(gè)事實(shí)，1978年美國MIT的三名數(shù)學(xué)家R.Rivest，A.Shamir和L.Adleman提出了著名的公鑰密碼體制：RSA算法。該算法以兩個(gè)大素?cái)?shù)的乘積作為算法的公鑰來加密消息，而密文的解密必須知道相應(yīng)的兩個(gè)大素?cái)?shù)。迄今為止，RSA算法是思想最簡單、分析最透徹、應(yīng)用最廣泛的公鑰密碼體制。RSA算法非常容易理解和實(shí)現(xiàn)，經(jīng)受住了密碼分析，密碼分析者既不能證明也不能否定它的安全性，這恰恰說明了RSA具有一定的可信度。5.3.1RSA算法的描述

基于大數(shù)分解問題，為了產(chǎn)生公、私鑰，首先獨(dú)立地選取兩個(gè)大素?cái)?shù)p和q(注：為了獲得最大程度的安全性，選取的p和q的長度應(yīng)該差不多，都應(yīng)為長度在100位以上的十進(jìn)制數(shù)字)。

計(jì)算

n=p×q

和φ(n)=φ(p)φ(q)=(p-1)(q-1)

這里φ(n)表示n的歐拉函數(shù)，即φ(n)為比n小且與n互素的正整數(shù)的個(gè)數(shù)。隨機(jī)選取一個(gè)滿足1<e<φ(n)且gcd(e，φ(n))=1的整數(shù)e，那么e存在模φ(n)下的乘法逆元d=e-1modφ(n)，d可由擴(kuò)展的歐幾里得算法求得(附錄A)。

這樣由p和q獲得了三個(gè)參數(shù)：n、e、d。在RSA算法里，以n和e作為公鑰，d作為私鑰(注：p和q不再需要，可以銷毀，但一定不能泄露)。具體的加/解密過程如下：

(1)加密變換：先將消息劃分成數(shù)值小于n的一系列數(shù)據(jù)分組，即以二進(jìn)制表示的每個(gè)數(shù)據(jù)分組的比特長度應(yīng)小于lbn。然后對(duì)每個(gè)明文分組m進(jìn)行如下的加密變換來得到密文c：

c=memodn

(2)解密變換：m=cdmodn。

命題5.3.1RSA算法中的解密變換m=cdmodn是正確的。

證明：數(shù)論中的歐拉定理指出，如果兩個(gè)整數(shù)a和b互素，那么aφ(b)≡1modb。

在RSA算法中，明文m必與兩個(gè)素?cái)?shù)p和q中至少一個(gè)互素。不然的話，若m與p和q都不互素，那么m既是p的倍數(shù)也是q的倍數(shù)，于是m也是n的倍數(shù)，這與m<n矛盾。

由de≡1modφ(n)可知，存在整數(shù)k使得de=kφ(n)+1。下面分兩種情形來討論：

情形一：m僅與p、q二者之一互素，不妨假設(shè)m與p互素且與q不互素，那么存在整數(shù)a使得m=aq，由歐拉定理可知

mkφ(n)modp≡mkφ(p)φ(q)modp≡(mφ(p))kφ(q)modp≡1modp

于是存在一個(gè)整數(shù)t使得mkφ(n)=tp+1。給mkφ(n)=tp+1兩邊同乘以m=aq得到

mkφ(n)+1=tapq+m=tan+m

由此得cd=med=mkφ(n)+1=tan+m≡mmodn。情形二：如果m與p和q都互素，那么m也和n互素，有

cd=med=mkφ(n)+1=m×mkφ(n)

mmodn

RSA算法實(shí)質(zhì)上是一種單表代換系統(tǒng)。給定模數(shù)n和合法的明文m，其相應(yīng)的密文為c=memodn且對(duì)于m′≠m必有c′≠c。RSA算法的關(guān)鍵在于當(dāng)n極大時(shí)，在不知道陷門信息的情況下，很難確定明文和密文之間的這種對(duì)應(yīng)關(guān)系。

例5.3

選取p=5，q=11，則n=55且φ(n)=40，明文分組應(yīng)取為1到54的整數(shù)。如果選取加密指數(shù)e=7，則e滿足1<e<φ(n)且與φ(n)互素，于是解密指數(shù)為d=23。假如有一個(gè)消息m=53197，分組可得m1=53，m2=19，m3=7。分組加密得到密文的解密為

最后恢復(fù)出明文m=53197。5.3.2RSA算法的安全性

RSA算法的安全性完全依賴于對(duì)大數(shù)分解問題困難性的推測，但面臨的問題是迄今為止還沒有證明大數(shù)分解問題是一類NP問題。為了抵抗窮舉攻擊，RSA算法采用了大密鑰空間，通常模數(shù)n取得很大，e和d也取為非常大的自然數(shù)，但這樣做的一個(gè)明顯缺點(diǎn)是密鑰產(chǎn)生和加/解密過程都非常復(fù)雜，系統(tǒng)運(yùn)行速度比較慢。與其他的密碼體制一樣，嘗試每一個(gè)可能的d來破解是不現(xiàn)實(shí)的。那么分解模數(shù)n就成為最直接的攻擊方法。只要能夠分解n就可以求出φ(n)，然后通過擴(kuò)展的歐幾里得算法可以求得加密指數(shù)e模φ(n)的逆d，從而達(dá)到破解的目的。目前還沒有找到分解大整數(shù)的有效方法，但隨著人們計(jì)算能力的不斷提高和計(jì)算成本的不斷降低，許多被認(rèn)為是不可能分解的大整數(shù)已被成功分解。例如模數(shù)為129位十進(jìn)制數(shù)字的RSA-129已于1994年4月在Internet上通過分布式計(jì)算被成功分解出一個(gè)64位和一個(gè)65位的因子。更困難的RSA-130也于1996年被分解出來，緊接著RSA-154也被分解，據(jù)報(bào)導(dǎo)158位的十進(jìn)制整數(shù)也已被分解，這意味著512比特模數(shù)的RSA已經(jīng)不安全了。更危險(xiǎn)的安全威脅來自于大數(shù)分解算法的改進(jìn)和新算法的不斷提出。當(dāng)年破解RSA-129采用的是二次篩法，而破解RSA-130使用的算法稱為推廣的數(shù)域篩法，該算法使破解RSA-130的計(jì)算量僅比破解RSA-129多10%。盡管如此，密碼專家們認(rèn)為一定時(shí)期內(nèi)1024到2048比特模數(shù)的RSA還是相對(duì)安全的。

除了對(duì)RSA算法本身的攻擊外，RSA算法還面臨著攻擊者對(duì)密碼協(xié)議的攻擊，即利用RSA算法的某些特性和實(shí)現(xiàn)過程對(duì)其進(jìn)行攻擊。下面介紹一些攻擊方法。

1.共用模數(shù)攻擊

在RSA的實(shí)現(xiàn)中，如果多個(gè)用戶選用相同的模數(shù)n，但有不同的加解密指數(shù)e和d，這樣做會(huì)使算法運(yùn)行起來更簡單一些，但卻是不安全的。假設(shè)一個(gè)消息用兩個(gè)不同的加密指數(shù)加密且共用同一個(gè)模數(shù)，如果這兩個(gè)加密指數(shù)互素(一般情況下都這樣)，則不需要知道解密指數(shù)，任何一個(gè)加密指數(shù)都可以恢復(fù)明文。理由如下：

設(shè)e1和e2是兩個(gè)互素的加密密鑰，共用的模數(shù)為n。對(duì)同一個(gè)明文消息m加密得

。攻擊者知道n、e1、e2、c1和c2，他可以用如下方法恢復(fù)出明文m。由于e1和e2互素，由擴(kuò)展的歐幾里德算法可找到滿足re1+se2=1的r和s。由此可得

明文消息m被恢復(fù)出來。(注意：r和s必有一個(gè)為負(fù)整數(shù)，上述計(jì)算需要用擴(kuò)展的歐幾里德算法算出c1或者c2在模n下的逆)

2.低加密指數(shù)攻擊

較小的加密指數(shù)e可以加快消息加密的速度，但太小的e會(huì)影響RSA系統(tǒng)的安全性。在多個(gè)用戶采用相同的加密密鑰e和不同的模數(shù)n的情況下，如果將同一個(gè)消息(或者一組線性相關(guān)的消息)分別用這些用戶的公鑰加密，那么利用中國剩余定理可以恢復(fù)出明文。舉例來說，取e=3，三個(gè)用戶的不同模數(shù)分別是n1、n2和n3，將消息x用這三組密鑰分別加密為

y1=x3modn1，y2=x3modn2，y3=x3modn3

一般來講，應(yīng)選n1、n2和n3互素，以避免通過求出它們的公因子的方式導(dǎo)致模數(shù)被分解。根據(jù)中國剩余定理，可由y1、y2和y3求出

y=x3modn1n2n3

由于x<n1，x<n2，x<n3，因此x3<n1n2n3，于是。

已經(jīng)證明只要k>e(e+1)/2，將k個(gè)線性相關(guān)的消息分別使用k個(gè)加密指數(shù)相同而模數(shù)不同的加密密鑰加密，則低加密指數(shù)攻擊能夠奏效；如果消息完全相同，那么e個(gè)加密密鑰就夠了。因此，為了抵抗這種攻擊，加密指數(shù)e必須足夠大。對(duì)于較短的消息則要進(jìn)行獨(dú)立的隨機(jī)數(shù)填充，破壞明文消息的相關(guān)性，以防止低加密指數(shù)攻擊。

3.中間相遇攻擊

指數(shù)運(yùn)算具有可乘性，這種可乘性有可能招致其他方式的攻擊。事實(shí)上，如果明文m可以被分解成兩項(xiàng)之積m=m1×m2，那么

這意味著明文的分解可導(dǎo)致密文的分解，明文分解容易使得密文分解也容易。密文分解容易將導(dǎo)致中間相遇攻擊，攻擊方法描述如下。

假設(shè)c=memodn，攻擊者知道m(xù)是一個(gè)合數(shù)，且滿足m<2l，m=m1×m2，m1和m2都小于2l/2。那么，由RSA的可乘性，有

。攻擊者可以先創(chuàng)建一個(gè)有序的序列

然后，攻擊者搜索這個(gè)有序的序列，嘗試從中找到兩項(xiàng)ie和je滿足

攻擊者能在步操作之內(nèi)找到ie和je，由此獲得明文m=i×j。攻擊者的空間代價(jià)是需要能夠提供比特的存儲(chǔ)空間，時(shí)間代價(jià)的復(fù)雜度為，明顯小于O(2l)，與平方根量級(jí)約化相當(dāng)。在明文消息的長度為40～60比特的情況時(shí)，明文可被分解成兩個(gè)大小相當(dāng)?shù)恼麛?shù)的概率為18%～50%。舉例來說，假設(shè)用1024比特模數(shù)的RSA加密一個(gè)長度為56的比特串，如果能夠提供228×1024=238比特(約為32GB)的存儲(chǔ)空間，經(jīng)過229次模指數(shù)運(yùn)算，就可以有很大的把握找出明文比特串，它是兩個(gè)28比特的整數(shù)之積。這種空間和時(shí)間的代價(jià)由一臺(tái)普通的個(gè)人計(jì)算機(jī)就足夠了。這說明用RSA直接加密一些比較短的比特串(如DES等單鑰體制的密鑰或者長度小于64比特的系統(tǒng)口令等)是非常危險(xiǎn)的。5.3.3RSA算法的參數(shù)選擇

1.模數(shù)n的確定

首先，多用戶之間共用模數(shù)會(huì)招致共用模數(shù)攻擊，因此不能在多個(gè)用戶之間共用模數(shù)。

其次，模數(shù)n是兩個(gè)大素?cái)?shù)p和q的乘積，因此n的確定問題可轉(zhuǎn)化為如何恰當(dāng)?shù)剡x擇p和q。p和q除了要足夠大(至少100位以上的十進(jìn)制整數(shù))以外，還應(yīng)滿足如下要求:

(1)p和q應(yīng)為強(qiáng)素?cái)?shù)；

(2)p與q之差要合適；

(3)p-1與q-1的最大公因子要小。若一個(gè)素?cái)?shù)p稱為強(qiáng)素?cái)?shù)或一級(jí)素?cái)?shù)，則p滿足下列條件：

a)存在兩個(gè)大素?cái)?shù)p1和p2，使得p1|(p-1)，p2|(p+1)；

b)存在四個(gè)大素?cái)?shù)r1，s1，r2和s2，使得r1|(p1-1)，s1|(p1+1)，r2|(p2-1)，s2|(p2+1)。

稱p1和p2為2級(jí)素?cái)?shù)；r1，s1，r2和s2為3級(jí)素?cái)?shù)。

為什么要采用強(qiáng)素?cái)?shù)？這是因?yàn)閜和q的取值會(huì)影響分解模數(shù)n的困難性。若p或q不是強(qiáng)素?cái)?shù)，則可通過下面的方法分解模數(shù)n。其中pi為素?cái)?shù)，ai為正整數(shù)(i=1，2，…，k)。如果pi都很小，不妨設(shè)pi<A(A為已知的小整數(shù))，構(gòu)造

其中，a≥max{ai}，顯然有(p-1)|R。假設(shè)p-1有k個(gè)素因子，由算術(shù)基本定理可得,因?yàn)槿我庑∮谒財(cái)?shù)p的正整數(shù)t均與p互素，不妨設(shè)t=2，由歐拉定理可知

tφ(p)=2φ(p)=2(p-1)≡1modp

因而tR=2R≡1modp。計(jì)算X=tRmodn=2Rmodn，若X=1，則令t=3重新計(jì)算X，直到算出的X≠1。此時(shí)由gcd(X-1，n)=p，得到n的分解因子p和q。

對(duì)于q也可以類似討論。因此p-1和q-1必須有大素?cái)?shù)因子，即p和q要為強(qiáng)素?cái)?shù)。如果p與q之差很小，則由(p+q)2-(p-q)2=4pq=4n可得(p+q)2-4n=(p-q)2是一個(gè)小的平方數(shù)，所以(p+q)/2與近似。令u=(p+q)/2，v=(p-q)/2，可以從大于的整數(shù)依次嘗試u且，從而解出p與q。

盡管要求p與q之差不能太小，但二者之差也不能很大。如果很大，則其中一個(gè)必然較小，那么可以從一個(gè)小的素?cái)?shù)開始依次嘗試，最終分解n。因此，p與q之差要適當(dāng)，一般是長度

相差幾個(gè)比特。要求p-1與q-1的最大公因子要小是為了防止迭代攻擊。假設(shè)攻擊者截獲了密文c=memodn，可以進(jìn)行如下的迭代攻擊。記

如果存在t使得etmodφ(n)=1，則有整數(shù)k使et=kφ(n)+1，那么由歐拉定理可知與此同時(shí)還有

所以

因而

如果t較小，則這種迭代攻擊很容易成功。

由歐拉定理可知t=φ(φ(n))=φ((p-1)(q-1))，若p-1與q-1的最大公因子較小，則t較大，如果t大到(p-1)(q-1)的一半，則迭代攻擊難以奏效。

2.加密密鑰e的選取

加密密鑰e要滿足以下幾個(gè)要求：

(1)e要與模數(shù)n的歐拉函數(shù)值φ(n)互素，即gcd(e，φ(n))＝1，否則無法計(jì)算解密密鑰d。這一要求容易滿足，現(xiàn)在已經(jīng)證明兩個(gè)隨機(jī)數(shù)互素的概率約為3/5。

(2)e不能太小，否則容易遭受低加密指數(shù)攻擊。另外，如果e和m都很小且滿足me<n，此時(shí)密文c=memodn不需要經(jīng)過模運(yùn)算可直接得到，這樣由c開e次方可得明文m。

(3)e在模數(shù)φ(n)下的階要足夠大，即滿足etmodφ(n)=1的最小正整數(shù)t要盡可能大，一般應(yīng)達(dá)到(p-1)(q-1)/2。

3.解密密鑰d的選取

加密密鑰e選定之后，利用擴(kuò)展的歐幾里德算法可以求出解密密鑰d。類似于對(duì)加密密鑰e的要求，解密密鑰d也不能太小，否則容易遭受已知明文攻擊。

如果對(duì)明文m加密得到密文c，在解密密鑰d很小的情況下，從某個(gè)正整數(shù)開始依次嘗試，直接找出一個(gè)數(shù)t滿足ctmodn=m，那么這個(gè)t就是解密密鑰d。另外，Wiener于1990年利用連分?jǐn)?shù)理論證明了當(dāng)解密密鑰d小于時(shí)很容易分解模數(shù)n，然后可求出解密密鑰d。因此，一般要求d不能小于。5.4Rabin算法5.4.1求解數(shù)模下的平方根問題

定理5.4.1

假定n是大于1的奇數(shù)，且有如下分解

其中，pi是互不相同的素?cái)?shù);ei是正整數(shù)。對(duì)于與n互素的整數(shù)a，如果a是模pi的平方剩余且對(duì)所有的i=1，2，…，l都成立，那么同余方程x2≡amodn存在2l個(gè)模n的解。

證明：根據(jù)已知條件，由同余理論可知同余方程x2≡amodn等價(jià)于同余方程組

因此，問題轉(zhuǎn)化為求解上述的同余方程組。

對(duì)所有的i=1，2，…，l，由a是模pi的平方剩余可知同余方程x2≡amod有兩個(gè)模的解，分別記為

和。這樣可以得到一系列的一次同余方程組

其中，bi可取bi，1或者bi，2。由中國剩余定理可知每一個(gè)這樣的一次同余方程組都有惟一的模n解。由于每個(gè)bi可取bi，1和bi，2之一，因此可以產(chǎn)生2l個(gè)不同的(b1，…，bl)，即共有2l個(gè)不同的一次同余方程組。所以同余方程組(i=1，2，…,l)共有2l個(gè)模n的解，即原同余方程x2≡amodn存在2l個(gè)模n的解。

命題5.4.1

如果素?cái)?shù)p≡3(mod4)，a是模p的平方剩余，那么a模p的平方根是±a(p+1)/4modp。

證明：根據(jù)a是模p的平方剩余，由Euler準(zhǔn)則可知a

(p-1)/2modp=1。于是

(±a(p+1)/4)2modp≡a(p+1)/2modp≡a×a(p-1)/2modp≡amodp5.4.2Rabin算法描述

對(duì)于RSA算法，如果能夠成功分解模數(shù)n，則可攻破RSA系統(tǒng)。因此，攻擊RSA算法的難度不會(huì)超過大整數(shù)的分解，但它是否等價(jià)于大整數(shù)的分解，目前還不知道。本節(jié)討論的Rabin算法既可看成是RSA算法的一個(gè)特例，也可以看成是對(duì)RSA算法的一個(gè)修正。Rabin算法是一個(gè)被證明其破解難度正好等價(jià)于大整數(shù)分解的公鑰密碼算法，它也是第一個(gè)可證明安全的公鑰密碼算法。

Rabin算法的安全性基于求解合數(shù)模下的平方根的困難性。Rabin算法的基本框架類似于RSA，也是依賴于以兩個(gè)大素?cái)?shù)之積為模數(shù)的模指數(shù)運(yùn)算，但Rabin算法對(duì)模數(shù)的選擇和加解密模指數(shù)運(yùn)算提出了特別的要求。Rabin算法的描述如下：

首先選取兩個(gè)相異的滿足p≡q≡3mod4的大素?cái)?shù)p和q，以n=p×q為模數(shù)。然后再隨機(jī)選取一個(gè)整數(shù)b∈Zn。算法以(n，b)為公開密鑰，(p，q)為私有密鑰。

(1)加密變換：對(duì)于一個(gè)明文消息m，通過計(jì)算c=m(m+b)modn得到密文c。

(2)解密變換：為了解密出密文c，需要求解二次同余方程

m2+bm-c≡0modn

如果令，上面的方程可改寫為

如果再令，方程進(jìn)一步可改寫為

x2≡C(modn)

因此解密問題歸結(jié)為求C模n的平方根。方程x2≡C(modn)有四個(gè)解，由命題5.3.1可知，當(dāng)p≡q

≡3mod4時(shí)，方程x2≡Cmodp的兩個(gè)解是x=±C

(p+1)/4modp，方程x2≡Cmodq的兩個(gè)解是

x=±C(q+1)/4modq

因此，可以組合得到四個(gè)一次同余方程組利用中國剩余定理解這四個(gè)同余方程組得到四個(gè)解，它們是C模n的四個(gè)平方根。要尋找的明文就是四個(gè)解的其中之一。

由上面的敘述可見，Rabin算法的加密函數(shù)不是單射，解密具有不確定性，合法用戶不能確切地知道到底哪一個(gè)解是真正的明文。如果加密之前在明文消息中插入一些冗余信息，比如用戶的身份數(shù)字、日期、時(shí)間或者事先約定的某個(gè)數(shù)值等，則可以幫助收信者準(zhǔn)確地識(shí)別解密后的明文。

Rabin算法的解密過程是尋找C模n的平方根，這個(gè)問題的難度等價(jià)于n的因子分解。盡管計(jì)算模為素?cái)?shù)的平方根是多項(xiàng)式時(shí)間可解的，但其過程仍然很復(fù)雜。要求p與q是模4同余3的限制條件是為了使解密的計(jì)算和分析變得容易。在實(shí)踐中通常使用Rabin算法的一個(gè)變形或者說是特例，即取b=0。在這種情況下，加解密處理變成如下形式：

(1)加密變換：c=m2modn

(2)解密變換：modn

這種變形的Rabin算法可以看做是加密指數(shù)e=2的RSA算法。

例5.4

假定模數(shù)n=19×23=437，對(duì)明文m=183加密，則密

文為c=m2modn=1832mod437=277如果要對(duì)密文c=277進(jìn)行解密，首先需要計(jì)算出277模19和模23的平方根。由于19和23都是模4同余3的，因此可得

277模19的平方根：±277(19+1)/4≡±2775≡±7mod19

277模23的平方根：±277(23+1)/4≡±2776≡±1mod23再解下面的同余方程組：利用中國剩余定理，可解出上面四個(gè)同余方程組的解，分別是

x=254，45，392，183mod437

由此可見，原始明文m=183是這四個(gè)解之一。5.4.3Rabin算法的修正

Rabin算法具有解密不確定性的缺陷，為此研究者們對(duì)其進(jìn)行了多種改進(jìn)，提出了一些更簡單有效、可證明安全和解密惟一的修正方案。Williams方案比較具有代表性，簡述如下。

取兩個(gè)不同的滿足p≡q≡3mod4的大素?cái)?shù)p和q，以n=p×q為模數(shù)。再取一個(gè)小整數(shù)s，且s不是模n的平方剩余。以n和s為公鑰對(duì)外公布，需要保密的私鑰k滿足

(1)加密變換：對(duì)于消息m，先確定參數(shù)c1。如果m是模n的平方剩余，c1取0；否則，c1取1。然后計(jì)算

以三元組(C，c1，c2)為所得密文。

(2)解密變換：對(duì)于密文(C，c1，c2)，收信者根據(jù)

m2=±Ckmodn

計(jì)算出m2，m2的符號(hào)由c2確定：c2≡0mod2時(shí)m2取負(fù)，

c2≡1mod2時(shí)m2取正。最后，由下式計(jì)算出明文消息m：

例5.5

假設(shè)取p=3，q=7，則n=21，選s=2不是模21的平方剩余。對(duì)于消息m=19，不是模21的平方剩余，取c1=1。于是

這樣加密所得的密文為(16，1，1)。如果要對(duì)密文解密恢復(fù)出明文，計(jì)算

于是

可見，解密是惟一的。

Rabin算法對(duì)選擇明文攻擊是安全的，但已經(jīng)證明它確實(shí)不能抵抗選擇密文攻擊。此外，針對(duì)RSA算法的一些攻擊方法對(duì)Rabin算法也有效。因此，與RSA安全性有關(guān)的一些問題，比如如何選擇系統(tǒng)參數(shù)等，對(duì)Rabin算法也同樣適用。5.5ElGamal算法

ElGamal算法也是一種具有廣泛應(yīng)用的公鑰密碼體制，它的安全性基于有限域上計(jì)算離散對(duì)數(shù)問題的困難性，還有許多常用的密碼算法與ElGamal算法具有類似的基本原理。相對(duì)來講，ElGamal算法比較容易理解。5.5.1離散對(duì)數(shù)問題

假設(shè)a是群G中的任一元素，滿足at=1的最小正整數(shù)t稱為元素a的階，如果不存在這樣的正整數(shù)t，則稱a的階為∞。假設(shè)群G為有限乘法群(p為素?cái)?shù))，將滿足at=1modp的最小正整數(shù)t稱為元素a在模p下的階。如果元素a模p的階等于φ(p)，則稱a是p的本原根或者本原元。如果模數(shù)取任意的正整數(shù)，上面模運(yùn)算下元素的階和本原根的概念仍然有意義。設(shè)a是素?cái)?shù)p的本原根，那么a，a2，…，aφ(p)在模p下互不相同且正好產(chǎn)生1到φ(p)=p-1的所有值。因此，對(duì)于b∈{1，2，…，p-1}，一定存在惟一的x∈{1，2，…，p-1}滿足b≡axmodp

。稱x為模p下以a為底b的離散對(duì)數(shù)，并記為x≡logab(modp)。

如果已知a、p和x，那么使用快速指數(shù)算法可以輕易地算出b；如果僅知a、p和b，特別是當(dāng)p的取值特別大時(shí)，要想求出x是非常困難的，目前還沒有特別有效的多項(xiàng)式時(shí)間算法。因此，離散對(duì)數(shù)問題可以用于設(shè)計(jì)公鑰密碼算法。為了使基于離散對(duì)數(shù)問題的公鑰密碼算法具有足夠的密碼強(qiáng)度，一般要求模數(shù)p的長度在150位以上。5.5.2ElGamal算法的描述

設(shè)p是一個(gè)素?cái)?shù)，Zp是含有p個(gè)元素的有限域，是Zp的乘法群，p的大小足以使乘法群上的離散對(duì)數(shù)難以計(jì)算。選擇的一個(gè)生成元g和一個(gè)秘密隨機(jī)數(shù)a，要求它們都小于p，計(jì)算

y=gamodp

公開密鑰取為(y，g，p)，且g和p可由一組用戶共享；a作為私有密鑰，需要保密。

(1)加密變換：對(duì)于消息m，秘密選取一個(gè)隨機(jī)數(shù)k∈Zp-1，然后計(jì)算

c1=gkmodp

和c2=mykmodp

c1與c2并聯(lián)構(gòu)成密文，即密文c=(c1，c2)，因此密文的長度是明文的兩倍。

(2)解密變換：。

由加密變換可知，。所以，解密結(jié)果是正確的。

例5.6

設(shè)p＝2579，取模p乘法群的生成元g=2，私鑰x＝765。計(jì)算

y=gxmodp=2765mod2579＝949

如果明文消息m＝1299，選擇隨機(jī)數(shù)k＝853，那么可計(jì)算出密文：

c=(c1，c2)=(gk，myk)modp

=(2853mod2579，1299×949853mod2579)

=(435，2396)對(duì)密文進(jìn)行解密變換可計(jì)算出明文m：

由于密文不僅取決于明文，還依賴于加密者每次選擇的隨機(jī)數(shù)k，因此ElGamal公鑰體制是非確定性的，同一明文多次加密得到的密文可能不同，同一明文最多會(huì)有多達(dá)p-1個(gè)不同的密文。

ElGamal算法建立在乘法群(p為素?cái)?shù))上，事實(shí)上可以基于任何離散對(duì)數(shù)問題難以求解的群來構(gòu)造ElGamal算法。此時(shí)是將ElGamal算法建立在某個(gè)生成子群上，稱這樣得到的公鑰密碼體制為推廣的ElGamal算法，簡單描述如下。

設(shè)G是運(yùn)算符為*的有限群，元素g∈G，H是由g生成的子群，即H={gi|i≥0}。G上的離散對(duì)數(shù)問題是：對(duì)一個(gè)元素b∈H，能否找到惟一的整數(shù)a∈［0，|H|-1］，滿足ga=b∈H，記。如果上述的離散對(duì)數(shù)在有限群G的生成子群H上是難以求解的，那么可以在有限群G上構(gòu)造如下的ElGamal公鑰密碼體制。

任取a∈［0，|H|-1］，計(jì)算y=ga∈H，公開密鑰取為(g，y)，私有密鑰取為a。

(1)加密變換：對(duì)于明文分組m，隨機(jī)選取k∈［0，|H|-1］，計(jì)算密文c=(c1，c2)，其中c1=gk，c2=m*yk。

(2)解密變換：

。5.5.3ElGamal算法的安全性

ElGamal算法的安全性基于有限群上離散對(duì)數(shù)問題的困難性。有學(xué)者曾提出模p生成的離散對(duì)數(shù)密碼可能存在陷門，一些“弱”素?cái)?shù)p下的離散對(duì)數(shù)較容易求解。因此，要仔細(xì)地選擇p，且g應(yīng)是模p的本原根，一般認(rèn)為這類問題是困難的，而且目前尚未發(fā)現(xiàn)有效解決該問題的多項(xiàng)式時(shí)間算法。此外，為了抵抗已知的攻擊，p應(yīng)該至少是300位的十進(jìn)制整數(shù)，并且p-1應(yīng)該至少有一個(gè)較大的素?cái)?shù)因子。

ElGamal算法的安全性還來自于加密的不確定性。ElGamal算法的一個(gè)顯著特征是在加密過程中引入了隨機(jī)數(shù)，這意味著相同的明文可能產(chǎn)生不同的密文，能夠給密碼分析者制造更大的困難。但在某些情況下，ElGamal算法也可能向攻擊者泄漏部分信息。比如在實(shí)際應(yīng)用中，為了提高效率，一般會(huì)選用階r遠(yuǎn)小于p的生成元g。在這種情況下，如果一個(gè)比較短的消息m并不是由g生成的子群中的元素，那么類似于RSA體制的中間相遇攻擊則有可能成功。這是因?yàn)閷?duì)于密文c=(c1，c2)=(gk，myk)modp，攻擊者能夠得到

即攻擊者將ElGamal的不確定加密體制轉(zhuǎn)化成一種確定性的算法，且具有指數(shù)運(yùn)算的可乘性。因此，對(duì)于一個(gè)容易分解的小尺寸的消息，攻擊者能夠?qū)rmodp實(shí)施中間相遇攻擊。由此可知，當(dāng)一個(gè)明文消息不屬于由g生成的子群的時(shí)候，ElGamal就成為一種確定性的算法。由于確定性加密體制允許使用多次“嘗試”的方法來尋找小的明文消息，因此

泄露了部分信息。所以，在應(yīng)用ElGamal算法，特別是推廣的ElGamal算法的時(shí)候一定要注意生成元g的選擇，確保每一個(gè)可能的明文消息都是由g生成的。5.6橢圓曲線算法橢圓曲線理論在公鑰密碼領(lǐng)域有著重要的應(yīng)用，以橢圓曲線上的點(diǎn)為元素定義的Abel群是構(gòu)造多種公鑰密碼體制的基礎(chǔ)。為了保證RSA算法的安全性，其密鑰長度不斷增加，導(dǎo)致加解密運(yùn)算負(fù)擔(dān)越來越重，處理速度越來越慢；相比之下，基于橢圓曲線理論的公鑰密碼體制可以用較短的密鑰獲得同樣的密碼強(qiáng)度。橢圓曲線密碼體制已經(jīng)成為近年來一個(gè)非常有吸引力的研究領(lǐng)域，特別是在移動(dòng)通信安全方面更為突出。橢圓曲線密碼體制已被IEEE公鑰密碼標(biāo)準(zhǔn)P1363采用。5.6.1橢圓曲線的定義及性質(zhì)

橢圓曲線的圖形并非橢圓，只是因?yàn)樗那€方程與計(jì)算橢圓周長的方程類似，而將其叫做橢圓曲線。通常所說的橢圓曲線是指由Weierstrass方程

y2+axy+by=x3+cx2+dx+e

所確定的平面曲線，其中a、b、c、d、e取自某個(gè)域F并滿足一些簡單的條件。橢圓曲線通常用字母E表示，滿足曲線方程的序偶(x，y)就是域F上的橢圓曲線E上的點(diǎn)。域F可以是數(shù)域，也可以是某個(gè)有限域GF(pn)。除了滿足曲線方程的所有點(diǎn)(x，y)之外，橢圓曲線E還包括一個(gè)特殊的點(diǎn)O，稱為無窮遠(yuǎn)點(diǎn)。在上面的Weierstrass方程中用 代替y，得到

y2=4x3+Ax2+2Bx+C

其中，A=a2+4c，B=2d+ab，C=b2+4e。因此，橢圓曲線關(guān)于x軸對(duì)稱。圖5-2是實(shí)數(shù)域上橢圓曲線的兩個(gè)例子。圖5-2實(shí)數(shù)域上橢圓曲線的例子我們可以在橢圓曲線E上定義一個(gè)二元運(yùn)算，使其成為Abel群，通常稱這個(gè)運(yùn)算為加法，并用⊕表示，其定義如下：

(1)取無窮遠(yuǎn)點(diǎn)O為單位元。因此，對(duì)任何點(diǎn)P∈E，有P⊕O=P。

(2)如果有三個(gè)點(diǎn)P，Q，R∈E且在同一條直線上，那么P⊕Q⊕R=O。

(3)設(shè)P=(x,y)∈E，那么P的加法逆元定義為=-P=(x,-y)∈E。這是因?yàn)镻與的連線延長到無窮遠(yuǎn)時(shí)將經(jīng)過無窮遠(yuǎn)點(diǎn)O，所以P，和O三點(diǎn)共線，即P⊕⊕O＝O，P⊕

=O，=-P。而橢圓曲線E是關(guān)于x軸對(duì)稱的，所以可以將-P定義為P點(diǎn)關(guān)于x軸的對(duì)稱點(diǎn)(x，-y)∈E。此外還有，-O＝O。

(4)若P和Q是橢圓曲線E上x坐標(biāo)不相同的兩個(gè)點(diǎn)，那么P⊕Q定義如下：過P和Q畫一條直線L交橢圓曲線于另一點(diǎn)R，因?yàn)镻≠Q(mào)，所以R是惟一的。因此，P⊕Q⊕R=O，即P⊕Q=-R，也就是說P⊕Q是P與Q的連線L交橢圓曲線E上另一點(diǎn)R關(guān)于x軸的對(duì)稱點(diǎn)。

如上定義的加法運(yùn)算符合群的定義，同時(shí)滿足交換律，因此(E，⊕)是一個(gè)Abel群。在密碼學(xué)中使用的橢圓曲線通常定義在有限域上，也就是說橢圓曲線方程中的所有系數(shù)都取自某個(gè)有限域GF(pn)。其中，最常用的是由有限域Zp(p為素?cái)?shù))上的同余方程

y2≡x3+ax+b(modp)，a，b∈Zp且滿足4a3+27b2≠0modp

確定的橢圓曲線，即由此同余方程的所有解(x，y)∈Zp×Zp，再加上一個(gè)特殊的無窮遠(yuǎn)點(diǎn)O，在上述加法運(yùn)算下構(gòu)造的Abel群。用Ep(a，b)來表示這樣得到的Abel群?？梢宰C明，在實(shí)數(shù)域中4a3+27b2≠0是保證方程y2≡x3+ax+b存在三個(gè)不同解(對(duì)于給定的y)的充分必要條件。否則，方程的三個(gè)解中至少有兩個(gè)相同，并且稱這樣的橢圓曲線為奇異橢圓曲線。在Zp中要求4a3+27b2≠0modp，以保證曲線方程的各個(gè)解不相同。按照上面給出的加法運(yùn)算定義方法，假設(shè)P(x1，y1)和Q(x2，y2)是橢圓曲線Ep(a，b)上的點(diǎn)，如果P與Q關(guān)于x軸對(duì)稱，即x1=x2且y1=-y2，則P⊕Q=O；否則記P⊕Q=R，根據(jù)橢圓曲線的方程和P、Q連線的方程可以計(jì)算出R點(diǎn)的坐標(biāo)(x3，y3)如下(在此略去計(jì)算過程)：其中

實(shí)際上，Zp上的橢圓曲線只是一些不連續(xù)的點(diǎn)，并不像實(shí)數(shù)域上橢圓曲線有直觀的幾何解釋，但同樣定義的加法運(yùn)算能夠保證(Ep(a，b)，⊕)仍然是一個(gè)Abel群。

例5.7

給定Z11上的一條橢圓曲線y2=x3+x+6，可按下述步驟計(jì)算出E11(1，6)中的所有點(diǎn)(無窮遠(yuǎn)點(diǎn)除外)。

首先，對(duì)每個(gè)x∈Z11，計(jì)算出同余式x3+x+6(mod11)的值a。

其次，利用Euler準(zhǔn)則判定上一步算出的每一個(gè)值a是否是模11的平方剩余。由Euler準(zhǔn)則知道：如果p為奇素?cái)?shù)且0＜a＜p，那么a是模p的平方剩余，當(dāng)且僅當(dāng)

a

(p-1)/2modp=1

對(duì)于本例p＝11，需要判斷a5mod11=1是否成立。由此可以方便地測試每一個(gè)a是不是模11的平方剩余。

最后，計(jì)算出每一個(gè)平方剩余的平方根。根據(jù)命題5.3.1，對(duì)于素?cái)?shù)p=3mod4，a是模p的平方剩余，則a的平方根是

±a

(p+1)/4modp。在本例中即是計(jì)算±a3mod11。上述計(jì)算結(jié)果列在下表中。因此，E11(1，6)共有13個(gè)點(diǎn)(上表中最右一列給出的12個(gè)點(diǎn)加上無窮遠(yuǎn)點(diǎn)O)。因?yàn)槿魏嗡財(cái)?shù)階的群都是循環(huán)群，故E11(1，6)與Z13同構(gòu)，且除無窮遠(yuǎn)點(diǎn)O以外的任意點(diǎn)都是E11(1，6)的生成元。選取g=(2，7)為生成元，計(jì)算g的冪。注意，這里的運(yùn)算是群上的加法，所以群里的冪就是倍乘，即gk=g⊕g⊕…⊕g=kg。首先計(jì)算2g=(2，7)⊕(2，7)=(x3，y3)，這里

所以有

x3=λ2-x1-x2(modp)=64-2-2(mod11)=5

y3=λ(x1-x3)-y1(modp)=8(2-5)-7(mod11)=2

因此，2g=(5，2)。下一個(gè)冪是3g=2g⊕g=(5，2)⊕(2，7)=(x4，y4)。再次計(jì)算λ，

所以有

x4=λ2-x1-x2(modp)=4-5-2(mod11)=8

y4=λ(x1-x

4)-y1(modp)=2(5-8)-2(mod11)=3

因此，3g=(8，3)。如此下去可計(jì)算出生成元g的所有冪，結(jié)果如下：

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=(2，7)是E11(1，6)的生成元。5.6.2橢圓曲線算法的描述

和ElGamal算法一樣，橢圓曲線算法也是建立在離散對(duì)數(shù)問題上的公鑰密碼體制。已經(jīng)知道，由橢圓曲線可以生成Abel群，于是可以在這樣的群上構(gòu)造離散對(duì)數(shù)問題。把使用有限域上橢圓曲線產(chǎn)生的Abel群Ep(a，b)來構(gòu)造的離散對(duì)數(shù)問題稱為橢圓曲線上的離散對(duì)數(shù)。目前的研究結(jié)果表明，解決橢圓曲線上的離散對(duì)數(shù)問題的最好算法比解決標(biāo)準(zhǔn)有限域上的離散對(duì)數(shù)問題的最好算法還要慢許多，這保證了在橢圓曲線上構(gòu)造密碼體制的可行性。橢圓曲線上的離散對(duì)數(shù)描述如下：設(shè)Ep(a，b)是有限域Zp(p＞3的素?cái)?shù))上的一條橢圓曲線產(chǎn)生的Abel群，對(duì)于Ep(a，b)上的任意兩點(diǎn)P和Q，尋找一個(gè)整數(shù)k<p使得Q=kP。明顯的，如果已知k和P，Q可直接求得；反過來，由P和Q難以計(jì)算出k，特別是當(dāng)k很大時(shí)，這個(gè)難度不亞于對(duì)k的分解。這個(gè)問題稱為橢圓曲線上的離散對(duì)數(shù)問題，有限域上的橢圓曲線提供了構(gòu)造離散對(duì)數(shù)的一個(gè)新途徑，可以將這種建立在橢圓曲線上的離散對(duì)數(shù)問題應(yīng)用于公鑰密碼體制的構(gòu)造。橢圓曲線算法的描述如下：設(shè)Ep(a，b)是有限域Zp(p＞3的素?cái)?shù))上的一條橢圓曲線產(chǎn)生的Abel群，任取g∈Ep(a，b)，且滿足在由g生成的子群H上的橢圓曲線離散對(duì)數(shù)問題是難解的。再取正整數(shù)x<p，計(jì)算y=xg。公開密鑰取為g、y、p，私有密鑰取為x。

(1)加密變換：對(duì)于明文m，隨機(jī)選取正整數(shù)k<p，計(jì)算c1=kg和c2=m⊕ky。密文為c=(c1，c2)=(kg，m⊕ky)。

(2)解密變換：m=c2⊕(-xc1)。

解密的正確性是顯而易見的。在使用橢圓曲線密碼算法時(shí)，一個(gè)需要注意的問題是，橢圓曲線算法中的運(yùn)算都是群Ep(a，b)上元素的加法運(yùn)算，因此要用某種編碼方法將原始明

文消息m嵌入到Ep(a，b)的點(diǎn)上，然后才能使用群Ep(a，b)的運(yùn)算規(guī)則進(jìn)行加法運(yùn)算。原始消息到Ep(a，b)上點(diǎn)的嵌入編碼方法這里不予討論。下面利用例5.7的橢圓曲線及其Abel群E11(1，6)來說明橢圓曲線算法的操作細(xì)節(jié)。

例5.8

取g=(2，7)為E11(1，6)的一個(gè)生成元，假設(shè)某用戶的私鑰是x=7，那么

y=7g=(7，2)

即該用戶的公鑰是(g，y，p)=((2，7)，(7，2)，11)。

假設(shè)有一明文消息m=(10，9)，現(xiàn)在對(duì)其進(jìn)行加密。隨機(jī)選取k=3，密文的計(jì)算如下

c=(c1，c2)=(kg，m⊕ky)=(3g，(10，9)⊕3(7，2))

=((8，3)，(10，9)⊕(3，5))

=((8，3)，(10，2))反過來，如果要對(duì)密文c=((8，3)，(10，2))解密，則解密過程如下

m=c2⊕(-xc1)=(10，2)⊕(-7(8，3))

=(10，2)⊕(-(3，5))

=(10，2)⊕(3，6)

=(10，9)

解密恢復(fù)出正確的明文。5.6.3橢圓曲線算法的特性

求解橢圓曲線上離散對(duì)數(shù)問題的難度比標(biāo)準(zhǔn)有限域上離散對(duì)數(shù)問題的難度更高；在同等難度的情況下，橢圓曲線算法比RSA等基于因數(shù)分解的算法有更小密鑰量。因此橢圓曲線算法具有更好的密碼學(xué)特性。具體如下：

(1)安全性高?，F(xiàn)在已知的解決橢圓曲線上離散對(duì)數(shù)問題的最好算法是以Pollardρ算法為代表的通用離散對(duì)數(shù)求解算法，該類算法的計(jì)算時(shí)間復(fù)雜度為，其中N是