新編密碼學(xué) 課件 第7章 公鑰密碼

7.1公鑰密碼體制的基本原理

7.2背包算法

7.3RSA算法

7.4Rabin算法

7.5ElGamal算法

7.6橢圓曲線密碼

7.7SM2公鑰加密算法

7.8基于身份的公鑰密碼體制7.1公鑰密碼體制的基本原理7.1.1公鑰密碼的基本思想運(yùn)用DES等經(jīng)典密碼系統(tǒng)進(jìn)行保密通信時(shí),通信雙方必須擁有一個(gè)共享的秘密密鑰來(lái)實(shí)現(xiàn)對(duì)消息的加密和解密,而密鑰具有的機(jī)密性使得通信雙方如何獲得一個(gè)共同的密鑰變得非常困難。通常采用人工傳送的方式分配各方所需的共享密鑰,或借助一個(gè)可靠的密鑰分配中心來(lái)分配所需的共享密鑰。但在具體實(shí)現(xiàn)過(guò)程中,這兩種方式都面臨很多困難,尤其在計(jì)算機(jī)網(wǎng)絡(luò)化時(shí)代更為困難。1976年,兩位美國(guó)密碼學(xué)者W.Diffie和M.Hellman在該年度的美國(guó)國(guó)家計(jì)算機(jī)會(huì)議上提交了一篇名為“NewDirectionsinCryptography”(《密碼學(xué)的新方向》)的論文。文中首次提出公鑰密碼體制的新思想,為解決傳統(tǒng)經(jīng)典密碼學(xué)中面臨的諸多難題提供了一個(gè)新的思路。其基本思想是把密鑰分成兩個(gè)部分———公開密鑰(簡(jiǎn)稱公鑰)和私有密鑰(簡(jiǎn)稱私鑰),分別用于消息的加密和解密。公鑰密碼體制又稱為雙鑰密碼體制、非對(duì)稱密碼體制,與之對(duì)應(yīng),傳統(tǒng)的經(jīng)典密碼體制又稱為單鑰密碼體制、對(duì)稱密碼體制。公鑰密碼體制中的公開密鑰可被記錄在一個(gè)公共數(shù)據(jù)庫(kù)里,或者以某種可信的方式公開發(fā)放,而私有密鑰必須由持有者妥善、秘密地保存。這樣,任何人都可以通過(guò)某種公開的途徑獲得一個(gè)用戶的公開密鑰,然后與其進(jìn)行保密通信,而解密者只能是那些知道相應(yīng)私鑰的密鑰持有者。用戶公鑰的這種公開性使得公鑰體制的密鑰分配變得非常簡(jiǎn)單,目前常以公鑰證書的形式發(fā)放和傳遞用戶公鑰,而私鑰的保密專用性決定了它不存在分配的問(wèn)題(但需要用公鑰來(lái)驗(yàn)證它的真實(shí)性,以防止欺騙)。公鑰密碼算法的最大特點(diǎn)是采用兩個(gè)具有一一對(duì)應(yīng)關(guān)系的密鑰對(duì)k=(ps,sk)來(lái)分離加密和解密過(guò)程。當(dāng)兩個(gè)用戶希望借助公鑰體制進(jìn)行保密通信時(shí),發(fā)信方Alice用收信方Bob的公開密鑰pk加密消息并發(fā)送給接收方;而收信方Bob使用與公鑰相對(duì)應(yīng)的私鑰sk進(jìn)行解密。根據(jù)公私鑰之間嚴(yán)格的一一對(duì)應(yīng)關(guān)系,只有與加密時(shí)所用公鑰相對(duì)應(yīng)的用戶私鑰才能正確解密,從而恢復(fù)出正確的明文。由于這個(gè)私鑰是通信中的收信方獨(dú)有的,其他用戶不可能知道,所以只有收信方Bob能正確恢復(fù)出明文消息,其他有意或無(wú)意獲得消息密文的用戶都不能解密出正確的明文,從而達(dá)到了保密通信的目的。圖7-1給出了公鑰密碼體制用于消息加、解密的基本流程。7.1.2公鑰密碼算法應(yīng)滿足的要求基于圖71給出的公鑰密碼體制加密、解密的基本流程,一個(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ì)算上是不可行的,或者說(shuō),在知道公鑰pk的情況下推知私鑰sk在計(jì)算上是不可行的。由上面的基本要求可以看出,公鑰密碼體制的核心在于加密變換與解密變換的設(shè)計(jì)。在密碼算法中,加解密變換是互逆的,但條件(2)說(shuō)明在公鑰密碼體制中加解密變換不能簡(jiǎn)單地直接互推。上述條件表明公鑰密碼體制的加解密變換類似于陷門單向函數(shù)的運(yùn)算,因此可以利用陷門單向函數(shù)來(lái)構(gòu)造公鑰密碼體制。陷門單向函數(shù)是一個(gè)可逆函數(shù)f(x)。對(duì)于定義域中的任何x,函數(shù)值y=f(x)都是容易計(jì)算的;但對(duì)幾乎所有的x,要由y=f(x)求出x在計(jì)算上不可行(即使已經(jīng)知道函數(shù)f(x)),除非知道某些輔助信息(稱為陷門信息)。這里所說(shuō)的“容易計(jì)算”是指函數(shù)值能在其輸入長(zhǎng)度的多項(xiàng)式時(shí)間內(nèi)計(jì)算出來(lái)。例如,若輸入長(zhǎng)度為n位,求函數(shù)值的計(jì)算時(shí)間是na(這里a是一個(gè)固定常數(shù))的某個(gè)倍數(shù),則稱此函數(shù)是容易計(jì)算的,否則就是不可行的。針對(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)生密文c=EpkB[m]在計(jì)算上是容易的。(3)收信方Bob用自己的私鑰skB

解密密文c,還原明文消息m=DskB[c]在計(jì)算上是容易的。(4)不僅攻擊者由密文c和Bob的公鑰pkB

恢復(fù)明文m在計(jì)算上是不可行的,而且攻擊者由Bob的公鑰pkB

求解對(duì)應(yīng)的私鑰skB

在計(jì)算上也是不可行的。(5)一般情況下,加解密的次序可交換,即DskB[EpkB[m]]=EpkB[DskB[m]]。公鑰密碼體制的思想完全不同于單鑰密碼體制。公鑰密碼算法的基本操作不再是單鑰密碼體制中使用的替換和置換。公鑰密碼體制通常將其安全性建立在某個(gè)尚未解決(且尚未證實(shí)能否有效解決)的數(shù)學(xué)難題的基礎(chǔ)上,并經(jīng)過(guò)精心設(shè)計(jì)來(lái)保證其具有非常高的安全性。公鑰密碼算法以非對(duì)稱的形式使用兩個(gè)密鑰,不僅在實(shí)現(xiàn)消息加解密基本功能的同時(shí)簡(jiǎn)化了密鑰分配任務(wù),而且對(duì)密鑰協(xié)商與密鑰管理、數(shù)字簽名與身份認(rèn)證等密碼學(xué)問(wèn)題產(chǎn)生了深刻的影響?？梢哉f(shuō),公鑰密碼思想為密碼學(xué)的發(fā)展提供了新的理論和技術(shù)基礎(chǔ),是密碼學(xué)發(fā)展史上的一次革命。7.2背包算法7.2.1背包問(wèn)題在組合數(shù)學(xué)中有一個(gè)背包問(wèn)題:假設(shè)有一堆物品,體積各不相同,能否從這堆物品中找出幾個(gè)正好裝滿一個(gè)給定容量的背包(假定物品之間不留空隙)?記物品的體積分別為v1,v2,…,vn,背包的容量為C,則背包問(wèn)題可表示為其中,bi(i=1,2,…,n)等于1或者0,bi=1表示第i個(gè)物品在背包中,bi=0表示第i個(gè)物品不在背包中;物品體積的序列(v1,v2,…,vn)稱為背包向量。理論上講,通過(guò)檢查背包向量V的所有子集,計(jì)算出每個(gè)子集的元素之和,總能找出一個(gè)子集作為背包問(wèn)題的解,因此背包問(wèn)題又稱為子集和問(wèn)題。然而長(zhǎng)度為n的背包向量V的全體子集共有2n

個(gè),當(dāng)n很大時(shí),對(duì)全部2n

個(gè)子集進(jìn)行窮舉搜索是不可能的。事實(shí)上,背包問(wèn)題是一類NPC問(wèn)題,而目前還沒(méi)有發(fā)現(xiàn)比窮舉搜索更好的NPC問(wèn)題求解方法。幸運(yùn)的是,并非所有的背包問(wèn)題都沒(méi)有有效算法,有一類特殊的背包問(wèn)題是容易求解的,這就是超遞增背包問(wèn)題。即V中每一項(xiàng)都大于它前面所有項(xiàng)之和,則稱V是一個(gè)超遞增向量,或者稱序列v1,v2,…,vn是一個(gè)超遞增序列,以V為背包向量的背包問(wèn)題稱作超遞增背包問(wèn)題。例如,序列1,2,4,…,2n就是一個(gè)超遞增序列。超遞增背包問(wèn)題的解很容易通過(guò)以下過(guò)程找到:設(shè)背包容量為C,從右向左(從大到小)依次檢查超遞增背包向量V中的每個(gè)元素,以確定問(wèn)題的解。若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ù)上述過(guò)程,并判斷C是否減少到0。若C最終變成0,則問(wèn)題的解存在,否則解不存在。7.2.2背包算法的描述借助背包問(wèn)題中的超遞增向量和相應(yīng)的非超遞增向量,可以構(gòu)造一個(gè)公鑰

密

碼

算法———背包密碼算法。背包算法的描述如下:私有密鑰設(shè)置為將一個(gè)超遞增向量V轉(zhuǎn)換為非超遞增向量U的參數(shù)t、t-1和k,公開密鑰設(shè)置為非超遞增向量U。加密變換:首先將二進(jìn)制明文消息劃分成長(zhǎng)度與非超遞增向量U長(zhǎng)度相等的明文分組b1b2…bn;然后計(jì)算明文分組向量B=(b1,b2,…,bn)與非超遞增向量U=(u1,u2,…,un)的內(nèi)積B·U=b1u1+b2u2+…+bnun,所得結(jié)果為密文。解密變換:先還原出超遞增背包向量V=t-1Umodk≡t-1tVmodk,再將密文B·U模k乘以t-1的結(jié)果作為超遞增背包問(wèn)題的背包容量,求解超遞增背包問(wèn)題,得到消息明文。7.2.3背包算法的安全性背包算法利用難解的一般背包問(wèn)題作為公開密鑰,可以方便地對(duì)明文進(jìn)行加密;而私有密鑰則利用易解的超遞增背包問(wèn)題給出一個(gè)解密的簡(jiǎn)單方法。那些不知道私鑰的攻擊者要想破譯密文就不得不求解一個(gè)困難的背包問(wèn)題,這在計(jì)算上看似是不可行的。背包算法提出兩年后即被破解。破解的基本思想是不必找出真正的模數(shù)k和乘數(shù)t,也不用窮舉搜索背包向量的所有子集,而是找出一對(duì)任意的k'和t',使得用公開的背包向量U模k'乘t'后能得到一個(gè)超遞增向量。究其原因是Merkle-Hellman背包體制的公開密鑰是由超遞增向量變換而來(lái)的,雖然經(jīng)過(guò)模乘置換,但超遞增向量?jī)?nèi)在的規(guī)律性并不能完全被隱藏,這就給攻擊者留下了可乘之機(jī)。隨后Merkle又提出了多次迭代背包體制,但最終也被破解。1984年,Brickell最終證明了Merkle-Hellman背包體制的不安全性,并發(fā)現(xiàn)了一種可將難解的背包問(wèn)題轉(zhuǎn)化為易解的背包問(wèn)題的算法。背包算法是第一個(gè)使公鑰密碼體制成為現(xiàn)實(shí)的密碼算法,它說(shuō)明了如何將數(shù)學(xué)難題應(yīng)用于公鑰密碼算法的設(shè)計(jì)。背包體制的優(yōu)勢(shì)是加解密速度很快,但它存在的不安全性使其不能用于商業(yè)目的。7.3RSA算法數(shù)論里有一個(gè)大數(shù)分解問(wèn)題:計(jì)算兩個(gè)素?cái)?shù)的乘積非常容易,但分解該乘積卻異常困難,特別是在這兩個(gè)素?cái)?shù)都很大的情況下?；谶@個(gè)事實(shí),1978年,美國(guó)MIT(麻省理工學(xué)院)的三名數(shù)學(xué)家R.Rivest、A.Shamir和L.Adleman提出了著名的公鑰密碼體制———RSA公鑰算法。該算法基于指數(shù)加密概念,以兩個(gè)大素?cái)?shù)的乘積作為算法的公鑰來(lái)加密消息,而密文的解密必須知道相應(yīng)的兩個(gè)大素?cái)?shù)。迄今為止,RSA公鑰算法是思想最簡(jiǎn)單、分析最透徹、應(yīng)用最廣泛的公鑰密碼體制。RSA算法非常容易理解和實(shí)現(xiàn),經(jīng)受住了密碼分析,密碼分析者既不能證明也不能否定它的安全性,這恰恰說(shuō)明了RSA具有一定的可信度。7.3.1RSA算法的描述基于大數(shù)分解問(wèn)題,為了產(chǎn)生公私鑰,首先獨(dú)立地選取兩個(gè)大素?cái)?shù)p和q(注:為了獲得最大程度的安全性,選取的p和q的長(zhǎng)度應(yīng)該差不多,都應(yīng)為長(zhǎng)度在100位以上的十進(jìn)制數(shù)字),計(jì)算這里φ(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ò)展的歐幾里得算法求得。這樣我們由p和q獲得了3個(gè)參數(shù)n,e,d。在RSA算法里,以n和e作為公鑰,d作為私鑰(注:不再需要p和q,可以銷毀,但一定不能泄露)。具體的加解密過(guò)程如下所示。加密變換:先將消息劃分成數(shù)值小于n的一系列數(shù)據(jù)分組,即以二進(jìn)制表示的每個(gè)數(shù)據(jù)分組的位長(zhǎng)應(yīng)小于lbn。然后對(duì)每個(gè)明文分組m進(jìn)行加密變換,得到密文c,即解密變換:m≡cdmodn。命題7.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≡1modg(n)可知，存在整數(shù)k，使得de=kφ(n)+1。下面分兩種情形討論:情形一,m僅與p,q二者之一互素,不妨假設(shè)m與p互素且與q不互素,那么存在整數(shù)a,使得m=aq,由歐拉定理可知于是存在一個(gè)整數(shù)t,使得

兩邊同時(shí)乘以m=aq,得到由此得情形二,如果m與p和q都互素,那么m也和n互素,有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)系。7.3.2RSA算法的安全性RSA算法的安全性完全依賴于對(duì)大數(shù)分解問(wèn)題的困難性的推測(cè),但面臨的問(wèn)題是迄今為止還沒(méi)有證明大數(shù)分解問(wèn)題是一類NP問(wèn)題。為了抵抗窮舉攻擊,RSA算法采用了大密鑰空間,通常模數(shù)n取值很大,e和d也取非常大的自然數(shù),但這樣做的一個(gè)明顯缺點(diǎn)是密鑰產(chǎn)生和加解密過(guò)程都非常復(fù)雜,系統(tǒng)運(yùn)行速度比較慢。與其他密碼體制一樣,嘗試破解每一個(gè)可能的d是不現(xiàn)實(shí)的,那么分解模數(shù)n就成為最直接的攻擊方法。只要能夠分解n就可以求出φ(n),然后通過(guò)擴(kuò)展的歐幾里得算法可以求得加密指數(shù)e模φ(n)的逆d,從而達(dá)到破解的目的。目前還沒(méi)有找到分解大整數(shù)的有效方法,但隨著計(jì)算能力的不斷提高和計(jì)算成本的不斷降低,許多被認(rèn)為不可能分解的大整數(shù)已被成功分解。例如,模數(shù)為129位十進(jìn)制數(shù)字的RSA-129已于1994年4月在Internet上通過(guò)分布式計(jì)算被成功分解出一個(gè)64位和一個(gè)65位的因子。更困難的RSA-130也于1996年被分解出來(lái),緊接著RSA-154也被分解,據(jù)報(bào)道,158位的十進(jìn)制整數(shù)也已被分解,這意味著512位模數(shù)的RSA已經(jīng)不安全了。更嚴(yán)重的安全威脅來(lái)自于大數(shù)分解算法的改進(jìn)和新算法的不斷提出。當(dāng)年破解RSA-129采用的是二次篩法,而破解RSA-130使用的算法為推廣的數(shù)域篩法,該算法使破解RSA-130的計(jì)算量?jī)H比破解RSA-129多10%。盡管如此,密碼專家認(rèn)為一定時(shí)期內(nèi)1024~2048位模數(shù)的RSA還是相對(duì)安全的。除了對(duì)RSA算法本身的攻擊外,RSA算法還面臨著攻擊者對(duì)密碼協(xié)議的攻擊,即利用RSA算法的某些特性和實(shí)現(xiàn)過(guò)程對(duì)其進(jìn)行攻擊。下面介紹一些攻擊方法。1.共用模數(shù)攻擊在RSA的實(shí)現(xiàn)中,如果多個(gè)用戶選用相同的模數(shù)n,但有不同的加解密指數(shù)e和d,這樣做會(huì)使算法運(yùn)行更簡(jiǎn)單,卻是不安全的。假設(shè)一個(gè)消息用兩個(gè)不同的加密指數(shù)加密且共用同一個(gè)模數(shù),如果這兩個(gè)加密指數(shù)互素(一般情況下都這樣),則不需要知道解密指數(shù),任何一個(gè)加密指數(shù)都可以恢復(fù)明文,理由如下所示。設(shè)e1和e2是兩個(gè)互素的加密密鑰,共用的模數(shù)為n。對(duì)同一個(gè)明文消息m加密得到c1≡me1modn和c2≡me2modn。攻擊者知道n,e1,e2,c1和c2,可以用如下方法恢復(fù)出明文m:由于e1和e2互素,因此由擴(kuò)展的歐幾里得算法可找到滿足re1+se2=1的r和s,由此可得明文消息m被恢復(fù)出來(lái)。注意: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)的消息)分別用這些用戶的公鑰加密,那么利用中國(guó)剩余定理可以恢復(fù)出明文。舉例來(lái)說(shuō),取e=3,3個(gè)用戶的不同模數(shù)分別是n1,n2和n3,將消息x用這3組密鑰分別加密,得到一般來(lái)講,應(yīng)使n1,n2和n3互素。根據(jù)中國(guó)剩余定理,可由y1,y2和y3求出由于x<n1,x<n2,x<n3,所以已經(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)算具有可乘性,這種可乘性有可能導(dǎo)致其他方式的攻擊。事實(shí)上,如果明文m可以被分解成兩項(xiàng)之積m=m1×m2,那么這意味著明文的分解可導(dǎo)致密文的分解,明文分解容易使得密文分解也容易。密文分解容易導(dǎo)致中間相遇攻擊,攻擊方法描述如下:假設(shè)

攻擊者知道m(xù)是一個(gè)合數(shù),且滿足

和m2

都小于那么由RSA的可乘性,有攻擊者可以先創(chuàng)建一個(gè)有序的序列國(guó)際電信聯(lián)盟的實(shí)質(zhì)性工作由國(guó)際電信聯(lián)盟標(biāo)準(zhǔn)化部門(ITU)、國(guó)際電信聯(lián)盟無(wú)線電通信部門和國(guó)際電信聯(lián)盟電信發(fā)展部門這三大部門承擔(dān)。其中國(guó)際電信聯(lián)盟標(biāo)準(zhǔn)化部門由原來(lái)的國(guó)際電報(bào)電話咨詢委員會(huì)(CCITT)和國(guó)際無(wú)線電咨詢委員會(huì)(CCIR)的標(biāo)準(zhǔn)化工作部門合并而成，主要職責(zé)是實(shí)現(xiàn)國(guó)際電信聯(lián)盟有關(guān)電信標(biāo)準(zhǔn)化的目標(biāo)，使全世界的電信完成標(biāo)準(zhǔn)化。ITU目前已制定了2024項(xiàng)國(guó)際標(biāo)準(zhǔn)。ITU的目標(biāo)和任務(wù)是：維持和發(fā)展國(guó)際合作，以改進(jìn)和合理利用電信；促進(jìn)技術(shù)設(shè)施的發(fā)展及其有效運(yùn)用，以提高電信業(yè)務(wù)的效率；擴(kuò)大技術(shù)設(shè)施的用途，并盡可能使之得到廣泛應(yīng)用；協(xié)調(diào)各國(guó)的活動(dòng)等。然后,攻擊者搜索這個(gè)有序的序列,嘗試從這個(gè)有序的序列中找到兩項(xiàng)ie

和je,滿足其中攻擊者能在

步操作之內(nèi)找到ie

和je,攻擊者由此獲得明文m=i×j。當(dāng)明文消息的長(zhǎng)度為40~60位時(shí),明文可被分解成兩個(gè)大小相當(dāng)?shù)恼麛?shù)的概率為18%~50%。舉例來(lái)說(shuō),假設(shè)用1024位模數(shù)的RSA加密一個(gè)長(zhǎng)度為56的位串,如果能夠提供228×1024=238位(約為32GB)的存儲(chǔ)空間,則經(jīng)過(guò)229次模指數(shù)運(yùn)算,就可以有很大的把握找出明文位串,它是兩個(gè)28位的整數(shù)之積。這種空間和時(shí)間用一臺(tái)普通的個(gè)人計(jì)算機(jī)就可以實(shí)現(xiàn)。這說(shuō)明用RSA直接加密一些比較短的位串(如DES等單鑰體制的密鑰或者長(zhǎng)度小于64位的系統(tǒng)口令等)是非常危險(xiǎn)的。7.3.3RSA算法的參數(shù)選擇通過(guò)對(duì)RSA算法的安全性分析可以看出,要想保證RSA體制的安全,必須審慎選擇系統(tǒng)的各個(gè)參數(shù)。下面討論參數(shù)選擇時(shí)需要注意的一些問(wèn)題。1.模數(shù)n的確定首先,多用戶之間共用模數(shù)會(huì)導(dǎo)致共用模數(shù)攻擊,因此不能在多個(gè)用戶之間共用模數(shù)。其次,模數(shù)n是兩個(gè)大素?cái)?shù)p和q的乘積,因此模數(shù)n的確定問(wè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滿足條件:(1)存在兩個(gè)大素?cái)?shù)p1和p2,使得p1|(p-1)、p2|(p+1),(2)存在4個(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ù),則可通過(guò)下面的方法分解模數(shù)n。假設(shè)p-1有k個(gè)素因子,由算術(shù)基本定理可得

其中pi為素?cái)?shù),ai為正整數(shù)(i=1,2,…,k)。如果pi都很小,不妨設(shè)pi<A(A為已知的小整數(shù)),構(gòu)造其中,a≥max{ai},顯然有(p-1)|R。因?yàn)槿我庑∮谒財(cái)?shù)p的正整數(shù)t均與p互素,不妨設(shè)t=2,由歐拉定理可知因而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也可以進(jìn)行類似討論。因此p-1和q-1必須有大素因子,即p和q要為強(qiáng)素?cái)?shù)。如果p與q之差很小,則由

可得

是一個(gè)小的平方數(shù),所以

近似。令

可以從大于

的整數(shù)中依次嘗試u且從而解出p與q。

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

要求p-1與q-1的最大公因子要小是為了防止迭代攻擊。假設(shè)攻擊者截獲了密文c≡memodn,可以進(jìn)行如下迭代攻擊:如果存在t,使得etmodφ(n)≡1,則有整數(shù)k,使et=kφ(n)+1,那么由歐拉定理可知與此同時(shí)還有

所以

因而如果t較小,則這種迭代攻擊很容易成功。由歐拉定理可知若p-1與q-1的最大公因子較小,則t較大;如果t大到(p-1)(q-1)的一半,則迭代攻擊難以奏效。2.加密密鑰e的選取加密密鑰e要滿足以下幾個(gè)條件:(1)e要與模數(shù)n的歐拉函數(shù)值φ(n)互素,即gcd(e,φ(n))=1,否則無(wú)法計(jì)算解密密鑰d。這一要求容易滿足,現(xiàn)在已經(jīng)證明兩個(gè)隨機(jī)數(shù)互素的概率約為3/5。(2)e不能太小,e太小容易遭受低加密指數(shù)攻擊。另外,如果e和m都很小且滿足me<n,此時(shí)密文c≡memodn不需要經(jīng)過(guò)模運(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不能小于7.4Rabin算法7.4.1求解數(shù)模下的平方根問(wèn)題定理7.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à)于同余方程組:因此,問(wèn)題轉(zhuǎn)化為求解上述同余方程組。對(duì)所有的i=1,2,…,l,由a是模pi

的平方剩余可知,同余方程

有兩個(gè)模

的解,分別記為這樣我們可以得到一系列一次同余方程組其中,bi可取bi,1或者bi,2。由中國(guó)剩余定理可知,每一個(gè)這樣的一次同余方程組都有唯一的模n解。由于每個(gè)bi可取bi,1和bi,2中的一個(gè),所以可以產(chǎn)生2l

個(gè)不同的(b1,…,bl),即共有2l

個(gè)不同的一次同余方程組。因此同余方程組共有2l

個(gè)模n的解,即原同余方程x2≡amodn存在2l

個(gè)模n的解。命題7.2如果素?cái)?shù)p≡3mod4,a是

模p的

平

方

剩

余,那

么a模p的

平

方

根

是證明

根據(jù)a是模p的平方剩余,由Euler準(zhǔn)則可知于是7.4.2Rabin算法的描述對(duì)于RSA算法,如果能夠成功分解模數(shù)n,則可攻破RSA系統(tǒng)。因此,攻擊RSA算法的難度不會(huì)超過(guò)大整數(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∈?n。算法以(n,b)為公開密鑰,(p,q)為私有密鑰。加密變換:對(duì)于一個(gè)明文消息m,通過(guò)計(jì)算c≡m(m+b)modn得到密文c。解密變換:為了解密出密文c,需要求解二次同余方程如果令

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

方程進(jìn)一步可改寫為因此解密問(wèn)題歸結(jié)為求C模n的平方根。方程x2≡Cmodn有4個(gè)解。由命題7.2可知,當(dāng)p=q≡3mod4時(shí),方程x2≡Cmodp的2個(gè)解是方程x2≡Cmodq的2個(gè)解是例如，在萬(wàn)方中外標(biāo)準(zhǔn)數(shù)據(jù)庫(kù)中檢索“永磁式直流電機(jī)”方面的標(biāo)準(zhǔn)文獻(xiàn)，可以通過(guò)高級(jí)檢索方式，選擇“題名或關(guān)鍵詞”字段，分別輸入“永磁式”和“直流電機(jī)”；邏輯運(yùn)算符選擇“與”，單擊“檢索”按鈕，即可得到檢索結(jié)果(如圖7-9所示)。因此,可以組合得到4個(gè)一次同余方程組:利用中國(guó)剩余定理解這4個(gè)同余方程組得到4個(gè)解,它們是C模n的4個(gè)平方根。要尋找的明文就是4個(gè)解的其中之一。由上面的敘述可知,Rabin算法的加密函數(shù)不是單射,解密具有不確定性,合法用戶不能確切地知道到底哪一個(gè)解是真正的明文。如果加密之前在明文消息中插入一些冗余信息,比如用戶的身份數(shù)字、日期、時(shí)間或者事先約定的某個(gè)數(shù)值等,可以幫助收信者準(zhǔn)確識(shí)別解密后的明文。Rabin算法的解密過(guò)程是尋找C模n的平方根，這個(gè)問(wèn)題的難度等價(jià)于n的因子分解。盡管計(jì)算模為素?cái)?shù)的平方根是多項(xiàng)式時(shí)間可解的，但其過(guò)程仍然很復(fù)雜。要求p與q是模4同余3是為了使解密的計(jì)算和分析變得容易。在實(shí)踐中，通常使用Rabin算法的一個(gè)變形或者特例，即取b=0。在這種情況下，加解密處理變成如下形式:這種變形的Rabin算法可以看作加密指數(shù)e=2的RSA算法。7.5ElGamal算法7.5.1離散對(duì)數(shù)問(wèn)題假設(shè)a是群G中的任一元素,滿足at=1的最小正整數(shù)t稱為元素a的階,如果不存在這樣的正整數(shù)t,則稱a的階為∞。假設(shè)群G為有限乘法群?p*(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的本原根,那么在模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≡logabmodp。如果已知a、p和x,那么使用快速指數(shù)算法可以輕易地算出b;但如果僅知a、p和b,特別是當(dāng)p的取值特別大時(shí),要想求出x是非常困難的,目前還沒(méi)有特別有效的多項(xiàng)式時(shí)間算法。因此,離散對(duì)數(shù)問(wèn)題可以用于設(shè)計(jì)公鑰密碼算法。為了使基于離散對(duì)數(shù)問(wèn)題的公鑰密碼算法具有足夠的密碼強(qiáng)度,一般要求模數(shù)p的長(zhǎng)度在150位以上。7.5.2ElGamal算法的描述設(shè)p是一個(gè)素?cái)?shù),?p

是含有p個(gè)元素的有限域,?p*是?p

的乘法群,p的大小足以使乘法群?p*上的離散對(duì)數(shù)難以計(jì)算。選擇?p*的一個(gè)生成元g和一個(gè)秘密隨機(jī)數(shù)a,要求它們都小于p,計(jì)算公開密鑰取為(y,g,p),且g和p可由一組用戶共享;a作為私有密鑰,需要保密。加密變換:對(duì)于消息m,秘密選取一個(gè)隨機(jī)數(shù)k∈?p-1,然后計(jì)算c1與c2并聯(lián)構(gòu)成密文,即密文c=(c1,c2),因此密文的長(zhǎng)度是明文的兩倍。解密變換:由加密變換可知所以解密結(jié)果是正確的。7.5.3ElGamal算法的安全性ElGamal密碼體制的安全性基于有限群?p*上離散對(duì)數(shù)問(wèn)題的困難性。有學(xué)者曾提出,模p生成的離散對(duì)數(shù)密碼可能存在陷門,一些“弱”素?cái)?shù)p下的離散對(duì)數(shù)較容易求解。因此,要仔細(xì)選擇p,且g應(yīng)是模p的本原根,一般認(rèn)為這類問(wèn)題是困難的,而且目前尚未發(fā)現(xiàn)有效解決該問(wèn)題的多項(xiàng)式時(shí)間算法。此外,為了抵抗已知的攻擊,p應(yīng)該至少是300位的十進(jìn)制整數(shù),并且p-1應(yīng)該至少有一個(gè)較大的素?cái)?shù)因子。ElGamal算法的安全性還來(lái)自加密的不確定性。ElGamal體制的一個(gè)顯著特征是在加密過(guò)程中引入了隨機(jī)數(shù),這意味著相同的明文可能產(chǎn)生不同的密文,能夠給密碼分析者制造更大的困難。但在某些情況下,ElGamal體制也可能向攻擊者泄露部分信息。比如在實(shí)際應(yīng)用中,為了提高效率,一般會(huì)選用階r遠(yuǎn)小于p的生成元g,在這種情況下,如果一個(gè)比較短的消息m并不是由g生成的子群中的元素,那么類似于RSA體制的中間相遇攻擊則有可能成功。這是因?yàn)閷?duì)于密文攻擊者能夠得到即攻擊者將ElGamal的不確定加密體制轉(zhuǎn)化成一種確定性的算法,且具有指數(shù)運(yùn)算的可乘性。因此,對(duì)于一個(gè)容易分解的小尺寸的消息,攻擊者能夠?qū)rmodp實(shí)施中間相遇攻擊。由此可知,當(dāng)一個(gè)明文消息不屬于由g生成的子群的時(shí)候,ElGamal密碼體制就成為一種確定性的體制。由于確定性加密體制允許使用多次嘗試的方法來(lái)尋找小的明文消息,因此泄露了部分信息。所以,在應(yīng)用ElGamal公鑰體制,特別是推廣的ElGamal體制的時(shí)候,一定要注意生成元g的選擇,確保每一個(gè)可能的明文消息都是由g生成的。7.6橢圓曲線密碼7.6.1橢圓曲線的定義與性質(zhì)橢圓曲線的圖形并非橢圓,只是因?yàn)樗那€方程與計(jì)算橢圓周長(zhǎng)的方程類似,所以將其叫作橢圓曲線。通常所說(shuō)的橢圓曲線是指由Weierstrass方程所確定的平面曲線,其中a,b,c,d,e取自某個(gè)域F并滿足一些簡(jiǎn)單的條件。橢圓曲線通常用字母E表示,滿足曲線方程的序偶(x,y)就是域F上的橢圓曲線E上的點(diǎn)。域F可以是數(shù)域,也可以是某個(gè)有限域GF(pn)。除了滿足曲線方程的所有點(diǎn)(x,y)之外,橢圓曲線E還包括一個(gè)特殊的點(diǎn)O,稱為無(wú)窮遠(yuǎn)點(diǎn)。在上面的Weierstrass方程中用

代替y,得到其中,因此,橢圓曲線關(guān)于x軸對(duì)稱。圖7-2是實(shí)數(shù)域上橢圓曲線的兩個(gè)例子。我們可以在橢圓曲線E上定義一個(gè)二元運(yùn)算,使其成為Abel群,通常稱這個(gè)運(yùn)算為加法,并用表示,其定義如下所示。(1)取無(wú)窮遠(yuǎn)點(diǎn)O為單位元,因此對(duì)任何點(diǎn)(2)如果有三個(gè)點(diǎn)P,Q,R∈E且在同一條直線,那么(3)設(shè)P=(x,y)∈E,那么P的加法逆元定義為

這是因?yàn)镻與

的連線延長(zhǎng)到無(wú)窮遠(yuǎn)時(shí)將經(jīng)過(guò)無(wú)窮遠(yuǎn)點(diǎn)O,所以P,和O三點(diǎn)共線,即而橢圓曲線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定義如下:過(guò)P和Q畫一條直線L交橢圓曲線于另一點(diǎn)R,因?yàn)镻≠Q(mào),所以R是唯一的。因此,P⊕Q⊕R=O,即P⊕Q=-R。也就是說(shuō),P⊕Q是P與Q的連線L交橢圓曲線E上的另一點(diǎn)R關(guān)于x軸的對(duì)稱點(diǎn)。如上定義的加法運(yùn)算符合群的定義,同時(shí)滿足交換律,因此(E,⊕)是一個(gè)Abel群。在密碼學(xué)中使用的橢圓曲線通常定義在有限域上。也就是說(shuō),橢圓曲線方程中的所有系數(shù)都取自某個(gè)有限域GF(pn)。其中,最常用的是由有限域?p(p為素?cái)?shù))上的同余方程確定的橢圓曲線,即由此同余方程的所有解(x,y)∈?p

×?p,再加上一個(gè)特殊的無(wú)窮遠(yuǎn)點(diǎn)O,在上述加法運(yùn)算下構(gòu)造的Abel群。通常用Ep(a,b)來(lái)表示這樣得到的Abel群?？梢宰C明,在實(shí)數(shù)域,是保證方程

存在3個(gè)不同解(對(duì)于給定的y)的充分必要條件;否則,方程的3個(gè)解中至少有2個(gè)相同,并且稱這樣的橢圓曲線為奇異橢圓曲線。在?p

中要求

以保證曲線方程的各個(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ì)算過(guò)程):其中:實(shí)際上,?p上的橢圓曲線只是一些不連續(xù)的點(diǎn),并不像實(shí)數(shù)域上橢圓曲線有直觀的幾何解釋,但同樣定義的加法運(yùn)算能夠保證(Ep(a,b),⊕)仍然是一個(gè)Abel群。7.6.2橢圓曲線上的密碼體制和ElGamal密碼體制一樣,橢圓曲線密碼體制也是建立在離散對(duì)數(shù)問(wèn)題上的公鑰體制。我們已經(jīng)知道,由橢圓曲線可以生成Abel群,于是可以在這樣的群上構(gòu)造離散對(duì)數(shù)問(wèn)題。我們把使用有限域上橢圓曲線產(chǎn)生的Abel群Ep(a,b)構(gòu)造的離散對(duì)數(shù)問(wèn)題稱為橢圓曲線上的離散對(duì)數(shù)。目前的研究結(jié)果表明,解決橢圓曲線上的離散對(duì)數(shù)問(wèn)題的最好算法比解決標(biāo)準(zhǔn)有限域上的離散對(duì)數(shù)問(wèn)題的最好算法還要慢許多,這保證了在橢圓曲線上構(gòu)造密碼體制的可行性。橢圓曲線上的離散對(duì)數(shù)描述如下:設(shè)Ep(a,b)是有限域?p(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可直接求得;反過(guò)來(lái),由P和Q很難計(jì)算出k,特別是當(dāng)k很大時(shí),這個(gè)難度不亞于對(duì)k進(jìn)行分解。這個(gè)問(wèn)題稱為橢圓曲線上的離散對(duì)數(shù)問(wèn)題,有限域上的橢圓曲線提供了構(gòu)造離散對(duì)數(shù)的一個(gè)新途徑,可以將這種建立在橢圓曲線上的離散對(duì)數(shù)問(wèn)題應(yīng)用于公鑰密碼體制的構(gòu)造。橢圓曲線上的ElGamal公鑰密碼體制的描述如下:設(shè)Ep(a,b)是有限域?p(p>3的素?cái)?shù))上的一條橢圓曲線產(chǎn)生的Abel群,任取g∈Ep(a,b),且滿足在由g生成的子群H上的橢圓曲線離散對(duì)數(shù)問(wèn)題是難解的。再取正整數(shù)x<p,計(jì)算y=xg。公開密鑰取為g,y,p,私有密鑰取為x。加密變換:對(duì)于明文m,隨機(jī)選取正整數(shù)k<p,計(jì)算c1=kg和c2=m⊕ky。密文為c=(c1,c2)=(kg,m⊕ky)。解密變換:m=c2⊕(-xc1)。解密的正確性是顯而易見(jiàn)的。在使用橢圓曲線密碼算法時(shí),需要注意一個(gè)問(wèn)題:橢圓曲線密碼算法中的運(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)的嵌入編碼方法這里不予討論。下面利用例7.7的橢圓曲線及其Abel群E11(1,6)來(lái)說(shuō)明橢圓曲線密碼體制的操作細(xì)節(jié)。7.6.3橢圓曲線密碼算法的特性求解橢圓曲線上離散對(duì)數(shù)問(wèn)題的難度比求解標(biāo)準(zhǔn)有限域上離散對(duì)數(shù)問(wèn)題的難度更高,在同等難度的情況下,橢圓曲線密碼算法比RSA等基于因數(shù)分解的密碼算法有更小密鑰量。因此橢圓曲線密碼算法具有更好的密碼學(xué)特性,具體如下:(1)安全性高。現(xiàn)在已知的解決橢圓曲線上離散對(duì)數(shù)問(wèn)題的最好算法是以Pollardρ算法為代表的通用離散對(duì)數(shù)求解算法,該類算法的時(shí)間復(fù)雜度為

其中ρmax是Ep(a,b)的最大循環(huán)子群的階的最大素因子。而要解決有限域?p上的標(biāo)準(zhǔn)離散對(duì)數(shù)問(wèn)題,則可用指數(shù)積分法,它的時(shí)間復(fù)雜度為

其中,ρ是模數(shù),為素?cái)?shù)。顯然,橢圓曲線離散對(duì)數(shù)比有限域上的標(biāo)準(zhǔn)離散對(duì)數(shù)的復(fù)雜度更高,因此橢圓曲線密碼體制也更安全。(2)密鑰量小,運(yùn)算速度快。在同等安全級(jí)別的前提下,橢圓曲線密碼體制比其他公鑰密碼體制所需的密鑰位數(shù)要少得多。在算法的執(zhí)行速度方面,橢圓曲線上的一次群運(yùn)算最終化為域上不超過(guò)15次的乘法運(yùn)算,因此在算法實(shí)現(xiàn)上不成問(wèn)題,但目前還難以將橢圓曲線與現(xiàn)有的其他公鑰體制進(jìn)行準(zhǔn)確的定量比較,一個(gè)粗略的結(jié)論是橢圓曲線密碼體制比相應(yīng)的標(biāo)準(zhǔn)離散對(duì)數(shù)密碼體制快,且在

解

密

方

面

比RSA快,而

在

驗(yàn)

證

加

密

方

面

比RSA慢。所

以橢圓曲線密碼體制除了常規(guī)的應(yīng)用以外,在移動(dòng)計(jì)算設(shè)備和智能卡等存儲(chǔ)與計(jì)算能力受限的領(lǐng)域特別有優(yōu)勢(shì)。表7-2是在同等安全級(jí)別下,RSA算法與橢圓曲線算法所需密鑰大小的對(duì)比。(3)密碼資源豐富,靈活性好。對(duì)于一個(gè)給定的有限域,其上的循環(huán)群或者循環(huán)子群也

是

確

定

的

有

限

多

個(gè)。而

有限域上的橢圓曲線可以通過(guò)改變曲線方程的系數(shù),得到大量的不同曲線,進(jìn)而生成更多的循環(huán)群,這為算法的安全性增加了額外的保障,同時(shí)也為算法的實(shí)現(xiàn)提供了更大的靈活性。盡管橢圓曲線公鑰體制具有如此好的密碼學(xué)特性,經(jīng)過(guò)眾多密碼學(xué)家多年來(lái)的深入分析,還是發(fā)現(xiàn)了一些問(wèn)題。首先,正如DES算法存在某些容易破解的弱密鑰一樣,也有一些橢圓曲線,在其上建立的離散對(duì)數(shù)是易于求

解

的,并

且

有

人

給

出

了

對(duì)

應(yīng)

的

攻

擊

方

法。例

如,1993年,Menezes、Okamoto和Vanstone發(fā)

現(xiàn)

了

一

類

超

奇

異

橢

圓

曲

線

可

用

亞

指

數(shù)

攻

擊

法

破

解,這種方法現(xiàn)在被稱為MOV攻擊法。隨后,Semaev又發(fā)現(xiàn)了一類異常橢圓曲線可在線性時(shí)間內(nèi)求解。因此,在構(gòu)造橢

圓

曲

線

密

碼

體

制

時(shí)

應(yīng)

避

免

使

用

這

兩

類

曲

線。為

此,在選擇橢圓曲線時(shí)應(yīng)使所用Ep(a,b)的循環(huán)子群的階具有長(zhǎng)度不少于160位的素因子。這樣的橢圓曲線離散對(duì)數(shù)的安全水平相當(dāng)于有限域?p上標(biāo)準(zhǔn)離散對(duì)數(shù)在p的長(zhǎng)度不少于1000位情況下的安全性。之

所

以

有

如

此

大

的

差

異,是

因

為

已

知

的

指

數(shù)

積

分

攻

擊對(duì)橢圓曲線離散對(duì)數(shù)不起作用。其次,為抵抗已知的諸如Polardρ等求解橢圓曲線離散對(duì)數(shù)算法的攻擊,也應(yīng)該使橢圓曲線群Ep(a,b)具有階足夠大的循環(huán)子群,這一點(diǎn)與上述要求是一致的?？傊?已經(jīng)發(fā)現(xiàn)的橢圓曲線密碼體制的缺點(diǎn)還不多,大多

數(shù)

密

碼

學(xué)

家

對(duì)

這

種

公

鑰體制仍持

樂(lè)

觀

態(tài)

度,相

關(guān)

的

實(shí)

現(xiàn)

和

標(biāo)

準(zhǔn)

化

工

作

已

經(jīng)

逐

步

展

開,應(yīng)

用

的

領(lǐng)

域

也

日

漸擴(kuò)大。7.7SM2公鑰加密算法7.7.1SM2算法的描述我國(guó)從2001年開始組織研究自主知識(shí)產(chǎn)權(quán)的ECC(,橢圓曲線密碼學(xué))算法,2004年研制完成SM2橢圓曲線公鑰密碼算法(簡(jiǎn)稱SM2算法),2010年12月首次公開發(fā)布,2012年3月成為中國(guó)商用密碼標(biāo)準(zhǔn)(GM/T0003—2012),2016年8月成為中國(guó)國(guó)家密碼標(biāo)準(zhǔn)(GB/T32918—2016)。當(dāng)前,我國(guó)商用密碼行業(yè)對(duì)SM2算法正在進(jìn)行大規(guī)模地應(yīng)用和推廣,2011年3月中國(guó)人民銀行發(fā)布了《中國(guó)金融集成電路(IC)卡規(guī)范》(簡(jiǎn)稱PBOC3.0),PBOC3.0采用了SM2算法以增強(qiáng)金融IC卡應(yīng)用的安全性,以PBOC3.0為參考規(guī)范的非金融類應(yīng)用也基本采用了SM2算法。國(guó)際可信計(jì)算組織(TrustedComputingGroup,TCG)發(fā)布的TPM2.0規(guī)范采納了SM2算法。2016年10月,ISO/IECSC27會(huì)議通過(guò)了SM2算法標(biāo)準(zhǔn)草案,SM2算法進(jìn)入了ISO148883正式文本階段。這些重要事件將進(jìn)一步促進(jìn)SM2算法的應(yīng)用和推廣。SM2算法包含3個(gè)不同功能的算法:公鑰加密算法、數(shù)字簽名算法、密鑰交換協(xié)議。本節(jié)只介紹SM2公鑰加密算法。迄今為止的相關(guān)研究表明,SM2算法的可證安全性已經(jīng)達(dá)到了公鑰密碼算法的最高安全級(jí)別,其實(shí)現(xiàn)效率相當(dāng)于或略優(yōu)于一些國(guó)際標(biāo)準(zhǔn)的同類型橢圓曲線密碼算法。SM2公鑰加密算法共包含3個(gè)子算法,分別是密鑰派生函數(shù)、加密算法、解密算法。算法初始化時(shí)首先選擇有限域Fq上的橢圓曲線E,同時(shí)選擇該曲線上的基點(diǎn)G=(xG,yG),G的階為n,記稱為余因子。選擇Hash函數(shù)Hv(x),輸出長(zhǎng)度為v的Hash值,目前SM2一般取v=256。1.密鑰派生函數(shù)密鑰生成函數(shù)記作KDF(Z,Klen),其中:輸入:位串Z,整數(shù)Klen(該值表示要獲得的密鑰長(zhǎng)度,要求小于(232-1)v)。輸出:長(zhǎng)度為Klen的密鑰K。具體的函數(shù)計(jì)算過(guò)程如下:(1)初始化一個(gè)32位的計(jì)數(shù)器ct=00000001(十六進(jìn)制的形式)。(2)循環(huán)執(zhí)行以下操作,其中ct=1,2,…,(3)若

不是整數(shù),則最后一輪算出來(lái)

只取最左邊的(4)令

輸出長(zhǎng)度為Klen的密鑰K。2.SM2加密算法消息發(fā)送者A加密明文消息,將密文發(fā)送給消息接收者B,B解密密文得到原始的明文消息。設(shè)B的密鑰對(duì)分別為私鑰dB∈{1,2,…,n-1}和公鑰PB=dBG,待加密消息為M,M的長(zhǎng)度為Klen,則A需要執(zhí)行以下操作:(1)使用隨機(jī)數(shù)生成器產(chǎn)生隨機(jī)數(shù)k∈{1,2,…,n-1}。(2)計(jì)算橢圓曲線點(diǎn)C1=kG=(x1,y1),將C1轉(zhuǎn)換為位串。(3)計(jì)算橢圓曲線點(diǎn)S=hPB,若S是無(wú)窮遠(yuǎn)點(diǎn),則報(bào)錯(cuò)退出。(4)計(jì)算橢圓曲線點(diǎn)kPB=(x2,y2),將坐標(biāo)轉(zhuǎn)換為位串。(5)計(jì)算t=KDF(x2‖y2,Klen),若t為全0位串,則返回1,重新選擇k。(6)計(jì)算C2=M⊕t。(7)計(jì)算C3=Hash(x2‖M‖y2)。(8)輸出密文C=C1‖C2‖C3。SM2的加密流程如圖7-3所示。3.SM2解密算法接收者B接收到密文C=C1‖C2‖C3以后,執(zhí)行以下操作進(jìn)行解密:(1)從C中取出位串C1,將C1的數(shù)據(jù)類型轉(zhuǎn)換為橢圓曲線上的點(diǎn),驗(yàn)證C1是否滿足橢圓曲線方程,若不滿足則報(bào)錯(cuò)退出。(2)計(jì)算橢圓曲線上的點(diǎn)S=hC1,若S是無(wú)窮遠(yuǎn)點(diǎn),則報(bào)錯(cuò)退出。(3)計(jì)算dBC1=(x1,y2),將坐標(biāo)轉(zhuǎn)換為位串。(4)計(jì)算t=KDF(x2‖y2,Klen),若t為全0位串,則報(bào)錯(cuò)退出。(5)從C中取出位串C2,計(jì)算M'=C2⊕t。(6)計(jì)算u=Hash(x2‖M'‖y2),從C中取出位串C3,若u≠C3,則報(bào)錯(cuò)退出。(7)輸出明文M'。SM2的解密流程如圖7-4所示。4.解密的正確性分析根據(jù)上述解密算法的描述,如果整個(gè)解密過(guò)程不出現(xiàn)報(bào)錯(cuò)退出的情況,則第3步計(jì)算的(x2,y2)與加密算法中的一致,即此時(shí)第4步得到的t也與加密算法中的一致,最終第7步得到的M'滿足此外,第6步計(jì)算并與C3進(jìn)行比較,起到的是校驗(yàn)的作用,若相等則說(shuō)明解密正確,否則解密有錯(cuò)誤。7.7.2SM2加密算法的分析1.安全性分析由SM2的加解密過(guò)程可以看出,接收者B的公私鑰滿足條件PB=dBG。顯然,在已知G的前提下,由私鑰dB計(jì)算公鑰PB是容易的,但是要由公鑰PB計(jì)算私鑰dB就等價(jià)于求解橢圓曲線上的離散對(duì)數(shù)問(wèn)題。離散對(duì)數(shù)問(wèn)題的求解關(guān)系到SM2的安全性,因此SM2算法必須選擇安全的橢圓曲線,即避免弱橢圓曲線。目前對(duì)于一般橢圓曲線上的離散對(duì)數(shù)問(wèn)題,求解的方法均為采用指數(shù)級(jí)計(jì)算復(fù)雜度算法,未發(fā)現(xiàn)有效的亞指數(shù)級(jí)計(jì)算復(fù)雜度的攻擊方法,但是對(duì)于某些特殊曲線上的離散對(duì)數(shù)問(wèn)題,存在多項(xiàng)式級(jí)計(jì)算復(fù)雜度或者亞指數(shù)級(jí)計(jì)算復(fù)雜度算法,這些曲線稱為弱橢圓曲線。一般來(lái)說(shuō),為了避免Pollard方法的攻擊,基點(diǎn)G的階n必須是一個(gè)足夠大的素?cái)?shù),即G生成一個(gè)素?cái)?shù)階循環(huán)群。SM2算法采用的橢圓曲線參數(shù)經(jīng)檢測(cè)完全滿足安全性條件,其上的離散對(duì)數(shù)問(wèn)題不存在亞指數(shù)級(jí)計(jì)算復(fù)雜度的攻擊方法,n為256位的素?cái)?shù),具有足夠的長(zhǎng)度。SM2算法加密的過(guò)程中使用了Hash函數(shù),密文中的一部分C3是具有校驗(yàn)功能的Hash值,而計(jì)算C3所使用的位串又是根據(jù)一次性的秘密隨機(jī)數(shù)生成的。攻擊者不能獲得或偽造任何有效的密文,保證SM2算法具備CCA2的安全性。2.效率分析一般來(lái)說(shuō),ECC類加密算法的實(shí)現(xiàn)效率本身就優(yōu)于RSA。SM2加密算法的實(shí)現(xiàn)效率比起普通的ECC加密算法更高,這主要體現(xiàn)在加密的核心步驟C2=M⊕t是逐位模2加法,具有很高的加密速度。SM2加密算法的唯一不足在于密文偏長(zhǎng)。與普通ECC加密算法相比,SM2生成的密文包含了3部分,數(shù)據(jù)擴(kuò)張程度嚴(yán)重,但是擴(kuò)張的密文中的C3具備校驗(yàn)功能,又進(jìn)一步提高了算法的數(shù)據(jù)完整性和可靠性。目

前,SM2加

密

算

法

已

經(jīng)

得

到

了

廣

泛

的

應(yīng)

用

。例

如,我

國(guó)

正

在

推

廣

使

用

的eID(ElectronicIdentity,公民網(wǎng)絡(luò)電子身份標(biāo)識(shí))就使用了SM2算法。此外,SM2在可信計(jì)算、通信、金融、衛(wèi)生、電力系統(tǒng)等領(lǐng)域都有著廣泛的應(yīng)用。7.8基于身份的公鑰密碼體制7.8.1概述在公鑰密碼的實(shí)際應(yīng)用中,需要一種機(jī)制能夠很方便地驗(yàn)證公鑰與主體身份之間的聯(lián)系,對(duì)于這一問(wèn)題,傳統(tǒng)的解決方法是采用基于公鑰基礎(chǔ)設(shè)施(PublicKeyInfrastructure,PKI)的公鑰證書機(jī)制,但這種方式的證書管理過(guò)程需要很高的計(jì)算開銷和存儲(chǔ)開銷。為了簡(jiǎn)化證書

管

理

工

作,1984年,Shamir首

先

提

出

了

基

于

身

份

密

碼

體

制的思想。在這種新的密碼系統(tǒng)中,用戶的身份信息直接作為公鑰,或者公鑰可以容易地從身份信息中計(jì)算得到,而私鑰則由可信的第三方私鑰生成中心產(chǎn)生后發(fā)送給用戶。當(dāng)用戶使用通信對(duì)方的公鑰時(shí),僅需知道其身份信息,而無(wú)須獲得并驗(yàn)證其公鑰證書,這樣就大大節(jié)省了公鑰證書管理和使用中的開銷。為了闡述IBC的工作過(guò)程,Shamir設(shè)計(jì)了一個(gè)郵件加密的方案,當(dāng)用戶Alice向Bob發(fā)送郵件時(shí),假設(shè)Bob的郵箱為Bob@,則Alice直接用公開的字符串Bob@加密信息即可,無(wú)須從任何證書管理機(jī)構(gòu)獲得Bob的公鑰證書。Bob收到密文時(shí),與PKG聯(lián)系,通過(guò)認(rèn)證后,得到自己的私鑰,從而解密信息。這樣做可以大大簡(jiǎn)化郵件系統(tǒng)中的密鑰管理,使公鑰密碼的應(yīng)用變得極為方便?？梢钥吹?基于身份的密碼系統(tǒng)與傳統(tǒng)基于證書的密碼系統(tǒng)都屬于公鑰密碼體制,具有相似的功能,但是基于身份的密碼系統(tǒng)的用戶公鑰直接與身份信息自然地綁定在一起,不再需要證書和公鑰目錄,因此在密鑰生成和管理方面具有很大的優(yōu)勢(shì),節(jié)約了計(jì)算和通信成本。一個(gè)理想的基于身份的密碼系統(tǒng)應(yīng)滿足以下幾個(gè)特點(diǎn):(1)用戶只需知道通信對(duì)方的身份。(2)用戶不用存儲(chǔ)任何公鑰、證書之類的列表。(3)PKG只是在系統(tǒng)的建立階段提供服務(wù),且用戶絕對(duì)無(wú)條件信任該可信機(jī)構(gòu)。傳統(tǒng)基于證書密碼體制與基于身份的密碼體制的相同之處在于:(1)都屬于公開密鑰體系,具有一對(duì)公開密鑰和私有密鑰,公開密鑰可以公開,私有密鑰由用戶秘密保存。(2)用戶的身份都需要認(rèn)證。傳統(tǒng)基于證書密碼體制中,用戶需要向證書權(quán)威機(jī)構(gòu)CA證實(shí)自己的身份;基于身份的密碼體制中,用戶需要向PKG證實(shí)自己的身份。(3)公鑰和私鑰用于加密方案中,都是公鑰用于加密,私鑰用于解密;用于簽名方案中,都是私鑰用于簽名,公鑰用于驗(yàn)證簽名。(4)體系的安全性都可以依賴于大數(shù)分解、離散對(duì)數(shù)求解、橢圓曲線求解等數(shù)學(xué)難題。傳統(tǒng)基于證書密碼體制與基于身份的密碼體制的不同之處在于:(1)密鑰生成過(guò)程不同。傳統(tǒng)基于證書的密碼體制中,用戶的私鑰和公鑰同時(shí)產(chǎn)生。由用戶先選取私鑰,然后計(jì)算出公鑰=F(私鑰)(其中F是一個(gè)從私鑰空間映射到公鑰空間的有效單向函數(shù))?；谏矸莸拿艽a體制中,用戶的公鑰是已經(jīng)被公開的用戶的身份信息,由PKG為用戶生成私鑰,私鑰=F(主密鑰,公鑰),其中主密鑰由PKG秘密保存。由此可見(jiàn),這兩種密碼體制的密鑰生成過(guò)程正好相反。(2)用戶身份信息的獲取方式不同。在傳統(tǒng)基于證書的密碼體制中,用戶的身份