3.3　非對稱密鑰加密

加密用哪個密鑰、解密也必須用哪個，似乎就像鎖定保險箱用這把鑰匙、打開保險箱就一定用這把那樣必然。然而這種“自然而然”的狀況在1976年被Diffie和Hellman打破了，他們在《密碼學新方向》一文中提出的技術顛覆了“一把鑰匙開一把鎖”的思維定式，開創了密碼學的新領域。

3.3.1　非對稱密鑰加密技術原理

非對稱密鑰加密（asymmetric key cryptography）也稱公開密鑰加密（public key cryptography）或公鑰加密、雙密鑰加密，其方法是使用一對密鑰來加密和解密，其中一個是只有密鑰擁有者自己掌握的、保密的私鑰（private key），另一個是通信過程中由其他方使用的、可以公開的公鑰（public key）。

公鑰體制的優越性在于分離出兩個相關的密鑰，其中的公鑰不需要保密，而私鑰絕對不在網絡上傳輸，因此就不存在密鑰泄露問題。公鑰和私鑰的使用規則為：

?　用公鑰加密的數據用且只能用對應的私鑰解密。

?　用私鑰加密的數據用且只能用對應的公鑰解密。

假設Alice有一對密鑰priKeyA和pubKeyA，Bob有priKeyB和pubKeyB，他們需要在網絡上傳輸信息。利用非對稱密鑰加密技術，Alice和Bob有三種可選方法，如圖3.14（a）、（b）和（c）所示，獲得的效果完全不同。

（1）Alice用自己的私鑰priKeyA加密，可以確保信息是由其發出的，其他人沒有其私鑰就無法假冒，同時Alice也不能否認其發送的信息，該過程具有確權性；但用于解密的Alice的公鑰pubKeyA是公開的，說明除了Bob以外的其他人也能獲得公鑰并能夠解密，因此方法（a）不具有保密性。

（2）Alice用Bob的公鑰pubKeyB加密，使得只有握有私鑰priKeyB的Bob才能解密，其他人則無法輕易解密，達到了保密的效果；但由于Bob的公鑰是公開的，任何人都能進行加密發送，并不能指證該密文是Alice加密發出的，因此方法（b）不具有確權性。

（3）方法（a）和（b）從安全效果上基本上是“互補”的關系，方法（c）就是對兩種方法的綜合，既能確認發送者，又能保護信息的私密性。

對于公鑰加密的幾種方法，擅于找破綻的Bob還有話要說：“追根溯源，不管哪種方法，首先要把自己的公鑰傳播出去，這是一切操作的基礎對不對？”

“是的。”Alice不知道Bob的葫蘆里賣的什么藥。

“假如有個‘中間人’攻擊者攔截了你我發出的公鑰，分別替換為他自己構造的密鑰，會發生什么呢？”

“在方法（a）中我發送的信息你會拒絕認可，反而認可攻擊者假冒我的身份發出的信息。”Alice越說越心驚，“方法（b）中攻擊者可以解密我發給你的保密信息，然后可以篡改后再‘加密’發送給你。”

Alice和Bob探討的就是公鑰的安全發布問題，是公鑰體系安全運行的前提條件。公鑰不僅可以公開，而且是越公開越好，假如讓自己的公鑰變成“眾所周知”，那么“中間人攻擊”就沒有空子可鉆了。實際的網絡系統中應建立嚴密、可靠的公鑰傳播機制，才能讓需要者獲取到真實可信的公鑰。

公鑰加密的重要作用是信息驗證。如圖3.15所示，Bob想公開自己的電子郵件地址，但又不希望被人惡意篡改，于是將名片信息用私鑰加密后與名片一并發布，其他打算聯絡Bob卻將信將疑的人就可以用Bob的公鑰來驗證，以確認這條信息真的是Bob發出的以及電子郵件地址真的屬于Bob。

公鑰加密的計算效率通常很低，甚至只有對稱密鑰加密方法的千分之一，因此不適合對大量的數據進行加密，一般用來加密會話密鑰等短小數據。

常用的公鑰加密算法有RSA、ElGamal等，目前技術含量最高、安全性最強的是ECC算法，該算法在比特幣系統中得到充分運用，實現了虛擬貨幣資產的匿名持有和支付驗證。

3.3.2　RSA算法

RSA算法于1977年被提出，以三位發明者Ron Rivest、Adi Shamir和Leonard Adleman姓氏的首字母來命名，是最早也是最著名的公開密鑰加密算法，應用相當廣泛。RSA算法的數學基礎是數論中的歐拉（Euler）定理，安全性建立在大整數分解質數（素數）因子的困難性之上。

RSA算法公鑰、私鑰密鑰對的生成步驟如下：

（1）選擇不同的大質數p和q，計算n=p×q和φ（n）=（p-1）×（q-1）。

（2）選擇大整數e，與φ（n）互質，且1＜e＜φ（n）。

（3）計算整數d，使d×e=1 modφ（n）。

（4）舍棄p和q，得：公鑰pubKey={e，n}，私鑰priKey={d，n}。

考查私鑰的安全性：雖然攻擊者可以從公開的公鑰得到e和n，但以現有的數學理論成果，要分解一個整數為兩個質數因子一般只能采用窮舉法，而整數非常大時，計算機除法運算十分耗時，很難在有限時間內完成。1991年RSA實驗室曾發起因子分解挑戰賽，公布了54個十進制位數為100~617位的大整數，不論誰無論用何種方法，分解出一個即得重獎。結果在20年時間里，只有最小的18個數（二進制768位長度以下）被成功分解，可見其困難程度。雖然近年來陸續有一些數學研究成果，可以在一定程度上擺脫暴力試除，但二進制1024位乃至2048位以上大整數仍然保持相當高的安全性。既然攻擊者難以分解大數n以獲取至關重要的p和q，就無法獲得d，因此私鑰是安全的。

RSA密鑰生成算法中，e與φ（n）互質的意思是兩個數的最大公因數（Greatest Common Divisor，GCD）為1。可以運用輾轉相除法，又名歐幾里得算法（Euclidean），在判別e是否與φ（n）互質時，不需要先把兩個數作質因數分解，即可直接求出最大公因數。

求解GCD的算法用代碼表示如下（不失一般性，設p＞q，遞歸函數返回值就是p和q的最大公因數）：

此外，私鑰中的d實際上是求e的modφ（n）乘法逆元，可使用擴展歐幾里得算法。設求解k^-1 mod n，算法extended_euclid（k，n）程序流程如下：

使用公鑰pubKey={e，n}的加密過程如下。對于明文M，若M＜n，將M作為一個大整數來計算，若M≥n，則進行分段計算：

C=M^e mod n

使用私鑰priKey={d，n}的解密過程如下：

M=C^d mod n

解密與加密為互逆的運算，可簡單證明如下（根據歐拉定理）：

M′=（M^e）^d mod n=M^e×d mod n=M¹ mod n=M

用私鑰加密、公鑰解密的計算公式同理可得。從計算方式來看，加密、解密都是指數運算，而且底和冪都是大整數，對計算機而言單次運算量很大，這正是公鑰加密方法不太適用于大量信息的原因。

實際應用中應選擇十進制100位以上的質數，n的長度至少要達到1024b。為了抵抗整數分解算法，對p和q另有如下要求：

（1）|p-q|很大，通常p和q的長度相近。

（2）p-1和q-1分別含有大素因子p₁和q₁。

（3）p₁-1和q₁-1分別含有大素因子p₂和q₂。

（4）p+1和q+1分別含有大素因子p₃和q₃。

3.3.3　ElGamal算法

ElGamal算法是一種公開密鑰加密技術，其安全性原理依賴于計算有限域上離散對數這一難題。ElGamal密鑰對的產生流程如下：

首先選擇一個質數p和兩個隨機數g和x（g，x＜p），計算：

y=g^x mod p

則公鑰為{y，g，p}，私鑰為x。其中g和p可由一組用戶共享。

ElGamal進行公鑰加密時，設明文為M，需選擇一個隨機數k，使k與（p-1）互質（可采用歐幾里得輾轉相除法），并計算：

a=g^k mod p

b=y^kM mod p

所得（a，b）即為密文，長度是明文的兩倍。用私鑰解密時計算：

求解時可采用擴展歐幾里得算法，先求a^x（mod p）乘法逆元，再與b相乘，以降低計算難度。

在運用ElGamal時，質數p必須足夠大，且p-1應至少包含一個大質數因子，并保證g對于p-1的大質數因子不可約。ElGamal的一個不足之處是其密文長度為明文的兩倍，增加了存儲空間和傳輸帶寬的占用。

3.3.4　ECC算法

橢圓曲線加密算法（Ellipse Curve Cryptography，ECC）是基于橢圓曲線理論的公鑰加密技術。在數學上，對橢圓曲線的性質和功能的研究已逾150年，但是在加密技術上的應用是在1985年由Neal Koblitz和Victor Miller首次提出。與其他建立在大質數因子分解困難性基礎上的加密方法不同，ECC利用橢圓曲線方程式的數學性質產生密鑰，正向計算比較容易，反過來卻非常困難。

與RSA方法相比，ECC可以使用164b密鑰產生一個安全級相當于RSA方法的1024b密鑰提供的保密強度，而且計算量較小、處理速度更快、存儲空間和傳輸帶寬占用較少，具有較大的技術優勢。

與一般加密方法采用的對數據進行函數運算的方式大相徑庭，橢圓曲線加密是有限離散域的、曲線上坐標點的轉換，其技術原理必須從抽象的射影平面開始去理解。

1. 射影平面

平面上的兩條直線只有相交、平行兩種情況。相交線只有一個交點，若有兩個交點則為重合；平行線沒有交點。

定義平行線相交于無窮遠點P_∞，如圖3.16所示，這樣，平面上任何兩條直線都統一為有唯一的交點。P_∞具有以下性質：

（1）一條直線只有一個無窮遠點，一對平行線有公共的無窮遠點（即交點）。

（2）任何兩條不平行的直線有不同的無窮遠點（否則會造成兩個交點）。

（3）平面上全體無窮遠點構成一條無窮遠直線。

平面上全體無窮遠點（無窮遠直線）與全體平常點構成射影平面（projective plane）。

對普通平面上點（x，y），令x=X/Z，y=Y/Z，Z≠0，則投影為射影平面上的點（X∶Y∶Z）。例如點（1，3）可投影為（Z∶3Z∶Z），即可為（1∶3∶1）、（2.3∶6.9∶2.3）等多種賦值。

對普通平面上的直線ax+by+c=0，作同理變換，得到對應于射影平面上的直線為aX+bY+cZ=0。

對平行線aX+bY+c₁Z=0和aX+bY+c₂Z=0，易解得Z=0，說明射影平面上平行線交點即無窮遠點P_∞的坐標為（X∶Y∶0）。

2. 橢圓曲線

一條橢圓曲線（ellipse curve）是在射影平面上滿足威爾斯特拉斯方程（Weierstrass）的所有點的集合。射影平面上統一的橢圓曲線方程為

Y²Z+a₁XYZ+a₃YZ²=X³+a₂X²Z+a₄XZ²+a₆Z³

橢圓曲線方程是一個齊次方程，且要求橢圓曲線上的每個點都必須是非奇異的（光滑的）、可導的，即方程的偏導數F_X（X，Y，Z）、F_Y（X，Y，Z）和F_Z（X，Y，Z）不能同時為0。

令Z=0，代入橢圓曲線方程得X=0，說明橢圓曲線上有一個無窮遠點O_∞，其坐標為（0∶Y∶0）。無窮遠點O_∞和普通平面上的平常點（即曲線）一起，共同組成射影平面上的橢圓曲線。

運用射影平面與普通平面的點的轉換關系，橢圓曲線方程可轉換為普通平面方程：

y²+a₁xy+a₃y=x³+a₂x²+a₄x+a₆

對橢圓曲線的平常點（x，y）求導，并計算過該點的切線的斜率k，有：

F_x（x，y）=a₁y-3x²-2a₂x-a₄

F_y（x，y）=2y+a₁x+a₃

橢圓曲線的形狀并非如其名呈橢圓狀，例如，方程Y²Z=X³+XZ²+Z³可轉換為普通方程y²=x³+x+1，曲線如圖3.17（a）所示；方程Y²Z=X³-XZ²可轉換為普通方程y²=x³-x，曲線如圖3.17（b）所示。

而且并非所有形式類似的方程都是橢圓曲線方程，例如，如圖3.18（a）和（b）所示的方程Y²Z=X³+X²和Y²Z=X³就不屬于橢圓曲線，因為0點為奇異點（不可導）。

3. 橢圓曲線加法

在橢圓曲線中引入阿貝爾（Abel）加法群（又稱交換群）的概念，可進一步實現對橢圓曲線上的點的運算。

任意取橢圓曲線上兩點P、Q（若P、Q兩點重合，則作P點的切線），過兩點作直線交于橢圓曲線的另一點R′，過R′做y軸的平行線交橢圓曲線于R，定義P+Q=R。可見，加法的和也在橢圓曲線上，并同樣遵循加法的交換律、結合律。

例如，圖3.17（b）所示的橢圓曲線方程為Y²Z=X³-XZ²，普通方程為y²=x³-x，加法運算過程如圖3.19所示，其中圖3.19（a）和圖3.19（b）分別為P、Q重合與不重合兩種情況。

如圖3.20（a）所示，橢圓曲線無窮遠點O_∞與橢圓曲線上一點P的連線交橢圓曲線于另一點P′，過P′作y軸的平行線必交橢圓曲線于P（兩條線重合），根據加法定義，有O_∞+P=P。可見，無窮遠點O_∞與普通加法中零相當，因此把O_∞稱為零元。同時易知P+P′=O_∞，于是P′被稱為P的負元，記作-P。如圖3.20（b）所示，還可推出：如果橢圓曲線上的3個點A、B、C處于同一直線上，則其和等于零元，即A+B+C=O_∞。

再進一步，如圖3.21所示，若有k個相同的點P相加，記作kP，有：

P+P+P=2P+P=3P

在圖3.19所示曲線上，若已知點P、Q的坐標分別為（x₁，y₁）、（x₂，y₂），令R=P+Q，設：-R（即R′）的坐標為（x₃，y₃），R的坐標為（x₄，y₄），顯然有x₃=x₄。

因為P、Q、-R三點共線，所以設共線方程為y=kx+b，分兩種情況：

（1）若P≠Q（P、Q兩點不重合），則直線斜率為：

（2）若P=Q（P、Q兩點重合），則直線為橢圓曲線的切線，代入斜率公式可得：

因此，P、Q、-R三點的坐標值（x₁，y₁）、（x₂，y₂）、（x₃，y₃）就是橢圓曲線統一方程與共線方程組成的方程組的解（即三個交點）。將共線方程代入后得：

（kx+b）²+a₁x（kx+b）+a₃（kx+b）=x³+a₂x²+a₄x+a₆

將其整理（按次數歸并）并化為一般方程為：

x³+（a₂-ka₁-k²）x²+（a₄-a₁b-2kb-ka₃）x+a₆-a₃b=0

根據三次方程根與系數的關系可知：當三次項系數為1時，-x₁x₂x₃等于常數項，x₁x₂+x₂x₃+x₃x₁等于一次項系數，-（x₁+x₂+x₃）等于二次項系數，列方程組可解出x₁、x₂、x₃，再根據共線方程可求出y₁、y₂、y₃。

由于-（x₁+x₂+x₃）=a₂-ka₁-k²，即x₄=x₃=k²+ka₁-a₂-x₁-x₂，又由于k=，即可求出：y₃=y₁-k（x₁-x₃）。

由于R就是R′作y軸平行線與曲線的交點，因此將x=x₄代入橢圓曲線統一方程，并化為一般方程，得：

根據二次方程根與系數的關系，有-（a₁x₄+a₃）=y₃+y₄，則可求出y₄=-y₃-（a₁x₄+a₃）。所得R（x₄，y₄）即為P、Q的和。

4. 有限域橢圓曲線

由于信息的明文、密文都是整數型數值，因此信息加密（即整數間的變換）應當是在有限域上進行的，域的最大值、最小值由信息長度決定（并非無窮大），而且信息是離散型的整數，所以必須對實數域上的橢圓曲線進行改進，以適合有限數量的整數運算的需要。另外，橢圓曲線的選擇很重要，并不是所有橢圓曲線都適合加密。

定義有限域F_p：

（1）F_p中有p（p為質數）個元素0，1，2，…，p-2，p-1。

（2）F_p的加法是a+b≡c（mod p）。

（3）F_p的乘法是a×b≡c（mod p）。

（4）F_p的除法是a÷b≡c（mod p）。

（5）F_p的單位元是1，零元是0。

（6）F_p域內運算滿足交換律、結合律、分配律。

以橢圓曲線y²=x³+ax+b為例，將其定義在F_p上，即對應y²=x³+ax+b（mod p）上的所有點（x，y）再加上無窮遠點O_∞。無窮遠點O_∞是零元，O_∞+O_∞=O_∞，O_∞+P=P。P（x，y）的負元是-P=P′（x，-y），有P+（-P）=O_∞。

選擇質數p，應有x，y∈[0，p-1]。將這條橢圓曲線記為E_p（a，b）。選擇兩個小于p的非負整數a、b，滿足約束條件：4a³+27b²≠0（mod p）。

以一條簡單的橢圓曲線為例。設p=23，a=b=1，橢圓曲線可記為E₂₃（1，1），曲線如圖3.22所示。可見離散域上的橢圓曲線已經變成一些不連續的點，其坐標均為整數。

如果已知曲線上兩點P（3，10）、Q（9，7），則P的負元-P=（3，-10），即（3，13），斜率，因為2×12=1（mod 23），所以2的乘法逆元為12，即1/2，同時-12（mod 23）=11（mod 23），所以有k=11。

根據P和Q的和R（x，y）的計算公式，有：

因此P+Q的坐標為（17，20）。

另外，過P（3，10）的切線斜率k′根據公式可計算為：

則可同理計算R（x，y）的坐標為：

因此2P的坐標為（7，12），依此類推可得3P、4P及任意nP。

如果橢圓曲線上一點P，存在最小的正整數n，使得數乘nP=O_∞（顯然（n-1）P=-P），則將n稱為P的階，若n不存在，則P是無限階的。事實上，在有限域上定義的橢圓曲線上所有的點的階n都是存在的。

5. 橢圓曲線加密

在橢圓曲線E_p（a，b）上選擇一個點G為基點（Base Point），n為階（nG=O_∞），并選擇一個整數k（k＜n）。計算K=kG，K也是橢圓曲線上的點。則點k為私鑰，K為公鑰（橢圓曲線E_p（a，b）和G也是公鑰的組成部分）。

不難發現，給定k和G，根據加法法則，計算K很容易；但反過來，即使已知K和G，求k卻是非常困難的（k是大數），唯一途徑是暴力破解，但耗時漫長。這就是橢圓曲線加密算法安全性的數學依據。

橢圓曲線加密的基本原理是對曲線上的點實施變換，所以首先需要將待加密的明文數據進行編碼，轉化為橢圓曲線上的一個點（坐標形式），才能符合加密運算的條件。解密后的數據同樣是曲線上的點，則需要反過來進行譯碼，恢復為明文數據的表達方式。

根據數論定義，令n為正整數，若整數a滿足與n互質（即有GCD（a，n）=1），且使得x²=a（mod n）有解，則稱a為模n的平方剩余，記為QR_n，否則a稱為模n的平方非剩余，記為QNR_n。

設：明文m∈（0，M），M為與m相同二進制長度的最大整數。又設函數f（x）：y²=x³+ax+b（標準橢圓曲線方程），有限域E_p（a，b）元素個數為p（p為質數）。

選擇整數k，滿足Mk＜p，令x_i=mk+i（i=1，2，…，k-1），依次計算f（x_i）=x³+ax+b（mod p）。若找到f（x_i）是模p的平方剩余（QR_p），則用x_m表示此時的x_i，y_m表示f（x_i）的平方根，這樣明文m即編碼成為橢圓曲線上的點（x_m，y_m）。

譯碼計算非常簡單，由于i∈（0，k），只需取解密后的x′_m坐標值進行除法運算并取整[x′_m/k]，即恢復明文m。

因為模p的平方剩余和平方非剩余各占一半，所以k次內找到的概率不小于1-（1/2）^k，編碼成功率很高。另外也可設計其他不同的編碼、譯碼方法。

需要進行公鑰加密、私鑰解密來傳輸保密數據時，密鑰生成方法和加密、解密的操作過程如下：

（1）接收方選定一條橢圓曲線E_p（a，b），并取橢圓曲線上一點作為基點G；選擇一個隨機數為私鑰k，并生成公鑰K=kG。接收方將橢圓曲線E_p（a，b）和點K、G（即公鑰）傳給發送方。

（2）發送方收到公鑰后，先將待傳輸的明文編碼到E_p（a，b）上的一點M，并產生一個隨機數r（r＜n）。計算C₁=M+rK和C₂=rG。發送密文C₁和C₂。

（3）接收方收到密文后，進行解密計算M′=C₁-kC₂，M′經過譯碼即為明文。解密運算的原理證明如下：

C₁-kC₂=M+rK-k（rG）=M+r（K-kG）=M

如需要用私鑰加密原消息作簽名，然后用公鑰來驗證簽名，則密鑰對由發送方生成，密鑰生成方法不變，公鑰被傳給接收方，之后進行的加密、驗證過程如下：

（1）發送方生成隨機數r，計算S₁=rG。對原消息M作單向函數運算h=Hash（M），計算S₂=（h+kM）/r。

（2）接收方收到原消息M和密文S₁、S₂后，計算驗證hG/S₂+MK/S₂=S₁是否成立。原理證明如下：

橢圓曲線方程的選擇對于加密算法而言至關重要，是加密強度的基礎。選擇不當可能造成加密強度不足，甚至可能存在安全漏洞（假如是故意為之，則為安全后門）。

通常將F_p上的一條橢圓曲線描述為T=（p，a，b，G，n，h）。其中：p、a、b用來確定一條橢圓曲線，G為基點，n為點G的階，h是橢圓曲線上所有點的個數m與n相除的商的整數部分。這6個參量取值的選擇，直接影響了加密的安全性。參量值一般要求滿足以下幾個條件：

?　p越大安全性越好，但會導致計算速度變慢，200b左右可滿足一般安全要求；

?　n應為質數；

?　h≤4；

?　p≠n×h；

?　pt≠1（mod n），1≤t＜20；

?　4a³+27b²≠0（mod p）。

比特幣系統中即采用橢圓曲線加密法為簽名算法，并選用了Secp256k1曲線，參照SEC標準（Standards for Efficient Cryptography）。F_p上的橢圓曲線參量T=（p，a，b，G，n，h）定義如下（方程式為y²=x³+7，曲線如圖3.23所示）：

?　有限域采用256b的質數p：

p=FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F

=2²⁵⁶-2³²-2⁹-2⁸-2⁷-2⁶-2⁴-1

?　橢圓曲線E為y²=x³+ax+b，其中：a=0，b=7。

?　基點G選擇分為兩種情況：

（1）壓縮格式下G=02 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798

（2）非壓縮格式下G=04 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8

?　基點G的階n為：

n=FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE

BAAEDCE6 AF48A03B BFD25E8C D0364141

?　h=1。