橢圓曲線加密演算法在比特幣

1. 理解橢圓曲線加密演算法

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

簽名介面：

驗證介面:

一個例子：

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

公鑰加密演算法有兩種，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 的惡意操縱，還並沒有證據。

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

3. 比特幣演算法原理

比特幣演算法主要有兩種，分別是橢圓曲線數字簽名演算法和SHA256哈希演算法。

橢圓曲線數字簽名演算法主要運用在比特幣公鑰和私鑰的生成過程中，該演算法是構成比特幣系統的基石。SHA-256哈希演算法主要是運用在比特幣的工作量證明機制中。

比特幣產生的原理是經過復雜的運演算法產生的特解，挖礦就是尋找特解的過程。不過比特幣的總數量只有2100萬個，而且隨著比特幣不斷被挖掘，越往後產生比特幣的難度會增加，可能獲得比特幣的成本要比比特幣本身的價格高。

比特幣的區塊由區塊頭及該區塊所包含的交易列表組成，區塊頭的大小為80位元組，由4位元組的版本號、32位元組的上一個區塊的散列值、32位元組的 Merkle Root Hash、4位元組的時間戳（當前時間）、4位元組的當前難度值、4位元組的隨機數組成。擁有80位元組固定長度的區塊頭，就是用於比特幣工作量證明的輸入字元串。不停的變更區塊頭中的隨機數即 nonce 的數值，並對每次變更後的的區塊頭做雙重 SHA256運算，將結果值與當前網路的目標值做對比，如果小於目標值，則解題成功，工作量證明完成。

比特幣的本質其實是一堆復雜演算法所生成的一組方程組的特解（該解具有唯一性）。比特幣是世界上第一種分布式的虛擬貨幣，其沒有特定的發行中心，比特幣的網路由所有用戶構成，因為沒有中心的存在能夠保證了數據的安全性。

4. 什麼是比特幣加密技術

比特幣和區塊鏈的誕生需要依賴於很多核心技術的突破：一是拜占庭容錯技術；二是非對稱加密技術；三是點對點支付技術。下面會依次介紹。
拜占庭容錯技術
比特幣和區塊鏈誕生的首要難點在於如何創建分布式共識機制，也就是菜斯利·蘭伯特等人1982年提出的拜占庭將軍問題。所謂拜占庭將軍問題是指，把戰爭中互不信任的各城邦軍隊如何達成共識並決定是否出兵的決策過程。延伸至計算機領域，試圖創建具有容錯性的分布式系統，即使部分節點失效仍可確保系統正常運行，也可讓多個基於零信任基礎的節點達成共識，並確保信息傳遞的一致性。
中本聰所提到的「拜占庭將軍問題」解決方法起始於亞當﹒拜克在1997年發明的哈希現金演算法機制，起初該設計是用於限制垃圾郵件發送與拒絕服務攻擊。2004年，密碼朋克運動早期和重要成員哈爾·芬尼將亞當﹒拜克的哈希現金演算法改進為可復用的工作量證明機制。他們的研究又是基於達利亞·馬凱與邁克爾·瑞特的學術成果：拜占庭容錯機制。正是哈爾·芬尼的可復用的工作量證明機制後來成為比特幣的核心要素之一。哈爾·芬尼是中本聰的最早支持者，同時也是第一筆比特幣轉賬的接受者，在比特幣發展的早期與中本聰有大量互動與交流。
非對稱加密技術
比特幣的非對稱加密技術來源於以下幾項密碼學的技術創新：1976年，Sun公司前首席安全官Whitfield Diffie與斯坦福大學教授Martin Hell，在開創性論文《密碼學的新方向》首次提出公開鑰匙密碼學的概念，發明了非對稱加密演算法。1978年省理工學院的倫納德·阿德曼、羅納德·李維斯特、阿迪·薩莫爾三名研究人員，共同發明了公開鑰匙系統「RSA」可用於數據加密和簽名，率先開發第一個具備商業實用性的非對稱RSA加密演算法。1985年，Neal Koblitz和Victor Miller倆人，首次提出將橢圓曲線演算法（ECC），應用於密碼學，並建立公鑰加密的演算法，公鑰密碼演算法的原理是利用信息的不對稱性，公鑰對應的是私鑰，私鑰是解開所有信息的鑰匙，公鑰可以由私鑰反推算出。ECC能夠提供比RSA更高級別的安全。比特幣使用的就是橢圓曲線演算法公鑰用於接收比特幣，而私鑰則是比特幣支付時的交易簽名。這些加密演算法奠定了當前非對稱加密理論的基礎，被廣泛應用於網路通信領域。但是，當時這些加密技術發明均在NSA嚴密監視的視野之內。NSA最初認為它們對國家安全構成威脅，並將其視為軍用技術。直到20世紀90年代末，NSA才放棄對這些非對稱加密技術的控制，RSA演算法、ECC演算法等非對稱加密技術最終得以走進公眾領域。
不過，中本聰並不信任NSA公布的加密技術，在比特幣系統中沒有使用RSA公鑰系統，原因除了ECC能夠提供比RSA更高級別的安全性能外，還擔心美國安全部門在RSA留有技術後門。2013年9月，斯諾登就曾爆料NSA採用秘密方法控制加密國際標准，比特幣採用的RSA可能留有後門，NSA能以不為人知的方法弱化這條曲線。所幸的是，中本聰神一般走位避開了RSA的陷阱,使用的加密技術不是NSA的標准，而是另一條鮮為人知的橢圓曲線，這條曲線並不在美國RSA的掌握之下。全世界只有極少數程序躲過了這一漏洞，比特幣便是其中之一。

5. 高中生如何理解比特幣加密演算法

加密演算法是數字貨幣的基石，比特幣的公鑰體系採用橢圓曲線演算法來保證交易的安全性。這是因為要攻破橢圓曲線加密就要面對離散對數難題，目前為止還沒有找到在多項式時間內解決的辦法，在演算法所用的空間足夠大的情況下，被認為是安全的。本文不涉及高深的數學理論，希望高中生都能看懂。

密碼學具有久遠的歷史，幾乎人人都可以構造出加解密的方法，比如說簡單地循環移位。古老或簡單的方法需要保密加密演算法和秘鑰。但是從歷史上長期的攻防斗爭來看，基於加密方式的保密並不可靠，同時，長期以來，秘鑰的傳遞也是一個很大的問題，往往面臨秘鑰泄漏或遭遇中間人攻擊的風險。

上世紀70年代，密碼學迎來了突破。Ralph C. Merkle在1974年首先提出非對稱加密的思想，兩年以後，Whitfield Diffie和Whitfield Diffie兩位學者以單向函數和單向暗門函數為基礎提出了具體的思路。隨後，大量的研究和演算法涌現，其中最為著名的就是RSA演算法和一系列的橢圓曲線演算法。

無論哪一種演算法，都是站在前人的肩膀之上，主要以素數為研究對象的數論的發展，群論和有限域理論為基礎。內容加密的秘鑰不再需要傳遞，而是通過運算產生，這樣，即使在不安全的網路中進行通信也是安全的。密文的破解依賴於秘鑰的破解，但秘鑰的破解面臨難題，對於RSA演算法，這個難題是大數因式分解，對於橢圓曲線演算法，這個難題是類離散對數求解。兩者在目前都沒有多項式時間內的解決辦法，也就是說，當位數增多時，難度差不多時指數級上升的。

那麼加解密如何在公私鑰體系中進行的呢？一句話，通過在一個有限域內的運算進行，這是因為加解密都必須是精確的。一個有限域就是一個具有有限個元素的集合。加密就是在把其中一個元素映射到另一個元素，而解密就是再做一次映射。而有限域的構成與素數的性質有關。

前段時間，黎曼猜想（與素數定理關系密切）被熱炒的時候，有一位區塊鏈項目的技術總監說橢圓曲線演算法與素數無關，不受黎曼猜想證明的影響，就完全是瞎說了。可見區塊鏈項目內魚龍混雜，確實需要好好洗洗。

比特幣及多數區塊鏈項目採用的公鑰體系都是橢圓曲線演算法，而非RSA。而介紹橢圓曲線演算法之前，了解一下離散對數問題對其安全性的理解很有幫助。

先來看一下 費馬小定理 ：

原根 定義：
設（a, p)=1 （a與p互素），滿足

的最下正整數 l，叫作a模p的階，模p階為（最大值）p-1的整數a叫作模p的原根。

兩個定理：

基於此，我們可以看到，{1, 2, 3, … p-1} 就是一個有限域，而且定義運算 gi (mod p), 落在這個有限域內，同時，當i取0～p-2的不同數時，運算結果不同。這和我們在高中學到的求冪基本上是一樣的，只不過加了一層求模運算而已。

另一點需要說明的是，g的指數可以不限於0~p-2, 其實可以是所有自然數，但是由於

所以，所有的函數值都是在有限域內，而且是連續循環的。

離散對數定義：
設g為模p的原根，（a,p) = 1，

我們稱 i 為a（對於模p的原根g）的指數，表示成：

這里ind 就是 index的前3個字母。
這個定義是不是和log的定義很像？其實這也就是我們高中學到的對數定義的擴展，只不過現在應用到一個有限域上。

但是，這與實數域上的對數計算不同，實數域是一個連續空間，其上的對數計算有公式和規律可循，但往往很難做到精確。我們的加密體系裡需要精確，但是在一個有限域上的運算極為困難，當你知道冪值a和對數底g，求其離散對數值i非常困難。

當選擇的素數P足夠大時，求i在時間上和運算量上變得不可能。因此我們可以說i是不能被計算出來的，也就是說是安全的，不能被破解的。

比特幣的橢圓曲線演算法具體而言採用的是 secp256k1演算法。網上關於橢圓曲線演算法的介紹很多，這里不做詳細闡述，大家只要知道其實它是一個三次曲線（不是一個橢圓函數），定義如下：

那麼這里有參數a, b；取值不同，橢圓曲線也就不同，當然x, y 這里定義在實數域上，在密碼體系裡是行不通的，真正採用的時候，x, y要定義在一個有限域上，都是自然數，而且小於一個素數P。那麼當這個橢圓曲線定義好後，它反應在坐標系中就是一些離散的點，一點也不像曲線。但是，在設定的有限域上，其各種運算是完備的。也就是說，能夠通過加密運算找到對應的點，通過解密運算得到加密前的點。

同時，與前面講到的離散對數問題一樣，我們希望在這個橢圓曲線的離散點陣中找到一個有限的子群，其具有我們前面提到的遍歷和循環性質。而我們的所有計算將使用這個子群。這樣就建立好了我們需要的一個有限域。那麼這里就需要子群的階（一個素數n）和在子群中的基點G（一個坐標，它通過加法運算可以遍歷n階子群）。

根據上面的描述，我們知道橢圓曲線的定義包含一個五元祖（P, a, b, G, n, h)；具體的定義和概念如下：

P: 一個大素數，用來定義橢圓曲線的有限域（群）
a, b: 橢圓曲線的參數，定義橢圓曲線函數
G: 循環子群中的基點，運算的基礎
n: 循環子群的階（另一個大素數，< P ）
h：子群的相關因子，也即群的階除以子群的階的整數部分。

好了，是時候來看一下比特幣的橢圓曲線演算法是一個怎樣的橢圓曲線了。簡單地說，就是上述參數取以下值的橢圓曲線：

橢圓曲線定義了加法，其定義是兩個點相連，交與圖像的第三點的關於x軸的對稱點為兩個點的和。網上這部分內容已經有很多，這里不就其細節進行闡述。

但細心的同學可能有個疑問，離散對數問題的難題表現在求冪容易，但求其指數非常難，然而，橢圓曲線演算法中，沒有求冪，只有求乘積。這怎麼體現的是離散對數問題呢？

其實，這是一個定義問題，最初橢圓曲線演算法定義的時候把這種運算定義為求和，但是，你只要把這種運算定義為求積，整個體系也是沒有問題的。而且如果定義為求積，你會發現所有的操作形式上和離散對數問題一致，在有限域的選擇的原則上也是一致的。所以，本質上這還是一個離散對數問題。但又不完全是簡單的離散對數問題，實際上比一般的離散對數問題要難，因為這里不是簡單地求數的離散對數，而是在一個自定義的計算上求類似於離散對數的值。這也是為什麼橢圓曲線演算法採用比RSA所需要的（一般2048位）少得多的私鑰位數（256位）就非常安全了。

6. ECDSA（橢圓曲線數字簽名演算法）

ECDSA（Elliptic Curve Digital Signature Algorithm）

在現實工作和生活中，我們使用簽名的方式表達對一份文件的認可，其他人可以識別出你的簽名並且無法偽造你的簽名。數字簽名就是對顯示簽名的一種電子實現，它不僅可以完全達到現實簽名的特點，甚至能夠做的更好。
常用的數字簽名演算法有RSA（Rivest-Shamir-Adleman Scheme）、DSS（Digital Signature Standard）等。 比特幣使用ECDSA來生成賬戶的公私鑰以及對交易和區塊進行驗證。

1.Alice（密碼學中常用A到Z開頭的人名代替甲乙丙丁等，字母越靠後出現頻率越低）生成一對密鑰，一個是sk（signing key），是非公開的；另一個是vk（verification key），是公開的。
這一對密鑰同時生成，並且在數學上是相互關聯的，同時，根據vk無法推測出關於sk的任何信息。
2.數字簽名演算法接收兩個輸出：信息M和sk，生成一個數字簽名Sm
3.驗證函數接收信息M、Sm以及vk作為輸入，，返回結果是yes或者no。這一步的目的是為了驗證你看到的針對信息M的數字簽名確實是由Alice的sk來簽發的，用於確認信息與簽名是否相符。
與手寫簽名不同，手寫簽名基本都是相似的，但是數字簽名卻受輸入影響很大。對輸入輕微的改變都會產生一個完全不同的數字簽名。一般不會對信息直接進行數字簽名，而是對信息的哈希值進行簽名。由加密哈希函數的無碰撞性可知，這樣和對原信息進行簽名一樣安全。

在數學上，任何滿足以下方程的點所形成的曲線稱為隨機橢圓曲線： 並且 ，a和b可以為任意值。下面展示幾個隨機橢圓函數的示例：

在了解如何通過基於secp256k1橢圓曲線的ECDSA演算法生成公私鑰之前，我們需要了解在隨機橢圓曲線里，點的加法是如何實現的。
首先定義橢圓曲線上點的加法。設橢圓曲線上有兩點，A和B點，那麼作過這兩點的直線與該曲線相交於第三點（C點），然後關於X軸對稱得到D點，則D為這兩個點的和，記作D=A+BD=A+BD=A+B。很明顯，D點也在該曲線上。所以橢圓曲線上兩點之和也是曲線上的點。

特例：
1.如果兩點重合，則做該點的切線，與曲線相交點的對稱點為和，即A+A=C
如圖：

有了加法以後，乘法實現是不過是進行多次加法運算。有了一個基準點P以後，我們可以對其進行乘法運算，最後可以得到曲線上的另外一個點。
設PPP是橢圓曲線上的一個點，那麼正整數kkk乘以點PPP的結果由下面的式子定義，注意式子中的加法是上面提到的橢圓曲線上點的加法：

點的運算滿足結合律：

很顯然，通過累加 的方式計算 是一種很笨的辦法，其時間復雜度是線性的。上面我們提到過，橢圓曲線上點的加法是滿足結合律的，即 ，擴展一下，就有

於是就有這么一種騷操作，比如計算 ，我們可以先計算 ；然後計算 ；再計算 ；最後計算 。這里我們把15次加法減少到了4次。

當然，k的值不可能總是2的冪。實際上上面的操作可以推廣到k為任意正整數的情況。比如計算23P，首先計算 ，然後



因為 ，所以 。總共只需要7次加法。

分析一下，對於任意正整數k，我們都可以利用這個方法將計算k∗P所需的加法計算次數降低到

也就是說，從時間復雜度的角度來看，這個演算法是一個 的演算法。

這個方法被稱為快速冪演算法，原本常用於快速計算某個數的k次冪，這里將其推廣到橢圓曲線點乘的快速計算中。

為什麼要在介紹了橢圓曲線上點的乘法後突然冒出一個快速冪演算法？快速冪演算法對於橢圓曲線加密有什麼意義？因為數學家/密碼學家發現，利用快速冪演算法計算 的時間復雜度是對數級的，但是要在知道 和 的前提下，倒推出 的值，沒有比挨個嘗試 的值快太多的演算法。於是橢圓曲線加密依賴的數學難題就這么誕生了。

如果我們改一種記法，把橢圓曲線上點的加法記作乘法，原來的乘法就變成了冪運算，那麼上述難題的形式跟離散對數問題應該是一致的。即：

所以這個難題叫橢圓曲線上的離散對數問題。

盡管兩者形式一致，但是他們並不等價。實際上這個問題比大整數質因子分解（RSA）和離散對數（DH）難題都要難得多，目前還沒有出現亞指數級時間復雜度的演算法（大整數質因子分解和離散對數問題都有），以致於同樣的安全強度下，橢圓曲線加密的密鑰比RSA和DH的短不少，這是橢圓曲線加密的一大優勢。

假設隨機取一個 ~ 位之間的值x，計算 ，最後的結果一定會落在曲線上的一點。假設該點為 ，在公開 以及具體曲線的方程的情況下，能否反推出最初的隨機值 ？
證：尋找 的過程只能通過暴力計算， 的可能值為 ~ 中的一個，平均來說需要計算 次能夠找到一次 值。那麼問題來了，運行一次 的計算需要多長的時間呢？
假設我們使用的是超級計算機，主頻為 （一秒鍾可以進行一萬億次運算），從宇宙誕生的那一刻開始計算，到現在也就進行了 次。找到 值的概率為 。這個概率和下一秒地球被巨型隕石撞擊而毀滅的概率接近，既然我們讀到了這里，那麼說明這件事沒有發生。
在上面的案例中， 是 ~ 位的一個隨機數，可以作為私鑰。 是隨機橢圓曲線上的一個點，也就是由私鑰生成的公鑰，因此優點可以1得證。

但是密碼學中，並不能使用上面介紹的實數域上的橢圓曲線。因為

所以我們需要引入有限域上的橢圓曲線。
要證明優點2，還需要將隨機橢圓曲線做一些改動：為了保證最後計算出來的點的坐標值相加是512位，secp256k1引入了一個對質數取模的機制。具體來說，隨機橢圓曲線從
變為了 其中 ，是小於 的最大質數。
此時的隨機橢圓曲線函數圖如下：

具體來說，就是向別人證明我知道 ，但不暴露 的任何信息。（有些類似於零知識證明）
證：前面介紹過結合律： 添加一個hash函數，簡單修改可以得出： 使 ，那麼可知 為 。此時方程為： 為了簡單起見，我們記 和 。此時方程化簡為： 上面這個方程是什麼意思呢？
可以這樣假設：在已知 的情況下，如果能夠提供一個 和 滿足上面的方程，就可以證明一個人擁有 。這個假設有一個前提，如果一個人不知道x，那麼他就無法提供 和 滿足上面的等式。
詳細探討這個前提：如果一個人不知道x，又想計算出 和 ，能夠辦到嗎？結論是不能，首先我們無法從 計算出 （在有限時間內）。
還有一個問題：在已知 和 的情況下，能否計算出關於 的任何信息？
根據公式： 只要解出 就可以了。
要想計算出x，就需要知道r，但是在r沒有公開的情況下，有什麼辦法可以計算r嗎？我們知道R=r*P；但是根據這個公式無法倒推出r（剛才介紹的那個數學難題），所以x也是安全的。
至此，可以證明演算法的第二個優點。

7. 密碼學基礎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] 的域參數如下：

8. 橢圓曲線加密演算法原理

橢圓曲線加密演算法，簡稱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，則稱這個群為阿貝爾群，根據這個定義整數集是個阿貝爾群。

9. 比特幣源碼研讀一:橢圓曲線在比特幣密碼中的加密原理

參加比特幣源碼研讀班後首次寫作，看到前輩black寫的有關密鑰，地址寫的很好了，就選了他沒有寫的橢圓曲線，斗膽寫這一篇。

在密碼學上有兩種加密方式，分別是對稱密鑰加密和非對稱密鑰加密。

對稱加密：加密和解密使用的同樣的密鑰。

非對稱加密：加密和解密是使用的不同的密鑰。

二戰中圖靈破解德軍的恩尼格碼應該就是用的對稱加密，因為他的加密和解密是同一個密鑰。比特幣的加密是非對稱加密，而且用的是破解難度較大的橢圓曲線加密，簡稱ECC。

非對稱加密的通用原理就是用一個難以解決的數學難題做到加密效果，比如RSA加密演算法。RSA加密演算法是用求解一個極大整數的因數的難題做到加密效果的。就是說兩個極大數相乘，得到乘積很容易，但是反過來算數一個極大整數是由哪兩個數乘積算出來的就非常困難。

下面簡要介紹一下橢圓曲線加密演算法ECC。

首先橢圓曲線的通式是這個樣子的：

一般簡化為這個樣子：

()發公式必須吐槽一下，太麻煩了。)

其中

這樣做就排除了帶有奇點的橢圓曲線，可以理解為所有的點都有一條切線。

圖像有幾種，下面列舉幾個：[1]

橢圓曲線其實跟橢圓關系不大，也不像圓錐曲線那樣，是有圓錐的物理模型為基礎的。在計算橢圓曲線的周長時，需要用到橢圓積分，而橢圓曲線的簡化通式：

，周長公式在變換後有一項是這樣的：，平方之後兩者基本一樣。

我們大體了解了橢圓曲線，就會有一個疑問，這個東西怎麼加密的呢？也就是說橢圓曲線是基於怎樣的數學難題呢？在此之前還得了解一些最少必要知識：橢圓曲線加法，離散型橢圓曲線。

橢圓曲線加法

數學家門從普通的代數運算中，抽象出了加群（也叫阿貝爾群或交換群），使得在加群中，實數的演算法和橢圓曲線的演算法得到統一。

數學中的「群」是一個由我們定義了一種二元運算的集合，二元運算我們稱之為「加法」，並用符號「+」來表示。為了讓一個集合G成為群，必須定義加法運算並使之具有以下四個特性：

1. 封閉性：如果a和b是集合G中的元素，那麼（a + b)也是集合G中的元素。

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

3. 存在單位元0，使得a + 0 = 0 + a =a;

4. 每個元素都有逆元，即：對於任意a，存在b，使得a + b = 0.

如果我們增加第5個條件：

5. 交換律： a + b = b + a

那麼，稱這個群為阿貝爾群。[1]

運演算法則：任意取橢圓曲線上兩點P、Q （若P、Q兩點重合，則做P點的切線）做直線交於橢圓曲線的另一點R』，過R』做y軸的平行線交於R。我們規定P+Q=R。（如圖）[2]

特別的，當P和Q重合時，P+Q=P+P=2P，對於共線的三點，P，Q，R』有P+Q+R』=0∞.

這里的0∞不是實數意義的0，而是指的無窮遠點(這里的無窮遠點就不細說了，你可以理解為這個點非常遙遠，遙遠到兩條平行線都在這一點相交了。具體介紹可以看參考文獻[2])。

注意這里的R與R』之間的區別，P+Q=R，R並沒有與P，Q共線，是R』與P，Q共線，不要搞錯了。

法則詳解：

這里的+不是實數中普通的加法，而是從普通加法中抽象出來的加法，他具備普通加法的一些性質，但具體的運演算法則顯然與普通加法不同。

根據這個法則，可以知道橢圓曲線無窮遠點O∞與橢圓曲線上一點P的連線交於P』，過P』作y軸的平行線交於P，所以有無窮遠點 O∞+ P = P 。這樣，無窮遠點 O∞的作用與普通加法中零的作用相當（0+2=2），我們把無窮遠點 O∞ 稱為零元。同時我們把P』稱為P的負元（簡稱，負P；記作，-P）。（參見下圖）

離散型橢圓曲線

上面給出的很好看的橢圓曲線是在實數域上的連續曲線，這個是不能用來加密的，原因我沒有細究，但一定是連續曲線上的運算太簡單。真正用於加密的橢圓曲線是離散型的。要想有一個離散型的橢圓曲線，先得有一個有限域。

域：在抽象代數中，域（Field）之一種可進行加、減、乘、除運算的代數結構。它是從普通實數的運算中抽像出來的。這一點與阿貝爾群很類似。只不過多了乘法，和與乘法相關的分配率。

域有如下性質[3]：

1.在加法和乘法上封閉，即域里的兩個數相加或相乘的結果也在這個域中。

2.加法和乘法符合結合律，交換率，分配率。

3.存在加法單位，也可以叫做零元。即存在元素0，對於有限域內所有的元素a，有a+0=a。

4.存在乘法單位，也可以叫做單位元。即存在元素1，對於有限域內所有的元素a，有1*a=a。

5.存在加法逆元，即對於有限域中所有的元素a，都存在a+(-a)=0.

6.存在乘法逆元，即對於有限域中所有的元素a，都存在a*=0.

在掌握了這些知識後，我們將橢圓曲線離散化。我們給出一個有限域Fp，這個域只有有限個元素。Fp中只有p(p為素數)個元素0,1,2 …… p-2,p-1；

Fp 的加法（a+b）法則是 a+b≡c (mod p)；它的意思是同餘，即（a+b）÷p的余數與c÷p的余數相同。

Fp 的乘法(a×b)法則是 a×b≡c (mod p)；

Fp 的除法(a÷b)法則是 a/b≡c (mod p)；即 a×b∧-1≡c (mod p)；（也是一個0到p-1之間的整數，但滿足b×b∧-1≡1 (mod p)；

Fp 的單位元是1，零元是 0（這里的0就不是無窮遠點了，而是真正的實數0）。

下面我們就試著把

這條曲線定義在Fp上：

選擇兩個滿足下列條件的小於p(p為素數)的非負整數a、b，且a，b滿足

則滿足下列方程的所有點(x,y)，再加上無窮遠點O∞ ，構成一條橢圓曲線。

其中 x,y屬於0到p-1間的整數，並將這條橢圓曲線記為Ep(a,b)。

圖是我手畫的，大家湊合看哈。不得不說，p取7時，別看只有10個點，但計算量還是很大的。

Fp上的橢圓曲線同樣有加法，法則如下：

        1. 無窮遠點 O∞是零元，有O∞+ O∞= O∞，O∞+P=P

        2. P(x,y)的負元是 (x,-y)，有P+(-P)= O∞

3. P(x1,y1),Q(x2,y2)的和R(x3,y3) 有如下關系：

x3≡-x1-x2(mod p)

y3≡k(x1-x3)-y1(mod p)

其中若P=Q 則 k=(3+a)/2y1 若P≠Q，則k=(y2-y1)/(x2-x1)

通過這些法則，就可以進行離散型橢圓曲線的計算。

例：根據我畫的圖，（1，1）中的點P（2，4），求2P。

解：把點帶入公式k=(3*x∧2+a)/2y1

有（3*2∧2+1）/2*4=6（mod 7）.

(注意，有些小夥伴可能算出13/8,這是不對的，這里是模數算數，就像鍾表一樣，過了12點又回到1點，所以在模為7的世界裡，13=6，8=1).

x=6*6-2-2=4（mod 7）

y=6*（2-4）-4=2 （mod 7）

所以2P的坐標為（2，4）

那橢圓曲線上有什麼難題呢？在模數足夠大的情況下，上面這個計算過程的逆運算就足夠難。

給出如下等式：

K=kG （其中 K,G為Ep(a,b)上的點，k為小於n（n是點G的階）的整數）不難發現，給定k和G，根據加法法則，計算K很容易；但給定K和G，求k就相對困難了。

這就是橢圓曲線加密演算法採用的難題。我們把點G稱為基點（base point），k稱為私鑰，K稱為公鑰。

現在我們描述一個利用橢圓曲線進行加密通信的過程[2]：

1、用戶A選定一條橢圓曲線Ep(a,b)，並取橢圓曲線上一點，作為基點G。

2、用戶A選擇一個私鑰k，並生成公鑰K=kG。

3、用戶A將Ep(a,b)和點K，G傳給用戶B。

4、用戶B接到信息後 ，將待傳輸的明文編碼到Ep(a,b)上一點M（編碼方法很多，這里不作討論），並產生一個隨機整數r（r<n）。

5、用戶B計算點C1=M+rK；C2=rG。

6、用戶B將C1、C2傳給用戶A。

7、用戶A接到信息後，計算C1-kC2，結果就是點M。因為

C1-kC2=M+rK-k(rG)=M+rK-r(kG)=M

再對點M進行解碼就可以得到明文。

整個過程如下圖所示：

密碼學中，描述一條Fp上的橢圓曲線，常用到六個參量：

T=(p,a,b,G,n,h)，p 、a 、b 用來確定一條橢圓曲線，G為基點，n為點G的階，h 是橢圓曲線上所有點的個數m與n相除的整數部分

這幾個參量取值的選擇，直接影響了加密的安全性。參量值一般要求滿足以下幾個條件：

1、p 當然越大越安全，但越大，計算速度會變慢，200位左右可以滿足一般安全要求；

2、p≠n×h；

3、pt≠1 (mod n)，1≤t<20；

4、4a3+27b2≠0 (mod p)；

5、n 為素數；

6、h≤4。

200位位的一個數字，那得多大？而且還是素數，所以這種方式是非常安全的。而且再一次交易中，區塊被記錄下來只有10分鍾的時間，也就是說要想解決這個難題必須在10分鍾以內。即便有技術能夠在10分鍾以內破解了現在這個難度的加密演算法，比特幣社區還可以予以反制，提高破解難度。所以比特幣交易很安全，除非自己丟掉密鑰，否則不存在被破解可能。

第一次寫一個完全陌生的數學領域的知識，也許我有錯誤的地方，也許有沒講明白的地方，留言討論吧。總之寫完後對比特比系統的安全性表示很放心。

參考文獻

[1] 橢圓曲線密碼學簡介

[2] 什麼是橢圓曲線加密（ECC）

[3] 域（數學）維基網路

區塊鏈研習社源碼研讀班 高若翔

10. 非對稱加密之ECC橢圓曲線（go語言實踐）

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

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

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

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

具體演算法詳解參考: