橢圓加密演算法最早出現

『壹』 首次將橢圓曲線用於密碼學,建立公開密鑰加密的演演算法是在那一年

橢圓曲線密碼學（英語：Elliptic curve cryptography，縮寫為 ECC），一種建立公開密鑰加密的演算法，基於橢圓曲線數學。

橢圓曲線在密碼學中的使用是在1985年由Neal Koblitz和Victor Miller分別獨立提出的。

橢圓曲線密碼學：

橢圓曲線密碼學（英語：Elliptic curve cryptography，縮寫為ECC），一種建立公開密鑰加密的演算法，基於橢圓曲線數學。橢圓曲線在密碼學中的使用是在1985年由Neal Koblitz和Victor Miller分別獨立提出的。

ECC的主要優勢是在某些情況下它比其他的方法使用更小的密鑰——比如RSA加密演算法——提供相當的或更高等級的安全。ECC的另一個優勢是可以定義群之間的雙線性映射。

基於Weil對或是Tate對；雙線性映射已經在密碼學中發現了大量的應用，例如基於身份的加密。其缺點是同長度密鑰下加密和解密操作的實現比其他機制花費的時間長。

但由於可以使用更短的密鑰達到同級的安全程度，所以同級安全程度下速度相對更快。一般認為160比特的橢圓曲線密鑰提供的安全強度與1024比特RSA密鑰相當。

『貳』 理解橢圓曲線加密演算法

橢圓曲線加密演算法，即：Elliptic Curve Cryptography，簡稱ECC，是基於橢圓曲線數學理論實現的一種非對稱加密演算法。相比RSA，ECC優勢是可以使用更短的密鑰，來實現與RSA相當或更高的安全。據研究，160位ECC加密安全性相當於1024位RSA加密，210位ECC加密安全性相當於2048位RSA加密。

一般橢圓曲線方程式表示為:(其中a,b,c,d為系數)
> y2=ax3+ bx2+cx+d
典型的橢圓曲線如：y2=x3−4x2+16

先擺一個栗子：

小米很難算到的那個數，就是公鑰密碼演算法中的私鑰（一個公鑰密碼演算法安全的必要條件（非充分）是「由公鑰不能反推出私鑰」），公鑰密碼演算法最根本的原理是利用信息的不對稱性：即掌握私鑰的人在整個通信過程中掌握最多的信息。
橢圓曲線加密演算法是一個基於加法階數難求問題的密碼方案。 對於橢圓曲線來講，橢圓曲線的基點就是例子裡面的5，而私鑰就是基點的加法階數（例子裡面的11），公鑰是基點（5）進行對應階數的加法（11次）得到的結果（55）。

簡單描述就是:G * k = K （G,K公開，k保密）

上述例子相對簡單，橢圓曲線加密演算法里的加法建立在 「有限域上的二元三次曲線上的點」上 ，組成一個「有限加法循環群」。具體的說，這個加法的幾何定義如下圖，兩個點的加法結果是指這兩點的連線和曲線的交點關於x軸的鏡像。

如果我們從某一點出發（所謂的單位元，比如正整數域的1，代表一個空間里的最基本單元），不停做自增操作（所謂群操作，比如++），枚舉出整個空間的集合元素。如圖：

因此給定橢圓曲線的某一點G，從G出發，不停做切線，找對稱點，依次得到-2G，2G，-4G，4G，-8G，8G... 。即：當給定G點時，已知x，求xG點並不困難。反之，已知xG點，求x則非常困難。即Q = NG，N就是我們的私鑰，Q就是我們的公鑰。

現在我們知道了公鑰(Q)和私鑰(N)的生成的原理,我們在看看橢圓曲線數字簽名演算法(ECDSA)的過程,橢圓曲線數字簽名演算法（ECDSA）是使用橢圓曲線密碼（ECC）對數字簽名演算法（DSA）的模擬。ECDSA於1999年成為ANSI標准，並於2000年成為IEEE和NIST標准。

私鑰主要用於 簽名，解密 ；公鑰主要用於 驗簽，加密 ，可以通過私鑰可以計算出公鑰，反之則不行。
公鑰加密：公鑰加密的內容可以用私鑰來解密——只有私鑰持有者才能解密。
私鑰簽名：私鑰簽名的內容可以用公鑰驗證。公鑰能驗證的簽名均可視為私鑰持有人所簽署。

通常需要六個參數來描敘一個特定的橢圓曲線:T = (p, a, b, G, n, h).
p: 代表有限域Fp的那個質數 a,b：橢圓方程的參數 G: 橢圓曲線上的一個基點G = (xG, yG) n：G在Fp中規定的序號，一個質數。 h：余因數（cofactor），控制選取點的密度。h = #E(Fp) / n。

這里以secp256k1曲線(比特幣簽名所使用的曲線)為例介紹一下公私鑰對的產生的過成。
secp256k1的參數為：

本質上ECDSA的私鑰就是一個隨機數滿足在曲線G的n階里及k∈(0,n),根據Q=kG可以計算出公鑰，生成的私鑰一般為32位元組大小，公鑰通常為64個位元組大小。如：

ECDSA簽名演算法的輸入是數據的哈希值，而不是數據的本身，我們假設用戶的密鑰對:（d, Q）；(d為私鑰，Q為公鑰) 待簽名的信息：M； e = Hash(M);簽名：Signature(e) = ( r, s)。

簽名介面：

驗證介面:

一個例子：

『叄』 ECC橢圓曲線加密演算法(一)

btc address:
eth address:

隨著區塊鏈的大熱，橢圓曲線演算法也成了密碼學的熱門話題。在Bitcoin 生成地址 中使用到了橢圓曲線加密演算法。

橢圓曲線的一般表現形式：

橢圓曲線其實不是橢圓形的，而是下面的圖形：

Bitcoin使用了 secp256k1 這條特殊的橢圓曲線，公式是：

這個東西怎麼加密的呢？

19世紀挪威青年 尼爾斯·阿貝爾 從普通的代數運算中，抽象出了加群（也叫阿貝爾群或交換群），使得在加群中，實數的演算法和橢圓曲線的演算法得到了統一。是什麼意思呢？

我們在實數中，使用的加減乘除，同樣可以用在橢圓曲線中！
對的，橢圓曲線也可以有加法、乘法運算。

數學中的群是一個集合，我們為它定義了一個二元運算，我們稱之為「加法」，並用符號 + 表示。假定我們要操作的群用𝔾表示，要定義的 加法 必須遵循以下四個特性：

如果在增加第5個條件：
交換律：a + b = b + a

那麼，稱這個群為阿貝爾群。根據這個定義整數集是個阿貝爾群。

岔開一下話題， 伽羅瓦 與 阿貝爾 分別獨立的提出了群論，他們並稱為現代群論的創始人，可惜兩位天才都是英年早逝。

如上文所說，我們可以基於橢圓曲線定義一個群。具體地說：

在橢圓曲線上有 不重合且不對稱的 A 、B兩點，兩點與曲線相交於X點, X與 x軸 的對稱點為R，R即為 A+B 的結果。這就是橢圓曲線的加法定義。

因為橢圓曲線方程存在 項，因此橢圓曲線必然關於x軸對稱

曲線： ，
坐標：A=(2,5)，B=(3,7)
A、B正好在曲線上，因為坐標滿足曲線公式


那如何找到相交的第三個點呢？

通過 A、B兩點確定直線方程，
設直線方程： ，m為直線的斜率

進一步得到c=1。

聯立方程：

X(-1,-1)的x坐標-1代入方式正好滿足方程，所以A、B兩點所在直線與曲線相交於 X(-1,-1)，則點X的關於x軸的對稱點為R(-1,1)，即A(2,5)+B(3,5)=R(-1,1)。

根據橢圓曲線的 群律(GROUP LAW) 公式，我們可以方便的計算R點。

曲線方程：
當A=(x1,y1)，B=(x2,y2) ，R=A+B=(x3,y3)，x1≠x2時,
， m是斜率
x3=
y3=m(x1-x3)-y1

A=(2,5), B=(3,7) , R=(-1,1) 符合上面的公式。

橢圓曲線加法符合交換律么？

先計算(A+B)，在計算 A+B+C

先計算B+C， 在計算 B+C+A

看圖像，計算結果相同，大家手動算下吧。

那 A + A 呢， 怎麼計算呢？

當兩點重合時候，無法畫出 「過兩點的直線」，在這種情況下，
過A點做橢圓曲線的切線，交於X點，X點關於 x軸 的對稱點即為 2A ，這樣的計算稱為 「橢圓曲線上的二倍運算」。

下圖即為橢圓曲線乘法運算：

我們將在 ECC橢圓曲線加密演算法(二) 介紹有限域，橢圓曲線的離散對數問題，橢圓曲線加密就是應用了離散對數問題。

參考：

https://eng.paxos.com/blockchain-101-foundational-math
https://eng.paxos.com/blockchain-101-elliptic-curve-cryptography
https://andrea.corbellini.name/2015/05/17/elliptic-curve-cryptography-a-gentle-introction/

『肆』 橢圓加密演算法的方程

橢圓曲線密碼體制來源於對橢圓曲線的研究，所謂橢圓曲線指的是由韋爾斯特拉斯（Weierstrass）方程：
y2+a1xy+a3y=x3+a2x2+a4x+a6 (1)
所確定的平面曲線。其中系數ai(I=1,2,…,6)定義在某個域上，可以是有理數域、實數域、復數域，還可以是有限域GF（pr），橢圓曲線密碼體制中用到的橢圓曲線都是定義在有限域上的。
橢圓曲線上所有的點外加一個叫做無窮遠點的特殊點構成的集合連同一個定義的加法運算構成一個Abel群。在等式
mP=P+P+…+P=Q (2)
中，已知m和點P求點Q比較容易，反之已知點Q和點P求m卻是相當困難的，這個問題稱為橢圓曲線上點群的離散對數問題。橢圓曲線密碼體制正是利用這個困難問題設計而來。橢圓曲線應用到密碼學上最早是由Neal Koblitz 和Victor Miller在1985年分別獨立提出的。
橢圓曲線密碼體制是目前已知的公鑰體制中，對每比特所提供加密強度最高的一種體制。解橢圓曲線上的離散對數問題的最好演算法是Pollard rho方法，其時間復雜度為，是完全指數階的。其中n為等式(2)中m的二進製表示的位數。當n=234, 約為2117，需要1.6x1023 MIPS 年的時間。而我們熟知的RSA所利用的是大整數分解的困難問題，目前對於一般情況下的因數分解的最好演算法的時間復雜度是子指數階的，當n=2048時，需要2x1020MIPS年的時間。也就是說當RSA的密鑰使用2048位時，ECC的密鑰使用234位所獲得的安全強度還高出許多。它們之間的密鑰長度卻相差達9倍，當ECC的密鑰更大時它們之間差距將更大。更ECC密鑰短的優點是非常明顯的，隨加密強度的提高，密鑰長度變化不大。
德國、日本、法國、美國、加拿大等國的很多密碼學研究小組及一些公司實現了橢圓曲線密碼體制，我國也有一些密碼學者
做了這方面的工作。許多標准化組織已經或正在制定關於橢圓曲線的標准，同時也有許多的廠商已經或正在開發基於橢圓曲線的產品。對於橢圓曲線密碼的研究也是方興未艾，從ASIACRYPTO』98上專門開辟了ECC的欄目可見一斑。
在橢圓曲線密碼體制的標准化方面，IEEE、ANSI、ISO、IETF、ATM等都作了大量的工作，它們所開發的橢圓曲線標準的文檔有：IEEE P1363 P1363a、ANSI X9.62 X9.63、 ISO/IEC14888等。
2003年5月12日中國頒布的無線區域網國家標准 GB15629.11 中，包含了全新的WAPI(WLAN Authentication and Privacy Infrastructure)安全機制，能為用戶的WLAN系統提供全面的安全保護。這種安全機制由 WAI和WPI兩部分組成，分別實現對用戶身份的鑒別和對傳輸的數據加密。WAI採用公開密鑰密碼體制，利用證書來對WLAN系統中的用戶和AP進行認證。證書裡麵包含有證書頒發者(ASU)的公鑰和簽名以及證書持有者的公鑰和簽名，這里的簽名採用的就是橢圓曲線ECC演算法。
加拿大Certicom公司是國際上最著名的ECC密碼技術公司,已授權300多家企業使用ECC密碼技術，包括Cisco 系統有限公司、摩托羅拉、Palm等企業。Microsoft將Certicom公司的VPN嵌入微軟視窗移動2003系統中。
以下資料摘自：http://www.hids.com.cn/data.asp

『伍』 橢圓曲線加密演算法

橢圓曲線加密演算法，即：Elliptic Curve Cryptography，簡稱ECC，是基於橢圓曲線數學理論實現的一種非對稱加密演算法。相比RSA，ECC優勢是可以使用更短的密鑰，來實現與RSA相當或更高的安全。據研究，160位ECC加密安全性相當於1024位RSA加密，210位ECC加密安全性相當於2048位RSA加密。

橢圓曲線在密碼學中的使用，是1985年由Neal Koblitz和Victor Miller分別獨立提出的。

一般情況下，橢圓曲線可用下列方程式來表示，其中a,b,c,d為系數。

例如，當a=1,b=0,c=-2,d=4時，所得到的橢圓曲線為:

該橢圓曲線E的圖像如圖X-1所示，可以看出根本就不是橢圓形。

過曲線上的兩點A、B畫一條直線，找到直線與橢圓曲線的交點，交點關於x軸對稱位置的點，定義為A+B，即為加法。如下圖所示：A + B = C

上述方法無法解釋A + A，即兩點重合的情況。因此在這種情況下，將橢圓曲線在A點的切線，與橢圓曲線的交點，交點關於x軸對稱位置的點，定義為A + A，即2A，即為二倍運算。

將A關於x軸對稱位置的點定義為-A，即橢圓曲線的正負取反運算。如下圖所示：

如果將A與-A相加，過A與-A的直線平行於y軸，可以認為直線與橢圓曲線相交於無窮遠點。

綜上，定義了A+B、2A運算，因此給定橢圓曲線的某一點G，可以求出2G、3G（即G + 2G）、4G......。即：當給定G點時，已知x，求xG點並不困難。反之，已知xG點，求x則非常困難。此即為橢圓曲線加密演算法背後的數學原理。

橢圓曲線要形成一條光滑的曲線，要求x,y取值均為實數，即實數域上的橢圓曲線。但橢圓曲線加密演算法，並非使用實數域，而是使用有限域。按數論定義，有限域GF(p)指給定某個質數p，由0、1、2......p-1共p個元素組成的整數集合中定義的加減乘除運算。

假設橢圓曲線為y² = x³ + x + 1，其在有限域GF(23)上時，寫作：y² ≡ x³ + x + 1 (mod 23)

此時，橢圓曲線不再是一條光滑曲線，而是一些不連續的點，如下圖所示。以點(1,7)為例，7² ≡ 1³ + 1 + 1 ≡ 3 (mod 23)。如此還有如下點：

(0,1) (0,22)(1,7) (1,16)(3,10) (3,13)(4,0)(5,4) (5,19)(6,4) (6,19)(7,11) (7,12)(9,7) (9,16)(11,3) (11,20)等等。

另外，如果P(x,y)為橢圓曲線上的點，則-P即(x,-y)也為橢圓曲線上的點。如點P(0,1)，-P=(0,-1)=(0,22)也為橢圓曲線上的點。

相關公式如下：有限域GF(p)上的橢圓曲線y² = x³ + ax + b，若P(Xp, Yp), Q(Xq, Yq)，且P≠-Q，則R(Xr,Yr) = P+Q 由如下規則確定：

Xr = (λ² - Xp - Xq) mod pYr = (λ(Xp - Xr) - Yp) mod p其中λ = (Yq - Yp)/(Xq - Xp) mod p（若P≠Q）, λ = (3Xp² + a)/2Yp mod p（若P=Q）

因此，有限域GF(23)上的橢圓曲線y² ≡ x³ + x + 1 (mod 23)，假設以(0,1)為G點，計算2G、3G、4G...xG等等，方法如下：

計算2G：λ = (3x0² + 1)/2x1 mod 23 = (1/2) mod 23 = 12Xr = (12² - 0 - 0) mod 23 = 6Yr = (12(0 - 6) - 1) mod 23 = 19即2G為點(6,19)

計算3G：3G = G + 2G，即(0,1) + (6,19)λ = (19 - 1)/(6 - 0) mod 23 = 3Xr = (3² - 0 - 6) mod 23 = 3Yr = (3(0 - 3) - 1) mod 23 = 13即3G為點(3, 13)

建立基於橢圓曲線的加密機制，需要找到類似RSA質因子分解或其他求離散對數這樣的難題。而橢圓曲線上的已知G和xG求x，是非常困難的，此即為橢圓曲線上的的離散對數問題。此處x即為私鑰，xG即為公鑰。

橢圓曲線加密演算法原理如下：

設私鑰、公鑰分別為k、K，即K = kG，其中G為G點。

公鑰加密：選擇隨機數r，將消息M生成密文C，該密文是一個點對，即：C = {rG, M+rK}，其中K為公鑰

私鑰解密：M + rK - k(rG) = M + r(kG) - k(rG) = M其中k、K分別為私鑰、公鑰。

橢圓曲線簽名演算法，即ECDSA。設私鑰、公鑰分別為k、K，即K = kG，其中G為G點。

私鑰簽名：1、選擇隨機數r，計算點rG(x, y)。2、根據隨機數r、消息M的哈希h、私鑰k，計算s = (h + kx)/r。3、將消息M、和簽名{rG, s}發給接收方。

公鑰驗證簽名：1、接收方收到消息M、以及簽名{rG=(x,y), s}。2、根據消息求哈希h。3、使用發送方公鑰K計算：hG/s + xK/s，並與rG比較，如相等即驗簽成功。

原理如下：hG/s + xK/s = hG/s + x(kG)/s = (h+xk)G/s= r(h+xk)G / (h+kx) = rG

假設要簽名的消息是一個字元串：「Hello World!」。DSA簽名的第一個步驟是對待簽名的消息生成一個消息摘要。不同的簽名演算法使用不同的消息摘要演算法。而ECDSA256使用SHA256生成256比特的摘要。
摘要生成結束後，應用簽名演算法對摘要進行簽名：
產生一個隨機數k
利用隨機數k，計算出兩個大數r和s。將r和s拼在一起就構成了對消息摘要的簽名。
這里需要注意的是，因為隨機數k的存在，對於同一條消息，使用同一個演算法，產生的簽名是不一樣的。從函數的角度來理解，簽名函數對同樣的輸入會產生不同的輸出。因為函數內部會將隨機值混入簽名的過程。

關於驗證過程，這里不討論它的演算法細節。從宏觀上看，消息的接收方從簽名中分離出r和s，然後利用公開的密鑰信息和s計算出r。如果計算出的r和接收到的r值相同，則表示驗證成功。否則，表示驗證失敗。

『陸』 非對稱加密演算法 (RSA、DSA、ECC、DH)

非對稱加密需要兩個密鑰：公鑰(publickey) 和私鑰 (privatekey)。公鑰和私鑰是一對，如果用公鑰對數據加密，那麼只能用對應的私鑰解密。如果用私鑰對數據加密，只能用對應的公鑰進行解密。因為加密和解密用的是不同的密鑰，所以稱為非對稱加密。

非對稱加密演算法的保密性好，它消除了最終用戶交換密鑰的需要。但是加解密速度要遠遠慢於對稱加密，在某些極端情況下，甚至能比對稱加密慢上1000倍。

演算法強度復雜、安全性依賴於演算法與密鑰但是由於其演算法復雜，而使得加密解密速度沒有對稱加密解密的速度快。對稱密碼體制中只有一種密鑰，並且是非公開的，如果要解密就得讓對方知道密鑰。所以保證其安全性就是保證密鑰的安全，而非對稱密鑰體制有兩種密鑰，其中一個是公開的，這樣就可以不需要像對稱密碼那樣傳輸對方的密鑰了。這樣安全性就大了很多。

RSA、Elgamal、背包演算法、Rabin、D-H、ECC (橢圓曲線加密演算法)。使用最廣泛的是 RSA 演算法，Elgamal 是另一種常用的非對稱加密演算法。

收信者是唯一能夠解開加密信息的人，因此收信者手裡的必須是私鑰。發信者手裡的是公鑰，其它人知道公鑰沒有關系，因為其它人發來的信息對收信者沒有意義。

客戶端需要將認證標識傳送給伺服器，此認證標識 (可能是一個隨機數) 其它客戶端可以知道，因此需要用私鑰加密，客戶端保存的是私鑰。伺服器端保存的是公鑰，其它伺服器知道公鑰沒有關系，因為客戶端不需要登錄其它伺服器。

數字簽名是為了表明信息沒有受到偽造，確實是信息擁有者發出來的，附在信息原文的後面。就像手寫的簽名一樣，具有不可抵賴性和簡潔性。

簡潔性：對信息原文做哈希運算，得到消息摘要，信息越短加密的耗時越少。

不可抵賴性：信息擁有者要保證簽名的唯一性，必須是唯一能夠加密消息摘要的人，因此必須用私鑰加密 (就像字跡他人無法學會一樣)，得到簽名。如果用公鑰，那每個人都可以偽造簽名了。

問題起源：對1和3，發信者怎麼知道從網上獲取的公鑰就是真的？沒有遭受中間人攻擊？

這樣就需要第三方機構來保證公鑰的合法性，這個第三方機構就是 CA (Certificate Authority)，證書中心。

CA 用自己的私鑰對信息原文所有者發布的公鑰和相關信息進行加密，得出的內容就是數字證書。

信息原文的所有者以後發布信息時，除了帶上自己的簽名，還帶上數字證書，就可以保證信息不被篡改了。信息的接收者先用 CA給的公鑰解出信息所有者的公鑰，這樣可以保證信息所有者的公鑰是真正的公鑰，然後就能通過該公鑰證明數字簽名是否真實了。

RSA 是目前最有影響力的公鑰加密演算法，該演算法基於一個十分簡單的數論事實：將兩個大素數相乘十分容易，但想要對其乘積進行因式分解卻極其困難，因此可以將乘積公開作為加密密鑰，即公鑰，而兩個大素數組合成私鑰。公鑰是可發布的供任何人使用，私鑰則為自己所有，供解密之用。

A 要把信息發給 B 為例，確定角色：A 為加密者，B 為解密者。首先由 B 隨機確定一個 KEY，稱之為私鑰，將這個 KEY 始終保存在機器 B 中而不發出來；然後，由這個 KEY 計算出另一個 KEY，稱之為公鑰。這個公鑰的特性是幾乎不可能通過它自身計算出生成它的私鑰。接下來通過網路把這個公鑰傳給 A，A 收到公鑰後，利用公鑰對信息加密，並把密文通過網路發送到 B，最後 B 利用已知的私鑰，就能對密文進行解碼了。以上就是 RSA 演算法的工作流程。

由於進行的都是大數計算，使得 RSA 最快的情況也比 DES 慢上好幾倍，無論是軟體還是硬體實現。速度一直是 RSA 的缺陷。一般來說只用於少量數據加密。RSA 的速度是對應同樣安全級別的對稱密碼演算法的1/1000左右。

比起 DES 和其它對稱演算法來說，RSA 要慢得多。實際上一般使用一種對稱演算法來加密信息，然後用 RSA 來加密比較短的公鑰，然後將用 RSA 加密的公鑰和用對稱演算法加密的消息發送給接收方。

這樣一來對隨機數的要求就更高了，尤其對產生對稱密碼的要求非常高，否則的話可以越過 RSA 來直接攻擊對稱密碼。

和其它加密過程一樣，對 RSA 來說分配公鑰的過程是非常重要的。分配公鑰的過程必須能夠抵擋中間人攻擊。假設 A 交給 B 一個公鑰，並使 B 相信這是A 的公鑰，並且 C 可以截下 A 和 B 之間的信息傳遞，那麼 C 可以將自己的公鑰傳給 B，B 以為這是 A 的公鑰。C 可以將所有 B 傳遞給 A 的消息截下來，將這個消息用自己的密鑰解密，讀這個消息，然後將這個消息再用 A 的公鑰加密後傳給 A。理論上 A 和 B 都不會發現 C 在偷聽它們的消息，今天人們一般用數字認證來防止這樣的攻擊。

(1) 針對 RSA 最流行的攻擊一般是基於大數因數分解。1999年，RSA-155 (512 bits) 被成功分解，花了五個月時間（約8000 MIPS 年）和224 CPU hours 在一台有3.2G 中央內存的 Cray C916計算機上完成。

RSA-158 表示如下：

2009年12月12日，編號為 RSA-768 (768 bits, 232 digits) 數也被成功分解。這一事件威脅了現通行的1024-bit 密鑰的安全性，普遍認為用戶應盡快升級到2048-bit 或以上。

RSA-768表示如下：

(2) 秀爾演算法
量子計算里的秀爾演算法能使窮舉的效率大大的提高。由於 RSA 演算法是基於大數分解 (無法抵抗窮舉攻擊)，因此在未來量子計算能對 RSA 演算法構成較大的威脅。一個擁有 N 量子位的量子計算機，每次可進行2^N 次運算，理論上講，密鑰為1024位長的 RSA 演算法，用一台512量子比特位的量子計算機在1秒內即可破解。

DSA (Digital Signature Algorithm) 是 Schnorr 和 ElGamal 簽名演算法的變種，被美國 NIST 作為 DSS (DigitalSignature Standard)。 DSA 是基於整數有限域離散對數難題的。

簡單的說，這是一種更高級的驗證方式，用作數字簽名。不單單只有公鑰、私鑰，還有數字簽名。私鑰加密生成數字簽名，公鑰驗證數據及簽名，如果數據和簽名不匹配則認為驗證失敗。數字簽名的作用就是校驗數據在傳輸過程中不被修改，數字簽名，是單向加密的升級。

橢圓加密演算法（ECC）是一種公鑰加密演算法，最初由 Koblitz 和 Miller 兩人於1985年提出，其數學基礎是利用橢圓曲線上的有理點構成 Abel 加法群上橢圓離散對數的計算困難性。公鑰密碼體制根據其所依據的難題一般分為三類：大整數分解問題類、離散對數問題類、橢圓曲線類。有時也把橢圓曲線類歸為離散對數類。

ECC 的主要優勢是在某些情況下它比其他的方法使用更小的密鑰 (比如 RSA)，提供相當的或更高等級的安全。ECC 的另一個優勢是可以定義群之間的雙線性映射，基於 Weil 對或是 Tate 對；雙線性映射已經在密碼學中發現了大量的應用，例如基於身份的加密。不過一個缺點是加密和解密操作的實現比其他機制花費的時間長。

ECC 被廣泛認為是在給定密鑰長度的情況下，最強大的非對稱演算法，因此在對帶寬要求十分緊的連接中會十分有用。

比特幣錢包公鑰的生成使用了橢圓曲線演算法，通過橢圓曲線乘法可以從私鑰計算得到公鑰， 這是不可逆轉的過程。

https://github.com/esxgx/easy-ecc

Java 中 Chipher、Signature、KeyPairGenerator、KeyAgreement、SecretKey 均不支持 ECC 演算法。

https://www.jianshu.com/p/58c1750c6f22

DH，全稱為"Diffie-Hellman"，它是一種確保共享 KEY 安全穿越不安全網路的方法，也就是常說的密鑰一致協議。由公開密鑰密碼體制的奠基人 Diffie 和 Hellman 所提出的一種思想。簡單的說就是允許兩名用戶在公開媒體上交換信息以生成"一致"的、可以共享的密鑰。也就是由甲方產出一對密鑰 (公鑰、私鑰)，乙方依照甲方公鑰產生乙方密鑰對 (公鑰、私鑰)。

以此為基線，作為數據傳輸保密基礎，同時雙方使用同一種對稱加密演算法構建本地密鑰 (SecretKey) 對數據加密。這樣，在互通了本地密鑰 (SecretKey) 演算法後，甲乙雙方公開自己的公鑰，使用對方的公鑰和剛才產生的私鑰加密數據，同時可以使用對方的公鑰和自己的私鑰對數據解密。不單單是甲乙雙方兩方，可以擴展為多方共享數據通訊，這樣就完成了網路交互數據的安全通訊。

具體例子可以移步到這篇文章： 非對稱密碼之DH密鑰交換演算法

參考：
https://blog.csdn.net/u014294681/article/details/86705999

https://www.cnblogs.com/wangzxblog/p/13667634.html

https://www.cnblogs.com/taoxw/p/15837729.html

https://www.cnblogs.com/fangfan/p/4086662.html

https://www.cnblogs.com/utank/p/7877761.html

https://blog.csdn.net/m0_59133441/article/details/122686815

https://www.cnblogs.com/muliu/p/10875633.html

https://www.cnblogs.com/wf-zhang/p/14923279.html

https://www.jianshu.com/p/7a927db713e4

https://blog.csdn.net/ljx1400052550/article/details/79587133

https://blog.csdn.net/yuanjian0814/article/details/109815473

『柒』 非對稱加密之ECC橢圓曲線（go語言實踐）

橢圓曲線密碼學(英語:Elliptic curve cryptography，縮寫為 ECC)，一種建立公開密鑰加密的演算法，基於橢圓曲線數學。橢圓曲線在密碼學中的使用是在1985年由Neal Koblitz和Victor Miller分別獨立提出的。

ECC的主要優勢是在某些情況下它比其他的方法使用更小的密鑰——比如RSA加密演算法——提供相當的或更高等級的安全。

橢圓曲線密碼學的許多形式有稍微的不同，所有的都依賴於被廣泛承認的解決橢圓曲線離散對數問題的 困難性上。與傳統的基於大質數因子分解困難性的加密方法不同，ECC通過橢圓曲線方程式的性質產生密鑰。

ECC 164位的密鑰產生的一個安全級相當於RSA 1024位密鑰提供的保密強度，而且計算量較小，處理速度 更快，存儲空間和傳輸帶寬佔用較少。目前我國 居民二代身份證 正在使用 256 位的橢圓曲線密碼，虛擬 貨幣 比特幣 也選擇ECC作為加密演算法。

具體演算法詳解參考:

『捌』 密碼學相關知識梳理

密碼學是研究編制密碼和破譯密碼的技術科學。

密碼學的歷史最早可以追溯到幾千年以前，古今中外都有密碼學運用的記載，從歷史看，戰爭很大程度給密碼學提供了應用環境，推動了密碼學的發展，密碼學按照發展歷程，大體可以分為三個階段，手工加密、機械加密和計算機加密階段，下面是近代密碼學的一些重要進展。
1949年，資訊理論始祖克勞德·艾爾伍德·香農（Claude Elwood Shannon）發表了《保密系統的通信理論》一文，把密碼學建立在嚴格的數學基礎之上，奠定理論基礎，從此成為真正的科學。
1976年，密碼學專家惠特菲爾德·迪菲（Bailey Whitfield Diffie）和馬丁·赫爾曼（Martin Edward Hellman）兩人發表了《密碼學的新方向》一文，解決了密鑰管理的難題，把密鑰分為加密的公鑰和解密的私鑰，提出了密鑰交換演算法Diffie-Hellman。
1977年，美國國家標准技術研究所制定數據加密標准（Data Encryption Standard ）,將其頒布為國家標准。
1977年，麻省理工學院的羅納德·李維斯特（Ron Rivest）、阿迪·薩莫爾（Adi Shamir）和倫納德·阿德曼（Leonard Adleman）一起提出RSA加密演算法，RSA就是他們三人姓氏開頭字母拼在一起組成的。
1997年4月，美國ANSI發起徵集AES（advanced encryption standard）的活動，並為此成立了AES工作小組，經過幾年的時間篩選，最終採用了由比利時的Joan Daemen和Vincent Rijmen設計的Rijndael演算法，並在2002年5月26日成為有效的加密標准。

按密碼體制劃分：對稱密碼體制密碼學和非對稱密碼體制密碼學對應的有對稱密碼演算法和非對稱密碼演算法。

消息摘要演算法又稱散列演算法，其核心在於散列函數的單向性，即通過散列函數可獲得對應的散列值，但不可通過該散列值反推其原始信息，這是消息摘要演算法的安全性的根本所在，我們通常使用該演算法判斷數據的完整性。

消息摘要演算法我們常見比如MD(Message Digest）、SHA(Secure Hash Algorithm)、HMAC(Hash Message Authentication Code)等，常用於驗證數據的完整性，是數字簽名演算法的核心演算法。

我們以微信支付的介面調用分析一下摘要演算法怎麼應用的，首先可以打開微信支付如下相關文檔：
微信支付統一下單介面文檔
微信支付簽名過程

對稱加密簡單的說就是加密和解密使用同一個密鑰，解密演算法是加密演算法的逆運算。

對稱加密演算法主要有DES、DES演算法的變種DESede、DES替代者AES演算法、IDEA、PBE等

非對稱加密演算法稱為雙鑰或公鑰加密演算法，跟對稱加密演算法不同的是，對稱加密演算法只一個密鑰，非對稱加密演算法 一個公鑰和一個私鑰，一個用於加密，另外一個用於解密。
簡單的說：一對密鑰公鑰A和私鑰B，A加密只能B解密，B加密只能A解密。

非對稱加密演算法源於DH演算法（Diffie-Hellman,密鑰交換演算法）由W.Diffie和 M.Hellman共同提出,該演算法為非對稱加密演算法奠定了基礎，下面我們先來了解下密鑰交換演算法DH和ECDH演算法。
為什麼需要密鑰交換演算法？前面我們提到對稱加密演算法加解密都是用同一個密鑰，我們可以想一下，我們怎樣能安全的把一個密鑰給到對方呢？比如我們經常用到HTTPS，大家都說HTTPS加密了是安全的，那它加密的密鑰怎麼來的呢？很顯然我們在訪問一個https地址的時候，事先並沒有密鑰，訪問過程中客戶端跟服務端通過握手協議協商出來的密鑰，如果服務端直接把密鑰在網路上傳輸那肯定不安全的，所以這過程到底發生了什麼？後面專門分析https的時候會詳細寫，這里先了解下該演算法。
DH密鑰交換演算法的安全性基於有限域上的離散對數難題
ECDH密鑰交換演算法是基於橢圓曲線加密

從上面圖中可以看出，DH&ECDH密鑰交換演算法交互雙方都會向對方公開一部分信息，即所謂的公鑰，這部分即使被別人拿到了也不會威脅到最終的密鑰，這里很關鍵的一點是甲乙兩方公布的公鑰是不相同的，但是最終生成的密鑰兩邊是一致的，這里是利用的演算法原理，有興趣的可以去查閱詳細的演算法公式，因為最終的密鑰不需要傳輸給對方，所以很大程度保證安全性。
非對稱加密演算法：
比較典型的非對稱加密演算法有RSA、ECC、ElGamal,RSA演算法基於大數因子分解難題，而ElGamal和ECC演算法則是基於離散對數難題。

從上面消息傳遞模型我們可以看出，非對稱加密演算法遵循「私鑰加密，公鑰解密」和「公鑰加密，私鑰解密」的原則，但是有一點需要注意，公鑰是公開的，所以用在什麼場景是需要根據該演算法的特徵來考慮的，比如既然公鑰是公開的，你用私鑰加密敏感數據傳遞給第三方合適么？顯然不合適，因為公鑰公開的，別人都可以拿到公鑰，也就意味著你加密的數據都可以解密，所以適合的場景比如私鑰加密，公鑰只是用來驗證加密的內容，每個人都可以來驗證，該場景是不在乎加密內容被其它攻擊者看到的，甚至說內容本來就是公開的，對於接收者用公鑰確保內容沒有被篡改即可，所以我們通常說非對稱演算法「私鑰簽名，公鑰驗證簽名」，另外一點，「公鑰加密，私鑰解密」，因為私鑰只有我們自己手上有，所以理論上也只有我們自己可以解密，這樣是安全的，https證書驗證以及握手協議過程中會體現這一點。

數字簽名演算法可以看做是一種帶有密鑰的消息摘要演算法，並且這種密鑰包含了公鑰和私鑰。也就是說數字簽名演算法是非對稱加密演算法和消息摘要演算法的結合體，遵循「私鑰簽名，公鑰驗證」的簽名認證方式。
數字簽名演算法是公鑰基礎設施（Public Key Infrastructure,PKI）以及許多網路安全機制（SSL/TLS,VPN等）的基礎。
數字簽名演算法要求能夠驗證數據完整性、認證數據來源，並起到抗否認的作用。

數字簽名演算法主要包括RSA、DSA、ECDSA共3種演算法，其中RSA演算法源於整數因子分解問題，DSA和ECDSA演算法源於離散對數問題。

我們以螞蟻金服開放平台上介面簽名方案為例，詳細說明可以打開如下文檔：
螞蟻開放平台簽名專區

『玖』 密碼學基礎2：橢圓曲線密碼學原理分析

首先要說明的一點是，橢圓曲線不是橢圓。橢圓方程是下面這樣的：

而通常我們討論的橢圓曲線的曲線方程是一個二元三次方程，它有多種形式，在橢圓曲線密碼體系中，最常用的是如下的Weierstrass通用式(curve25519 等其他類型的橢圓曲線本文不討論)：

之所以取名叫橢圓曲線，是因為該曲線方程跟求橢圓弧長的積分公式相似。從曲線方程和圖像易知，橢圓曲線關於X軸對稱。判定式不等於零是為了橢圓曲線不存在奇異點，即處處光滑可導，這樣才能進行橢圓曲線上的加法運算。下面是一些適合用於加密的橢圓曲線，其中 。

橢圓曲線加密演算法涉及數學中的群論、有限域等內容，這節簡要介紹下相關數學理論。亦可以跳過直接看第3節，遇到相關名詞再查閱即可。

在討論群之前，先說說集合。集合簡單來說就是把一堆東西放在一起，如自然數集合。當然光有一堆東西還不夠，東西之間相互作用才能更好的描述大千世界。於是，自然數集合通過加減運算衍生出整數集合、整數集合經過乘除又可以衍生出有理數，而後通過無理數的加入又衍生出實數集合、負數開方引入了復數集合。群則是集合和一個二元運算。

而如果再滿足交換律，則該群就被稱為是一個阿貝爾群。

根據群的定義，整數的加法運算 就是一個群，而且還是一個阿貝爾群。而自然數的加法運算 就不是一個群。整數加法運算構成群，因為它滿足群的定義：整數加法的封閉性、結合律、交換律都成立。整數加法運算中單位元是 0。所有整數 n 都有加法逆元 -n。

在密碼學中一般都需要一個有限的群，定義如下:

為了使一個結構同時支持四種基本算術(即加減乘除)，我們需要一個包含加法和乘法群的集合，這就是域。當一個集合為域的時候，我們就能在其中進行基本算術運算了。

所以域中元素只要形成加法群和乘法群並滿足分配律就行，因為群中元素都有逆元，減法/除法可以轉換為加/乘元素的逆元實現。實數集合 是一個域，加法群中單位元是 0，每個實數 都有加法逆元 ，乘法群中單位元是 ，每個非零實數都有乘法逆元 。而整數集合就不是域，因為大部分元素沒有乘法逆元，不能構成一個乘法群。

在密碼學中，通常只對有限元素的域感興趣，這種域稱為有限域(Finite Field)。有限域中我們經常用到的是素數域，所謂素數域，就是階為素數的有限域。 比如當 p 為素數時，整數環 就是一個素數域，可以記作 。在素數域 中進行算術運算，需要遵守整數環的規則，即加法是模 p 加法，而乘法是模 p 乘法。

例如對於 有：

橢圓曲線上的點經過一種特定的加法運算可以讓橢圓曲線在實數域構成一個群。

無窮遠點 ：定義一個無窮遠點 ，即經過橢圓上任意一點的與X軸垂直的直線都經過該點。可能有人疑惑垂直於X軸的直線是平行線，為啥可以定義為都經過 點？因為在非歐幾何中，可認為平行線在無窮遠處會交於一點。

橢圓曲線點加法 ：橢圓曲線上經過 和 兩個點的直線與橢圓曲線的交點記作 ，根據定義有 以及 。繼而定義橢圓曲線點加法： ，即加法結果是經過點 且與 X 軸垂直的直線與橢圓曲線的另外一個交點，簡單來說，就是交點 關於 X 軸的對稱點。

橢圓曲線群：定義為橢圓曲線在實數域上的點集以及點加法

由此可知，橢圓曲線上的點在橢圓曲線加法運算上構成了一個阿貝爾群。增加了單位元後，橢圓曲線方程改為：

由定義可知， ，所以，最終加法只需要計算交點 的逆元 即可。 幾種特殊情況說明：

上一節定義了橢圓曲線幾何上意義的點加法，需要轉換為代數加法以方便計算。 要注意的是，這並不是兩個點的坐標簡單相加 。

假設直線 PQ 的斜率 ，然後將直線方程 代入曲線可以得到： , 轉換成標準式，根據韋達定理 ，即而可求得 ，想了解具體推導過程的可參見 [cubic-equations] 。

斜率 計算需要區分兩種情況，當 P=Q 時求橢圓曲線在 P 點的切線斜率(求導)即可：

可以簡單驗證，比如橢圓曲線是 ，通過參考資料1的 [可視化工具] 可得 。容易驗證，與代數加法公式計算結果一致。

對於特殊情況 中有一個是切點的情況，如 ，計算方式不變，易得 。而對於特殊情況 ，採用切線斜率亦可驗證公式正確。

在實際加密演算法中，我們通常需要多次通過橢圓曲線加法來實現一次加密，如下圖所示：

圖中打點的過程就是：

而在實際加密演算法中，我們常常是使用一個點自己疊加，即初始直線變成橢圓曲線的切線即可，像下面這樣：

我們定義對一個點 P 進行 n 次加法得到 nP，稱之為標量乘法。如前面例子中 。

不過，當 n 很大時，執行 n 次加法需要 時間，效率有問題。 因為橢圓曲線點加法在實數域構成阿貝爾群，滿足交換律和結合律，於是可以通過 [Double-and-add] 演算法進行優化 。比如 ，其二進製表示為 ，通過優化只要7次倍乘和4次加法計算即可，時間復雜度降到 。這是一個很好的單向函數，正向計算容易，而反向和蠻力計算復雜。

令 ，則 Q 作為公鑰，n 為私鑰。如果要破解該密鑰，問題就是 "Q = nP，如果已知 P 和 Q，如何求解 n"? 這個問題是比較困難的。不過由於在實數域上曲線連續，可能會更容易找到一些規律進行破解。而且實數域上數值大小沒有限制、浮點數等問題而導致計算效率問題，在實際應用中常將橢圓曲線限制到一個有限域內，將曲線變成離散的點，這樣即方便了計算也加大了破解難度。

前面提到為了安全性和便於實現，需要將橢圓曲線限制到一個有限域內，通常用的是素數域 (即對於點 為素數)。於是破解就會變成一個離散對數問題，這比連續曲線上的對數問題會難很多。素數域下橢圓曲線定義如下：

下面是曲線 和 的圖像。可以發現，橢圓曲線變成了離散的點，且關於 對稱。

定義 上橢圓曲線點加法 如下，公式跟實數域上相比只是多了模 操作。

斜率 m 計算同樣分兩種情況：

橢圓曲線在素數域 上的點加法依然構成阿貝爾群。單位元依舊是無窮遠點，元素 的逆元變成 。而交換律、結合律、封閉性則可以通過素域上的模加法、模乘法來證明 。實數域的橢圓曲線點加法定義是有明確幾何意義的，從幾何上好證明。而橢圓曲線在 就沒有明顯的幾何意義了，觀察可發現 三點滿足 ，群律的證明過於繁瑣，略去(其實是沒有找到一個簡易的證明)。

以前面曲線為例， ，則有 ，且 和 都在橢圓曲線上。從圖形上看， 在直線 上。

在有限域下，橢圓曲線加法群的元素是有限的，元素數目就是群的階。

如橢圓曲線 ，其在素數域 中元素有 ，階為24(23個素數域中的點 + 1個無窮遠點)，如果 p 很大的話，則通過蠻力計算階是很難的，好在使用 [Schoof演算法] 可以在多項式時間內計算出群的階。計算橢圓曲線在有限域上點的數目可以參見 [Counting points on elliptic curves] 。

Schoof演算法運用了 Hasses 定理。Hasses定理給出了橢圓曲線在 的階的范圍，可以看出，當 p 很大時，階跟 p 的值是比較接近的。

跟實數域一樣，在素數域裡面也是選取一個點 P，然後計算倍乘 nP 作為公鑰。還是以 為例， ，我們採用素數域下新的計算公式計算 。

可以發現 ，即 P 的標量乘法得到的點集是原橢圓曲線群的一個子集，則它是原橢圓曲線群的一個子群，而且是循環子群。子群中元素個數稱為子群的階(示例子群的階為8)，點 P 稱為該子群的基點或者生成元。循環子群是橢圓曲線密碼體系的基礎，我們期望子群中元素越多越好，如何找到一個合適的子群尤為重要。

首先要解決一個問題，就是已知 下的橢圓曲線上的點 P，如何求得 P 的倍乘運算後生成的子群的階? 根據拉格朗日的群論定理，子群的階是父群的階的約數。求解曲線上點 P 生成的子群的階可以用下面方法：

以示例曲線為例，父群的階是 ，則以曲線上的點生成的子群的階只能是 。對於點 ，故其生成的子群的階就是 8，而點 生成的子群的階則正好等於父群的階24。

在加密演算法中，我們期望找到一個階高的子群。不過，通常不是先去找個基點，然後計運算元群的階，因為這樣過於不確定，演算法上不好實現。相反地，先選擇一個大的子群階，然後再找生成該子群的一個基點就容易多了。

前面提到，子群的階 n 是父群的階 N 的約數，即有 ，h 是一個整數，我們稱之為子群的余因子(cofactor)。因為 ，所以有:

通常會選擇一個素數作為子群的階，即 n 是素數。可以發現，點 生成了階為 n 的子群( 除外，因為這個子群的階為1)，不等於 的點 就是我們尋找的基點。具體步驟如下：

需要注意，上面演算法里的 n 必須是素數，否則計算的基點 G 生成的子群的階可能是 n 的約數而不是 n，不符合要求 。以曲線 為例， ，我們選擇 ，則 ，隨機選取一個點 ，計算 ，恰好滿足要求。

如前所述，橢圓曲線加密演算法工作在素數域下的橢圓曲線循環子群中，需要的域參數(Domain Parameter)包括 ：

如比特幣用來做數字簽名中採用的橢圓曲線 [secp256k1] 的域參數如下：

『拾』 ECC橢圓曲線密碼應用

1背景簡介
隨著通訊網路特別是Internet的高速發展，利用網路作為信息交流和信息處理變得越來越普遍，社會的傳統事務和業務運作模式受到前所未有的沖擊。目前，無論是國家政府還是企業都正融入這場網路革命中，從其原來的傳統經營模式向網路模式演化。未來的電子政務、電子商務、電子業務將成為不可逆轉的發展趨勢。在與日俱增的網路活動中，人們越來越關心信息安全這個問題。這集中體現在：

（1）網路的身份認證——確認網路客戶的真實身份
（2）信息和數據的保密性——個人或系統機密信息和數據保護
（3）信息和數據完整性——防止不合法的數據修改
（4）不可抵賴性——網路環境下行為的事後的不可抵賴（數字簽名）
信息安全中最核心的技術是密碼技術，基本上可分為序列密碼、對稱密碼（又稱分組密碼）、非對稱密碼（又稱公鑰密碼）三種。

非對稱密碼演算法是支撐解決以上所涉的四個關鍵方面的問題的核心。目前越來越流行的是基於PKI體系模型的解決方案。在PKI體系模型中，客戶端需要一較好的個人信息安全載體，智能卡或智能密碼鑰匙將是一較理想的方式，都必須支持公鑰演算法，而ECC是最適合使用在這一資源受限制的客戶端產品中。

2 橢圓曲線密碼演算法ECC

自公鑰密碼問世以來，學者們提出了許多種公鑰加密方法，它們的安全性都是基於復雜的數學難題。根據所基於的數學難題來分類，有以下三類系統目前被認為是安全和有效的：

（1）大整數因子分解系統(代表性的有RSA)，

（2）有限域（數學中的一種代數結構）離散對數系統(代表性的有DSA)，

（3）有限域橢園曲線離散對數系統(ECC)。

當前最著名、應用最廣泛的公鑰系統RSA是由Rivet、Shamir、Adelman提出 的(簡稱為RSA系統)，它的安全性是基於大整數素因子分解的困難性，而大整數因子分解問題是數學上的著名難題，至今沒有有效的方法予以解決，因此可以確保RSA演算法的安全性。RSA系統是公鑰系統的最具有典型意義的方法，大多數使用公鑰密碼進行加密和數字簽名的產品和標准使用的都是RSA演算法。RSA方法的優點主要在於原理簡單，易於使用。但是，隨著分解大整數方法的進步及完善、計算機速度的提高以及計算機網路的發展（可以使用成千上萬台機器同時進行大整數分解），作為RSA加解密安全保障的大整數要求越來越大。為了保證RSA使用的安全性，其密鑰的位數一直在增加，比如，目前一般認為RSA需要1024位以上的字長才有安全保障。

但是，密鑰長度的增加導致了其加解密的速度大為降低，硬體實現也變得越來越難以忍受，這對使用RSA的應用帶來了很重的負擔，對進行大量安全交易的電子商務更是如此，從而使得其應用范圍越來越受到制約。DSA（Data Signature Algorithm）是基於有限域離散對數問題的數字簽名標准，它僅提供數字簽名，不提供數據加密功能。安全性更高、演算法實現性能更好的公鑰系統橢圓曲線加密演算法ECC（Elliptic Curve Cryptography）基於有限域上橢圓曲線的離散對數計算困難性。人類研究橢圓曲線已有百年以上的歷史，但真正把其應用到密碼學中是1985年由Koblitz(美國華盛頓大學)和Miller(IBM公司) 兩人提出。定義在有限域（Fp 或F(2m)）的橢圓曲線(y2=x3+ax+b)上的點（x,y），再加上無窮點O，如按一定的規則運算（估且稱為乘法）將組成一個群（數學中的一種代數結構）。有限域上橢圓曲線乘法群也有相對應的離散對數計算困難性問題。因此，許多公開密碼系統都是基於此問題發展出來的，如類似ELGamal,DSA等密碼系統的ECES，ECDSA。

3 橢圓曲線加密演算法ECC的優點

橢圓曲線加密演算法ECC與RSA方法相比有著很多技術優點：

●安全性能更高

加密演算法的安全性能一般通過該演算法的抗攻擊強度來反映。ECC和其他幾種公鑰系統相比，其抗攻擊性具有絕對的優勢。橢圓曲線的離散對數計算困難性（ECDLP）在計算復雜度上目前是完全指數級，而RSA 亞指數級的。這體現ECC比RSA的每bit安全性能更高。

●計算量小和處理速度快

在一定的相同的計算資源條件下，雖然在RSA中可以通過選取較小的公鑰（可以小到3）的方法提高公鑰處理速度，即提高加密和簽名驗證的速度，使其在加密和簽名驗證速度上與ECC有可比性，但在私鑰的處理速度上（解密和簽名），ECC遠比RSA、DSA快得多。因此ECC總的速度比RSA、DSA要快得多。同時ECC系統的密鑰生成速度比RSA快百倍以上。因此在相同條件下，ECC則有更高的加密性能。

●存儲空間佔用小

ECC的密鑰尺寸和系統參數與RSA、DSA相比要小得多。160位 ECC與1024位 RSA、DSA有相同的安全強度。而210位 ECC則與2048bit RSA、DSA具有相同的安全強度。意味著它所佔的存貯空間要小得多。這對於加密演算法在資源受限環境上（如智能卡等）的應用具有特別重要的意義。

●帶寬要求低

當對長消息進行加解密時，三類密碼系統有相同的帶寬要求，但應用於短消息時ECC帶寬要求卻低得多。而公鑰加密系統多用於短消息，例如用於數字簽名和用於對對稱系統的會話密鑰傳遞。帶寬要求低使ECC在無線網路領域具有廣泛的應用前景。

4橢圓曲線加密演算法ECC的相關標准

ECC的這些特點使它在某些領域（如PDA、手機、智能卡）的應用將取代RSA，並成為通用的公鑰加密演算法。許多國際標准化組織(政府、工業界、金融界、商業界等)已將各種橢圓曲線密碼體製作為其標准化文件向全球頒布。ECC標准大體可以分為兩種形式：一類是技術標准，即描述以技術支撐為主的ECC體制，主要有IEEEP1363、ANSI X9.62、ANSI X9.63、SEC1、SEC2、FIP 186-2、ISO/IEC 14888-3。規范了ECC的各種參數的選擇，並給出了各級安全強度下的一組ECC參數。另一類是應用標准，即在具體的應用環境中建議使用ECC技術，主要有ISO/IEC 15946、IETF PKIX、IETF TLS、WAP WTLS等。在標准化的同時，一些基於標准（或草案）的各種橢圓曲線加密、簽名、密鑰交換的軟、硬體也相繼問世。美國RSA數據安全公司在1997年公布了包含ECC的密碼引擎工具包BSAFE 4.0; 以加拿大Certicom為首的安全公司和工業界聯合也研製、生產了以橢圓曲線密碼演算法為核心的密碼產品，還提出了各種安全條件下對橢圓曲線離散對數攻擊的懸賞挑戰。可以相信，ECC技術在信息安全領域中的應用會越來越廣。