ecc256比特幣

① 橢圓曲線加密演算法原理

橢圓曲線加密演算法，簡稱ECC，是基於橢圓曲線數學理論實現的一種非對稱加密毀核演算法。

相比RSA，ECC優勢是可以使用更短的密鑰，來實現與RSA相當或更高的安全，RSA加密演算法也是純擾一種非對稱加密演算法，在公開密鑰加密和電子商業中RSA被廣泛使用。據研究，160位ECC加密安全性相當於1024位RSA加密，210位ECC加密安全性相當於2048位做余旦RSA加密（有待考證）。

橢圓曲線也可以有運算，像實數的加減乘除一樣，這就需要使用到加群。19世紀挪威的尼爾斯·阿貝爾抽象出了加群（又叫阿貝爾群或交換群）。數學中的群是一個集合，我們為它定義了一個「加法」，並用符號+表示。假定群用 表示，則加法必須遵循以下四個特性：

• 封閉性：如果a和b都是 的成員，那麼a+b也是 的成員；

• 結合律：(a + b) + c = a + (b + c);

• 單位元：a+0=0+a=a，0就是單位元；

• 逆元：對於任意值a必定存在b，使得a+b=0。

如果再增加一個條件，交換律：a + b = b + a，則稱這個群為阿貝爾群，根據這個定義整數集是個阿貝爾群。

② 橢圓曲線加密演算法中的密謀

公鑰加密演算法有兩種，RSA 和 ECC，RSA 簡單易懂但效率低，ECC 效率高，用 256 位秘鑰抵得過 RSA 3072 位秘鑰，但 ECC 數學原理復雜，實現也比 RSA 難。

要理解 ECC 橢圓曲線加密演算法，就得順藤摸瓜，一路搞定下面這些原理。

於是得到了這樣的曲線：

這個方程式用來加解密的過程，就不解釋了，網上資料不少，密碼學的書中也有。

其原理基於，射影平面上的加法演算法，其正向過程是簡單容易的，而加法的逆向過程，則是困難的。我們可以用打檯球來比喻，確定一個球的初始位置為 p1，對 p1 進行 n 次擊球（假設 n 次擊球的力度和方向一致），最終獲得位置為 p2。已知 p1 和 n，則獲得 p2 非常容易，進行 n 次擊球便可。但若已知 p1 和 p2，要倒推出 n 來，則很難。這個道理，人人皆知。 橢圓曲線在射影平面上的加法之不可逆，和上面的檯球游戲類似。

用來加解密和簽名的 ECC 曲線，由如下幾個參數確定：(p,a,b,G,n,h)。 p 便是有限域的整數范圍， a，b 則是確定曲線的形狀， G 是曲線上選擇的初始點，n 則是用來進行加法的次數， h 是協因子，不知道幹嘛用的，一般取 1。

比特幣所用 Secp256k1 曲線的參數如下：

p = 2^256 − 2^32 − 2^9 − 2^8 − 2^7 − 2^6 − 2^4 − 1 = 2^256 – 2^32 – 977

a = 0

b = 7

這就是中本聰挑選的曲線，並非一條流行通用的曲線。去掉模運算，用 x y 方程簡單表示為 y^2 = x^3 + 7。

Secp256k1 中 「sec」 的意思是 Standards for Efficient Cryptography，"p" 則代表有限域參數 p，256 代表 p 的位數，而 「k」 則大有深意。

「k」 代表 Koblitz，這是橢圓曲線加密演算法發明人 Koblitz 的名字，在這里指的一類曲線，這一類曲線的參數是刻意挑選出來的。比如上面的 a 和 b，一個 0，一個 7，一看就知道是刻意挑選出來的。

k 後面的 1 代表序號。

與 「k」 對應的叫 「r」，所謂 r 指代 Random，就是隨機數的意思。大家就明白了，曲線所用參數是隨機挑選出來的。比如 Secp256r1 的參數如下：

p = 2^224(2^32 − 1) + 2^192 + 2^96 − 1

a = 97853948

b = 7401291

這個 Secp256r1 還有一個名字，叫 NIST P256，NIST 是 National Institute of Standards and Technology，也就是美國國家標准技術委員會，隸屬商務部，專門為政府機構制定技術標准。所以，Secp256r1 那算是閃耀著官方光環的技術。這個標準是 1999 年 NIST 發布的。

既然 p，a，b這些參數都是隨機挑選出來的，那麼自然應該更安全了。理論上是這樣的，但「隨機」 這兩個字可不是那麼容易的，不是上嘴唇一碰下嘴唇就能出來一個隨機數。 計算機里的隨機數一直是個難題。 

Secp256r1 的隨機數生成是用哈希演算法 SHA1 實現的，用SHA1演算法對某個字元串進行哈希，每次都能生成非常隨即的數字。 而 Secp256r1 的 p，a，b 做 SHA1 的字元串是：。

密碼學界以及加密學應用技術行業的疑心由此而起：NIST 為何挑選了這個字元串？

哈希運算的特點，大家都清楚，NIST 無法根據一條既定曲線，返過去計算出 SHA1 的種子字元串。

所以大家就懷疑，NIST 很可能測試了無數的種子字元串，最終選擇了一條較弱的曲線。這是一種暴力的挑選方法，據傳 NIST 測試了 10 億條曲線。2014 年密碼學者 Daniel J. Bernstein1 和 Tung Chou 便發表過文章 「How to manipulate curve standards: a white paper for the black hat」 介紹了如何操控 ECC 曲線標準的制定。

大家的擔心雖然並無實證，但 NIST 在橢圓曲線上做手腳，並非第一次，而且之前那次是有實錘證據的。2007 年 NIST 發布了 130 頁的技術標准文書： NIST Special Publication 800-90，其中介紹了 「Deterministic Random Bit Generators」，也就是隨機數生成的技術，和上面所說用 SHA1 生成隨機數類似。 介紹的技術中，有一種叫 Dual_EC_DRBG，也就是用雙橢圓曲線生成隨機數的技術。 技術原理和用橢圓曲線做加法進行加密類似。

還用檯球做比，為了生成隨機數，在巨大巨大的 「有限域」 檯球桌上擺放兩個檯球在 p1 和 p2 位置。對在 p1 的第一個檯球進行 n 次擊打，n是一個秘密數字，獲得位置 p1『，這就是生成的隨機數。完事後 p2 也進行 n 次擊打，獲得位置 p2』，將 p2『 替代 n，作為下一次生成隨機數的秘密數字。最後，將 p1 和 p2 擺回最初的位置 p1 和 p2，等待下次。

從原理上來說，這種演算法生成隨機數是沒問題的。就是比起其它隨機數生成演算法，效率要慢一些，有些密碼學家就提出這個問題，這種演算法的效率比該標准中的其他演算法要慢三個數量級。

詭異的是，Dual_EC_DRBG 是 NSA 推薦到 NIST，並強力支持的。 NSA 是誰？大名鼎鼎的美國國家安全局，與美國民間密碼學界斗爭多年的強力部門。

2007 年，牛逼的 CRYPTO 大會上，密碼學者 Dan Shumow 和 Niels Ferguson 指出，Dual_EC_DRBG 不僅是慢的問題，它有後門啊，NIST 指定的演算法也許沒問題，但 P1 和 P2 這兩個初始位置有問題：這兩個參數之間是有關系的，可以推算的。

這真是打了 NIST 和 NSA 的臉。當然，密碼學者們並沒有實錘證據，到底這個是 NIST 和 NSA 惡意設計，還是一個為他們工作的科研人員私下作惡。

直到 2013 年棱鏡門爆發，斯諾登披露的政府文件顯示，NSA 刻意在加密演算法中植入後門。之後，路透社披露，NSA 收買了 RSA 公司，在其軟體中植入 Dual_EC_DRBG，以利於破解加密技術，對互聯網信息進行竊聽。一切水落石出真相大白，就是 NSA 協同 NIST 搗的鬼。

比特幣中對 Secp256r1 棄而不用，選擇了 Secp256k1，而中本聰開發比特幣軟體，是在 2008 年之前。所以應當是在 2007 年 CRYPTO 大會上對 Dual_EC_DRBG 的責難，引起了中本聰的警覺。那時候棱鏡門還沒爆發，對於 NSA 的惡意操縱，還並沒有證據。

機構作惡，人們無可奈何，無人臉紅，也無人為其負責。放個後門，放了就放了吧，大家躲著走就是。

③ 理解橢圓曲線加密演算法

橢圓曲線加密演算法，即：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)。

簽名介面：

驗證介面:

一個例子：