《現(xiàn)代密碼學(xué)原理與實(shí)踐》課件第4章

第4章公鑰密碼4.1引言

4.2背包公鑰密碼系統(tǒng)

4.3RSA公鑰密碼(基于大數(shù)分解)

4.4Rabin公鑰體系(基于二次剩余)

4.5ElGamal公鑰系統(tǒng)(基于離散對數(shù))4.6McEliece公鑰密碼(基于糾錯碼)

4.7橢圓曲線公鑰體制

習(xí)題4

實(shí)踐練習(xí)4

計算機(jī)互聯(lián)網(wǎng)的出現(xiàn)，極大地方便了人們對信息的交換和共享，電子商務(wù)和電子公務(wù)等越來越多的業(yè)務(wù)開始在網(wǎng)上進(jìn)行，這就對信息交互提出了一系列新的需求。另一方面，網(wǎng)絡(luò)也給攻擊者提供了更多的機(jī)會，病毒、黑客以及網(wǎng)絡(luò)犯罪時有發(fā)生。如何更好地解決信息安全問題，已成為刻不容緩的任務(wù)。20世紀(jì)70年代出現(xiàn)的公開密鑰體系，標(biāo)志著現(xiàn)代密碼學(xué)的誕生。新的理論與實(shí)踐迅速發(fā)展起來了，隨著一系列新觀念和方法的出現(xiàn)，現(xiàn)代信息網(wǎng)絡(luò)中的安全問題逐步得到解決，密碼學(xué)進(jìn)入了嶄新的發(fā)展階段。4.1引言［3］

4.1.1對稱密鑰的困惑

1.密鑰交換問題

為了使對稱密鑰(單鑰制)體系實(shí)現(xiàn)信息的保密傳輸，通信雙方必須事先約定相同的算法和步驟，稱之為保密協(xié)議，并且設(shè)法在不讓其他任何人知曉的條件下，雙方獲取統(tǒng)一的密鑰，這一過程叫做密鑰交換。密鑰交換往往是比較困難的任務(wù)，密鑰是用秘密信道傳遞的，而秘密信道卻昂貴且難得。因此，解決密鑰交換問題便成了對稱密鑰體制的最大障礙。

2.通信網(wǎng)絡(luò)中的密鑰管理問題

網(wǎng)絡(luò)中N個用戶兩兩保密通信，需要分配和保管M=N(N+1)把密鑰，當(dāng)N很大時，比如N=1000時，則M≈5×105，網(wǎng)管中心一定非常繁忙，甚至?xí)蔀橥ㄐ诺钠款i。因此，密鑰管理問題成了信息系統(tǒng)的又一難題。4.1.2公開密鑰的產(chǎn)生和雛形

1．Merkle難題

1974年，Merkle為解決對稱單鑰制保密系統(tǒng)的密鑰交換問題提出了一個設(shè)想［9］。其密鑰交換協(xié)議為：

(1)甲向乙發(fā)送100萬條消息，每條內(nèi)容均為：“這條信息是xi，它的密鑰是yi”；xi是從0到999999之間任意選取但又各不相同的隨機(jī)數(shù)，yi是xi的密鑰，它也是從0到999999之間的任意被甲預(yù)先指定的一個各不相同的隨機(jī)數(shù)。甲秘密保存所有yi與xi的密鑰對照表后，就把這100萬條消息分別用所宣布的這個yi加密，全部發(fā)給乙。(2)由于加密算法是公開的，乙收到100萬條消息后，從中任選一條，然后遍歷0~999999之間的100萬個密鑰進(jìn)行嘗試，總有一個yj可將其解密，從而得知xj的值。

(3)乙以明文形式將xj發(fā)給甲。

(4)甲收到xj，即知乙所選的是哪個yj，從而甲、乙二人都有了同樣的密鑰yj。

(5)非法竊聽者丙即使收到了全部往來的明文和密文，雖然知道了xj，但他不知道xj在哪條消息中，他需要對100萬條消息一一進(jìn)行解密，而每解譯一條消息需要嘗試100萬個密鑰。假若乙耗時半分鐘能完成對100萬個密鑰的嘗試，得到自己的密鑰，丙則需要100萬倍的時間，大約1年才能從100萬條消息中確定乙所選的是哪一條。

此設(shè)計方案顯然是不太現(xiàn)實(shí)的，但其思想是很先進(jìn)的。它用公開的算法通過不安全信道完成了密鑰交換，其保密理念基于計算復(fù)雜性，安全性則是建立在機(jī)密與破譯的時差之上的。該課題的出發(fā)點(diǎn)雖然是為了解決單鑰交換問題，但客觀上已走進(jìn)了公開密鑰的大門。

2.雙鑰制的提出

1976年11月，美國斯坦福大學(xué)電氣工程系研究生W.Diffie和副教授M.E.Hellman在IEEE上發(fā)表了題為“密碼學(xué)新方向”的學(xué)術(shù)論文［10］，首次提出雙密鑰思想，用公開的算法解決了單鑰制的密鑰交換問題。設(shè)p為一個大素數(shù)，已知x和b，不難求出:

y=bxmodp(4-1)然而若已知y和b，求逆運(yùn)算:

x=logbymodp(4-2)卻十分困難。利用離散對數(shù)復(fù)雜性，他們二人設(shè)計的密鑰交換協(xié)議如下：

(1)用戶i選xi為私鑰，求出為公鑰，公布之(連同b和p發(fā)給用戶j)。

(2)用戶j選xj為私鑰，求出為公鑰，公布之(發(fā)給用戶i)。

(3)約定

(4-3)為會話密鑰(對稱單鑰)，用戶i可由

獲得；用戶j可由

獲得。

(4)盡管公布了yi、yj和p，但基于離散對數(shù)的困難性，任何第三者都難以求出xi和xj，因此無法獲得kij。

Diffie和Hellman不僅用公開的算法，而且首次提出了公鑰和私鑰的概念，開創(chuàng)了現(xiàn)代密碼學(xué)的先河。4.1.3公開密鑰制的一般原理

1.公開密鑰體系的使用方式及功能

W.Diffie和M.E.Hellman的論文發(fā)表后，立即引起了學(xué)術(shù)界的重視，并且很快把雙密鑰的思想用到密碼系統(tǒng)中，這不僅解決了單鑰制的密鑰交換問題，更重要的是以一種全新的方式很好地解決了保密、認(rèn)證與網(wǎng)絡(luò)管理等問題。假設(shè)在算法公開的雙密鑰密碼體制下每個用戶都分得了自己的公鑰(可以公開的密鑰)與私鑰(必須秘密保存的密鑰)，于是就能完成以下功能：

(1)保密功能(包括會話密鑰的交換)：發(fā)信人用收信人的公鑰加密，形成密文，收信人用自己的私鑰解密。其他人因?yàn)椴徽莆湛膳鋵Φ乃借€，所以無法解讀這個密文。(2)認(rèn)證功能：發(fā)信人用自己的私鑰加密形成密文，收信人用發(fā)信人的公鑰解密。其實(shí)任何人都能查到發(fā)信人的公鑰來解譯密文，能正確解譯即證明該密文是發(fā)信人所加密的。

(3)雙重功能：發(fā)信人先用自己的私鑰加密明文，再用收信人的公鑰對密文再次加密；收信人收到密件后先用自己的私鑰解密一次，再用發(fā)信人的公鑰解密一次。這樣的密文只有合法收信人才有能力閱讀并驗(yàn)證。

(4)網(wǎng)管功能：N個用戶的系統(tǒng)，管理員只需保管(不必隱藏)N把公鑰，私鑰由用戶個人保管。密鑰分配與管理的問題立刻變得簡單了。2.公開密鑰體系的加、解密過程

公開密鑰體系把算法公開，并且把一對密鑰中的一把公開，才換來了功能上的增加與使用上的方便。而之所以將之公開，是因?yàn)榻饷芩盟惴ú⒎羌用艿哪孢\(yùn)算，解密所用密鑰也不同于加密所用的密鑰，而且二者不可互相推導(dǎo)。加密：明文M→變換(k1為加密密鑰)→密文C，即

(4-4)

解密：密文C→變換(k2為解密密鑰)→明文M，即

(4-5)3.單向陷門函數(shù)(加密、解密的數(shù)學(xué)原理)

作為一個保密系統(tǒng)，無論單鑰制還是雙鑰制，解密和加密的效果一定應(yīng)當(dāng)是互逆的，通過解密應(yīng)得到與原來的明文相同的譯文。一般說來，解密應(yīng)當(dāng)用加密的逆運(yùn)算實(shí)現(xiàn)，單鑰制就是這么做的。然而，拋開逆運(yùn)算的定式看問題，邏輯上并不排除存在其他算法也能解出正確譯文的途徑。如果有，為什么不可以用呢。至于密鑰，它只是加、解密運(yùn)算過程中的一些關(guān)鍵數(shù)據(jù)，更沒有理由認(rèn)為參與加密運(yùn)算的密鑰和參與解密運(yùn)算的密鑰必須相同。(當(dāng)然，加密密鑰與解密密鑰既然是配對的，那么總應(yīng)當(dāng)存在某種內(nèi)在的聯(lián)系，實(shí)際上也確實(shí)如此。不過只要這種內(nèi)在聯(lián)系涉及到復(fù)雜度很高的運(yùn)算，就可以認(rèn)為它們是無法相互推導(dǎo)的)。于是，問題又回到了數(shù)學(xué)上，能否找到這樣的算法和密鑰呢？

數(shù)學(xué)上存在一種單向陷門函數(shù)，它有下列性質(zhì)：

(1)對于每個x∈X，計算y=f(x)是容易的。正是因?yàn)檫@一點(diǎn)，加密運(yùn)算才是簡單可行的。

(2)明知y=f(x)在y∈Y中有解，但由給定的y難以求出x，其逆運(yùn)算x=f-1(y)十分復(fù)雜。正是因?yàn)檫@一點(diǎn)，它被叫做單向函數(shù)。即使公開了算法，也難以在有限機(jī)時內(nèi)計算出逆運(yùn)算結(jié)果，系統(tǒng)安全性才有了保障。

(3)對于某些特殊的單向函數(shù)(不是所有的單向函數(shù))，若附加一點(diǎn)相應(yīng)的“陷門信息k”，則存在另一個能算出x的方法：x=fk(y)。fk(y)不同于f-1(y)，它可以容易地算出x；求解這個問題的關(guān)鍵數(shù)據(jù)k就是密鑰。正是因?yàn)檫@一點(diǎn)，掌握密鑰的合法用戶才能容易地正確解譯密文。

數(shù)學(xué)中確實(shí)存在不少逆運(yùn)算非常復(fù)雜的單向函數(shù)，如大數(shù)的分解因數(shù)、離散對數(shù)等等，這是構(gòu)造公開密鑰體系的必要條件。但是還必須設(shè)法引入“陷門”，就像魔術(shù)師做一個套，知道竅門的人，就能輕易地從別的路鉆出來，而不必按進(jìn)來的路線在迷宮里摸索。目前已找到多種單向陷門函數(shù)，設(shè)計出多種公開密鑰系統(tǒng)，如RSA系統(tǒng)、背包系統(tǒng)、ElGamal[JP]系統(tǒng)、Rabin系統(tǒng)等，后面將陸續(xù)介紹。4.1.4現(xiàn)代密碼學(xué)的理念

1.從基于算法的神秘性到基于算法的復(fù)雜性

傳統(tǒng)密碼體系的安全性依賴于對算法的保密，一旦算法失密，攻擊者就可以用它的逆運(yùn)算來破譯密碼系統(tǒng)。而現(xiàn)代密鑰學(xué)則利用逆運(yùn)算復(fù)雜度非常高的單向算法來構(gòu)建密碼系統(tǒng)，就不必?fù)?dān)心算法失密，因?yàn)楣粽呒词箲?yīng)用現(xiàn)代最新計算技術(shù)，在有限時間內(nèi)也是無法算出結(jié)果的。所謂復(fù)雜性，是指計算所必須的基本運(yùn)算步驟的數(shù)量，它決定了計算所必須的機(jī)時和占用的計算機(jī)資源。計算復(fù)雜性理論告訴我們，計算量隨著數(shù)據(jù)位數(shù)N的增長而變大，其增大的速度與算法的函數(shù)類型有關(guān)。按照從小到大的次序是：常數(shù)，對數(shù)函數(shù)logN，線性函數(shù)aN，二次函數(shù)N2，三次函數(shù)N3，多項(xiàng)式函數(shù)Nd，亞指數(shù)函數(shù)2lgN，指數(shù)函數(shù)2N或10N。隨著數(shù)據(jù)位數(shù)N的增長，計算量按照多項(xiàng)式以下的依賴關(guān)系變大的算法都可認(rèn)為是有效算法，這樣的增加速度對于現(xiàn)有計算技術(shù)來說是可以接受的，有限時間內(nèi)能夠算出結(jié)果。否則，計算量將隨著N的增長而迅速膨脹，就不可能在有限時間內(nèi)算出結(jié)果。復(fù)雜性理論把依賴關(guān)系為多項(xiàng)式及其低于多項(xiàng)式的算法都稱為可解問題(p類)，而將超過多項(xiàng)式的算法都稱為難解問題(Np類，NpC類)。如果已經(jīng)證明了某種密碼的破譯是Np類問題，那么只要數(shù)據(jù)位足夠大，則任何現(xiàn)代的計算設(shè)備都不可能在允許的時間內(nèi)將其破譯，因此它是安全的。由基于算法的神秘性到基于算法的復(fù)雜性是現(xiàn)代密碼學(xué)設(shè)計理念上的一次重大轉(zhuǎn)變，不靠神奇靠麻煩，算法不怕別人猜出，甚至可以公開。這樣一來，密碼分析者的注意力也就從研究由密文提取信息的可能性(老觀點(diǎn))改變?yōu)橛擅芪奶崛⌒畔⒌目尚行?新觀點(diǎn))。2.算法的可公開性現(xiàn)代密碼學(xué)認(rèn)為藏著捂著的神秘算法，其安全性終究是僥幸的和脆弱的，只有根據(jù)算法的復(fù)雜性建立起來的密碼體制，其安全性才是堅固可信的。這是因?yàn)樗惴ǖ膹?fù)雜性完全能夠通過數(shù)學(xué)理論科學(xué)地預(yù)測，只要該算法復(fù)雜到不可行的程度，即使公開了算法，也難以在有限機(jī)時內(nèi)計算出逆運(yùn)算結(jié)果。算法既然失去了保密的價值，公開算法就成了現(xiàn)代密碼體制的一大特點(diǎn)。算法公開后，可以讓它在攻擊中不斷完善和改進(jìn)，并以此顯示其安全的堅固性。3.安全的相對性

在科學(xué)技術(shù)高度發(fā)展的今天，應(yīng)充分估計破譯者的計算能力和計算技術(shù)未來的發(fā)展，從這個意義講，不存在永遠(yuǎn)牢不可破的密碼，只存在當(dāng)前階段與需求相適應(yīng)的安全密碼體系，破譯只是時間和金錢的問題。但是如果破譯工作所花的代價大于秘密本身的價值，或破譯花費(fèi)的時間大于秘密的有效期，則破譯失去意義，則該保密系統(tǒng)就可以認(rèn)為是安全的。這才是實(shí)事求是的科學(xué)的保密觀和破譯觀。根據(jù)這個觀點(diǎn)，破譯的工作量取決于算法的復(fù)雜度，而復(fù)雜性又取決于數(shù)據(jù)位數(shù)的長短，因此可以根據(jù)客觀需求實(shí)事求是地設(shè)計不同層次、不同時效的密碼體系。不求絕對(安全)求相對(安全)是密碼設(shè)計理念上的又一個轉(zhuǎn)變。4.密鑰的機(jī)密性算法公開了，合法用戶與非法用戶的區(qū)別在哪里呢？合法用戶擁有密鑰，解譯密文十分容易；非法用戶沒有密鑰，破譯密文則很不容易。這是因?yàn)槿绻粽哂帽闅v法一個個去嘗試密鑰，設(shè)每嘗試一個密鑰需要1秒鐘，則遍歷160比特長的所有密鑰需要2160秒鐘，約1040年。只要密鑰具有足夠的長度與隨機(jī)性，偶然猜中密鑰的概率是極小的。不藏算法藏密鑰是設(shè)計理念上一致的觀點(diǎn)。保守密鑰的機(jī)密要比隱藏算法的機(jī)密容易得多，也安全得多。況且密鑰是可以隨時更換的，萬一暴露了密鑰，可以換一把，不致造成整個系統(tǒng)的破壞。4.2背包公鑰密碼系統(tǒng)當(dāng)初Diffie和Hellman提出公鑰思想的時候，還沒有一個實(shí)例。兩年后，1978年,Merkle和Hellman利用古老的背包問題設(shè)計出一個公開的密鑰系統(tǒng)［11］。4.2.1背包問題

1.問題

已知n個物體重量分別為A=(a1,a2,…,an)，任選其中若干件放入背包內(nèi)，使其總重量恰好等于預(yù)先給定的b值。設(shè)所選物體用X=(x1,x2,…,xn)表示，這里xi(i=1,2,…,n)可為0或1，分別表示該物體被取或不被取，則(4-6)2.解答

當(dāng)n較小時，這是一個多解的不定方程問題。例如，A={1，2，5，8，11，17，21},b=47,則答案可以是2+5+8+11+21,也可以是1+8+17+21。當(dāng)n較大時，它是一個Np類的難解問題。例如，n=100，2100=1.27×1030，以每秒107種方案的速度用計算機(jī)搜索，也得4.02×1015年才能完成窮舉。

3.超遞增序列的背包問題

如果限制這些物體的重量，即每個物體的重量都滿足比它的前面所有物體的重量之和大的條件，即(4-7)則這樣的背包問題叫做超遞增背包問題。超遞增背包問題是p類唯一解的可求解問題。例如：A={1，2，5，10，25，51}，b=64，則由64>51可知a6必存在；再由64-51=13<25知a5不必取，而由13>10知a4必選；又由13-10=3<5知a3必沒有；而又由3>2知a2必選；最后由3-2=1=a1知a1也必選。故答案是X={1,0,1,0,1,1}，即64=1+2+10+51。4.2.2MH背包公鑰系統(tǒng)

設(shè)明文為M={m1,m2,…,mn},mi=。若用超遞增序列B={b1,b2,…,bn}將之加密，則是p類可解問題；若用非超序列A={a1,a2,…,an}將之加密，則是Np類難解問題。

如果設(shè)計出一個方法，能把B變換成A，我們用A來加密，使問題成為Np類完全難題，則合法用戶由于掌握A變換成B所具有的信息(私鑰)，就能由A求出B，使問題成為p類可求解問題。而非法用戶只知道A(公鑰)，不掌握私鑰，因此就無法解答此題。

Merkle和Hellman當(dāng)初是利用模逆元進(jìn)行這個變換的。例如，B={1，3，7，13，26，119，267}，選大于全部元素之和501的一個數(shù)，p=523,再選一個與523互素的數(shù)w=28,并求出w-1=467mod523，于是可分別求出每個bi的模逆元：

ai=w-1·bimod523(i=1,2，…，n)結(jié)果是：

A={467×1,467×3,467×7,467×13,…}mod523={467,355,131,318,113,21,135,215}

A和p=523為公鑰，求出A后，將w-1銷毀。要發(fā)送信息就用A來加密。例如，明文M=10101100，則密文為

C=A·M=a1+a3+a5+a6=467+131+113+21=732mod523=209w=28為合法用戶的私鑰。合法接收者不難求出：

bi=waimodp=w·w-1bimodp=bimodp(i=1,2，…，n)即求出

B={1,3,7,13,26,65,119,267}還能求出

C′=wcmodp=28×209mod523=99而這是一個超遞增背包問題，容易解出：

m1=m3=m5=m6=1其他mi=0，所以明文是M=10101100。4.2.3背包公鑰體系的破解與發(fā)展現(xiàn)狀

Merkle和Hellman提出背包體系時，曾懸賞50美元征求人破譯，兩年后，Shamir將其破譯了。盡管求大數(shù)的模逆元與分解大素數(shù)的復(fù)雜度相同，但該設(shè)計存在漏洞。后來Merkle和Hellman將漏洞補(bǔ)上，再次懸賞破譯，兩年后又被人破譯，使背包體系受到致命打擊。背包體系目前基本上已不大用了，但它作為公鑰的先驅(qū)實(shí)踐者，作為算法和思路很簡單的公鑰體制，仍有了解的必要。同時，以背包問題為原理的各種新密碼體制目前仍有人在繼續(xù)研究。4.3RSA公鑰密碼(基于大數(shù)分解)［3，7，8］

RSA公鑰密碼是第一個實(shí)用的，同時也是流行至今的最典型的公鑰算法。1978年，美國麻省理工大學(xué)的Rivest、Shamir和Adelman利用數(shù)論相關(guān)知識，提出了這個公鑰系統(tǒng)［10］。4.3.1RSA加解密原理

設(shè)p和q為兩個大素數(shù)，計算n=pq和歐拉數(shù)Φ(n)=(p-1)(q-1),隨機(jī)選擇整數(shù)e,使?jié)M足(e,Φ(n))=1,于是它的逆元存在，即d=e-1modΦ(n),即有：

ed=1modΦ(n)或ed=kΦ(n)+1(4-8)

設(shè)m為明文，e為公鑰，n也是公鑰(公鑰是兩個數(shù)據(jù)),則加密過程為

C=memodn(4-9)因?yàn)槟孢\(yùn)算十分復(fù)雜，且存在多義性(λ不定)，所以它是一個單向函數(shù)。然而，利用歐拉定理知，若m與n互素，則

mΦ(n)=1modn(4-10)對任意整數(shù)k，mk仍與n互素，則

(mk)Φ(n)=1modn

于是：

mkΦ(n)+1=mmodn

由此得到解密算法：

Cd=medmodn=mkΦ(n)+1modn=mmodn

即

m=Cdmodn(4-11)

這里,d為私鑰，只有合法用戶掌握；p、q和Φ(n)在完成設(shè)計后都可銷毀；僅由公鑰e和n是無法求出d的，除非能將n分解，求出p和q，而這是Np類難題，難以實(shí)現(xiàn)。4.3.2RSA的參數(shù)選擇

1.p和q應(yīng)為強(qiáng)素數(shù)

強(qiáng)素數(shù)是這樣一種素數(shù)：對于素數(shù)p，若存在素數(shù)p1和p2，使p1|p-1，p2|p+1，則稱p為一級素數(shù)，稱p1和p2為二級素數(shù)；對于p1和p2，若存在素數(shù)r1r2和s1s2，使r1|p1-1,s1|p1+1,r2|p2-1,s2|p2+1,則稱r1、r2、s1、s2為三級素數(shù)。存在二級和三級素數(shù)的一級素數(shù)才是強(qiáng)素數(shù)。這樣才能保證在有效時間內(nèi)不可能將其分解。反之，就有可能找到一些簡便方法將其分解。2.p和q的位數(shù)問題提出RSA的三人最初建議p和q為100位的十進(jìn)制數(shù)(≈2332)，這樣可使n達(dá)到200位以上，在億次機(jī)上分解需55萬年。同時，他們希望p和q的位數(shù)相差一般是幾比特，這是因?yàn)槿绻嗖钐?，就接近于，而就很小，從而使費(fèi)爾瑪因式分解法容易進(jìn)行：從小數(shù)的平方來測試，可以大大減少復(fù)雜性。(4-12)3.e和d的選擇

e不能太小，太小了可以由得到m。d小了雖然有利于解密的速度，然而d太小了也存在隱患，破解者可以對Cd窮舉以獲得m。因此，最好d≥。

4.n在使用上的限制

不宜用同一個n去設(shè)計若干對(e,d),這樣會引起不安全因素。假若對同一明文m：

這里e1，e2互素，即滿足te1+se2=1,于是有：

這樣一來，無需私鑰，就得到了明文。4.3.3素數(shù)的檢測

1.素數(shù)是否夠用

數(shù)論有定理指出，對正整數(shù)N，小于N的素數(shù)數(shù)目約為。若p,q為十進(jìn)制154位(512bit)的大素數(shù)，那么在此范圍內(nèi)約有10151個素數(shù)。宇宙中原子僅1077個，如果每個原子從宇宙誕生至今每秒鐘需要一個素數(shù)，也才10109個。

2.是否會兩人偶然巧合選擇了同一個素數(shù)

小于n的素數(shù)的個數(shù)是，從中任選一個素數(shù)的概率是；當(dāng)n是N位十進(jìn)制大數(shù)時，這個概率小于，可見這種巧合的概率幾乎為零。

3.能否建立所有素數(shù)的數(shù)據(jù)庫，用來破譯RSA(分解n)

理論上可以這樣做，但實(shí)際行不通。設(shè)每克半導(dǎo)體存儲器可存儲10億字節(jié)，將512位的全部素數(shù)集中在有限尺寸的內(nèi)存中，其存儲器質(zhì)量將超過引力場極限，使它變成黑洞，無法提取數(shù)據(jù)。

4.怎么知道一個數(shù)是否為素數(shù)不能再分解的數(shù)才是素數(shù)，為此就得將其分解。而分解因數(shù)是Np問題，正因?yàn)樗鼰o法辦到所以才有了RSA的安全性。那RSA所用的素數(shù)從何而得呢？似乎像是個先有雞還是先有蛋的駁論。然而，檢測素數(shù)畢竟與分解因數(shù)不同?，F(xiàn)已找到多種素數(shù)測試方法和理論。①威爾遜定理：n為素數(shù)的充要條件是(n-1)!=-1modn(見前)。②費(fèi)爾馬定理：若p為素數(shù)，則對任一整數(shù)a，有aP-1≡1modp，但這只是必要條件。反過來，滿足費(fèi)爾馬定理的并不一定都是素數(shù)，如n=561=3×11×17就滿足an-1≡1modn，這樣的n被稱為卡密沙爾數(shù)(Carmichael)。③歐拉定理：二次剩余理論中指出，p是素數(shù)的充要條件是≡1modp，這里a是p的二次剩余。若a非二次剩余，則≡-1modp；若p是a的倍數(shù)，則≡0modp。合起來就是勒讓德函數(shù)：(4-13)當(dāng)不清楚n是不是素數(shù)時，上式為雅可比函數(shù):(4-14)設(shè)，則(4-15)由此得到素數(shù)判別程序的算法描述如下：

S1:隨機(jī)產(chǎn)生一整數(shù)a∈［1，n-1］。

S2:計算gcd{a,n}。

S3:若gcd{a,n}≠1，則n非素數(shù)，結(jié)束。

S4：否則計算及modn。

S5:若modn，則n可能是素數(shù)，轉(zhuǎn)S1，進(jìn)行第二輪，否則n是合數(shù)，結(jié)束。

這個算法每進(jìn)行一輪測試，正確性至少為；判斷錯誤的概率小于；若兩輪檢測都通過，則判錯概率小于；若n輪檢測都通過，則判錯概率小于=。進(jìn)行n=10～20輪判斷，可使判錯概率小于萬分之一。這種素數(shù)稱為工業(yè)級素數(shù)。④米勒-列賓(MillerRabin)測試法：使用方法③收斂很慢，而使用MR法k次通過的判錯率僅為，且比③減少一半的輪數(shù)。判別程序的算法描述如下：

S1：先化n-1=2lm(m為去掉二進(jìn)制最末位1后，再去掉l個連0)。

S2：在{1，2，…,n-1}中隨機(jī)均勻地產(chǎn)生數(shù)b；j←0，計算z←bmmodn。若z=1或n-1，則n通過測試，結(jié)束。

S3：若j=l，則n非素數(shù)，結(jié)束，否則轉(zhuǎn)S4。

S4：j=j+1,z←z2modn。若z=-1，則n通過測試，結(jié)束；否則轉(zhuǎn)S3。當(dāng)n通過第一輪測試后應(yīng)回到S2，重新產(chǎn)生隨機(jī)數(shù)b，開始下輪測試。4.3.4RSA的安全性

RSA的安全性是基于大數(shù)進(jìn)行因數(shù)分解的復(fù)雜性的。理論上已證明分解大數(shù)的漸進(jìn)復(fù)雜度大約正比于elnnln(lnn)，可見n必須足夠大，分解才能足夠復(fù)雜。最初Rivest懸賞100美元破譯129位(429比特)的RSA密碼體系，估計百萬次的計算機(jī)需連續(xù)工作4600年，結(jié)果43國600多人動用1600臺計算機(jī)通過因特網(wǎng)聯(lián)合工作，耗時8個月，于1994年4月20日破譯。后來130位的RSA也于1996年4月10日，用數(shù)域篩選法被攻破。人們又向154位發(fā)起攻擊。200位(664比特)和1024比特的RSA已有實(shí)用產(chǎn)品。

RSA的安全漏洞：由于雙鑰制既能用于加密，又能用于認(rèn)證，當(dāng)A用自己的私鑰對某文檔“加密”后，y=mdmodn，y就成為A對文檔x的簽名，任何人可以用A的公鑰將其“解密”，即x=yemodn，得到明文，同時證明該文是A所簽發(fā)的。利用這一點(diǎn)，竊密者想解析某人發(fā)給A的密文C=memodn，他可以先自己隨機(jī)產(chǎn)生一個文檔r，用A的公鑰加密s=remodn，并求出r在模n下的逆r-1；之后，他把y=sC發(fā)給A，請A簽名，如果A同意簽名，便計算u=yd

modn，發(fā)給竊密者；竊密者得到u后，計算r-1u=r-1yd=r-1sdCdmodn，因?yàn)閞=sdmodn，而r-1sd=r-1r=1modn,所以r-1u=Cdmodn=m，明文m被竊得。這個攻擊過程中，A被竊的疏漏在于他對陌生人的文檔y進(jìn)行了簽名。為了騙取A的簽名，有多種手法，比如A不愿對m3簽名(或許因m3中有不利于A的文字)，騙子可以寫m3=m1m2，而m1和m2的文字對A有利，它騙得和后，就可以計算。又如,他還可以將m3改頭換面為y=m3s(s=remodn，是隨機(jī)明文r的密文)，送y去讓A簽名，如果A簽名了，則u=ydmodn，騙子便可以計算出：

因此，絕不要對一個陌生人交給你的消息進(jìn)行簽名。即使要簽，也應(yīng)當(dāng)只對消息的HASH值簽名。

4.4Rabin公鑰體系(基于二次剩余)

Rabin公鑰體制是RSA的e=2的特例。其加密算法是：

C=m2modn(n為公鑰)(4-16)它相當(dāng)于同時滿足：

C=m2modp和C=m2modq表明C是兩個素數(shù)共同的平方剩余：(4-17)解密過程則是求同時滿足模p和模q下密文C的平方根(p和q是私鑰)。4.4.1GF(p)上平方根問題的討論在GF(p)域就是在整數(shù)［1，p-1］范圍內(nèi)求解。根據(jù)數(shù)學(xué)補(bǔ)充中關(guān)于二次剩余的知識，不難知道在［1，p-1］中的平方剩余方程：

x2=amodp

退化為

x2=ax∈［1，p-1］費(fèi)爾馬定理ap-1=1modp,則退化為

ap-1=1x∈［1，p-1］于是表明在［1，p-1］上，有個根滿足=1modp，它們是平方剩余(QR)；而另外個根滿足=-1modp=p-1modp，它們是非平方剩余(NQR)。

1.是奇數(shù)的情況

設(shè)β是一個平方剩余，滿足=1，則(4-18)因?yàn)闉槠鏀?shù)，所以必為偶數(shù)，所以必存在，因此有可見，是β的一個平方根。另一個平方根是p-α，這是因?yàn)?/p>

(p-α)2=p2-2pα+α2=α2modp

結(jié)論：對于p≠2的素數(shù)，它的平方剩余β有兩個根：

(4-19)【例1】β=2是否為二次剩余方程為x2=βmod23的平方剩余？如果是，求方程的根。

解：由=211mod23=2048mod23=1知β=2確為平方剩余，且=11為奇數(shù)。于是模23運(yùn)算下β=2的兩個根是:

和

α2=23-18=5

2.為偶數(shù)的情況

令p-1=2hq，q為奇數(shù)(p-1被2連除h次才能得到奇數(shù)q)，可以證明以下幾條：

(1)若α是NQR，則r=αq滿足=1modp。

(2)

=-1modp。

(3)若β∈QR，則存在偶數(shù)j(0≤j≤2h)使βq=rj。

(4)r-jβq+1=β。

(5)令j=2k(0≤k≤2k-1)，則

證明：(1)因?yàn)棣良俣镹QR，，所以

(2)因?yàn)?，而r=αq，p1=2hq，，所以

(3)由于β∈QR，因此又由于(2)的結(jié)論，因此若j為偶數(shù)，則比較可見:

βq=rj(0≤j≤2h)(4)由βq=rj就有r-jβq=1，即

r-jβq+1=β

或?qū)憺?/p>

(r-j/2β(q+1)/2)2=β

表明(r-j/2)β(q+1)/2是β的一個平方根。再利用(1)的結(jié)果就有(5)令j=2k，則βq=rj=r2k,所以

利用以上性質(zhì)，得到計算β平方根的算法如下：

S1：通過測試α(p-1)/2=p-1modp=p-1modp，來選擇α∈［1，p-1］為NQR。

S2：取值r←αq,δ←βq，I=h，J=1，K=0。

S3：若，則轉(zhuǎn)S5。

S4：J←J·

。

S5：若I=2則作：r←J-1β(q+1)/2，r即β的平方根，結(jié)束。

S6：I←I-1，K←K+1,轉(zhuǎn)S3。

3.n非素數(shù)，特別當(dāng)n=pq(p，q均為素數(shù))x2=bmodn的討論

x2=bmodn等價于兩個聯(lián)立方程：x2=bmodp和x2=bmodq。(1)當(dāng)和均為奇數(shù)的情況。由于它們分別有和個QR，因此原方程有個QR。兩個方程分別有解為：和；和。現(xiàn)在求x2=bmodn的解，必須是兩個方程都滿足的共同解。其次，應(yīng)將解得區(qū)域［1，p-1］和［1，q-1］擴(kuò)展到［1，n］，為此，第一個方程的解系可由和加上p的整數(shù)倍得到，第二個方程的解系可由和加上q的整數(shù)倍得到。最后，從兩個解系中找到共同的四個解?！纠?】p=3，q=7，n=21,求解x2=1mod21。

解：因?yàn)楹投际瞧鏀?shù)，所以：①顯然b=1滿足和，故知b=1是平方剩余。故：和p-1=2是x2=1modp的兩個解；和q-1=6是x2=1modq的兩個解；

第一個方程解系為{1，2，1+3，2+3，1+6，2+6,…}；第二個方程解系為{1，6，1+7，6+7，1+14，6+14,…}；共同解為α1=1和α2=8，另外兩個是21-α1=20和21-α2=13。②還可驗(yàn)證b=4也是平方剩余。這是因?yàn)?41modp=1和=43modq=64mod7=1。故：

x1==b1=4mod3=1和p-x1=3-1=2是方程x2=4mod3的兩個解；

x2==b2=16mod7=2和q-x2=7-2=5是方程x2=4mod7的兩個解；

擴(kuò)展后的解系為{1，2，4，5，7，8,…}和{2，5，9，12,…}

共同解為α1=2和α2=5，另兩個是21-2=19和21-5=16。③還可以驗(yàn)證b=16是平方剩余。這是因?yàn)?16modp=1和=163modq=23modq=1。故:

x1==16modp=1和p-x=2是方程x2=16mod3的兩個解；

x2==162modq=4mod7和q-4=3是方程x2=16mod7的兩個解；

擴(kuò)展后的解系為{1，2，4，5，7，8，10，11,…}和{3，4，10，11,…}

共同解為α1=4，α2=10,另外兩個是21-4=17和21-10=11，共有(p-1)(q-1)=3個QR。(2)或?yàn)榕紨?shù)的情況。這時，不能直接代公式寫出它的解或，然而如果用其他方法，比如窮舉試解法(或用計算機(jī)程序搜索)得到了一個解，則求另一個解和共同解的做法同上?！纠?】p=13，q=5，n=65，求解x2=1mod65。

解:這時=6,=2,均為偶數(shù),因此它共有(p-1)(q-1)=12個QR，不難驗(yàn)證b=1是p和q的平方剩余。對于b=1，有=b1=1和=b2=1，因此有:x2=1modp的解是x=1和x=p-1=12；x2=1modq的解是x=1和x=q-1=4。從而，解系為{1，12，14，25，…}和{1，4，6，9，11，14，…}；共同解為x=1，x=14，以及65-1=64和65-14=51。4.4.2Rabin密碼的安全性

先來證明，求解一個屬于QR元素的平方根的計算，等價于分解n為因子的計算。如果能分解n=pq，則解x2=amodn等價于解x2=amodp和x2=amodq。設(shè)它們的解分別是±x1和±x2，且|x1|≠|(zhì)x2|，則有：即

(x1+x2)(x1-x2)=0modn(4-21)

它等價于p|(x1+x2)而q|(x1-x2)，或者p|(x1-x2)而q|(x1+x2)。其中，p和q不能同時整除(x1+x2)和(x1-x2)。(4-20)

求出了x1和x2就等于求出了p和q。表明二次剩余的復(fù)雜度與分解大數(shù)相同，也就是說Rabin的復(fù)雜度不低于RSA，它除了求兩平方根問題外，還要求解中國剩余問題(二方程聯(lián)立求平方剩余)。4.5ElGamal公鑰系統(tǒng)(基于離散對數(shù))

ElGamal公鑰系統(tǒng)是基于GF(p)域中離散對數(shù)的Np復(fù)雜性而設(shè)計的。4.5.1基本算法

設(shè)p是素數(shù)，g是中的本原元素，選取α∈［0，p-1］，計算：

β=gαmodp(4-22)

設(shè)私有密鑰為k2=α,公有密鑰為k1=(g,β,p),則對于待加密消息m，選取隨機(jī)數(shù)k∈［0，p-1］，加密算法為(4-23)其中：

y1=gkmodp,y2=mβkmodp(4-23′)解密算法為(4-24)這是因?yàn)?4-24′)

算法中離散對數(shù)的復(fù)雜性決定了系統(tǒng)的安全，然而，算法的設(shè)計是基于群是p為模的同余乘法群，對乘法滿足封閉性，且存在乘法模逆元。如果p不是素數(shù)，則(模p)同余類群Zp只能是以加法為運(yùn)算的整數(shù)群，只存在加法模逆元，只對加法滿足封閉性，離散對數(shù)的關(guān)系就不存在了。4.5.2有限群上的離散對數(shù)公鑰體系

將群推廣到一般的有限群G，便得到推廣的ElGamal公鑰體制。設(shè)群G是運(yùn)算符為*的有限群，α∈G，H是由α生成的G的子群，H={αi︱i≥0}，選取a∈H，計算β=αa,則私有密鑰為a,公有密鑰為α、β。對于明文m，選擇隨機(jī)數(shù)k∈［0，|H|-1］,則加密算法為(4-25)其中：

y1=αk，y2=mβk(4-26)解密算法為這是因?yàn)椋?.5.3離散對數(shù)計算法

離散對數(shù)公鑰體系的安全性是基于計算離散對數(shù)的復(fù)雜性的。無論從破譯(分析)這種公鑰體系的還是從改進(jìn)(提高)這種公鑰體系的安全性出發(fā)，都應(yīng)了解計算離散對數(shù)的方法。離散對數(shù)是模冪運(yùn)算的逆運(yùn)算。計算模冪ax并不困難。將x表達(dá)為二進(jìn)制形式：

x=b0+b1·2+b2·22+…+bn-1·2n-1(4-28)則式中,bi=0的因子代之為1，bi=1的因子都化為a的各級二次冪。如求5375mod1823,則因?yàn)?/p>

375=(101110111)2=1+2+22+24+25+26+28所以

5375=5·52·54·516·532·564·5256求出5=5，52=25，54=625后，繼續(xù)求得：

58=6252mod1823=503，516=5032mod1823=1435532=14352mod1823=1058，564=10582mod1823=425128=422mod1823=1764，5256=17642mod1823=1658所以

5375=5×25×625×1435×1058×42×1658mod1823=591然而要求出log5591=?mod1823就不容易了。已知ax=ymodp，求logay=xmodp的運(yùn)算就是離散對數(shù)。1.商克(Shanks)法先看一例子:在GF(23)上求log53。因?yàn)閿?shù)值較小，我們把x=［1,22］對應(yīng)的全部y=5xmod23都計算出來，列于表4.1中。為了查對數(shù)“x=log5ymod23”的方便，數(shù)值已按y排序。查表得到log53=16。表4.1y=5xmod23的全部整數(shù)解

這種解法實(shí)際是窮舉法，p很大時復(fù)雜度將很高。由表可以看到，522mod23=50mod23=1mod23，這正是費(fèi)爾馬定理ap-1=1modp。它表明n=22是x的周期，5自乘22次就回到了1。同時表明原方程解的取值范圍是0≤x＜n。為了減少搜索范圍，現(xiàn)在把n分成了d段，每段d個值，這里：首先只在0≤r＜d內(nèi)搜索滿足

ar=bmodp的那些r值，它們被列在表4.2中。對于大于d的那些解x，可令：

x=qd+r(4-29)再進(jìn)行q輪的搜索，而q是整商，由于x≤n，(但不大于)，所以0≤q＜d。搜索輪數(shù)也不會大于d。這時：

y=ax=aqd+r(4-30)利用an=1modp(n為周期)，就有：

ar=aqd+r·a-qd=y·(a-d)q=y·(an-d)qmodp(4-31)

離散對數(shù)問題中，a和y是已知的，n與d也都容易得知，利用上式，分別令q=0,1,2,3,…去測試，而每次測試只是在表4.2的d個數(shù)據(jù)內(nèi)搜索，總共最多搜索d輪。表4.20～d范圍r=armod23的解【例4】已知y=3，a=5，求滿足y=ax

mod23的x。此例主要用以說明商克法的使用方法。

解：根據(jù)周期n=22，取d=5；賦初值a=5，y=3。計算an-d=522-5=517mod23=15，存入A，且令q←0。第一輪，計算

b=ar=y(an-d)0=3×150=3表中未查到，將結(jié)果b存入B，令q←q+1，這時q=1；第二輪，計算

b=y·(an-d)1=y·(an-d)0·(an-d)=B×A=3×15mod23=22表中仍未查到，將結(jié)果b存入B，令q←q+1，這時q=2；

第三輪，計算

b=y·(an-d)2=B×A=22×15mod23=8表中還是未查到，將b存入B，令q←q+1，這時q=3；第四輪,計算

b=y·(an-d)3=B×A=8×15mod23=5表中查到了，是r=1，這時q=3。因此，結(jié)果是：

x=qd+r=3×5+1=16總結(jié)以上算法，得到程序算法描述如下：

S1:選擇d≈，r←0，b←1。

S2：進(jìn)入表格(b～r),查表。

S3:若r=d-1，則作:對表格中b進(jìn)行排序，轉(zhuǎn)S4。否則作:始b←abmodp，r←r+1，轉(zhuǎn)S2。結(jié)束。

S4：計算A←an-d，B←y，q←0,開始下一輪。

S5:若查表存在(b～r)，其中b=B，則作：x←qd+r輸出x，結(jié)束。否則作：B←BA，q←q+1,轉(zhuǎn)S5。2.波里格-黑爾曼(PohligHellman)算法

此算法適應(yīng)于(4-32)的情況，即p-1可分解成許多小素數(shù)因子的情況。為了求解：

y=xrmodp(4-33)可令(4-33)根據(jù)中國剩余定理,只要能確定各個ri，原方程的解r即可知曉：

r=r1M1y1+r2M2y2+…+rkMkyk(4-35)式中：而ri可設(shè)為

先來討論r=r1mod。將式(4-35)代入式(4-33)，經(jīng)過一些推導(dǎo)：①可得到

由于離散對數(shù)問題中x和y都是已知的，因此比較等號兩邊就可以確定r10；②令，還可得到由此可確定r11。③令，則有由此可確定r12。類似地，令，則有……由此可確定r13、r14……從而:

對各的子方程同法處理,最后由式(4-35)可寫出r?！纠?】p=8101，x=6，y=7833，求滿足y≡xr(modp)的r。解：首先由p-1=8100=22×34×52知p1=2，p2=3，p3=5。令。

(1)對p1=2，有：

β1=68100/2=64050=8100(mod8101),=1另一方面，p1=2，n1=2，y=7833，y8100/2=8100(mod8101)，代入①可求得r10=1。又x-1=6751,y1=yx-1=5356，=1，代入②可求得r11=0。所以

r1=r10+r11p1=1(2)對p2=3，有：

β2=68100/3=62700=5883(mod8101),另一方面，p2=3,n2=4,y=7833,y8100/3=2217,代入①可求得r20=2。同法求得r21=2，r22=1，r23=1，所以

r2=2+2×3+32+33=44(3)對于p3=5，有：

β3=68100/5=61620=3547,=356,

另一方面，p3=5，n3=2，y8100/5=356，代入①可求得r30=2。又y1=yx-2=7833×7876=3593,

=356，代入②可求得r31=2.所以r3=2+2×5=12(4)現(xiàn)在就可以用中國剩余定理來求r了(還利用了a-1=a(m)-1modm)：

M1=3452=2025，y1=mod22=20251mod4=1，M1y1=2025(mod8101)

M2=2252=100，y2=mod34=10053mod81=64，M2y2=6400(mod8101)

M3=2234=324，y3=mod52=32415mod25=24，M3y3=7776(mod8101)所以

r=r1M1y1+r2M2y2+r3M3y3

=2025×1+44×6400+12×7776=376937=4337(mod8101)

以上求解過程表明，在GF(p)域中使用離散對數(shù)密碼體制時，p-1有小因數(shù)是不安全的。最好p-1=2p1，而p1是大素數(shù)。而在GF(2m)域中，則希望2m-1是大素數(shù)，如m=127時，N=2127-1是大素數(shù)，=1019；當(dāng)m=521時，N=2521-1也是大素數(shù)，=1078。4.6McEliece公鑰密碼(基于糾錯碼)

①

糾錯碼和密碼是編碼的不同分支，在20世紀(jì)70年代之前它們幾乎互不相關(guān)，各自獨(dú)立發(fā)展。隨著現(xiàn)代密碼學(xué)的誕生，計算復(fù)雜性成了密碼體系安全的基礎(chǔ)；而隨著糾錯碼的發(fā)展，許多代數(shù)方法的引入，糾錯碼中也出現(xiàn)了許多NPC問題，如1997年證明了一般線性碼的Hamming重量問題是NPC問題，還有：(1)陪集重量問題是NPC問題。

(2)重量分布問題是NPC問題。

(3)最小碼距問題是NPC問題。如此等等。1978年，McEliece基于糾錯碼設(shè)計出了公鑰體制，它利用了郭帕(Goppa)碼具有快速譯碼的特點(diǎn)，發(fā)明了McEliece碼，此后糾錯碼成了構(gòu)造公鑰密碼的又一熱點(diǎn)。4.6.1Goppa碼的一般描述［12］

1.Goppa碼的有理分式表示

正如可以利用一個多項(xiàng)式C(x)=cn-1xn-1+cn-2xn-2+…+c1x+c0表示一個n維線性空間的矢量(cn-1cn-2…c2c1c0)一樣，也可以用一個有理分式來表示這個矢量：(4-36)如果C(x)是一個(n,k)循環(huán)碼的碼多項(xiàng)式，則應(yīng)滿足：

C(x)=0modg(x)其中，g(x)是生成多項(xiàng)式。

同理，如果要把C(z)作為循環(huán)碼的有理多項(xiàng)式，它也應(yīng)當(dāng)被生成多項(xiàng)式g(z)整除：(4-37)顯然，若是某個碼組中的兩個碼字，則不難證明：(4-38)(4-39)也是一個碼字。可見有理分式碼是線性碼。下面討論有理分式表示與多項(xiàng)式表示的關(guān)系。由于生成多項(xiàng)式g(z)是既約多項(xiàng)式，所以必與它互素，所以必存在逆元其中，p(z)是次數(shù)不高于g(z)的多項(xiàng)式。于是：(4-40)如果有理分式各多項(xiàng)式都采用模逆元,就變成了多項(xiàng)式表達(dá)。2.Goppa碼的定義和描述

設(shè)0＜n≤qm(q為素數(shù)或素數(shù)冪，m為大于0的整數(shù))，L={α1α2…αn}是一個有序集合，αi∈GF(qm)，且對任何不大于n的正整數(shù)i和j，當(dāng)i