3.3　非對(duì)稱密鑰加密

加密用哪個(gè)密鑰、解密也必須用哪個(gè)，似乎就像鎖定保險(xiǎn)箱用這把鑰匙、打開保險(xiǎn)箱就一定用這把那樣必然。然而這種“自然而然”的狀況在1976年被Diffie和Hellman打破了，他們?cè)凇睹艽a學(xué)新方向》一文中提出的技術(shù)顛覆了“一把鑰匙開一把鎖”的思維定式，開創(chuàng)了密碼學(xué)的新領(lǐng)域。

3.3.1　非對(duì)稱密鑰加密技術(shù)原理

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

公鑰體制的優(yōu)越性在于分離出兩個(gè)相關(guān)的密鑰，其中的公鑰不需要保密，而私鑰絕對(duì)不在網(wǎng)絡(luò)上傳輸，因此就不存在密鑰泄露問題。公鑰和私鑰的使用規(guī)則為：

?　用公鑰加密的數(shù)據(jù)用且只能用對(duì)應(yīng)的私鑰解密。

?　用私鑰加密的數(shù)據(jù)用且只能用對(duì)應(yīng)的公鑰解密。

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

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

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

（3）方法（a）和（b）從安全效果上基本上是“互補(bǔ)”的關(guān)系，方法（c）就是對(duì)兩種方法的綜合，既能確認(rèn)發(fā)送者，又能保護(hù)信息的私密性。

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

“是的?！盇lice不知道Bob的葫蘆里賣的什么藥。

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

“在方法（a）中我發(fā)送的信息你會(huì)拒絕認(rèn)可，反而認(rèn)可攻擊者假冒我的身份發(fā)出的信息?！盇lice越說(shuō)越心驚，“方法（b）中攻擊者可以解密我發(fā)給你的保密信息，然后可以篡改后再‘加密’發(fā)送給你?！?/p>

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

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

公鑰加密的計(jì)算效率通常很低，甚至只有對(duì)稱密鑰加密方法的千分之一，因此不適合對(duì)大量的數(shù)據(jù)進(jìn)行加密，一般用來(lái)加密會(huì)話密鑰等短小數(shù)據(jù)。

常用的公鑰加密算法有RSA、ElGamal等，目前技術(shù)含量最高、安全性最強(qiáng)的是ECC算法，該算法在比特幣系統(tǒng)中得到充分運(yùn)用，實(shí)現(xiàn)了虛擬貨幣資產(chǎn)的匿名持有和支付驗(yàn)證。

3.3.2　RSA算法

RSA算法于1977年被提出，以三位發(fā)明者Ron Rivest、Adi Shamir和Leonard Adleman姓氏的首字母來(lái)命名，是最早也是最著名的公開密鑰加密算法，應(yīng)用相當(dāng)廣泛。RSA算法的數(shù)學(xué)基礎(chǔ)是數(shù)論中的歐拉（Euler）定理，安全性建立在大整數(shù)分解質(zhì)數(shù)（素?cái)?shù)）因子的困難性之上。

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

（1）選擇不同的大質(zhì)數(shù)p和q，計(jì)算n=p×q和φ（n）=（p-1）×（q-1）。

（2）選擇大整數(shù)e，與φ（n）互質(zhì)，且1＜e＜φ（n）。

（3）計(jì)算整數(shù)d，使d×e=1 modφ（n）。

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

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

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

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

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

使用公鑰pubKey={e，n}的加密過程如下。對(duì)于明文M，若M＜n，將M作為一個(gè)大整數(shù)來(lái)計(jì)算，若M≥n，則進(jìn)行分段計(jì)算：

C=M^e mod n

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

M=C^d mod n

解密與加密為互逆的運(yùn)算，可簡(jiǎn)單證明如下（根據(jù)歐拉定理）：

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

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

實(shí)際應(yīng)用中應(yīng)選擇十進(jìn)制100位以上的質(zhì)數(shù)，n的長(zhǎng)度至少要達(dá)到1024b。為了抵抗整數(shù)分解算法，對(duì)p和q另有如下要求：

（1）|p-q|很大，通常p和q的長(zhǎng)度相近。

（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算法是一種公開密鑰加密技術(shù)，其安全性原理依賴于計(jì)算有限域上離散對(duì)數(shù)這一難題。ElGamal密鑰對(duì)的產(chǎn)生流程如下：

首先選擇一個(gè)質(zhì)數(shù)p和兩個(gè)隨機(jī)數(shù)g和x（g，x＜p），計(jì)算：

y=g^x mod p

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

ElGamal進(jìn)行公鑰加密時(shí)，設(shè)明文為M，需選擇一個(gè)隨機(jī)數(shù)k，使k與（p-1）互質(zhì)（可采用歐幾里得輾轉(zhuǎn)相除法），并計(jì)算：

a=g^k mod p

b=y^kM mod p

所得（a，b）即為密文，長(zhǎng)度是明文的兩倍。用私鑰解密時(shí)計(jì)算：

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

在運(yùn)用ElGamal時(shí)，質(zhì)數(shù)p必須足夠大，且p-1應(yīng)至少包含一個(gè)大質(zhì)數(shù)因子，并保證g對(duì)于p-1的大質(zhì)數(shù)因子不可約。ElGamal的一個(gè)不足之處是其密文長(zhǎng)度為明文的兩倍，增加了存儲(chǔ)空間和傳輸帶寬的占用。

3.3.4　ECC算法

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

與RSA方法相比，ECC可以使用164b密鑰產(chǎn)生一個(gè)安全級(jí)相當(dāng)于RSA方法的1024b密鑰提供的保密強(qiáng)度，而且計(jì)算量較小、處理速度更快、存儲(chǔ)空間和傳輸帶寬占用較少，具有較大的技術(shù)優(yōu)勢(shì)。

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

1. 射影平面

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

定義平行線相交于無(wú)窮遠(yuǎn)點(diǎn)P_∞，如圖3.16所示，這樣，平面上任何兩條直線都統(tǒng)一為有唯一的交點(diǎn)。P_∞具有以下性質(zhì)：

（1）一條直線只有一個(gè)無(wú)窮遠(yuǎn)點(diǎn)，一對(duì)平行線有公共的無(wú)窮遠(yuǎn)點(diǎn)（即交點(diǎn)）。

（2）任何兩條不平行的直線有不同的無(wú)窮遠(yuǎn)點(diǎn)（否則會(huì)造成兩個(gè)交點(diǎn)）。

（3）平面上全體無(wú)窮遠(yuǎn)點(diǎn)構(gòu)成一條無(wú)窮遠(yuǎn)直線。

平面上全體無(wú)窮遠(yuǎn)點(diǎn)（無(wú)窮遠(yuǎn)直線）與全體平常點(diǎn)構(gòu)成射影平面（projective plane）。

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

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

對(duì)平行線aX+bY+c₁Z=0和aX+bY+c₂Z=0，易解得Z=0，說(shuō)明射影平面上平行線交點(diǎn)即無(wú)窮遠(yuǎn)點(diǎn)P_∞的坐標(biāo)為（X∶Y∶0）。

2. 橢圓曲線

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

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

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

令Z=0，代入橢圓曲線方程得X=0，說(shuō)明橢圓曲線上有一個(gè)無(wú)窮遠(yuǎn)點(diǎn)O_∞，其坐標(biāo)為（0∶Y∶0）。無(wú)窮遠(yuǎn)點(diǎn)O_∞和普通平面上的平常點(diǎn)（即曲線）一起，共同組成射影平面上的橢圓曲線。

運(yùn)用射影平面與普通平面的點(diǎn)的轉(zhuǎn)換關(guān)系，橢圓曲線方程可轉(zhuǎn)換為普通平面方程：

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

對(duì)橢圓曲線的平常點(diǎn)（x，y）求導(dǎo)，并計(jì)算過該點(diǎn)的切線的斜率k，有：

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

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

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

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

3. 橢圓曲線加法

在橢圓曲線中引入阿貝爾（Abel）加法群（又稱交換群）的概念，可進(jìn)一步實(shí)現(xiàn)對(duì)橢圓曲線上的點(diǎn)的運(yùn)算。

任意取橢圓曲線上兩點(diǎn)P、Q（若P、Q兩點(diǎn)重合，則作P點(diǎn)的切線），過兩點(diǎn)作直線交于橢圓曲線的另一點(diǎn)R′，過R′做y軸的平行線交橢圓曲線于R，定義P+Q=R?？梢姡臃ǖ暮鸵苍跈E圓曲線上，并同樣遵循加法的交換律、結(jié)合律。

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

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

再進(jìn)一步，如圖3.21所示，若有k個(gè)相同的點(diǎn)P相加，記作kP，有：

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

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

因?yàn)?i>P、Q、-R三點(diǎn)共線，所以設(shè)共線方程為y=kx+b，分兩種情況：

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

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

因此，P、Q、-R三點(diǎn)的坐標(biāo)值（x₁，y₁）、（x₂，y₂）、（x₃，y₃）就是橢圓曲線統(tǒng)一方程與共線方程組成的方程組的解（即三個(gè)交點(diǎn)）。將共線方程代入后得：

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

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

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

根據(jù)三次方程根與系數(shù)的關(guān)系可知：當(dāng)三次項(xiàng)系數(shù)為1時(shí)，-x₁x₂x₃等于常數(shù)項(xiàng)，x₁x₂+x₂x₃+x₃x₁等于一次項(xiàng)系數(shù)，-（x₁+x₂+x₃）等于二次項(xiàng)系數(shù)，列方程組可解出x₁、x₂、x₃，再根據(jù)共線方程可求出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軸平行線與曲線的交點(diǎn)，因此將x=x₄代入橢圓曲線統(tǒng)一方程，并化為一般方程，得：

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

4. 有限域橢圓曲線

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

定義有限域F_p：

（1）F_p中有p（p為質(zhì)數(shù)）個(gè)元素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域內(nèi)運(yùn)算滿足交換律、結(jié)合律、分配律。

以橢圓曲線y²=x³+ax+b為例，將其定義在F_p上，即對(duì)應(yīng)y²=x³+ax+b（mod p）上的所有點(diǎn)（x，y）再加上無(wú)窮遠(yuǎn)點(diǎn)O_∞。無(wú)窮遠(yuǎn)點(diǎn)O_∞是零元，O_∞+O_∞=O_∞，O_∞+P=P。P（x，y）的負(fù)元是-P=P′（x，-y），有P+（-P）=O_∞。

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

以一條簡(jiǎn)單的橢圓曲線為例。設(shè)p=23，a=b=1，橢圓曲線可記為E₂₃（1，1），曲線如圖3.22所示?？梢婋x散域上的橢圓曲線已經(jīng)變成一些不連續(xù)的點(diǎn)，其坐標(biāo)均為整數(shù)。

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

根據(jù)P和Q的和R（x，y）的計(jì)算公式，有：

因此P+Q的坐標(biāo)為（17，20）。

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

則可同理計(jì)算R（x，y）的坐標(biāo)為：

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

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

5. 橢圓曲線加密

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

不難發(fā)現(xiàn)，給定k和G，根據(jù)加法法則，計(jì)算K很容易；但反過來(lái)，即使已知K和G，求k卻是非常困難的（k是大數(shù)），唯一途徑是暴力破解，但耗時(shí)漫長(zhǎng)。這就是橢圓曲線加密算法安全性的數(shù)學(xué)依據(jù)。

橢圓曲線加密的基本原理是對(duì)曲線上的點(diǎn)實(shí)施變換，所以首先需要將待加密的明文數(shù)據(jù)進(jìn)行編碼，轉(zhuǎn)化為橢圓曲線上的一個(gè)點(diǎn)（坐標(biāo)形式），才能符合加密運(yùn)算的條件。解密后的數(shù)據(jù)同樣是曲線上的點(diǎn)，則需要反過來(lái)進(jìn)行譯碼，恢復(fù)為明文數(shù)據(jù)的表達(dá)方式。

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

設(shè)：明文m∈（0，M），M為與m相同二進(jìn)制長(zhǎng)度的最大整數(shù)。又設(shè)函數(shù)f（x）：y²=x³+ax+b（標(biāo)準(zhǔn)橢圓曲線方程），有限域E_p（a，b）元素個(gè)數(shù)為p（p為質(zhì)數(shù)）。

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

譯碼計(jì)算非常簡(jiǎn)單，由于i∈（0，k），只需取解密后的x′_m坐標(biāo)值進(jìn)行除法運(yùn)算并取整[x′_m/k]，即恢復(fù)明文m。

因?yàn)槟?i>p的平方剩余和平方非剩余各占一半，所以k次內(nèi)找到的概率不小于1-（1/2）^k，編碼成功率很高。另外也可設(shè)計(jì)其他不同的編碼、譯碼方法。

需要進(jìn)行公鑰加密、私鑰解密來(lái)傳輸保密數(shù)據(jù)時(shí)，密鑰生成方法和加密、解密的操作過程如下：

（1）接收方選定一條橢圓曲線E_p（a，b），并取橢圓曲線上一點(diǎn)作為基點(diǎn)G；選擇一個(gè)隨機(jī)數(shù)為私鑰k，并生成公鑰K=kG。接收方將橢圓曲線E_p（a，b）和點(diǎn)K、G（即公鑰）傳給發(fā)送方。

（2）發(fā)送方收到公鑰后，先將待傳輸?shù)拿魑木幋a到E_p（a，b）上的一點(diǎn)M，并產(chǎn)生一個(gè)隨機(jī)數(shù)r（r＜n）。計(jì)算C₁=M+rK和C₂=rG。發(fā)送密文C₁和C₂。

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

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

如需要用私鑰加密原消息作簽名，然后用公鑰來(lái)驗(yàn)證簽名，則密鑰對(duì)由發(fā)送方生成，密鑰生成方法不變，公鑰被傳給接收方，之后進(jìn)行的加密、驗(yàn)證過程如下：

（1）發(fā)送方生成隨機(jī)數(shù)r，計(jì)算S₁=rG。對(duì)原消息M作單向函數(shù)運(yùn)算h=Hash（M），計(jì)算S₂=（h+kM）/r。

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

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

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

?　p越大安全性越好，但會(huì)導(dǎo)致計(jì)算速度變慢，200b左右可滿足一般安全要求；

?　n應(yīng)為質(zhì)數(shù)；

?　h≤4；

?　p≠n×h；

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

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

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

?　有限域采用256b的質(zhì)數(shù)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。

?　基點(diǎn)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

?　基點(diǎn)G的階n為：

n=FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE

BAAEDCE6 AF48A03B BFD25E8C D0364141

?　h=1。