第4章公鑰密碼4.1引言

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

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

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

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

4.7橢圓曲線公鑰體制

習(xí)題4

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

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

4.1.1對(duì)稱密鑰的困惑

1.密鑰交換問(wèn)題

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

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

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

1．Merkle難題

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

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

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

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

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

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

2.雙鑰制的提出

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

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

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

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

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

(3)約定

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

獲得；用戶j可由

獲得。

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

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

1.公開(kāi)密鑰體系的使用方式及功能

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

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

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

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

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

(4-4)

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

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

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

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

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

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

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

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

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

1.問(wèn)題

已知n個(gè)物體重量分別為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較小時(shí)，這是一個(gè)多解的不定方程問(wèn)題。例如，A={1，2，5，8，11，17，21},b=47,則答案可以是2+5+8+11+21,也可以是1+8+17+21。當(dāng)n較大時(shí)，它是一個(gè)Np類的難解問(wèn)題。例如，n=100，2100=1.27×1030，以每秒107種方案的速度用計(jì)算機(jī)搜索，也得4.02×1015年才能完成窮舉。

3.超遞增序列的背包問(wèn)題

如果限制這些物體的重量，即每個(gè)物體的重量都滿足比它的前面所有物體的重量之和大的條件，即(4-7)則這樣的背包問(wèn)題叫做超遞增背包問(wèn)題。超遞增背包問(wèn)題是p類唯一解的可求解問(wèn)題。例如：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必沒(méi)有；而又由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類可解問(wèn)題；若用非超序列A={a1,a2,…,an}將之加密，則是Np類難解問(wèn)題。

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

Merkle和Hellman當(dāng)初是利用模逆元進(jìn)行這個(gè)變換的。例如，B={1，3，7，13，26，119，267}，選大于全部元素之和501的一個(gè)數(shù)，p=523,再選一個(gè)與523互素的數(shù)w=28,并求出w-1=467mod523，于是可分別求出每個(gè)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來(lái)加密。例如，明文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而這是一個(gè)超遞增背包問(wèn)題，容易解出：

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

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

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

設(shè)p和q為兩個(gè)大素?cái)?shù)，計(jì)算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也是公鑰(公鑰是兩個(gè)數(shù)據(jù)),則加密過(guò)程為

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

mΦ(n)=1modn(4-10)對(duì)任意整數(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è)計(jì)后都可銷毀；僅由公鑰e和n是無(wú)法求出d的，除非能將n分解，求出p和q，而這是Np類難題，難以實(shí)現(xiàn)。4.3.2RSA的參數(shù)選擇

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

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

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

4.n在使用上的限制

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

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

這樣一來(lái)，無(wú)需私鑰，就得到了明文。4.3.3素?cái)?shù)的檢測(cè)

1.素?cái)?shù)是否夠用

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

2.是否會(huì)兩人偶然巧合選擇了同一個(gè)素?cái)?shù)

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

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

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

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

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

S2:計(jì)算gcd{a,n}。

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

S4：否則計(jì)算及modn。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

x2=amodp

退化為

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

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

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

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

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

結(jié)論：對(duì)于p≠2的素?cái)?shù)，它的平方剩余β有兩個(gè)根：

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

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

和

α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ù)，則比較可見(jiàn):

β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是β的一個(gè)平方根。再利用(1)的結(jié)果就有(5)令j=2k，則βq=rj=r2k,所以

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

S1：通過(guò)測(cè)試α(p-1)/2=p-1modp=p-1modp，來(lái)選擇α∈［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非素?cái)?shù)，特別當(dāng)n=pq(p，q均為素?cái)?shù))x2=bmodn的討論

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

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

第一個(gè)方程解系為{1，2，1+3，2+3，1+6，2+6,…}；第二個(gè)方程解系為{1，6，1+7，6+7，1+14，6+14,…}；共同解為α1=1和α2=8，另外兩個(gè)是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的兩個(gè)解；

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

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

共同解為α1=2和α2=5，另兩個(gè)是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的兩個(gè)解；

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

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

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

解:這時(shí)=6,=2,均為偶數(shù),因此它共有(p-1)(q-1)=12個(gè)QR，不難驗(yàn)證b=1是p和q的平方剩余。對(duì)于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密碼的安全性

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

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

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

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

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

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

β=gαmodp(4-22)

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

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

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

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

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

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

x=b0+b1·2+b2·22+…+bn-1·2n-1(4-28)則式中,bi=0的因子代之為1，bi=1的因子都化為a的各級(jí)二次冪。如求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)算就是離散對(duì)數(shù)。1.商克(Shanks)法先看一例子:在GF(23)上求log53。因?yàn)閿?shù)值較小，我們把x=［1,22］對(duì)應(yīng)的全部y=5xmod23都計(jì)算出來(lái)，列于表4.1中。為了查對(duì)數(shù)“x=log5ymod23”的方便，數(shù)值已按y排序。查表得到log53=16。表4.1y=5xmod23的全部整數(shù)解

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

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

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

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

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

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

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

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

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

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

第三輪，計(jì)算

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

b=y·(an-d)3=B×A=8×15mod23=5表中查到了，是r=1，這時(shí)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，則作:對(duì)表格中b進(jìn)行排序，轉(zhuǎn)S4。否則作:始b←abmodp，r←r+1，轉(zhuǎn)S2。結(jié)束。

S4：計(jì)算A←an-d，B←y，q←0,開(kāi)始下一輪。

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可分解成許多小素?cái)?shù)因子的情況。為了求解：

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

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

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

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

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

(1)對(duì)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)對(duì)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)對(duì)于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)在就可以用中國(guó)剩余定理來(lái)求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)

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

①

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

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

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

1.Goppa碼的有理分式表示

正如可以利用一個(gè)多項(xiàng)式C(x)=cn-1xn-1+cn-2xn-2+…+c1x+c0表示一個(gè)n維線性空間的矢量(cn-1cn-2…c2c1c0)一樣，也可以用一個(gè)有理分式來(lái)表示這個(gè)矢量：(4-36)如果C(x)是一個(gè)(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)顯然，若是某個(gè)碼組中的兩個(gè)碼字，則不難證明：(4-38)(4-39)也是一個(gè)碼字?？梢?jiàn)有理分式碼是線性碼。下面討論有理分式表示與多項(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為素?cái)?shù)或素?cái)?shù)冪，m為大于0的整數(shù))，L={α1α2…αn}是一個(gè)有序集合，αi∈GF(qm)，且對(duì)任何不大于n的正整數(shù)i和j，當(dāng)i