2.3 公鑰密碼算法

對稱密碼算法在密鑰分配方面面臨著管理和分發(fā)的困難，而且對稱加密算法無法實現(xiàn)抗抵賴的要求，公鑰密碼算法的出現(xiàn)解決了這一難題。1976年，Diffie和Hellman首次提出了公開密鑰加密算法，在密碼學(xué)的發(fā)展史上具有里程碑式的意義。之后，Rivest、Shamire和Adleman提出了第一個比較完善的公鑰密碼算法，即著名的RSA算法。

公鑰密碼算法提出了“公私密鑰對”的概念，這一對“互補”的密鑰能夠提供身份認證和抗否認等安全保障，并且使得安全的密鑰交換成為可能。目前，已經(jīng)出現(xiàn)的多數(shù)非對稱密碼算法所依賴的數(shù)學(xué)難題大致有：大整數(shù)因式分解、離散對數(shù)、多項式求根、背包問題、二次剩余問題和模n的平方根問題等。這里所說的數(shù)學(xué)難題指的是不存在一個計算該問題的有效方法，或者說在目前和以后足夠長的時間里，計算該問題都是不可行的，要花很長的時間，這就大大增加了密碼破譯的成本。

常見的公鑰密碼算法有：RSA、ElGamal公鑰密碼算法、橢圓曲線公鑰密鑰算法（ECC）、NTRU公鑰加密算法和Rabin公鑰加密算法等。一些算法如著名的背包算法等都已經(jīng)被破譯，比較安全的公開密鑰算法主要有：RSA及其變種Rabin算法，以及基于離散對數(shù)難題的ElGamal算法和橢圓曲線算法。

2.3.1 公鑰密碼基本概念

在對稱密碼算法中，解密密鑰與加密密鑰相同或者由加密密鑰可以推導(dǎo)出解密密鑰，但在公鑰密碼算法中，解密密鑰和加密密鑰是不同的。這不僅僅體現(xiàn)在形式上，還體現(xiàn)在從其中的一個難以推導(dǎo)出另外一個，這就從根本上決定了公鑰密碼算法的加密密鑰與解密密鑰是可以分離的。公鑰密碼算法解決了密鑰的管理和分發(fā)問題，每個用戶都可以公開自己的公鑰，并由用戶自己保存私鑰，不被他人獲取。

公開密鑰算法與對稱加密算法顯著的不同是用一個密鑰進行加密，而用另一個不同但是相關(guān)的密鑰進行解密。

A加密：X-＞Y，Y=E（PuB（X））　A用B的公鑰PuB對明文X進行加密得到Y

B解密：Y-＞X，X=D（PrB（Y））　B用自己的私鑰PrB對密文Y進行解密獲得X

上式中，X表示明文，Y表示加密后的密文，E表示加密，D表示解密。PuB是B的公鑰，該密鑰是公開的，A使用此密鑰加密數(shù)據(jù)傳給B；P rB是B的私鑰，由B保存且不能被外人所知，B使用此密鑰解密A用P uB加密過的數(shù)據(jù)。P uB和P rB是相互關(guān)聯(lián)的，而且是成對出現(xiàn)的。

公鑰密碼算法的另一個特性是，僅僅知道密碼算法和加密密鑰而想確定解密密鑰，在計算上是不可能的。顯然，PuB和PrB雖然相關(guān)，但是由PuB不能推導(dǎo)出PrB，否則將無安全性可言。

公鑰密碼算法大多數(shù)都是基于困難問題的。正如把盤子打碎成數(shù)千個碎片很容易，但是把所有這些碎片再拼成一個完整的盤子就很難了。類似地，將許多大素數(shù)相乘比將其乘積的結(jié)果進行因式分解要容易得多。

2.3.2 RSA密碼算法

在實際中，求一對大素數(shù)的乘積很容易，但要對這個乘積進行因式分解則非常困難，因此，可以把一對大素數(shù)的乘積公開作為公鑰，而把素數(shù)作為私鑰，從而把使用公鑰將密文恢復(fù)成明文的難度等價于分解兩個大素數(shù)之積。

還有基于RSA算法建立的簽名算法，由于計算能力的不斷提高，RSA的密鑰長度也在不斷提升，從512增加到1024、2048、4096。

RSA算法的密鑰產(chǎn)生和加解密過程如下所述。其中，m表示明文，c和s表示密文。

1.密鑰的產(chǎn)生過程

1）獨立選取兩個大素數(shù)p和q（各為100～200位十進制數(shù)字，根據(jù)需要的密鑰長度進行選擇）。

2）計算n=p?q，其歐拉函數(shù)值?（n）=（p-1）（q-1）。

3）隨機選取一個整數(shù)e，滿足1≤e＜?（n），并使最大公約數(shù)gcd（?（n），e）=1。

4）在模?（n）下，計算e的逆：d=e^-1 mod（p-1）（q-1）。

5）以n，e為公鑰，d為私鑰（p，q不再需要，可以銷毀）。

2. RSA算法用于加密和解密

1）加密過程：c=m^emodn。

2）解密過程：m=c^dmodn。

3. RSA算法用于數(shù)字簽名和驗證

1）簽名過程：s=m^dmodn。

2）驗證過程：m=s^emodn。

RSA算法的安全性是基于大整數(shù)分解的困難性假定。如果能分解n=p?q，就可以立即獲得?（n）=（p-1）（q-1），從而計算得到d。

2.3.3 橢圓曲線密碼算法

橢圓曲線密碼算法是另外一類重要的公鑰密碼算法，它是基于橢圓曲線上的離散對數(shù)問題。我們首先對橢圓曲線的概念及橢圓曲線中的運算做簡要介紹。

1.橢圓曲線概念

所謂橢圓曲線是指由韋爾斯特拉（Weierstrass）方程

E：y²+axy+by=x³+cx²+dx+e

所確定的曲線，其中的參數(shù)a，b，c，d，e以及變量x和y都屬于F，F是一個域，可以是有理數(shù)域、復(fù)數(shù)域或是有限域GF（p），橢圓曲線是其上所有點（x，y）的集合，再加上一個無限遠點。這個無限遠點是橢圓曲線的一個特殊點，記為O，也稱為無窮遠點，它并不在橢圓曲線E上，如圖2-19所示。

對橢圓曲線上的加法運算定義：設(shè)P和Q兩點是橢圓曲線上的兩點，通過這兩點的直線與曲線交于第三點R，該點的x軸對稱點R′即為P和Q之和，圖2-20a可以清楚地說明該過程；當(dāng)P=Q時，則通過這點作曲線的一條切線，這條切線與曲線的交叉點R的x軸對稱點R′則為P和Q之和，如圖2-20b所示。

橢圓曲線的加法運算特性歸納如下。

1）封閉性：兩點相加的結(jié)果是曲線上的另一點。

2）結(jié)合性：（P+Q）+R=P+（Q+R）。

3）交換性：P+Q=Q+P。

4）單位元素：存在加法單位元素O，使得P=P+O=O+P。

5）存在逆元素：曲線上每一點都有逆元素，其逆元素對稱于x軸，單位元素為其本身的逆元素。

在密碼學(xué)中，普遍使用有限域上的橢圓曲線，即在前面的橢圓曲線方程中，所有的系數(shù)都屬于某個有限域GF（p）中的元素，最常用的方程為

E：y²=x³+ax+b（modp）

其中，p是一個大于3的素數(shù)，參數(shù)a，b以及變量x和y都屬于有限域GF（p），即從{0，1，…，p-1} 中取值，且4a³+27b²（modp）≠0。該橢圓曲線包括有限個點數(shù)N（稱為橢圓曲線的階，包括無窮遠點Ω），N越大，安全性越高。

定理2.3.1 橢圓曲線上的點集對于如下定義的加法規(guī)則構(gòu)成一個阿貝爾（Abel）群。此加法運算的定義如下。

設(shè)P（x₁，y₁），Q（x₂，y₂）∈E，若x₂=x₁，y₂=-y₁，則P+Q=O；否則，P+Q=（x₃，y₃），其中

x₃=aλ²-x₁-x₂ ，y₃=λ（x₁-x₃ ）-y₁

且

此外，對于所有的P∈E有

P+O=O+P=P

在這樣一個阿貝爾群中，P的逆元為（x₁，-y₁），寫作-P。這個阿貝爾群記作E_p（a，b）。

橢圓曲線密碼算法的重點在于一個點P及其在這個阿貝爾群上的k倍（即kP）之間的關(guān)系。為了直觀地表現(xiàn)出這種關(guān)系，借用實數(shù)域上的圖形來對此加以解釋。

圖2-20b所示，2P所在的點為R，即經(jīng)過P作一條切線，該切線與橢圓曲線相交的點沿x軸對稱的那一點即為2P所在的位置。那么3P則為R+P，即連接P和R與曲線的交點關(guān)于x軸的對稱點，依此類推可以得出kP。

橢圓曲線密碼算法的安全性基于如下的問題。

對于給定的兩個點P和Q，它們存在如下關(guān)系。

P=kQ

一個外人在擁有點P和Q的坐標的情況下，計算k值是困難的，這一問題被稱為橢圓曲線離散對數(shù)問題（ECDLP）。ECDLP可以用窮盡查找法來求解，即已知條件點P和Q，將P不斷自加，直至到達Q點。如果k值很大，解決這一問題就十分困難了。

在ECDLP的基礎(chǔ)上，如何對明文、密文及密鑰進行處理以使它們構(gòu)成一個在模P上的加密系統(tǒng)的方法有多種，不同的方法可以構(gòu)成不同的加密算法。下面給出其中的一種算法。

2.橢圓曲線密碼算法

基于前面所定義的阿貝爾群，現(xiàn)在只給出一種橢圓曲線密碼算法的描述，這里不對其有效性進行詳細證明。

假設(shè)發(fā)送方為A，接收方為B，A需要將消息加密后傳送給B。那么，首先需要考慮如何用橢圓曲線來生成B的公私密鑰對，可以分為以下3步。

（1）構(gòu)造橢圓群

設(shè)E：y²=x³+ax+b（modp）是GF（p）上的一個橢圓曲線（p＞3），首先構(gòu)造一個群E_p（a，b）。

（2）挑選生成元點

挑選E_p（a，b）中的一個生成元點G=（x₀，y₀），G應(yīng)滿足使nG=O成立的最小的n是一個大素數(shù)。

（3）選擇公私密鑰

選擇整數(shù)k_B（k＜n）作為私鑰，然后產(chǎn)生其公鑰P_B=k_BG，則B的公鑰為（E，n，G，P_B），私鑰為k_B。

下面介紹如何利用公私密鑰對進行加解密的運算（以下的運算都是在modp下進行的）。

（1）加密過程

1）發(fā)送方A將明文消息編碼成一個數(shù)m＜p，并在橢圓群E_p（a，b）中選擇一點P_t=（x_t，y_t）。

2）發(fā)送方A計算密文：C=mx_t+y_t。

3）發(fā)送方A選取一個保密的隨機數(shù)r（0＜r＜n），并計算rG。

4）依據(jù)接收方B的公鑰P_B，計算P_t+rP_B。

5）發(fā)送方A對m進行加密，得到數(shù)據(jù)C_m={rG，P_t+rP_B，C}。

（2）解密過程

接收方B在收到A發(fā)來的加密數(shù)C_m={rG，P_t+rP_B，C}之后，進行如下操作。

1）使用自己的私鑰k_B計算

P_t+rP_B-k_B（rG）=P_t+r（k_BG）-k_B（rG）=P_t

2）接收方B計算：m=（C-y_t）/x_t，得到明文m。

從上面的描述可以看出，如果攻擊者想從密文C得到明文m，就必須知道r或k_B，但是，已知rG或P_B求得r或k_B，都必須去解決橢圓曲線上的離散對數(shù)問題。因此，在現(xiàn)有的計算條件下，橢圓曲線密碼算法是安全的。與其他算法相比較，橢圓曲線密碼具有兩個優(yōu)點：一是算法的密鑰長度短，對于帶寬和存儲的要求比較低，運算效率高，適合在智能卡等計算與存儲資源都有限的硬件設(shè)備上使用；二是所有用戶可以選擇使用同一基域F上的不同曲線E，從而可以讓所有用戶使用相同的硬件來完成域算術(shù)。

3.橢圓曲線密碼算法的安全性

相對于基于有限域乘法群上的離散對數(shù)問題的密碼算法，橢圓曲線密碼算法的安全性是基于橢圓曲線上的離散對數(shù)問題，目前這一方法還沒有發(fā)現(xiàn)明顯的弱點，但也有一些這方面的研究思路，如利用一般曲線離散對數(shù)的攻擊方法以及針對特殊曲線的攻擊方法等。

為了保證橢圓曲線密碼算法的安全性，就需要選取安全的橢圓曲線。用于建立密碼算法的橢圓曲線的主要參數(shù)有p、a、b、G、n和h，其中p是域的大小，取值為素數(shù)或2的冪；a、b是方程的系數(shù)，取值于GF（p）；G為生成元點；n為點G的階；還定義了參數(shù)h為橢圓曲線上所有點的個數(shù)N除以n所得的結(jié)果。為了較好地建立一個橢圓曲線算法，需要大致滿足如下幾個條件。

1）p的取值應(yīng)盡可能大，但數(shù)值越大，計算時所消耗的時間也越多，為滿足目前的安全要求，p的位數(shù)可為160位。

2）n為大素數(shù)，并且應(yīng)盡可能大。

3）4a³+27b²≠0（modp）。

4）為保證n的取值足夠大，需滿足h≤4。

5）不能選取超奇異橢圓曲線和異常橢圓曲線這兩類特殊的橢圓曲線。

由于橢圓曲線的離散對數(shù)問題被公認為比整數(shù)的因式分解以及有限域的離散對數(shù)問題還要困難得多。因此，對于它的密鑰長度的要求可以大大降低，這也是該算法能夠高效運行的一個原因。通常而言，160位的橢圓曲線密鑰的安全強度就能達到1024位RSA算法的安全強度，這也使其成為目前已知的公鑰密碼算法中安全強度最高的算法之一。

2.3.4 NTRU公鑰密碼

傳統(tǒng)公鑰算法在無線通信安全領(lǐng)域的使用還不是很廣泛，主要原因是移動終端上的計算和存儲資源的限制，使得這些算法在移動終端上的運行速度難以滿足某些應(yīng)用的要求。因此，對快速公鑰系統(tǒng)的研究是當(dāng)前公鑰系統(tǒng)研究的一個熱點。

1. NTRU概述

NTRU（Number Theory Research Unit）是一種基于多項式環(huán)的加密系統(tǒng)，其加解密過程是基于環(huán)上多項式代數(shù)運算和對數(shù)p及q的模約化運算，只使用了簡單的模乘法和模求逆運算，因此它的加解密速度快，密鑰生成速度也快，而且NTRU是迄今為止唯一的增加格的維數(shù)而不損害其實用性的格密碼算法。它很好地解決了公鑰密碼算法的最大瓶頸——速度問題，使其適用于安全性要求、體積、成本、內(nèi)存及計算能力等受限的電子設(shè)備。近年來，NTRU算法引起了許多密碼學(xué)家的討論，它是目前為止已知的速度最快的公鑰密碼算法之一。

NTRU是1995年由J. Hoffstein、J. Pipher和J. Silverman發(fā)明的一種密碼算法。在數(shù)學(xué)上，NTRU比RSA和ElGamal密碼還要復(fù)雜。由于它的復(fù)雜性和出現(xiàn)的時間相對較短，國內(nèi)外密碼學(xué)界針對NTRU的安全性研究仍在繼續(xù)。NTRU也存在一些缺點，比如它雖然能夠?qū)崿F(xiàn)概率加密卻存在解密失敗的問題，雖然人們對它進行了改進，然而這也大大損傷了該算法的簡潔性。另外，與RSA和ECC算法相比，NTRU算法需要更大的帶寬和更大的密鑰空間。例如，對應(yīng)于公鑰長度為1024位的RSA算法，NTRU的公鑰長度是RSA的兩倍。但是，這種差異會隨著安全級別的增大而降低。

雖然密碼學(xué)界對NTRU進行了各種各樣的攻擊，但是這些都沒有對它造成致命的威脅。據(jù)密碼學(xué)家表示，只有當(dāng)量子計算機得到應(yīng)用時，NTRU密碼算法才有可能被破解，而那時RSA和普通的ElGamal密碼已經(jīng)被破解了。

2. NTRU的理論基礎(chǔ)

Diffie和Hellman提出應(yīng)利用計算的復(fù)雜性來設(shè)計加密算法，并指出可利用格理論以及NP C問題構(gòu)造密碼系統(tǒng)。此后的各種公鑰系統(tǒng)設(shè)計均遵循這一原則，而NTRU算法正是基于格理論在密碼學(xué)上的重要應(yīng)用。

格在不同的領(lǐng)域有不同的定義。在代數(shù)系統(tǒng)中，格通常定義為：設(shè)＜L，≤＞是一個偏序集，如果對任意a，b∈L，{a，b}都有最大下界和最小上界存在，則稱＜L，≤＞是格，這時＜L，≤＞可簡寫成L。

而NTRU系統(tǒng)中所涉及的格的概念不同于上述的代數(shù)格，而是一個定義在n維歐式空間上的離散子群。設(shè)R^m是一個m維的歐式空間，則R^m（m≥n）是由n個線性無關(guān)的向量a₁，a₂，…，a_m的所有整數(shù)線性組合的集合。

L（a₁，a₂，…，a_m）={∑x_ia_i：x_i∈Z}構(gòu)成了R^m的一個格。B=（a₁，a₂，…，a_m）稱為格L的一組基，維數(shù)為m，秩為n。若m=n則稱格L（a₁，a₂，…，a_m）是滿維的。

簡單來說，NTRU是基于高維格中尋找一個短向量的困難問題（SVP），即給定一個多項式h（x）=F_q?g（x）（modq），其中F_q是多項式f（x）在模q時的逆元，f（x）和g（x）的系數(shù)相對于q來說是小的，在適當(dāng)參數(shù)設(shè)置下，如果僅知道h（x），恢復(fù)出多項式f（x）或g（x）是困難的。

3. NTRU算法描述

NTRU密碼算法的工作過程如下。

（1）密鑰生成

在NTRU公鑰密碼算法中，接收方需要生成一組公/私密鑰對。具體步驟如下：

1）選擇公開參數(shù)。選擇正整數(shù)參數(shù)N、p、q，其中p、q不必為素數(shù)，但是它們必須互素，且滿足gcd（N，pq）=1。

2）選擇多項式f（x）和g（x）。由接收方選擇兩個小系數(shù)多項式f（x）和g（x），其中模q的隨機多項式的系數(shù)一般隨機地分布在區(qū)間[0，q]上，而所謂的小系數(shù)多項式的系數(shù)相對于模q的隨機多項式要小得多。接收方需要對多項式f（x）和g（x）保密，因為任何一個多項式信息泄露都可能導(dǎo)致密文被破解。

3）計算逆元F_p（x）和F_q（x）。接收方計算多項式f（x）在模p和模q時的逆元F_p（x）和F_q（x），即F_p（x）?f（x）=1（modp，modx^N-1）和F_q（x）?f（x）=1（modq，modx^N-1）。如果f（x）的逆元不存在，接收方需要重新選取f（x）。

4）計算公鑰。計算h（x）=F_q（x）?g（x）（modq，modx^N-1），多項式f（x）和F_p（x）為私鑰，h（x）為公鑰。

（2）加密過程

假設(shè)發(fā)送者發(fā)送一條明文消息m（x）給接收者，m（x）是次數(shù)為N-1的多項式，具有模p約簡的系數(shù)（可以理解為系數(shù)的范圍在（-p/2，p/2）內(nèi)）。發(fā)送方隨機選擇一個次數(shù)為N-1的多項式r（x）進行計算得到

c（x）=pr（x）?h（x）+m（x）（modq，modx^N-1）

然后將其發(fā)送給接收方。

（3）解密過程

假設(shè)接收者收到加密消息c，首先計算多項式a（x）

a（x）=f（x）?c（x）（modq，modx^N-1）

接著計算

d（c）=F_p（x）?a（x）（modp，modx^N-1）

d（c）就是解密后的明文。

（4）說明

這里的加法+，是通常的多項式加法。這里的乘法?，是比較特殊的乘法。設(shè)R為關(guān)于x的多項式的集合，具有整數(shù)系數(shù)和嚴格比N小的次數(shù)，乘法?表示

xⁱ?x^j=x^{i+j（modN）}

也就是

該乘法依然滿足交換律、結(jié)合律和分配律。此外，算法還會涉及模p約簡和模q約簡運算，這是指分別對多項式的系數(shù)做模p或q的約簡。可以寫作

f（x）（modp）=系數(shù)經(jīng)過模p約簡的多項式f（x）

f（x）（modq）=系數(shù)經(jīng)過模q約簡的多項式f（x）

（5）解密原理

因為a（x）=f（x）?c（x）（modq，modx^N-1）

=f（x）?（pr（x）?h（x）+m（x））（modq，modx^N-1）

=f（x）?（pr（x）?F_q（x）?g（x）+m（x））（modq，modx^N-1）

=f（x）?pr（x）?F_q（x）?g（x）+f（x）?m（x））（modq，modx^N-1）

=f（x）?F_q（x）?pr（x）?g（x）+f（x）?m（x））（modq，modx^N-1）

=1?pr（x）?g（x）+f（x）?m（x））（modq，modx^N-1）

=pr（x）?g（x）+f（x）?m（x））（modq，modx^N-1）

考慮到多項式pr（x）?g（x）+f（x）?m（x），只要參數(shù)選取適當(dāng)，幾乎可以確保多項式pr（x）?g（x）+f（x）?m（x）每一項的系數(shù)都在（-q/2，q/2）區(qū)間上，即

a（x）=pr（x）?g（x）+f（x）?m（x）（modx^N-1）

將a（x）再modp得到

a（x）=f（x）?m（x）（modp，modx^N-1）

則解密操作后可以得到

d（c）=F_p（x）?a（x）（modp，modx^N-1）

=F_p（x）?f（x）?m（x）（modp，modx^N-1）

=1?m（x）（modp，modx^N-1）

=m（x）