本科生必修課現(xiàn)代密碼學(xué)

本科生必修課：現(xiàn)代密碼學(xué)第四章公鑰密碼主講教師：董慶寬研究方向：密碼學(xué)與信息安全Email：qkdong@個(gè)人主頁：http:///qkdong/14.1密碼學(xué)中常用數(shù)學(xué)知識(shí)4.2公鑰密碼體制的基本概念4.3RSA算法4.4背包體制4.5Rabin體制

4.6NTRU公鑰密碼系統(tǒng)4.7橢圓曲線密碼體制4.8基于身份的密碼體制本章提要24.1密碼學(xué)中的常用數(shù)學(xué)知識(shí)群、環(huán)、域、素?cái)?shù)模運(yùn)算費(fèi)爾馬定理ap-1=1modp

，p是素?cái)?shù)歐拉函數(shù)(n)：小于n的且與n互素的正整數(shù)個(gè)數(shù)a(n)=1modn

素性檢驗(yàn)1.愛拉托斯散篩法(Eratosthenes)依次刪去小于素?cái)?shù)的倍數(shù)2.Miller-Rabin概率檢測法√3.AKS歐幾里得算法、擴(kuò)展歐幾里德算法求最大公約數(shù)和乘法的逆元中國剩余定理求一次同余方程組的解離散對(duì)數(shù)，本原根平方剩余計(jì)算復(fù)雜性3擴(kuò)展歐幾里德算法，求逆元計(jì)算dmodf的逆元1.(X1,X2,X3)(1,0,f);(Y1,Y2,Y3)(0,1,d);2.ifY3=0,thenreturnX3=gcd(f,d)3.ifY3=1,thenreturnY3=gcd(f,d);Y2=d-1modf4.Q=X3/Y35.(T1,T2,T3)(X1-QY1,X2-QY2,X3-QY3);6.(X1,X2,X3)(Y1,Y2,Y3)7.(Y1,Y2,Y3)(T1,T2,T3)8.goto24Miller-Rabin概率檢測法原理：若p是大于2的素?cái)?shù)，則x2=1modp只有1和-1兩個(gè)解，所以如果方程x2=1modp有一解x0{-1,1}，那么p不為素?cái)?shù)算法：(a<n是隨機(jī)選擇的一個(gè)數(shù)，n是待檢驗(yàn)的數(shù)，返回False則一定不是素?cái)?shù)，返回True則不一定是素?cái)?shù)）令d=1；n-1的二進(jìn)制表示為bkbk-1…b0fori=k

downto0do{

xd;d(dd)modn;(此時(shí)d剛好是x的平方)ifd=1andx1andxn-1thenreturnFalse;ifbi=1thend(da)modn;}ifd1thenreturnFalse;ReturnTrue;循環(huán)結(jié)束后有d=an-1modn，若d1，則n不是素?cái)?shù)。x1andxn-1意指x2=1modp有不在{-1,1}中的根該測試如果進(jìn)行s次，如果都是真T，則n是素?cái)?shù)的概率最小為1-2-s54.2公鑰密碼體制的基本概念公鑰密碼體制的出現(xiàn)在密碼學(xué)史上是一個(gè)最大的而且是惟一真正的革命。為密碼學(xué)發(fā)展提供了新的理論和技術(shù)基礎(chǔ)公鑰密碼算法基本工具不再是代換和置換，而是數(shù)學(xué)函數(shù)以非對(duì)稱的形式使用兩個(gè)密鑰，兩個(gè)密鑰的使用對(duì)保密性、密鑰分配、認(rèn)證等都有著深刻的意義。公鑰密碼體制的概念是在解決單鑰密碼體制中最難解決的兩個(gè)問題時(shí)提出的，即密鑰分配和數(shù)字簽字6對(duì)稱密碼算法的缺陷密鑰分配問題：通信雙方加密通信前要通過秘密的安全信道協(xié)商加密密鑰，這種安全信道可能很難實(shí)現(xiàn)；對(duì)這個(gè)信道安全性的要求比正常傳送消息信道的安全性要高密鑰管理問題：在多用戶網(wǎng)絡(luò)中，任何兩個(gè)用戶之間都需要有共享的秘密鑰，n個(gè)用戶需要Cn2=n(n-1)/2個(gè)密鑰，n=5000時(shí)，Cn2=12,497,500，系統(tǒng)開銷非常大沒有簽名功能：當(dāng)主體A收到主體B的電子文擋時(shí)，無法向第三方證明此電子文檔確實(shí)來源于B，傳統(tǒng)單鑰加密算法無法實(shí)現(xiàn)抗抵賴的需求7公鑰密碼的主要作用公鑰加密用于加密任何消息，象分組密碼一樣使用任何人可以用公鑰加密消息，私鑰的擁有者可以解密消息數(shù)字簽名(DigitalSignature)用于生成對(duì)某消息的數(shù)字簽名私鑰的擁有者生成數(shù)字簽名，任何人可以用公鑰驗(yàn)證簽名簽名時(shí)可將公鑰加密算法逆用來實(shí)現(xiàn)，也可單獨(dú)設(shè)計(jì)公鑰簽名算法基于公鑰的密鑰分配(KeyDistribution)用于交換秘密信息，常用于協(xié)商對(duì)稱加密算法的密鑰可采用公鑰加密的算法實(shí)現(xiàn)密鑰分配也可使用單獨(dú)設(shè)計(jì)的密鑰交換算法，如DH密鑰交換協(xié)議實(shí)現(xiàn)密鑰分配其它應(yīng)用：零知識(shí)證明，公平拋幣等等，（用于各種目的的認(rèn)證）參考資料：《公鑰密碼學(xué)》等84.2.1公鑰密碼體制的原理公鑰密碼算法的最大特點(diǎn)是采用兩個(gè)相關(guān)密鑰將加密和解密能力分開一個(gè)密鑰是公開的，稱為公開密鑰，簡稱公開鑰，用于加密、驗(yàn)證簽名，可以被任何人知道另一個(gè)密鑰是為用戶專用，因而是保密的，只能被消息的接收者或簽名者知道，稱為秘密密鑰，簡稱秘密鑰，用于解密、產(chǎn)生簽名因此公鑰密碼體制也稱為雙鑰密碼體制算法有以下重要特性：已知密碼算法和加密密鑰，求解密密鑰在計(jì)算上是不可行的因此加密和簽名的驗(yàn)證者不能解密和生成簽名9公鑰體制的加密過程①密鑰的產(chǎn)生：要求接收消息的端系統(tǒng)，產(chǎn)生一對(duì)用來加密和解密的密鑰PKB和SKB，如圖中的接收者B，其中PKB是公開鑰，SKB是秘密鑰。因此，公鑰可以發(fā)布給其他人②公開鑰的分發(fā)：端系統(tǒng)B將加密密鑰(PKB)予以公開。另一密鑰則被保密(SKB)③加密：A要想向B發(fā)送消息m，則使用B的公開鑰加密m，表示為c=EPKB[m]其中c是密文，E是加密算法④解密：B收到密文c后，用自己的秘密鑰SKB解密，即m=DSKB[c]，其中D是解密算法。因?yàn)橹挥蠦知道SKB，所以其他人都無法對(duì)c解密。10公鑰體制的認(rèn)證過程公鑰加密算法不僅能用于加、解密，還能用于對(duì)發(fā)方A發(fā)送的消息m提供認(rèn)證用戶A用自己的秘密鑰SKA對(duì)m加密，表示為c=ESKA[m]將c發(fā)往B。B用A的公開鑰PKA對(duì)c解密，表示為m=DPKA[c]因?yàn)閺膍得到c是經(jīng)過A的秘密鑰SKA加密，只有A才能做到。因此c可當(dāng)做A對(duì)m的數(shù)字簽字。任何人只要得不到A的秘密鑰SKA就不能篡改m，所以以上過程獲得了對(duì)消息來源和消息完整性的認(rèn)證。11認(rèn)證符：通過單向壓縮函數(shù)(hash)解決長文件的簽字用戶數(shù)目很多時(shí)，單純加解密的認(rèn)證方法需要很大的存儲(chǔ)空間因?yàn)槊總€(gè)文件都必須以明文形式存儲(chǔ)以方便實(shí)際使用，同時(shí)還必須存儲(chǔ)每個(gè)文件被加密后的密文形式即數(shù)字簽字，以便在有爭議時(shí)用來認(rèn)證文件的來源和內(nèi)容改進(jìn)的方法是減小文件的數(shù)字簽字的大小，即先將文件經(jīng)過一個(gè)函數(shù)壓縮成長度較小的比特串，得到的比特串稱為認(rèn)證符12認(rèn)證符具有這樣一個(gè)性質(zhì)：如果保持認(rèn)證符的值不變而修改文件，在計(jì)算上是不可行的簽名過程中，往往用發(fā)送者的秘密鑰對(duì)認(rèn)證符加密，加密后的結(jié)果為原文件的數(shù)字簽字。(詳見第7章)13公鑰體制同時(shí)提供加密和認(rèn)證的過程認(rèn)證過程中，由于消息是由用戶自己的秘密鑰加密的，所以消息不能被他人篡改，但卻能被他人竊聽。這是因?yàn)槿魏稳硕寄苡糜脩舻墓_鑰對(duì)消息解密。為了同時(shí)提供認(rèn)證功能和保密性，可使用雙重加、解密先簽名后加密：發(fā)方首先用自己的秘密鑰SKA對(duì)消息m加密，用于提供數(shù)字簽字。再用收方的公開鑰PKB第2次加密，表示為c=EPKB[ESKA[m]]先解密再驗(yàn)證：解密過程為m=DPKA[DSKB[c]]即收方先用自己的秘密鑰，再用發(fā)方的公開鑰對(duì)收到的密文兩次解密。如果先加密后簽名是不安全的，別人可以先將簽名去掉，再簽上自己的簽名，從而實(shí)現(xiàn)了篡改。144.2.2公鑰密碼算法應(yīng)滿足的要求公鑰密碼算法應(yīng)滿足以下要求①收方B產(chǎn)生密鑰對(duì)（公開鑰PKB和秘密鑰SKB）在計(jì)算上是容易的。由私鑰及其他密碼信息容易計(jì)算出公開密鑰(P問題)②發(fā)方A用收方的公開鑰對(duì)消息m加密以產(chǎn)生密文c，即c=EPKB[m]在計(jì)算上是容易的③收方B用自己的秘密鑰對(duì)c解密，即m=DSKB[c]在計(jì)算上是容易的④敵手由B的公開鑰PKB求秘密鑰SKB在計(jì)算上是不可行的⑤敵手由密文c和B的公開鑰PKB恢復(fù)明文m在計(jì)算上是不可行的⑥加、解密次序可換，即EPKB[DSKB(m)]=DSKB[EPKB(m)]其中最后一條雖然非常有用，但不是對(duì)所有的算法都作要求。在構(gòu)建盲簽字等算法時(shí)需要類似要求以上要求的本質(zhì)之處在于要求一個(gè)陷門單向函數(shù)。15單向函數(shù)是兩個(gè)集合X、Y之間的一個(gè)映射，使得Y中每一元素y都有惟一的一個(gè)原像x∈X，且由x易于計(jì)算它的像y，由y計(jì)算它的原像x是不可行的“易于計(jì)算”是指函數(shù)值能在其輸入長度的多項(xiàng)式時(shí)間內(nèi)求出，即如果輸入長n比特，則求函數(shù)值的計(jì)算時(shí)間是na

的某個(gè)倍數(shù)，其中a是一固定的常數(shù)這時(shí)稱求函數(shù)值的算法屬于多項(xiàng)式類P，否則就是不可行的，例如，函數(shù)的輸入是n比特，如果求函數(shù)值所用的時(shí)間是2n的某個(gè)倍數(shù)，則認(rèn)為求函數(shù)值是不可行的16易于計(jì)算和不可行兩個(gè)概念與計(jì)算復(fù)雜性理論中復(fù)雜度的概念極為相似，然而又存在著本質(zhì)的區(qū)別在復(fù)雜性理論中，算法的復(fù)雜度是以算法在最壞情況或平均情況時(shí)的復(fù)雜度來度量的。這時(shí)可能對(duì)某些情況很容易求解，復(fù)雜度很低而在此所說的兩個(gè)概念是指算法在幾乎所有情況下的情形17陷門單向函數(shù)稱一個(gè)函數(shù)是陷門單向函數(shù)，是指該函數(shù)是易于計(jì)算的，但求它的逆是不可行的，除非再已知某些附加信息。當(dāng)附加信息給定后，求逆可在多項(xiàng)式時(shí)間完成總結(jié)為：陷門單向函數(shù)是一族可逆函數(shù)fk，滿足①當(dāng)k和X已知時(shí)，Y=fk(X)易于計(jì)算②當(dāng)k和Y已知時(shí)，X=fk-1(Y)易于計(jì)算③當(dāng)Y已知但k未知時(shí)，X=fk-1(Y)計(jì)算上是不可行的研究公鑰密碼算法就是要找出合適的陷門單向函數(shù)184.2.3對(duì)公鑰密碼體制的攻擊以下討論的攻擊是指對(duì)所有公鑰密碼體制都有效的平凡的攻擊涉及到公鑰算法所基于的困難問題的安全性和參數(shù)空間大小的安全性第一種平凡的攻擊：（窮搜索攻擊與密鑰長度）如果密鑰太短，公鑰密碼體制也易受到窮搜索攻擊然而又由于公鑰密碼體制所使用的可逆函數(shù)的計(jì)算復(fù)雜性與密鑰長度常常不是呈線性關(guān)系，而是增大得更快。所以密鑰長度太大又會(huì)使得加解密運(yùn)算太慢而不實(shí)用因此公鑰密碼體制目前主要用于密鑰管理和數(shù)字簽字。即處理短消息如密鑰和hash值19第二種平凡的攻擊是尋找從公開鑰計(jì)算秘密鑰的方法目前為止，對(duì)常用公鑰算法還都未能夠證明這種攻擊是不可行的第三種平凡的攻擊：(可能字攻擊)僅適用于對(duì)公鑰密碼算法的攻擊例如對(duì)56比特的DES密鑰用公鑰密碼算法加密后發(fā)送，敵手用算法的公開鑰對(duì)所有可能的密鑰加密后與截獲的密文相比較如果一樣，則相應(yīng)的明文即DES密鑰就被找出。因此不管公鑰算法的密鑰多長，攻擊的本質(zhì)是對(duì)56比特DES密鑰的窮搜索攻擊抵抗方法是在欲發(fā)送的明文消息后添加一些隨機(jī)比特不同的公鑰密碼算法在設(shè)計(jì)和實(shí)現(xiàn)中的密碼協(xié)議是影響安全性的主要方面，不同算法的攻擊不同。公鑰的安全性是指計(jì)算上的安全性2021典型算法和困難問題IKE使用DH密鑰交換RSA(基于大數(shù)分解困難問題)RSA系列算法，Rabin體制DLP(基于求解離散對(duì)數(shù)困難問題)ElGamal加密體制ECC(橢圓曲線公鑰密碼體制)ECC上雙線性對(duì)，ECC上基于身份的密碼體制基于格的概率加密體制(NTRU…)，基于糾錯(cuò)碼的體制…22量子密碼量子計(jì)算，可能破譯RSA，DSA，ECDSA實(shí)現(xiàn)對(duì)稱密鑰分發(fā)，準(zhǔn)確的說法是量子密鑰分配，目前也有一些量子簽名，量子加密等方面的研究后量子密碼學(xué)post-quantumcryptography2006年在比利時(shí)魯汶天主教大學(xué)召開了第一次后量子密碼學(xué)的國際會(huì)議DanielJ.Bernstein,JohannesBuchmann,ErikDahmen,“Post-QuantumCryptography,”Springer-Verlag,pp.245,2009.幾種量子計(jì)算尚不能征服的密碼體制基于Hash的密碼（Hash-basedcryptography）如Merkle于1979年提出的hash樹公鑰簽名體制，按Lamport和Diffie的單消息簽名概念構(gòu)建的23基于編碼（糾錯(cuò)碼）的密碼(Hash-basedcryptography)如McEliece1978年提出的隱Goppa碼公鑰加密體制。王新梅教授提出的新梅算法基于格的密碼（Code-basedcryptography）Hoffstein-Pipher-Silverman于1998年提出的“NTRU”公鑰加密體制，雖不是第一個(gè)，但為最引人注目的一個(gè)多變量二次方程密碼（Multivariate-quadratic-equationscryptography)如Patarin于1996年提出的“HFEv-”公鑰簽名體制就是幾個(gè)重要例子中的一個(gè)，此例后為Matsumoto和Imai所推廣秘密（單）鑰密碼（Secret-keycryptography）如高級(jí)數(shù)據(jù)加密標(biāo)準(zhǔn)AES244.3RSA算法1978年由R.Rivest,A.Shamir和L.Adleman提出的一種用數(shù)論構(gòu)造的、也是迄今為止理論上最為成熟完善的公鑰密碼體制，已得到廣泛的應(yīng)用RLRivest,AShamir,LAdleman,"OnDigitalSignaturesandPublicKeyCryptosystems",CommunicationsoftheACM,vol21no2,pp120-126,Feb1978它既可用于加密、又可用于數(shù)字簽字。RSA算法的安全性是基于數(shù)論中大整數(shù)分解的困難性(但可能達(dá)不到大數(shù)分解的困難強(qiáng)度)IEEEP1363公鑰密碼標(biāo)準(zhǔn)254.3.1算法描述1．密鑰的產(chǎn)生①選兩個(gè)保密的大素?cái)?shù)p和q②計(jì)算n=p×q，(n)=(p-1)(q-1)，其中(n)是n的歐拉函數(shù)值③選一整數(shù)e，滿足1<e<(n)，且gcd((n),e)=1④計(jì)算d，滿足d·e≡1mod(n)，即d是e在模(n)下的乘法逆元，因e與(n)互素，模(n)的乘法逆元一定存在⑤以{e,n}為公開鑰,{d,p,q}為秘密鑰秘密鑰也可記為d，或{d,n}，如果是系統(tǒng)負(fù)責(zé)產(chǎn)生密鑰，則用戶可能不知道p,q262．加密加密時(shí)首先將明文比特串分組，使得每個(gè)分組對(duì)應(yīng)的十進(jìn)制數(shù)小于n，即分組長度小于log2n。然后對(duì)每個(gè)明文分組m，作加密運(yùn)算：

c≡memodn3．解密對(duì)密文分組的解密運(yùn)算為：

m≡cdmodn27RSA算法中解密過程的正確性證明證明：由c≡memodn，可知cd

modn≡medmodn≡mk(n)+1modn下面分兩種情況：①

m與n互素，則由Euler定理得m(n)≡1modn，mk(n)≡1modn，mk(n)+1≡mmodn即cdmodn≡m②gcd(m,n)≠1，因n=pq，所以m是p的倍數(shù)或q的倍數(shù)，不妨設(shè)m=cp，其中c為一正整數(shù)。此時(shí)必有g(shù)cd(m,q)=1，否則m也是q的倍數(shù)，從而是pq的倍數(shù)，與m<n=pq矛盾。由gcd(m,q)=1及Euler定理得m(q)≡1modq，所以mk(q)≡1modq，(mk(q))(p)≡1modq，即mk(n)≡1modq因此存在一整數(shù)r，使得mk(n)＝1+rq，兩邊同乘以m=cp得mk(n)＋1＝m+rcpq＝m+rcn即mk(n)＋1＝mmodn，所以cdmodn≡m。(證畢)28【例4-24】：選p=7，q=17。求n=p×q=119，(n)=(p-1)(q-1)=96取e=5，滿足1<e<(n)，且gcd((n),e)=1確定滿足d·e=1mod96且小于96的d，因?yàn)?7×5=385=4×96+1，所以d為77公開鑰為{5，119}，秘密鑰為{77}設(shè)明文m=19，則由加密過程得密文為c≡195mod119≡2476099mod119≡66解密為6677mod119≡19【例4-25】略加密長消息時(shí)相當(dāng)于一個(gè)分組密碼算法首先將明文比特串分組，使得每個(gè)分組對(duì)應(yīng)的十進(jìn)制數(shù)小于n，即分組長度小于log2n294.3.2RSA算法中的計(jì)算問題1.RSA的加密與解密過程①模運(yùn)算的累次乘法RSA的加密、解密過程都為求一個(gè)整數(shù)的整數(shù)次冪，再取模如果按其含義直接計(jì)算，則中間結(jié)果非常大，有可能超出計(jì)算機(jī)所允許的整數(shù)取值范圍。如上例中解密運(yùn)算6677mod119，先求6677再取模，則中間結(jié)果就已遠(yuǎn)遠(yuǎn)超出了計(jì)算機(jī)允許的整數(shù)取值范圍。用模運(yùn)算的性質(zhì)：即采用累次乘法，可減小中間結(jié)果(a×b)modn=[(amodn)×(bmodn)]modn30②蒙哥馬利模乘算法避免求模過程中復(fù)雜耗時(shí)的除法（P.L.Montgomery,1985年提出)計(jì)算TR-1modN(1)T=(T+MN)/R(2)IFTNreturnT-N;ELSEreturnT其中M=(TmodR)×(N-1modR)modR，且0<T<NR而且顯然有R(R-1modN)+N(N-1modR)=1+RN(R-1modN)以及(N-1modR）可預(yù)計(jì)算，R常取2的冪次31蒙哥馬利模乘算法計(jì)算Z=XYR-1modM32③快速指數(shù)算法考慮如何提高加、解密運(yùn)算中模指數(shù)運(yùn)算的有效性。例如求x16，直接計(jì)算需做15次乘法。若重復(fù)對(duì)每個(gè)部分結(jié)果做平方運(yùn)算即求x，x2，x4，x8，x16則只需4次乘法求am可如下進(jìn)行，其中a，m是正整數(shù)：將m表示為二進(jìn)制形式bkbk-1…b0，即m=bk2k+bk-12k-1+…+b12+b0因此am＝例如：19=1×24+0×23+0×22+1×21+1×20，所以a19=((((a1)2a0)2a0)2a1)2a133快速指數(shù)算法：c=0;

d=1；fori=k

downto0do{

c=2×c;//僅為驗(yàn)證以上過程，而在具體算法中可刪去

d=(d×d)modn;//計(jì)算平方

ifbi=1then{

c=c+1;//僅為驗(yàn)證以上過程，而在具體算法中可刪去

d=(d×a)modn//bi=1時(shí)與a相乘

}}returnd.其中d是中間結(jié)果，d的終值即為所求結(jié)果。c在這里的作用是表示指數(shù)的部分結(jié)果，其終值即為指數(shù)m，c對(duì)計(jì)算結(jié)果無任何貢獻(xiàn)，算法中完全可將之去掉34計(jì)算復(fù)雜度:l＋W(m)次模乘（m為模指數(shù)）l為指數(shù)的bit長，W(m)為指數(shù)m的重量(二進(jìn)制比特1的個(gè)數(shù))例：求7560mod561。將560表示為1000110000，算法的中間結(jié)果如表4-6所示所以7560mod561=1(561＝3x11x17,(561)=2x10x16=320,780=1mod561)i

9876543210bi

1000110000c01248173570140280560d174915752616024129816667135T進(jìn)制快速模指數(shù)算法：求am可如下進(jìn)行：將m表示為T進(jìn)制形式bkbk-1…b0，即m=bkTk+bk-1Tk-1+…+b1T+b0取T=2wam=首先預(yù)計(jì)算出aimodn，其中i=1,2，…，2w-1再用快速模指數(shù)運(yùn)算w的選擇與預(yù)計(jì)算需要的存儲(chǔ)空間有關(guān)36④一種改進(jìn)的RSA實(shí)現(xiàn)方法(即4.3.3節(jié)）

RSA的加密很快，因?yàn)榧用苤笖?shù)e一般選擇得很小解密指數(shù)d很大，需要計(jì)算模300digits(or1024bits)的乘法，計(jì)算機(jī)不能直接處理這么大的數(shù)，計(jì)算速度很慢，需要考慮其它技術(shù)，加速RSA的實(shí)現(xiàn)如果知道p和q，可采用中國剩余定理CRT：CRT對(duì)RSA解密算法生成兩個(gè)解密方程（利用M=CdmodN，N=pq）即：M1=Mmodp=(Cmodp)d

mod(p-1)modp

M2=Mmodq=(Cmodq)dmod(q-1)modq解方程M=M1modp

M=M2modq

具有唯一解（利用CRT）：

M=M1×q×(q－1modp)+M2×p×(p－1modq)modN不考慮CRT的計(jì)算代價(jià)，改進(jìn)的算法的解密速度是原來的4倍若考慮CRT的計(jì)算代價(jià)，改進(jìn)后的算法解密速度是原來的3倍多372.RSA密鑰的產(chǎn)生需考慮兩個(gè)大素?cái)?shù)p、q的選取，以及e的選取和d的計(jì)算n(=pq)是公開的，為了防止敵手通過窮搜索發(fā)現(xiàn)p、q，這兩個(gè)素?cái)?shù)應(yīng)是在一個(gè)足夠大的整數(shù)集合中選取的大數(shù)(1)如何有效地尋找大素?cái)?shù)是第一個(gè)需要解決的問題尋找大素?cái)?shù)時(shí)一般是先隨機(jī)選取一個(gè)大的奇數(shù)（例如用偽隨機(jī)數(shù)產(chǎn)生器），然后用素性檢驗(yàn)算法檢驗(yàn)這一奇數(shù)是否為素?cái)?shù)，如果不是則選取另一大奇數(shù)，重復(fù)這一過程，直到找到素?cái)?shù)為止素性檢驗(yàn)算法通常都是概率性的，常用Miller-Rabin概率檢測算法實(shí)現(xiàn)尋找大素?cái)?shù)是一個(gè)比較繁瑣的工作，然而在RSA體制中，只有在產(chǎn)生新密鑰時(shí)才需執(zhí)行這一工作38(2)p和q決定出后，下一個(gè)需要解決的問題是如何選取滿足1<e<(n)和gcd((n),e)=1的e，并計(jì)算滿足d·e≡1mod(n)的d這一問題可由推廣的Euclid算法完成注意：注意用于產(chǎn)生大素?cái)?shù)的隨機(jī)數(shù)之間的不可預(yù)測性，如果可預(yù)測，則p和q的安全性就沒有了RSA的模很長，如模n為1024比特的RSA一次加密約1024比特明文，相當(dāng)于16次DES加密，但一次RSA比16次DES要慢很多，不在一個(gè)數(shù)量級(jí)上）394.3.4RSA的安全性RSA的安全性是基于分解大整數(shù)的困難性假定之所以為假定是因?yàn)橹两襁€未能證明分解大整數(shù)就是NP問題，也許有尚未發(fā)現(xiàn)的多項(xiàng)式時(shí)間分解算法如果RSA的模數(shù)n被成功地分解為p×q，則立即求得(n)，從而能夠確定e模(n)的乘法逆元d，即d≡e-1mod(n)，因此攻擊成功隨著人類計(jì)算能力的不斷提高，原來被認(rèn)為是不可能分解的大數(shù)已被成功分解例如RSA-129（即n為129位十進(jìn)制數(shù)，大約428個(gè)比特）已在網(wǎng)絡(luò)上通過分布式計(jì)算歷時(shí)8個(gè)月于1994年4月被成功分解RSA-130已于1996年4月被成功分解RSA-140已于1999年2月被成功分解RSA-155（512bit）已于1999年8月被成功分解RSA-158，2002年被成功分解，現(xiàn)在768比特的模值已經(jīng)被分解40量子計(jì)算：可能解決大整數(shù)分解問題（分解15和21）對(duì)于大整數(shù)的威脅除了人類的計(jì)算能力外，還來自分解算法的進(jìn)一步改進(jìn)分解算法過去都采用二次篩法，如對(duì)RSA-129的分解而對(duì)RSA-130的分解則采用了一個(gè)新算法，稱為推廣的數(shù)域篩法，該算法在分解RSA-130時(shí)所做的計(jì)算僅比分解RSA-129多10%。對(duì)RSA-140和RSA-155的分解也采用此法將來也可能還有更好的分解算法因此在使用RSA算法時(shí)對(duì)其密鑰的選取要特別注意其大小。估計(jì)在未來一段比較長的時(shí)期，密鑰長度介于1024比特至2048比特之間的RSA是安全的41是否有不通過分解大整數(shù)的其他攻擊途徑？下面證明由n直接確定φ(n)等價(jià)于對(duì)n的分解設(shè)n=p×q中，p>q，由

(n)=(p-1)(q-1)，則有

p+q=n－(n)+1，以及

p-q=由此可見，由p、q確定(n)和由(n)確定p、q是等價(jià)的42為保證算法的安全性，對(duì)p和q提出以下要求：(1)|p-q|要大由(p+q)2/4－n=(p+q)2/4－pq=(p－q)2/4，如果|p-q|小，則(p－q)2/4也小，因此(p+q)2/4稍大于n，(p+q)/2稍大于n1/2?？傻胣的如下分解步驟：①順序檢查大于n1/2的每一整數(shù)x，直到找到一個(gè)x使得x2-n是某一整數(shù)（記為y）的平方。②由x2-n=y2，得n=(x+y)(x-y)。(2)p-1和q-1都應(yīng)有大素因子(強(qiáng)素?cái)?shù))這是因?yàn)镽SA算法存在著可能的重復(fù)加密攻擊法。43重復(fù)加密攻擊法設(shè)攻擊者截獲密文c，可如下進(jìn)行重復(fù)加密：

…若，則有，即所以在上述重復(fù)加密的倒數(shù)第2步就已恢復(fù)出明文m這種攻擊法只有在t較小時(shí)才是可行的。為抵抗這種攻擊，p、q的選取應(yīng)保證使t很大。設(shè)m在模n下階為k，由得，所以k|(et-1)，即et≡1(modk)，t取為滿足前式的最小值（為e在模k下的階）。又當(dāng)e與k互素時(shí)t|(k)。為使t大，k就應(yīng)大且(k)應(yīng)有大的素因子。又由k|(n)，所以為使k大，p-1和q-1都應(yīng)有大的素因子此外，研究表明，如果e<n且d<n1/4，則d能被容易地確定D.Boneh證明了RSA算法中私有密鑰長度小于ｎ的0.292冪時(shí)方案容易被攻破444.3.5對(duì)RSA的攻擊RSA存在以下兩種攻擊，并不是因?yàn)樗惴ū旧泶嬖谌毕?，而是由于參?shù)選擇不當(dāng)造成的1.共模攻擊在實(shí)現(xiàn)RSA時(shí)，為方便起見，可能給每一用戶相同的模數(shù)n，雖然加解密密鑰不同，然而這樣做是不行的設(shè)兩個(gè)用戶的公開鑰分別為e1和e2，且e1和e2互素（一般情況都成立），明文消息是m，密文分別是

c1≡me1(modn)

c2≡me2(modn)敵手截獲c1和c2后，可如下恢復(fù)m。用推廣的Euclid算法求出滿足re1+se2=1的兩個(gè)整數(shù)r和s，其中一個(gè)為負(fù)，設(shè)為r。再次用推廣的Euclid算法求出c1-1，由此得(c1-1)-rc2s≡m(modn)。452.低指數(shù)攻擊假定將RSA算法同時(shí)用于多個(gè)用戶（為討論方便，以下假定3個(gè)），然而每個(gè)用戶的加密指數(shù)（即公開鑰）都很小。設(shè)3個(gè)用戶的模數(shù)分別為ni(i=1,2,3)，當(dāng)i≠j時(shí)，gcd(ni,nj)=1，否則通過gcd(ni,nj)有可能得出ni和nj的分解。設(shè)明文消息是m，加密指數(shù)e＝3，密文分別是:c1≡m3(modn1)c2≡m3(modn2)c3≡m3(modn3)由中國剩余定理可求出m3(modn1n2n3)。由于m3<n1n2n3，可直接由m3開立方根得到m。最初建議使用e=3，不安全，e是有下限的明文消息空間太小時(shí)，消息需要填充464.4背包密碼體制設(shè)A=(a1,a2,…,an)是由n個(gè)不同的正整數(shù)構(gòu)成的n元組，s是另一已知的正整數(shù)。背包問題就是從A中求出所有的ai，使其和等于s。其中A稱為背包向量，s是背包的容積。例如,A=(43,129,215,473,903,302,561,1165,697,1523)，s=3231。由于

3231=129+473+903+561+1165所以從A中找出的滿足要求的數(shù)有129、473、903、561、1165原則上講，通過檢查A的所有子集，總可找出問題的解（若有解的話）本例A的子集共有210=1024個(gè)（包括空集）。然而如果A中元素個(gè)數(shù)n很大，子集個(gè)數(shù)2n將非常大。如A中有300個(gè)元素，A的子集有2300。尋找滿足要求的A的子集沒有比窮搜索更好的算法，因此背包問題是NPC問題。47由背包問題構(gòu)造公鑰密碼體制同樣是要構(gòu)造一個(gè)(陷門)單向函數(shù)f將x(1≤x≤2n-1)寫成長為n的二元表示0…001,0…010，0…011,…,1…111,f(x)定義為A中所有ai的和，其中x的二元表示的第i位為1，即

f(1)=f(0…001)=an

f(2)=f(0…010)=an-1

f(3)=f(0…011)=an-1+an …

f(2n-1)=f(1…111)=a1+a2+…+an使用向量乘(內(nèi)積)，有f(x)=A·Bx，其中Bx是x二元表示的列向量。上例中f(364)=f(0101101100)=129+473+903+561+1165=3231類似地可求出:f(609)=2942,f(686)=3584,f(32)=903,f(46)=3326,f(128)=215,f(261)=2817,f(44)=2629,f(648)=819。由f的定義可見，已知x很容易求f(x)，但已知f(x)求x就是要解背包問題。當(dāng)然在實(shí)際應(yīng)用中，n不能太小，比如說，至少為200。48用f對(duì)明文消息m加密時(shí)，首先將m寫成二元表示，再將其分成長為n的分組（最后一個(gè)分組不夠長的話，可在后面填充一些0），然后求每一分組的函數(shù)值，以函數(shù)值作為密文分組。例如，明文消息是英文文本，則可將每個(gè)字母用其在字母表中的序號(hào)表示，再將該序號(hào)轉(zhuǎn)換為二進(jìn)制形式（5位即可），如表4.5所示，其中符號(hào)‘’表示空格。表4－7英文字母表及字母的二進(jìn)制表示字母序號(hào)二進(jìn)制字母序號(hào)二進(jìn)制字母序號(hào)二進(jìn)制‘’000000I901001R1810010A100001J1001010S1910011B200010K1101011T2010100C300011L1201100U2110101D400100M1301101V2210110E500101N1401110W2310111F600110O1501111X2411000G700111P1610000Y2511001H801000Q1710001Z261101049背包向量仍取上例中的A，設(shè)待加密的明文是SAUNAANDHEALTH。因?yàn)锳長為10，所以應(yīng)將明文分成長為10比特（即兩個(gè)明文字母）的分組SA，UN，A‘’，AN，D‘’，HE，AL，TH相應(yīng)的二元序列為1001100001，1010101110，0000100000，0000101110，0010000000，0100000101，0000101100，1010001000。分別對(duì)以上二元序列作用于函數(shù)f，得密文為（2942，3584，903，3326，215，2817，2629，819）。為使接收方能夠解密，就需找出單向函數(shù)f(x)的陷門。為此需引入一種特殊類型的背包向量。50定義背包向量A=(a1,a2,…,an)稱為超遞增的，如果，j＝1,2,…,n超遞增背包向量對(duì)應(yīng)的背包問題很容易通過以下算法求解。已知s為背包容積，對(duì)A從右向左檢查每一元素，以確定是否在解中。若s≥an，則an在解中，令xn=1；若s<an，則an不在解中，令xn=0。下面令s＝對(duì)an-1重復(fù)上述過程，一直下去，直到檢查出a1是否在解中。檢查結(jié)束后得x=(x1x2…xn)，Bx=(x1x2…xn)T51敵手如果也知道超遞增背包向量，同樣也很容易解密為此可用模乘對(duì)A進(jìn)行偽裝，模乘的模數(shù)k和乘數(shù)t皆取為常量，滿足，gcd(t,k)=1，即t在模k下有乘法逆元。設(shè)bi≡t·aimodk,i=1,2,…,n得一新的背包向量B=(b1,b2,…,bn)，記為B≡t·Amodk，用戶以B作為自己的公開鑰，A,t,k為私鑰【例4-10】A=(1,3,5,11,21,44,87,175,349,701)是一超遞增背包向量，取k=1590，t=43，gcd(43,1590)=1，得B=(43,129,215,473,903,302,561,1165,697,1523)。得到B后，對(duì)明文分組x=(x1x2…xn)的加密運(yùn)算為c=f(x)=B·Bx≡t·A·Bxmodk對(duì)單向函數(shù)f(x)，t、t-1和k可作為其秘密的陷門信息，即解密密鑰。52解密時(shí)首先由s≡t-1cmodk，求出s作為超遞增背包向量A的容積，再解背包問題即得x=(x1x2…xn)。這是因?yàn)閠-1cmodk≡t-1tABxmodk≡ABxmodk，而由，知ABx<k，所以t-1cmodk=ABx是惟一的?！纠?－28】：接上例，A=(1,3,5,11,21,44,87,175,349,701)是一超遞增背包向量，k=1590，t=43，得t-1≡37mod1590設(shè)用戶收到的密文是(2942,3584,903,3326,215,2817,2629,819)，由37×2942≡734mod1590,37×3584≡638mod1590,37×903≡21mod1590,37×3326≡632mod1590,37×215≡5mod1590,37×2817≡879mod1590,37×2629≡283mod1590,37×819≡93mod1590,得(734,638,21,632,5,879,283,93)取s=734，由734>701，得x10=1；令s=734-701=33，由33<349，得x9=0；重復(fù)該過程得第一個(gè)明文分組是1001100001，它對(duì)應(yīng)的英文文本是SA；類似地得其他明文分組，解密結(jié)果為SAUNAANDHEALTH。53背包密碼體制是Diffie和Hellman1976年提出公鑰密碼體制的設(shè)想后的第一個(gè)公鑰密碼體制，由Merkle和Hellman1978年提出。它表示了如何將NP完全問題用于公開密鑰算法。然而又過了兩年該體制即被破譯破譯的基本思想是不必找出正確的模數(shù)k和乘數(shù)t（即陷門信息），只須找出任意模數(shù)k′和乘數(shù)t′，使得用k′和t′去乘公開的背包向量B時(shí)，能夠產(chǎn)生超遞增的背包向量即可。544.5Rabin密碼體制對(duì)RSA密碼體制，n被分解成功，該體制便被破譯，即破譯RSA的難度不超過大整數(shù)的分解。但還不能證明破譯RSA和分解大整數(shù)是等價(jià)的，雖然這一結(jié)論已得到普遍共識(shí)Rabin密碼體制已被證明對(duì)該體制的破譯與分解大整數(shù)一樣困難Rabin密碼體制是對(duì)RSA的一種修正，它有以下兩個(gè)特點(diǎn)：它不是以一一對(duì)應(yīng)的單向陷門函數(shù)為基礎(chǔ)，對(duì)同一密文，可能有兩個(gè)以上對(duì)應(yīng)的明文;破譯該體制等價(jià)于對(duì)大整數(shù)的分解。RSA中選取的公開鑰e滿足1<e<(n)，且gcd(e,

(n))=1。Rabin密碼體制則取e=2551.密鑰的產(chǎn)生隨機(jī)選擇兩個(gè)大素?cái)?shù)p、q，滿足p≡q≡3mod4，Blum數(shù)，即這兩個(gè)素?cái)?shù)形式為4k+3；計(jì)算n=p×q。以n作為公開鑰，p、q作為秘密鑰。2.加密

c≡m2modn

其中m是明文分組，c是對(duì)應(yīng)的密文分組。3.解密解密就是求c模n的平方根，即解x2≡cmodn，由中國剩余定理知解該方程等價(jià)于解方程組56由于p≡q≡3mod4，下面將看到，方程組的解可容易地求出，其中每個(gè)方程都有兩個(gè)解，即

x≡m1modp，x≡－m1modp

x≡m2modq，x≡－m2modq經(jīng)過組合可得4個(gè)同余方程組，，，由中國剩余定理可解出每一方程組的解，共有4個(gè)，即每一密文對(duì)應(yīng)的明文不惟一。為了有效地確定明文,可在m中加入某些信息,如發(fā)送者的身份號(hào)、接收者的身份號(hào)、日期、時(shí)間等。57下面證明，當(dāng)p≡q≡3mod4，兩個(gè)方程x2≡cmodp,x2≡cmodq的平方根都可容易地求出由p≡3mod4得，p+1=4k，即(p+1)/4是一整數(shù)因c是模p的平方剩余，故≡c(p-1)/2≡1modp，≡≡c(p-1)/2·c≡cmodp所以和p-是方程x2≡cmodp的兩個(gè)根。同理和q-是方程x2≡cmodq的兩個(gè)根。由以前知識(shí)知，求解方程x2≡amodn與分解n是等價(jià)的，所以破譯Rabin密碼體制的困難程度等價(jià)于大整數(shù)n的分解。584.6NTRU公鑰密碼系統(tǒng)NTRU是一種基于環(huán)的公鑰密碼系統(tǒng)，由JeffreyHoffstein

等人在1998年提出系統(tǒng)的特點(diǎn)是密鑰短且容易產(chǎn)生，算法的運(yùn)算速度快，所需的存儲(chǔ)空間小。系統(tǒng)建立在整系數(shù)多項(xiàng)式環(huán)上。設(shè)R表示最高次數(shù)不超過N－1的所有整系數(shù)多項(xiàng)式集合，設(shè)a＝a0+a1x+…+aN－1xN－1,b＝a0+b1x+…+bN－1xN－1,是R上的兩個(gè)元素，R上的加法定義為

a+b＝(a0+b0)+(a1+b1)x+…+(aN-1+bN-1)xN－1,乘法定義為a*b＝c0+c1x+…+cN-1xN－1其中k階系數(shù)ck＝a0bk+a1bk-1+…+akb0+ak+1bN-1+ak+2bN-2+…+aN-1bk+1

＝容易驗(yàn)證R在如上定義的加法和乘法運(yùn)算下構(gòu)成一個(gè)環(huán)（＋Abel群，×半群，可分配）591.算法的參數(shù)參數(shù)包括3個(gè)整數(shù)(N,p,q)和4個(gè)次數(shù)為N-1的整系數(shù)多項(xiàng)式集合Lf,Lg,L,Lm，其中p和q不要求是素?cái)?shù)，但滿足gcd(p,q)=1，且q>p2.密鑰的產(chǎn)生密鑰的產(chǎn)生由接收方完成：隨即選取兩個(gè)多項(xiàng)式f,gLg，其中多項(xiàng)式f在模q和模p下均可逆，其逆元分別表示為Fq和Fp，即：Fq*f=1modq

和Fp*f=1modp。計(jì)算h＝Fq*gmodq，以h為公鑰，f作為秘密鑰，接收方同時(shí)還需保存Fp3.加密設(shè)發(fā)送方欲將消息mLm發(fā)送給接收方，可對(duì)m作如下加密：隨機(jī)選取多項(xiàng)式L

，用公鑰h對(duì)消息進(jìn)行加密e＝p*h+m(modq)將e發(fā)送給接收方。604.解密接收方收到e后，使用秘密鑰f對(duì)其作如下解密。①首先計(jì)算a=f*e(mod

q),a的系數(shù)選在-q/2到q/2之間.②將a作為一個(gè)整系數(shù)多項(xiàng)式，計(jì)算Fp*a(mod

p)即可恢復(fù)明文m解密原理：a=f*e＝f*p*h+f*m(modq)

＝f*p*Fq*g

+f*m(modq)

＝p*g

+f*m(modq)

＝p*g

+f*m

最后一步是由于若選擇的參數(shù)合適，可保證多項(xiàng)式p*g

+f*m的系數(shù)在-q/2到q/2之間，所以對(duì)p*g

+f*m模q運(yùn)算后結(jié)果不變而Fp*a＝Fp*p*g

+Fp*f*m(modp)＝m(modp)614.7橢圓曲線密碼體制為保證RSA算法的安全性，它的密鑰長度需一再增大，使得它的運(yùn)算負(fù)擔(dān)越來越大。相比之下，橢圓曲線密碼體制ECC（ellipticcurvecryptography）可用短得多的密鑰獲得同樣的安全性，因此具有廣泛的應(yīng)用前景ECC已被IEEE公鑰密碼標(biāo)準(zhǔn)P1363采用624.7.1橢圓曲線橢圓曲線并非橢圓，之所以稱為橢圓曲線是因?yàn)樗那€方程與計(jì)算橢圓周長的方程類似。一般來講，橢圓曲線的曲線方程是以下形式的三次方程：

y2+axy+by=x3+cx2+dx+e(4-1)其中a，b，c，d，e是滿足某些簡單條件的實(shí)數(shù)。定義中包括一個(gè)稱為無窮點(diǎn)的元素，記為O。下圖是橢圓曲線的兩個(gè)例子。從圖可見，橢圓曲線關(guān)于x軸對(duì)稱。63橢圓曲線上的加法運(yùn)算定義如下：

如果其上的3個(gè)點(diǎn)位于同一直線上，那么它們的和為O。進(jìn)一步可如下定義橢圓曲線上的加法律（加法法則）：①O為加法單位元，即對(duì)橢圓曲線上任一點(diǎn)P，有

P+O=P(這是因?yàn)镻與-P在曲線的第三個(gè)交點(diǎn)是O)②設(shè)P1=(x,y)是橢圓曲線上的一點(diǎn)（如圖所示），它的加法逆元定義為P2=－P1=(x,-y)這是因?yàn)镻1、P2的連線延長到無窮遠(yuǎn)時(shí)，得到橢圓曲線上的另一點(diǎn)O，即橢圓曲線上的3點(diǎn)P1、P2，O共線，所以P1+P2+O=O，P1+P2=O，即P2=-P1。由O+O=O，還可得O=-O64③設(shè)Q和R是橢圓曲線上x坐標(biāo)不同的兩點(diǎn)，Q+R的定義如下：畫一條通過Q、R的直線與橢圓曲線交于P1這一交點(diǎn)是惟一的，除非所做的直線是Q點(diǎn)或R點(diǎn)的切線，此時(shí)分別取P1=Q或P1=R

由Q+R+P1=O得Q+R=-P1④點(diǎn)Q的倍數(shù)定義如下：在Q點(diǎn)做橢圓曲線的一條切線，設(shè)切線與橢圓曲線交于點(diǎn)S，定義2Q=Q+Q=-S。類似地可定義3Q=Q+Q+Q+，…，以上定義的加法具有加法運(yùn)算的一般性質(zhì)，如交換律、結(jié)合律等。654.7.2有限域上的橢圓曲線密碼中普遍采用的是有限域上的橢圓曲線，有限域上的橢圓曲線是指曲線方程定義式(4-1)中，所有系數(shù)都是某一有限域GF(p)中的元素（其中p為一大素?cái)?shù)）其中最為常用的是由方程(4-2)定義的曲線y2≡x3+ax+b(modp)(4-2)(a,bGF(p),4a3+27b2(modp)≠0)66因?yàn)椋?a/3)3+(b/2)2=(4a3+27b2)/108是方程x3+ax+b＝0的判別式，當(dāng)4a3+27b2

＝0時(shí)方程有重根，設(shè)為x0，則點(diǎn)Q0＝(x0,0)是方程(4-2)的重根即x3+ax+b＝(x-x0)3或者＝(x-x0)2(x-x1)，重根將使得一階導(dǎo)數(shù)3x2＋a在該Q0點(diǎn)為0令F(x,y)=y2－x3－ax－b，則F/x|Q0=F/y|Q0=0所以dy/dx=－(F/x)/(F/y)＝(3x2＋a)/2y在Q0點(diǎn)無定義，即曲線y2≡x3+ax+b在Q0點(diǎn)的切線無定義，因此點(diǎn)Q0的倍點(diǎn)運(yùn)算無定義67例：p=23，a=b=1，4a3+27b2(mod23)≡8≠0，方程為y2≡x3+x+1(mod23)，感興趣的是曲線在GF(23)中的整數(shù)點(diǎn)有限域上的橢圓曲線群定義如下：設(shè)Ep(a,b)表示方程(4-2)所定義的橢圓曲線上的點(diǎn)集{(x,y)|0x<p,0y<p，且x,y均為整數(shù)}并上無窮遠(yuǎn)點(diǎn)O本例中E23(1,1)由表4-8給出，表中未給出O表4－6橢圓曲線上的點(diǎn)集E23(1,1)(0，1)(0，22)(1，7)(1，16)(3，10)(3，13)(4，0)(5，4)(5，19)(6，4)(6，19)(7，11)(7，12)(9，7)(9，16)(11，3)(11，20)(12，4)(12，19)(13，7)(13，16)(17，3)(17，20)(18，3)(18，20)(19，5)(19，18)68一般來說，Ep(a,b)由以下方式產(chǎn)生：

①對(duì)每一x(0x<p且x為整數(shù)），計(jì)算x3+ax+b(modp)。②決定①中求得的值在模p下是否有平方根，如果沒有，則曲線上沒有與這一x相對(duì)應(yīng)的點(diǎn)；如果有，則求出兩個(gè)平方根(y=0時(shí)只有一個(gè)平方根)。即判斷是否是模p的平方剩余Ep(a,b)上的加法定義如下：設(shè)P，QEp(a,b)，則①P+O=P②如果P=(x,y)，那么(x,y)+(x,-y)=O，即(x,-y)是P的加法逆元，表示為-P。由Ep(a,b)的產(chǎn)生方式知，-P也是Ep(a,b)中的點(diǎn)，如上例，P=(13,7)E23(1,1)，-P=(13,-7)，而-7mod23≡16，所以-P=(13,16)，也在E23(1,1)中。69③設(shè)P=(x1,y1)，Q=(x2,y2)，P≠-Q，則P+Q=(x3,y3)由以下規(guī)則確定：

x3≡λ2－x1－x2(modp)y3≡λ(x1－x3)－y1(modp)其中λ＝切線【例4－29】仍以E23(1,1)為例，設(shè)P=(3,10)，Q=(9,7)，則λ＝(7-10)/(9-3)=-1/2=－1×2－1≡11mod23x3≡112－3－9＝109≡17mod23y3≡11(3－17)－10＝－164≡20mod23所以P+Q=(17,20)，仍為E23(1,1)中的點(diǎn)。若求2P則λ＝(3×32＋1)/(2×10)=5/20=1×4－1≡－1×220≡6mod23

x3≡62－3－3＝30≡7mod23y3≡6(3－7)－10＝－34≡12mod23

所以2P=(7,12)70公式推導(dǎo)示例71倍點(diǎn)運(yùn)算仍定義為重復(fù)加法，如4P=P+P+P+P快速倍點(diǎn)運(yùn)算kP可采用類似于快速指數(shù)運(yùn)算的相同算法即令k=bt2t+bt-12t-1+…+b12+b0，則可寫出2倍點(diǎn)和加法運(yùn)算的迭代形式Ep(a,b)是一個(gè)Abel群對(duì)一般的Ep(a,b)，可證其上的加法運(yùn)算是封閉的、滿足交換律，同樣還能證明其上的加法逆元運(yùn)算也是封閉的，有單位元O，所以Ep(a,b)是一個(gè)Abel群724.7.3橢圓曲線上的點(diǎn)數(shù)一條橢圓曲線Ep(a,b)（含無窮遠(yuǎn)點(diǎn)O)的總點(diǎn)數(shù)關(guān)系到運(yùn)算群的規(guī)模，即建立的密碼系統(tǒng)的安全性，有以下定理：定理4-13GF(p)上的橢圓曲線y2＝x3+ax+b(a,bGF(p),4a3+27b2(modp)≠0)在第一象限中的整數(shù)點(diǎn)加無窮遠(yuǎn)點(diǎn)O共有1+p+=1+p+個(gè)，其中是Legendre符號(hào)定理中的由以下定理給出定理4-14(Hasse定理)||734.7.4明文消息到橢圓曲線上的嵌入使用橢圓曲線構(gòu)造密碼體制前，需要將明文消息鑲嵌到橢圓曲線上去，作為橢圓曲線上的點(diǎn)。設(shè)明文消息是m(0mM)，k是一個(gè)足夠大的整數(shù)，使得將明文消息鑲嵌到橢圓曲線上時(shí)，錯(cuò)誤的概率是2-k實(shí)際情況中，k可在3050之間取值。不妨設(shè)k＝30，對(duì)明文消息m，如下計(jì)算一系列x：x＝{mk+j,j=0,1,2,…}={30m,30m+1,30m+2,…}直到x3+ax+b(modp)是平方剩余，即得到橢圓曲線上的點(diǎn)(x,)。因?yàn)樵?到p的整數(shù)中，有一半是模p的平方剩余，一半是模p的非平方剩余。所以k次找到x，使得x3+ax+b(modp)是平方根的概率不小于1－2-k。反之，為從橢圓曲線上的點(diǎn)(x,y)得到明文消息m，只須求m＝x/30744.7.5橢圓曲線上的密碼為使用橢圓曲線構(gòu)造密碼體制，需要找出橢圓曲線上的數(shù)學(xué)困難問題在橢圓曲線構(gòu)成的Abel群Ep(a,b)上考慮方程Q=kP，其中P，QEp(a,b)，k<p，則由k和P易求Q，但由P、Q求k則是困難的，這就是橢圓曲線上的離散對(duì)數(shù)問題，可應(yīng)用于公鑰密碼體制。Diffie-Hellman密鑰交換和ElGamal密碼體制是基于有限域上離散對(duì)數(shù)問題的公鑰體制，下面考慮如何用橢圓曲線來實(shí)現(xiàn)這兩種密碼體制。751.Diffie-Hellman密鑰交換(GF(p)上的方案見5.2.3節(jié))第1步：取一素?cái)?shù)p≈2180和兩個(gè)參數(shù)a、b，則得橢圓曲線上面的點(diǎn)及無窮遠(yuǎn)點(diǎn)構(gòu)成Abel群Ep(a,b)，a，b應(yīng)使群的階n具有大素因子第2步:取Ep(a,b)的一個(gè)生成元G＝(x1,y1)，要求G的階是一個(gè)非常大的素?cái)?shù)，G的階是滿足nG=O的最小正整數(shù)n。Ep(a,b)和G作為公開參數(shù)第3步:兩用戶A和B之間的密鑰交換如下進(jìn)行：①A選一小于n的整數(shù)nA，作為秘密鑰，并由PA=nAG產(chǎn)生Ep(a,b)上的一點(diǎn)作為公開鑰②B類似地選取自己的秘密鑰nB和公開鑰PB③A、B分別由K=nAPB和K=nBPA產(chǎn)生出雙方共享的秘密鑰這是因?yàn)镵=nAPB=nA(nBG)=nB(nAG)=nBPA攻擊者若想獲取K，則必須由PA和G求出nA，或由PB和G求出nB，即需要求橢圓曲線上的離散對(duì)數(shù)，因此是不可行的76【例4－14】:p=211，Ep(0,－4)，即橢圓曲線為y2≡x3－4G=(2,2)是E211(0,-4)的階為241的一個(gè)生成元，即241G=O。A的秘密鑰為nA=121，公開鑰為PA=121(2,2)=(115,48)。B的秘密鑰取為nB=203，公開鑰為PB=203(2,2)=(130,203)。由此得共享密鑰為121(130,203)=203(115,48)=(161,169)，即共享密鑰是一對(duì)數(shù)。如果將這一密鑰用作單鑰加密的會(huì)話密鑰，則可簡單地取其中的一個(gè)，如取x坐標(biāo)，或取x坐標(biāo)的某一簡單函數(shù)?；蛴?jì)算hash值2.ElGamal密碼體制有限域GF(p)上的方案原理：基于離散對(duì)數(shù)困難性密鑰產(chǎn)生過程：首先選擇一素?cái)?shù)p以及兩個(gè)小于p的隨機(jī)數(shù)g和x，計(jì)算y≡gxmodp。以(y,g,p)作為公開密鑰，x作為秘密密鑰。加密過程：設(shè)欲加密明文消息M，隨機(jī)選一與p-1互素的整數(shù)k

計(jì)算對(duì)C1≡gkmodp,C2≡ykMmodp，密文為C={C1,C2}解密過程：M=C2/C1xmodp

這是因?yàn)镃2/C1xmodp＝y(tǒng)kM/gkxmodp＝y(tǒng)kM/ykmodp＝Mmodp

77(2)利用橢圓曲線實(shí)現(xiàn)ElGamal密碼體制首先選取一條橢圓曲線，并得Ep(a,b)，將明文消息m通過編碼嵌入到曲線上得點(diǎn)Pm，再對(duì)點(diǎn)Pm做加密變換。如4.7.4取Ep(a,b)的一個(gè)生成元G，Ep(a,b)和G作為公開參數(shù)。用戶A選nA作為秘密鑰，并以PA=nAG作為公開鑰任一用戶B若想向A發(fā)送消息Pm，可選取一隨機(jī)正整數(shù)k，產(chǎn)生以下點(diǎn)對(duì)作為密文：Cm={kG，Pm+kPA}《存在密文擴(kuò)展問題》A解密時(shí)，以密文點(diǎn)對(duì)中的第二個(gè)點(diǎn)減去用自己的秘密鑰與第一個(gè)點(diǎn)倍乘，即

(Pm+kPA)－nAk