第4章公鑰密碼4.1引言

4.2背包公鑰密碼系統

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

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

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

4.7橢圓曲線公鑰體制

習題4

實踐練習4

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

4.1.1對稱密鑰的困惑

1.密鑰交換問題

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

2.通信網絡中的密鑰管理問題

網絡中N個用戶兩兩保密通信，需要分配和保管M=N(N+1)把密鑰，當N很大時，比如N=1000時，則M≈5×105，網管中心一定非常繁忙，甚至會成為通信的瓶頸。因此，密鑰管理問題成了信息系統的又一難題。4.1.2公開密鑰的產生和雛形

1．Merkle難題

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

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

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

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

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

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

2.雙鑰制的提出

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

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

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

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

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

(3)約定

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

獲得；用戶j可由

獲得。

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

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

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

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

(1)保密功能(包括會話密鑰的交換)：發信人用收信人的公鑰加密，形成密文，收信人用自己的私鑰解密。其他人因為不掌握可配對的私鑰，所以無法解讀這個密文。(2)認證功能：發信人用自己的私鑰加密形成密文，收信人用發信人的公鑰解密。其實任何人都能查到發信人的公鑰來解譯密文，能正確解譯即證明該密文是發信人所加密的。

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

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

公開密鑰體系把算法公開，并且把一對密鑰中的一把公開，才換來了功能上的增加與使用上的方便。而之所以將之公開，是因為解密所用算法并非加密的逆運算，解密所用密鑰也不同于加密所用的密鑰，而且二者不可互相推導。加密：明文M→變換(k1為加密密鑰)→密文C，即

(4-4)

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

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

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

數學上存在一種單向陷門函數，它有下列性質：

(1)對于每個x∈X，計算y=f(x)是容易的。正是因為這一點，加密運算才是簡單可行的。

(2)明知y=f(x)在y∈Y中有解，但由給定的y難以求出x，其逆運算x=f-1(y)十分復雜。正是因為這一點，它被叫做單向函數。即使公開了算法，也難以在有限機時內計算出逆運算結果，系統安全性才有了保障。

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

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

1.從基于算法的神秘性到基于算法的復雜性

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

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

1.問題

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

當n較小時，這是一個多解的不定方程問題。例如，A={1，2，5，8，11，17，21},b=47,則答案可以是2+5+8+11+21,也可以是1+8+17+21。當n較大時，它是一個Np類的難解問題。例如，n=100，2100=1.27×1030，以每秒107種方案的速度用計算機搜索，也得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背包公鑰系統

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

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

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

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

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

A和p=523為公鑰，求出A后，將w-1銷毀。要發送信息就用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背包公鑰體系的破解與發展現狀

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

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

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

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

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

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

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

(mk)Φ(n)=1modn

于是：

mkΦ(n)+1=mmodn

由此得到解密算法：

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

即

m=Cdmodn(4-11)

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

1.p和q應為強素數

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

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

4.n在使用上的限制

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

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

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

1.素數是否夠用

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

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

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

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

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

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

S1:隨機產生一整數a∈［1，n-1］。

S2:計算gcd{a,n}。

S3:若gcd{a,n}≠1，則n非素數，結束。

S4：否則計算及modn。

S5:若modn，則n可能是素數，轉S1，進行第二輪，否則n是合數，結束。

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

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

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

S3：若j=l，則n非素數，結束，否則轉S4。

S4：j=j+1,z←z2modn。若z=-1，則n通過測試，結束；否則轉S3。當n通過第一輪測試后應回到S2，重新產生隨機數b，開始下輪測試。4.3.4RSA的安全性

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

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

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

因此，絕不要對一個陌生人交給你的消息進行簽名。即使要簽，也應當只對消息的HASH值簽名。

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

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

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

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

x2=amodp

退化為

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

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

1.是奇數的情況

設β是一個平方剩余，滿足=1，則(4-18)因為為奇數，所以必為偶數，所以必存在，因此有可見，是β的一個平方根。另一個平方根是p-α，這是因為

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

結論：對于p≠2的素數，它的平方剩余β有兩個根：

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

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

和

α2=23-18=5

2.為偶數的情況

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

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

(2)

=-1modp。

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

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

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

證明：(1)因為α假定為NQR，，所以

(2)因為，而r=αq，p1=2hq，，所以

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

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

r-jβq+1=β

或寫為

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

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

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

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

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

S3：若，則轉S5。

S4：J←J·

。

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

S6：I←I-1，K←K+1,轉S3。

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

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

解：因為和都是奇數，所以：①顯然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。②還可驗證b=4也是平方剩余。這是因為=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的兩個解；

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

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

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

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

擴展后的解系為{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)或為偶數的情況。這時，不能直接代公式寫出它的解或，然而如果用其他方法，比如窮舉試解法(或用計算機程序搜索)得到了一個解，則求另一個解和共同解的做法同上。【例3】p=13，q=5，n=65，求解x2=1mod65。

解:這時=6,=2,均為偶數,因此它共有(p-1)(q-1)=12個QR，不難驗證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。設它們的解分別是±x1和±x2，且|x1|≠|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。表明二次剩余的復雜度與分解大數相同，也就是說Rabin的復雜度不低于RSA，它除了求兩平方根問題外，還要求解中國剩余問題(二方程聯立求平方剩余)。4.5ElGamal公鑰系統(基于離散對數)

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

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

β=gαmodp(4-22)

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

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

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

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

y1=αk，y2=mβk(4-26)解密算法為這是因為：4.5.3離散對數計算法

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

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

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

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

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的運算就是離散對數。1.商克(Shanks)法先看一例子:在GF(23)上求log53。因為數值較小，我們把x=［1,22］對應的全部y=5xmod23都計算出來，列于表4.1中。為了查對數“x=log5ymod23”的方便，數值已按y排序。查表得到log53=16。表4.1y=5xmod23的全部整數解

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

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

x=qd+r(4-29)再進行q輪的搜索，而q是整商，由于x≤n，(但不大于)，所以0≤q＜d。搜索輪數也不會大于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)

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

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

解：根據周期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表中未查到，將結果b存入B，令q←q+1，這時q=1；第二輪，計算

b=y·(an-d)1=y·(an-d)0·(an-d)=B×A=3×15mod23=22表中仍未查到，將結果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。因此，結果是：

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

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

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

S3:若r=d-1，則作:對表格中b進行排序，轉S4。否則作:始b←abmodp，r←r+1，轉S2。結束。

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

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

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

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

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

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

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

對各的子方程同法處理,最后由式(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)對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)現在就可以用中國剩余定理來求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)域中使用離散對數密碼體制時，p-1有小因數是不安全的。最好p-1=2p1，而p1是大素數。而在GF(2m)域中，則希望2m-1是大素數，如m=127時，N=2127-1是大素數，=1019；當m=521時，N=2521-1也是大素數，=1078。4.6McEliece公鑰密碼(基于糾錯碼)

①

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

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

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

1.Goppa碼的有理分式表示

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

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

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

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