《新編密碼學(xué)》課件第5章 公鑰密碼

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

公鑰密碼學(xué)解決的兩個(gè)問(wèn)題：密鑰分配數(shù)字簽名起源

1976年兩位美國(guó)密碼學(xué)者W.Diffie和M.Hellman在該年度的美國(guó)國(guó)家計(jì)算機(jī)會(huì)議上提交了一篇名為“密碼學(xué)的新方向（NewDirectionsinCryptography）”的論文，文中首次提出了公鑰密碼體制的新思想。它為解決傳統(tǒng)經(jīng)典密碼學(xué)中面臨的諸多難題提供了一個(gè)新的思路。公鑰密碼的基本思想

密鑰分成兩個(gè)部分：公開密鑰（簡(jiǎn)稱公鑰）用于消息的加密，公開的私有密鑰（簡(jiǎn)稱私鑰）用于消息的解密，秘密的

公鑰密碼體制

雙鑰密碼體制（非對(duì)稱密碼體制）

傳統(tǒng)的經(jīng)典密碼體制

單鑰密碼體制（對(duì)稱密碼體制）公鑰密碼體制的基本流程發(fā)送方加密算法密鑰空間接收方解密算法

C

AB公鑰算法應(yīng)滿足的要求公鑰密碼體制：

M

：明文

C

：密文

K

：密鑰對(duì)

E：加密變換

D：解密變換（續(xù)）

1）K中每一個(gè)公私密鑰對(duì)，在E中存在：一個(gè)加密變換：一個(gè)解密變換：

使得，任意明文消息均可以找到一個(gè)唯一的；滿足：（續(xù)）

2）對(duì)于任意的公私鑰對(duì)，加密變換和解密變換都是多項(xiàng)式可計(jì)算的函數(shù)。知道公鑰的情況下推知私鑰是計(jì)算上不可行的。

公鑰體制的核心：

加密變換和解密變換的設(shè)計(jì)

在密碼算法中，加解密變換是互逆的，由條件2）知在公鑰密碼體制中加解密變換不能簡(jiǎn)單的直接互推。

用陷門單向函數(shù)構(gòu)造公鑰密碼體制

注陷門單向函數(shù)

思想：

一個(gè)可逆函數(shù)，對(duì)于定義域中的任意滿足：計(jì)算函數(shù)值是容易的；由求在計(jì)算上是不可行的，除非知道某些輔助信息（稱為陷門信息）；一個(gè)可行的公鑰算法應(yīng)滿足的要求（續(xù)）小結(jié)公鑰密碼體制通常將其安全性建立在某個(gè)尚未解決（且尚未證實(shí)能否有效解決）的數(shù)學(xué)難題的基礎(chǔ)上。

好處：

簡(jiǎn)化了密鑰分配任務(wù)；對(duì)密鑰協(xié)商與密鑰管理，數(shù)字簽名與身份認(rèn)證產(chǎn)生了深刻的影響；是密碼學(xué)發(fā)展史上的一次革命；5.2背包算法

起源：

R.Merkle和M.Hellman在1978年根據(jù)組合數(shù)學(xué)中背包問(wèn)題提出第一個(gè)公鑰密碼算法。又稱為MH背包算法。

背包問(wèn)題

設(shè)有一堆物品，體積各不相同，問(wèn)能否從這堆物品中找出幾個(gè)正好裝滿一個(gè)給定容量的背包？（假定物品之間不留空隙）數(shù)學(xué)描述：

記物品的體積分別為，背包的容量為C，則背包問(wèn)題可表示為：其中，等于1或者0。

表示第i個(gè)物品在背包中；

表示第i個(gè)物品不在背包中；稱物品體積的序列為背包向量。

（續(xù)）理論上講，通過(guò)檢查背包向量的所有子集，計(jì)算出每個(gè)子集的元素之和，總可找出一個(gè)子集作為背包問(wèn)題的解，因此背包問(wèn)題又稱為子集和問(wèn)題。事實(shí)上，背包問(wèn)題是一類完全（）問(wèn)題。有一類特殊的背包問(wèn)題是容易求解的

超遞增背包問(wèn)題當(dāng)背包的長(zhǎng)度n過(guò)大時(shí)對(duì)全部子集進(jìn)行窮舉式搜索是不可能的超遞增背包問(wèn)題設(shè)是一個(gè)背包向量，若V滿足：則稱V是一個(gè)超遞增向量。

序列就是一個(gè)超遞增序列。

例：超遞增背包問(wèn)題的解法：

設(shè)背包的容量為C，從左到右依次檢查超遞增背包向量V中的每個(gè)元素；

若

，則在解中，對(duì)應(yīng)的應(yīng)為1，并將C的值更新為；

若

，則不在解中，對(duì)應(yīng)的應(yīng)為0,C的值保持不變；然后，對(duì)依次重復(fù)上述過(guò)程，并判斷C是否減少到0。

C為0，則問(wèn)題的解存在；

不為0，則問(wèn)題的解不存在；例5.1故，問(wèn)題的解為110101。非超遞增向量t和k互素，確保t在模k下的乘法逆元存在。令則U是一個(gè)非超遞增向量。背包算法的描述

思想：

私有密鑰設(shè)置為：將超遞增向量轉(zhuǎn)換為非超遞增向量的參數(shù)、和；公開密鑰設(shè)置為：非超遞增向量；加密變換：所得結(jié)果為密文解密變換：例5.2設(shè)V=(1,3,7,13,26,65,119,267)是一個(gè)超遞增向量；取模數(shù)k=523，乘數(shù)t=467，則：計(jì)算公鑰：并對(duì)外公布U。（續(xù)）

發(fā)送方：

有一消息m=10101100,用公鑰U對(duì)m加密得到密文；（續(xù)）接收方：

1）利用公鑰U與私鑰和k還原出超遞增背包V;2)計(jì)算出：

3）以99作為背包的容量去解超遞增背包問(wèn)題；則解密得到明文分組為：10101100，即為原m。背包算法的安全性

背包算法利用難解的一般背包問(wèn)題作為公開密鑰，對(duì)明文進(jìn)行加密；

私有密鑰則利用易解的超遞增背包問(wèn)題給出一個(gè)解密的簡(jiǎn)單方法。不知道私鑰的攻擊者要想破譯密文在計(jì)算上看似是不可行的。背包算法破解

基本思想：

找出一對(duì)任意的和，使得用公開的背包向量U模乘后得到一個(gè)超遞增向量。

Why?

MH背包體制的公開密鑰是由超遞增向量變換而來(lái)，雖經(jīng)過(guò)模乘置亂，但超遞增向量?jī)?nèi)在的規(guī)律并不能完全被隱藏，給攻擊者留下可乘之機(jī)。（續(xù)）背包算法是第一個(gè)使公鑰密碼體制成為現(xiàn)實(shí)的密碼算法，它說(shuō)明了如何將數(shù)學(xué)難題應(yīng)用于公鑰密碼算法的設(shè)計(jì)。

優(yōu)點(diǎn)：加解密速度很快

缺點(diǎn)：不安全性5.3

RSA算法

大數(shù)分解問(wèn)題：計(jì)算兩個(gè)素?cái)?shù)的乘積非常容易；分解該乘積卻異常困難；特別是在這兩個(gè)素?cái)?shù)都很大的情況下起源：

1978年美國(guó)MIT的三名數(shù)學(xué)家R.Rivest，A.Shamir和L.Adleman提出了著名的公鑰密碼體制：RSA公鑰算法。

思想：

RSA算法基于指數(shù)加密概念，以兩個(gè)大素?cái)?shù)的乘積作為算法的公鑰來(lái)加密消息，密文的解密必須知道相應(yīng)的兩個(gè)大素?cái)?shù)。（續(xù)）

RSA公鑰算法特點(diǎn)：

思想最簡(jiǎn)單；

分析最透徹；

應(yīng)用最廣泛；易于理解和實(shí)現(xiàn)；

經(jīng)受住了密碼分析，具有一定的可信度。5.3.1RSA算法的描述

獨(dú)立選取兩個(gè)大素?cái)?shù)p

和q

；計(jì)算：

隨機(jī)選取一個(gè)滿足且的整數(shù)e，則e在模下的逆元為：

n和e為公鑰，d為私鑰。

為了獲得最大程度的安全性，選取的p和q的長(zhǎng)度應(yīng)差不多，都應(yīng)位長(zhǎng)度在100位以上的十進(jìn)制數(shù)字。注：p和q不再需要時(shí)，可以銷毀，但一定不能泄露。加密變換：

將信息劃分成數(shù)值小于n的一系列數(shù)據(jù)分組。

對(duì)每個(gè)明文分組m進(jìn)行如下的加密變換得到密文c：解密變換：

證明：由歐拉定理知：如果兩個(gè)整數(shù)a和b互素，那么，。 在RSA算法中，明文m必與兩個(gè)素?cái)?shù)p和q中至少一個(gè)互素。由知，存在整數(shù)k使得

若m與p和q都不互素，那么m既是p的倍數(shù)也是q的倍數(shù)，于是m也是n的倍數(shù)，這與m<n矛盾。情況一：m僅與p、q二者之一互素假設(shè)m與p互素且與q不互素，則存在整數(shù)a使得：由歐拉定理知：

故存在一個(gè)整數(shù)t使得：給上式兩邊同乘，得到：即：情況二：m和p、q都互素

此時(shí)m和n也互素，故得：

RSA算法實(shí)質(zhì)：—單表帶換系統(tǒng)例5.3

選取p=5，q=11，則有：n=55且明文分組應(yīng)取1到54的整數(shù)。

選取加密指數(shù)e=7，則e滿足

且與互素，故解密指數(shù)為d=23。

假如有一個(gè)消息m=53197，分組可得：，，。

分組加密得到：密文的解密為：最后恢復(fù)出明文5.3.2RSA算法的安全性缺點(diǎn)：

密鑰產(chǎn)生和加/解密過(guò)程都很復(fù)雜，系統(tǒng)運(yùn)行速度比較慢。攻擊方法具體實(shí)現(xiàn)：現(xiàn)狀：模數(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)導(dǎo)158位的十進(jìn)制整數(shù)也已被分解，這意味著512比特模數(shù)的RSA已經(jīng)不安全了。RSA算法安全性（續(xù)）

更危險(xiǎn)的安全威脅來(lái)自于大數(shù)分解算法的改進(jìn)和新算法的不斷提出。

破解RSA-129采用的是二次篩法；

破解RSA-130使用的算法稱為推廣的數(shù)域篩法；盡管如此，密碼專家們認(rèn)為一定時(shí)期內(nèi)1024到2048比特模數(shù)的RSA還是相對(duì)安全的。該算法使破解RSA-130的計(jì)算量?jī)H比破解RSA-129多100%。攻擊方法（續(xù)）除了對(duì)RSA算法本身的攻擊外，RSA算法還面臨著攻擊者對(duì)密碼協(xié)議的攻擊。

利用RSA算法的某些特性和實(shí)現(xiàn)過(guò)程對(duì)其進(jìn)行攻擊。共用模數(shù)攻擊前提：RSA的實(shí)現(xiàn)中，多個(gè)用戶選用相同的模數(shù)

n，但有不同的加解密指數(shù)

e和

d。共用模數(shù)優(yōu)點(diǎn)：

—

算法運(yùn)行簡(jiǎn)單缺點(diǎn)：

—

算法不安全

共用模數(shù)攻擊（續(xù)）

設(shè)

和

是兩個(gè)互素的加密密鑰，共用的模數(shù)為

n。對(duì)同一個(gè)明文消息

m加密得:

攻擊者知道n，

，

，

和

，他可以用如下方法恢復(fù)出明文

:

共用模數(shù)攻擊（續(xù)）由于

和

互素，由擴(kuò)展的歐幾里德算法可找到

r和

s，使其滿足：由此可得：

明文消息

m

被恢復(fù)出來(lái)。r和

s必有一個(gè)為負(fù)整數(shù)，上述計(jì)算需要用擴(kuò)展的歐幾里德算法算出

或者

在模

n下的逆.低加密指數(shù)攻擊較小加密指數(shù)

e：

—可以加快消息加密的速度

—太小會(huì)影響RSA系統(tǒng)的安全性原理：在多個(gè)用戶采用相同的加密密鑰

e和不同的模數(shù)n的情況下，如果將同一個(gè)消息（或者一組線性相關(guān)的消息）分別用這些用戶的公鑰加密，那么利用中國(guó)剩余定理可以恢復(fù)出明文。低加密指數(shù)攻擊（續(xù)）

假設(shè)取e=3，三個(gè)用戶不同模數(shù)分別是n1,n2,和n3，將消息x用這三組密鑰分別加密為：根據(jù)中國(guó)剩余定理，由y1,y2和y3求出：低加密指數(shù)攻擊（續(xù)）由于：因此：于是：低加密指數(shù)攻擊（續(xù)）

如何抵抗攻擊？

—加密指數(shù)e必須足夠大；

—對(duì)較短的消息進(jìn)行獨(dú)立的隨機(jī)數(shù)填充；破壞明文消息的相關(guān)性，以防止低加密指數(shù)攻擊。中間相遇攻擊

指數(shù)運(yùn)算具有可乘性，這種可乘性有可能招致其他方式的攻擊。如果明文m可被分解成兩項(xiàng)之積那么：這意味著明文的分解可導(dǎo)致密文的分解，明文分解容易使得密文分解也容易。密文分解容易將導(dǎo)致中間相遇攻擊。攻擊方法描述由RSA的可乘性得：前提：攻擊方法（續(xù)）

1）攻擊者先創(chuàng)建一個(gè)有序的序列：

2）搜索這個(gè)有序序列，嘗試從中找到兩項(xiàng)和滿足：

3）攻擊者能在步操作之內(nèi)找到和，由此獲得明文。攻擊方法（續(xù)）RSA算法的參數(shù)選擇

1）模數(shù)n的確定

不能在多個(gè)用戶之間共用模數(shù)

模數(shù)n是兩個(gè)大素?cái)?shù)p和q的乘積多用戶之間共用模數(shù)會(huì)招致共用模數(shù)攻擊N的確定問(wèn)題可轉(zhuǎn)化為如何恰當(dāng)?shù)剡x擇p和q模數(shù)n的確定（續(xù)）

p和q應(yīng)滿足的要求：

p和q要足夠大

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

p和q之差要合適

p-1和q-1的最大公因子要小至少100位以上的十進(jìn)制整數(shù)P和q的取值會(huì)影響分解模數(shù)n的困難性防止迭代攻擊模數(shù)n的確定（續(xù)）若一個(gè)素?cái)?shù)p稱為強(qiáng)素?cái)?shù)或一級(jí)素?cái)?shù)，則p滿足以下條件：

存在兩個(gè)大素?cái)?shù)p1和p2，使得p1|(p-1)，p2|(p+1);

存在四個(gè)大素?cái)?shù)r1,r2,s1和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ù)。模數(shù)n的確定（續(xù)）

p和q不是強(qiáng)素?cái)?shù)：

假設(shè)p-1有k個(gè)素因子，由算術(shù)定理可得：其中，為素?cái)?shù)，為正整數(shù)()。如果很小，設(shè)（A為已知的小整數(shù)）構(gòu)造：其中，，顯然有。模數(shù)n的確定

任意小于素?cái)?shù)p的正整數(shù)t均與p互素，設(shè)t=2由歐拉定理可知：因而：計(jì)算：

若X=1，令t=3，重新計(jì)算直到

若

，由，得到n的分解因子p和q。若p和q之差很?。?/p>

由：可得：所以與近似。令：由大于的整數(shù)依次嘗試u且，從而解出p與q。

若p和q之差很大：如果兩者之差很大，則其中一個(gè)必然較小，那么可以從一個(gè)小的素?cái)?shù)開始依次嘗試，最終分解n。

p和q之差要適當(dāng)，一般是長(zhǎng)度相差幾個(gè)比特。迭代攻擊

假設(shè)攻擊者截獲了密文，則可進(jìn)行如下迭代攻擊：記：其中：若存在t使得：則有整數(shù)k使得：迭代攻擊（續(xù)）

由歐拉定理可知：還有：所以：因而：若t較小，則這種迭代攻擊很容易成功。迭代攻擊（續(xù)）

由歐拉定理可知：如果p-1與q-1的最大公因子較小，則t較大。如果t大到（p-1）(q-1)的一半，則迭代攻擊難以奏效。加密密鑰e的選取需要滿足以下幾個(gè)要求：

1）e要與模數(shù)n的歐拉函數(shù)值互素，否則無(wú)法計(jì)算解密密鑰d。

2）e不能太小，否則容易遭受低加密指數(shù)攻擊。

如果e和m都很小且滿足，此時(shí)密文可直接得到，則c開e次方可得明文m。

3）e在模數(shù)下的階要足夠大。一般達(dá)到

(p-1)(q-1)。解密密鑰d的選取

加密密鑰e選定之后，利用擴(kuò)展的歐幾里得算法可以求出解密密鑰d。

解密密鑰d不能太小，否則易受已知明文攻擊。

解密密鑰d的選?。ɡm(xù)）因此，一般要求d不能小于。5.4

Rabin算法

5.4.1求解數(shù)模下的平方根問(wèn)題

證明：根據(jù)已知條件：由同余理論可知：

（續(xù)）

由a是模的平方剩余可知：有兩個(gè)模的解，分別記為：可得一系列的一次同余方程組：

其中，可取或者。

由中國(guó)剩余定理可知每一個(gè)這樣的一次同余式都有唯一的模n解。（續(xù)）（續(xù)）證明：根據(jù)a是模p的平方剩余，由Euler準(zhǔn)則可知：

于是：5.4.2Rabin算法描述

Rabin算法既可看成是RSA算法的一個(gè)特例，也可看成對(duì)RSA算法的一個(gè)修正。Rabin算法是一個(gè)被證明其破解難度正好等價(jià)于大整數(shù)分解的公鑰密碼算法，它是第一個(gè)可證明安全的公鑰密碼算法。Rabin算法的安全性基于求解合數(shù)模下的平方根的困難性。Rabin算法描述Rabin算法描述（續(xù)）加密變換：明文消息m,通過(guò)計(jì)算得到密文c。

解密變換：為了解出密文c，需求解二次同余方程：Rabin算法描述（續(xù)）令，則上面方程可改寫為：

再令，則方程進(jìn)一步改寫為：

因此，解密問(wèn)題歸結(jié)為求C模n的平方根。Rabin算法描述（續(xù)）

方程有四個(gè)解，當(dāng)時(shí)：

方程

的兩個(gè)解為：

方程的兩個(gè)解為：Rabin算法描述（續(xù)）

組合得到四個(gè)一次同余方程組：解這四個(gè)同于方程組，其解是C模n的四個(gè)平方根，要尋找的明文就是四個(gè)解的其中之一。Rabin算法描述（續(xù)）

Rabin算法的加密函數(shù)不是單射，解密具有不確定性，合法用戶不能確切地知道到底哪一個(gè)解是真正的明文。

如果加密之前在明文消息中插入一些冗余信息，可以幫助收信者準(zhǔn)確的識(shí)別解密后的明文。Rabin算法描述（續(xù)）Rabin算法的解密過(guò)程是尋找C模

n

的平方根，這個(gè)問(wèn)題的難度等價(jià)于n的因子分解。盡管計(jì)算模為素?cái)?shù)的平方根是多項(xiàng)式時(shí)間可解的，但其過(guò)程仍然很復(fù)雜。要求p與q是模4同余3的限制條件是為了使解密的計(jì)算和分析變的更容易R(shí)abin算法的特例取b=0時(shí)：可看成加密指數(shù)e=2的RSA算法。

加密變換：

解密變換：例5.4

假設(shè)模數(shù)，對(duì)明文加密，則密文為：

解密時(shí)：

1）計(jì)算227模19和模23的平方根；

（續(xù)）由于19和23都是模4同余3的，則可得：

277模19的平方根：

277模23的平方根：（續(xù)）

2）解下面同于方程組：

分別是因此，原始明文是這四個(gè)解之一。5.4.3Rabin算法的修正

Rabin算法具有解密不確定性的缺陷

Williams方案：

取兩個(gè)不同的滿足的大素?cái)?shù)p和q，以為模數(shù)。

取一個(gè)小整數(shù)s,且s不是模n的平方剩余。

n和s為公鑰對(duì)外公布，保密的私鑰為：（續(xù)）

加密變換：

對(duì)于消息m，先確定參數(shù)；

m是模n的平方剩余，取0；

m不是模n的平方剩余，取1；計(jì)算：三元組為得到密文。

（續(xù)）

解密變換：

對(duì)于密文，根據(jù)計(jì)算出；的符號(hào)由確定：

時(shí)，取負(fù)；

時(shí)，取正；故，明文為：例5.5消息為m=19時(shí)，不是模21的平方剩余，取于是：故，加密所得到的密文為（16,1,1）。（續(xù)）

解密時(shí)：

計(jì)算：于是

解密唯一（續(xù)）Rabin算法對(duì)選擇明文攻擊是安全的，但已經(jīng)證明它確實(shí)不能抵抗選擇密文攻擊。此外，針對(duì)RSA算法的一些攻擊方法對(duì)Rabin算法也有效。5.5

ElGamal算法

ElGamal密碼體制也是一種具有廣泛應(yīng)用的公鑰密碼體制，它的安全性基于有限域上計(jì)算離散對(duì)數(shù)問(wèn)題的困難性。離散對(duì)數(shù)問(wèn)題離散對(duì)數(shù)問(wèn)題（續(xù)）設(shè)a是素?cái)?shù)p的本原根，那么

在模p下互不相同且正好產(chǎn)生1到

的所有值。對(duì)于

,一定存在唯一的

，滿足

。

稱x為模p下以a為底b的離散對(duì)數(shù)，并記為

離散對(duì)數(shù)問(wèn)題(續(xù))

如果已知a，p和x，那么使用快速指數(shù)算法可以輕易地算出b；如果僅知a，p和b，特別是當(dāng)p的取值特別大時(shí)，要想求出x是非常困難的。為了使基于離散對(duì)數(shù)問(wèn)題的公鑰密碼算法具有足夠的密碼強(qiáng)度，一般要求模數(shù)p的長(zhǎng)度在150位以上。5.5.2ElGamal算法的描述5.5.2ElGamal算法的描述

加密變換：

對(duì)于消息m，秘密選取一個(gè)隨機(jī)數(shù)計(jì)算：和并構(gòu)成密文，即密文為因此，密文的長(zhǎng)度是明文的兩倍。

（續(xù)）解密變換：

由加密變換可知：解密結(jié)果是正確的。

例5.6設(shè)p=2579，取模p

,乘法群的生成元g=2，私鑰x=765。計(jì)算：若明文消息m=1299，選擇隨機(jī)數(shù)k=853,則可計(jì)算密文為：（續(xù)）對(duì)密文進(jìn)行解密變換可計(jì)算出明文m：

由于密文不僅取決于明文，還依賴于加密者每次選擇的隨機(jī)數(shù)k，因此ElGamal公鑰體制是非確定性的。

同一明文多次加密得到的密文可能不同；

同一明文最多會(huì)有多達(dá)

p-1個(gè)不同的密文；ElGamal算法的描述（續(xù)）（續(xù)）（續(xù)）加密變換：對(duì)于明文分組m，隨機(jī)選取，計(jì)算密文：其中，，。解密變換：

ElGamal算法的安全性有學(xué)者曾提出模p生成的離散對(duì)數(shù)密碼可能存在陷門，一些“弱”素?cái)?shù)p下的離散對(duì)數(shù)較容易求解。

仔細(xì)地選擇p，且g應(yīng)是模p的本原根；

p應(yīng)該至少是300位的十進(jìn)制整數(shù)；

p-1應(yīng)該至少有一個(gè)較大的素?cái)?shù)因子；一般認(rèn)為這類問(wèn)題是困難的，而且目前尚未發(fā)現(xiàn)有效地解決該問(wèn)題的多項(xiàng)式時(shí)間算法。（續(xù)）加密的不確定性：

ElGamal體制的一個(gè)顯著特征是在加密過(guò)程中引入了隨機(jī)數(shù)。相同的明文可能產(chǎn)生不同的密文，能夠給密碼分析者制造更大的困難。算法體制自身泄露信息：（續(xù)）（續(xù)）當(dāng)一個(gè)明文消息不屬于由g生成的子群的時(shí)候，ElGamal密碼體制就成為一種確定性的體制。由于確定性加密體制允許使用多次“嘗試”的方法來(lái)尋找小的明文消息，因此泄露了部分信息。所以，在應(yīng)用ElGamal公鑰體制，特別是推廣的ElGamal體制的時(shí)候一定要注意生成元g的選擇，確保每一個(gè)可能的明文消息都是由g生成的。5.6橢圓曲線密碼

橢圓曲線理論在公鑰密碼領(lǐng)域有著重要的應(yīng)用，以橢圓曲線上的點(diǎn)為元素定義的Abel群是構(gòu)造多種公鑰密碼體制的基礎(chǔ)。優(yōu)點(diǎn)：

—較短的密鑰獲得同樣的密碼強(qiáng)度現(xiàn)狀：已成為近年來(lái)一個(gè)非常有吸引力的研究領(lǐng)域，特別是在移動(dòng)通信安全方面。橢圓曲線密碼體制已被IEEE公鑰密碼標(biāo)準(zhǔn)P1363采用。5.6.1橢圓曲線的定義及性質(zhì)

Weierstrass方程：

通常所說(shuō)的橢圓曲線是指由Weierstrass方程所確定的平面曲線，其中a,b,c,d,e取自某個(gè)域F并滿足一些簡(jiǎn)單條件。橢圓曲線通常用字母E表示，滿足曲線方程的序偶（x,y）就是域F上的橢圓曲線E上的點(diǎn)。

可以是數(shù)域，也可以是某個(gè)有限域。除了滿足曲線方程的所有點(diǎn)（x,y）之外，還包括一個(gè)特殊點(diǎn)O，稱為無(wú)窮點(diǎn)。橢圓曲線的圖形并非橢圓，只是因?yàn)樗那€方程與計(jì)算橢圓周長(zhǎng)的方程類似，而將其叫做橢圓曲線。Weierstrass方程

上面的Weierstrass方程用代替，得到：其中，，，。因此，橢圓曲線關(guān)于x軸對(duì)稱。橢圓曲線的例子橢圓曲線的定義及性質(zhì)在橢圓曲線E上定義一個(gè)二元運(yùn)算，使其成為Abel群，通常稱這個(gè)運(yùn)算為加法，并用表示，其定義如下：（續(xù)）這是因?yàn)镻與

的連線延長(zhǎng)到無(wú)窮遠(yuǎn)時(shí)將經(jīng)過(guò)無(wú)窮遠(yuǎn)點(diǎn)O，所以P,和O三點(diǎn)共線，即

＝O，

，

。而橢圓曲線E是關(guān)于x軸對(duì)稱的，所以可以將－P定義為P點(diǎn)關(guān)于x軸的對(duì)稱點(diǎn)

此外還有，－O＝O。即是P與Q的連線L交橢圓曲線E上另一點(diǎn)R關(guān)于x軸的對(duì)稱點(diǎn)。因?yàn)?，所以R是唯一的。P(x1,y1)Q(x2,y2)-RR點(diǎn)P和Q不同時(shí)求解點(diǎn)R:(x3,-y3)(x3,y3)P(x1,y1)R-R點(diǎn)P和Q相同時(shí)求解點(diǎn)R:(x3,y3)(x3,-y3)在密碼學(xué)中使用的橢圓曲線通常定義在有限域上，也就是說(shuō)橢圓曲線方程中的所有系數(shù)都取自某個(gè)有限域

。其中，最常用的是由有限域

（p為素?cái)?shù)）上的同余方程

，且滿足確定的橢圓曲線。由此同余方程的所有解

，再加上一個(gè)特殊的無(wú)窮遠(yuǎn)點(diǎn)O，在上述加法運(yùn)算下構(gòu)造的Abel群。用

來(lái)表示這樣得到的Abel群。（續(xù)）在實(shí)數(shù)域中是保證方程

存在三個(gè)不同解（對(duì)于給定的y）的充分必要條件。否則，方程的三個(gè)解中至少有兩個(gè)相同，并稱這樣的橢圓曲線為奇異橢圓曲線。（續(xù)）

假設(shè)和是橢圓曲線上的點(diǎn)；

※

如果P和Q關(guān)于x軸對(duì)稱：

※

否則：則根據(jù)橢圓曲線的方程和P、Q連線的方程可以計(jì)算出R點(diǎn)的坐標(biāo)(x3,y3)如下：(續(xù))實(shí)際上，Zp上的橢圓曲線只是一些不連續(xù)的點(diǎn)，并不像實(shí)數(shù)域上橢圓曲線有直觀的幾何解釋，但同樣定義的加法運(yùn)算能夠保證

仍然是一個(gè)Abel群。其中：例5.7

給定上的一條橢圓曲線，按下述步驟可計(jì)算出中的所有點(diǎn)（無(wú)窮遠(yuǎn)點(diǎn)除外）對(duì)每個(gè)，計(jì)算出同余式的值a。利用Euler準(zhǔn)則判定上一步算出的每一個(gè)值a是否是模11的平方剩余。計(jì)算出每一個(gè)平方剩余的平方根。由命題5.4.1可知，本例中是計(jì)算。Euler準(zhǔn)則：

計(jì)算結(jié)果：是否為平方剩余06否18否25是4，7（2,4）（2,7）33是5，6（3,5）（3,6）48否54是2，9（5,2）（5,9）68否74是2，9（7,2）（7,9）89是3，8（8,3）（8,8）97否104是2，9（10,2）（10,9）（續(xù)）選取為生成元，我們來(lái)計(jì)算g的冪。注意這里的運(yùn)算是群上的加法，所以群里的冪就是倍乘，即。（續(xù)）

1）先計(jì)算，這里圖示（續(xù)）所以有：因此，。（續(xù)）

2）計(jì)算，這里，所以有：因此，。圖示（續(xù)）

依次可計(jì)算出生成元g的所有冪，結(jié)果如下：可以看