誰能最簡單的詳解橢圓曲線演算法，secp256k1 是如何生成公鑰和私鑰的？

01-09

簡單且詳細講解橢圓曲線加密法原理，網上大多數寫的是雲里霧裡，好讓我們這個智力平平的眾生能理解。

第一次回答問題，略緊張。

------------------------------------------------------------&>

題主的問題是「最簡單的詳解橢圓曲線演算法」，我理解為用最基礎的數學知識來解釋橢圓曲線密碼。

實際上橢圓曲線密碼是一種公鑰密碼演算法，公鑰密碼演算法最根本的原理是利用信息的不對稱性：即掌握私鑰的人在整個通信過程中掌握最多的信息【上（開）帝（圖）視（可）角（恥）】，一切的運算對他而言都是沒有秘密的。為了讓別人能給自己發送加密的信息，私鑰擁有者把信息的一部分公開披露，披露的信息記為公鑰。顯而易見，一個公鑰密碼演算法安全的必要條件（非充分）是「由公鑰不能反推出私鑰」。

/* 先看一個栗子：

小明就讀於小學二年級，會計算加法，但是不會計算除法。你是小明的怪蜀黍大強，你想出一道題給他做，讓他雖然能理解題目意思但是做起來有難度：

強：「小明小明，過來，叔叔問你，1+1等於幾？」

明：「叔叔的大學白念了吧，我幼兒園就會了，等於2。」

強：「那考你個難的，7+7等於幾？」

明：「切，你當人家上課啃鉛筆頭，下課幫小紅寫作業都是白乾的是吧。手指都不用數，等於14唄。」

強：「行，有叔叔當年的風采，那叔叔再問你，幾個7相加等於56？」

明：「……」，默默掏出草稿紙、鉛筆、手指頭、腳趾頭，進行了10分鐘的深度計算:2個7等於14，3個7等於21，4個7等於28……。「叔叔,我算出來了，是8個，對不對？」

強：「好小子，叔叔就不信考不倒你。幾個7相加等於864192？」你心中默念，以小明的計算能力，要算到這個數恐怕得一年半載的。

明：「叔叔好厲害呀，我算不出來。」

//明天去考考小紅看她會不會算幾個7等於56，不會算我就交她，嘿嘿。」

與上述例子相同的是，橢圓曲線密碼也是一個基於加法階數難求問題的密碼方案。 對於橢圓曲線密碼來講，橢圓曲線的基點就是例子裡面的7，而私鑰就是基點的加法階數（例子裡面的8），公鑰是基點（7）進行對應階數的加法（8次）得到的結果（56）。

與上述例子不同的是，橢圓曲線密碼里的加法建立在「有限域上的二元三次曲線上的點」上，組成一個「有限加法循環群」。（好拗口的一句話。。）具體的說，這個加法的幾何定義如下面兩個圖，兩個點的加法結果是指這兩點的連線和曲線的交點關於x軸的鏡像。

圖1：兩個不同的點相加

圖二：兩個相同的點相加

看完這兩幅圖，默默思考1秒鐘,你可能要問（炸）了（毛）：為啥要這麼定義加法？我還是喜歡小明的那個加法題，不喜歡這個。

之所以這麼定義，原因有兩個：

（1）給你求逆向運算（由公鑰計算私鑰）的時候製造困難。要是像小明一樣在整數群里做加法，恐怕這密碼體制只能用來給小紅寫信。

（2）為了構造一個封閉的「較好的」代數結構，簡化正向運算（由私鑰計算公鑰的運算）。要是單純為了求解困難，那可以定義五光十色的加法，但是加法定義的隨性將導致了運算的複雜。為了能用一些最基本的運算：比如結合律、比如減法，才這麼定義讓這些點構成一個群。

行了，有了加法以後，我們只需要考慮兩件事：

（1）如何正向計算（由私鑰計算公鑰）：

確定橢圓曲線一個點作為基點P，由於所有的點構成一個有限群，那麼基點P必然可以作為一個生成元生成一個子群。記這個子群的階數為n，也就是說P點累加n次得到群的單位元（無窮遠點），記做nP=0。（注意此處0隻是一個代號，代指無窮遠點，因為我們習慣了用0來表示加法單位元。）

正向計算的定義很簡單，私鑰為 $Kin [0,n)$ ; 基點為點 $P$ ;公鑰點Q定義為 $K$ 個 $P$ 相加： $Q=underset{K}{widehat{underbrace{P+P+cdots +P)}}}$ （原諒我公式寫不好）。

先說相加，最不濟的演算法就是直接相加K次，求解完畢，好一點的方法是使用二進位梯子來加，這樣需要進行t次倍點（相同點相加）和t/2次點加（不同點相加），其中 $t=log_{2}K$ ：

當然還有更好的演算法，比如說非相鄰表示法（NAF）、窗口法等，此處不多說。

再說第二個問題，怎麼用代數的方法求出兩點相加。這恐怕得用一點高中數學了，此處直接上公式：

以域特徵不等於2或3的定義在素數域GF(p)上曲線為例，曲線方程為： $y^{2}=x^{3}+ax^{2}+b$

從這兩公式可以看到，要求點相加，只需要進行一些有限域的加減乘除即可。

事實上，加減乘除複雜度的關係如下：除法&>乘法&>加減。為了提高運算效率，往往在運算中把一個點的坐標保留分數的形式如： $(frac{x}{z},frac{y}{z})$ 。運算過程中一直保留分數，直到運算結束再做一次除法，回到有限域，這種演算法叫做投影坐標。

有了投影坐標以後，一次正向計算（私鑰求公鑰）其實就是一系列的乘法、加法、減法。當然，此處的乘法、加法、減法都是素數域上的運算。為了快速計算素數域乘法(實際上就是模乘)，又誕生了一系列演算法：蒙哥馬利模乘演算法，Barrett模乘演算法等，都是通過預計算加快求模速度的演算法。

（2）逆向計算（公鑰反推私鑰）有多難：

密碼學家都既是大強也是小明，大強給小明出了題，必須讓他算不出來，小明懂的東西一天天變多、計算速度一天天變快，大強的題也得一天天變複雜。

據本人的了解，目前由橢圓曲線公鑰求解私鑰的最有效演算法複雜度為 $O(sqrt{p})$ ,其中 $p$ 是階數 $n$ 的最大素因子。當參數選的足夠好讓 $p>2^{160}$ 時，以目前的計算能力，攻破橢圓曲線是不現實的。

但是，小明哪天長大，誰知道呢？小明哪天有了（量子）計算器，怎麼難倒他呢？

嗯，對，歡迎來到密碼學。。

不好意思讓大家久等了，最近太忙，現在添加一個例子。

首先寫一下橢圓曲線加密的「和」值演算法，這個演算法是必須的也是核心，之後只需要將點帶入計算就可以得到「和」值了。

假設曲線y^2=x^3+ax+b(mod p)上有兩點P1(x1,y1)，P2(x2,y2),現在要計算P3(x3,y3)=P1+P2：

首先演算法中需要一個輔助值m，其中滿足

（1）P1！=P2時---&>m=(y2-y1)*(x2-x1)^(-1) mod p;

（2）P1==P2時---&>m=(3*x1^2+a)*(2*y1)^(-1) mod p;

那麼現在就來計算x3和y3

x3=m^2-x1-x2 (mod p) ,y3=m(x1-x3)-y1 (mod p)

公式可能大家覺得有點複雜，那麼現在就用實例來說明，假設p=5,a=2，那麼就是有

y^2=x^3+2x+3 (mod 5)，取x=0,1,2,3,,4,帶入計算，那麼則有

x=0 ==&> y^2=3 ==&>(3&<5) 無解;

x=1 ==&> y^2=6=1 ==&>y=1,4mod5; （根據映射）

x=2==&> y^2=15=0 ==&>y=0mod5;

x=3 ==&> y^2=36=1 ==&>y=1,4mod5;

x=4==&> y^2=75=0 ==&>y=0mod5;

所以現在就有點(1,1),(1,4),(2,0),(3,1),(3,4),(4,0),還有個無窮~

現在取P1=(1,4)，P2=(3,1),則P3=(1,4)+(3,1)

m=(1-4)/(3-1)=-3*2^(-1)======(特別注意！！！！！！！！！！！！！這裡對2^(-1)的定義為x*2=1mod5,x為滿足表達式的任意值。)

所以m=-3*3=1mod 5，x3=2mod5,y3=0mod5，故P3=(2,0)

也就是說，在曲線y^2=x^3+2x+3 (mod5)上，得到（1,4）+（3,1）=（2,0），也就是（2,0）也在曲線上。

先補充這麼多，打的心好累。。。。

===========================================

忙完了先來大概寫一下。橢圓曲線加密體制(Elliptic Curve Cryptography,ECC)所追求的是獲得同樣級別的安全性，而需要的二進位位較少。因此ECC體制的數學計算較之此前的加密演算法更加複雜，其每個數學的操作代價也都更加昂貴。（近幾年美國政府公開的加密標準基本都是基於ECC的）

不同於基於模運算的方法，ECC主要使用的是「和」值，這個「和」既有幾何上的意義，又有算數上的解釋。而橢圓曲線E就是某個具體函數的圖形，然後看下圖

其中P1和P2是一條直線與曲線相交通過這兩點，該直線往往會與橢圓曲線在另一點處相交。如果上述條件成立，就將該交叉點圍繞x軸做對稱映射，獲得對稱點P3，此時得到了「和」值定義：

P3=P1+P2

（一定要知道這不是加法，而是幾何上的「和」！！！）

並且這個式子中的「加」法是ECC中唯一需要的數學運算。

之後便是具體的運算了，從加密的角度看，我們希望處理的是離散的點集，因此要在橢圓曲線計算式上執行「mod P」運算。

手機碼字很困難-_-||，先寫到這裡吧，有興趣我再往後寫。（後面的計算公式手機太難打出來了(′-ω-`)！）

一文讀懂比特幣私鑰、公鑰、錢包地址的來歷和關係

對比特幣熟悉的朋友一定都知道，買賣比特幣最後都是通過一個錢包地址來實現的，就像我們日常使用的銀行卡卡號，我們隨便找一個比特幣的錢包地址，大家看一下：

1QCXRuoxWo5Bya9NxHaVBArBQYhatHJrU7

但是當談到比特幣的錢包地址是如何算出來的時候，可能就很少有人能夠說清楚了。

下面，景辰通過實際計算，來給大家講解一下比特幣的錢包地址是怎麼來的，公鑰、私鑰是怎麼來的，以及他們三者之間的關係。

下面的過程你不一定懂得轉換的原理，知道他們流轉的過程就可以了。

眾所周知，比特幣是建立在數學加密學基礎上的，而不是像銀行卡那樣是基於信用的，基於信用體系的銀行卡卡號我們都熟悉，是我們在向銀行申請銀行卡的時候銀行給隨機發的，那麼比特幣的錢包地址是怎麼來的呢？

在《比特幣：一種點對點的電子現金系統》一文中，中本聰提到了用橢圓加密演算法（ECDSA）來產生比特幣的私鑰和公鑰。

基於橢圓加密的原理，由私鑰是可以計算出公鑰的，再由公鑰經過一系列數字簽名運算就會得到比特幣錢包地址。

因為由公鑰可以算出比特幣地址，所以我們經常把公鑰和比特幣地址的說法相混淆，他們都是指的同一個概念，比特幣錢包地址只是另一種格式的公鑰，但是兩者的外在表現形式是不一樣的。

那麼我們就可以梳理出一個脈絡了：

私鑰 —— 公鑰 —— 比特幣錢包地址

從比特幣私鑰得到我們日常轉賬所用的比特幣錢包地址總共需要九個步驟，中間用到了SHA256加密、RIPEMD160加密和BASE58編碼。

下面，我們以實際案例來模擬一下整個流程：

第一步：生成隨機私鑰

私鑰是一個隨機數，隨機選取一個32位元組的數，這個數的範圍大小是介於1 ~ 0xFFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFE BAAE DCE6 AF48 A03B BFD2 5E8C D036 4141之間的一個數，為了方便後面的計算，我們隨機生成一個合法的私鑰：

8F72F6B29E6E225A36B68DFE333C7CE5E55D83249D3D2CD6332671FA445C4DD3

第二步：橢圓曲線算公鑰

生成了私鑰之後，我們使用橢圓曲線加密演算法（ECDSA-secp256k1）計算私鑰所對應的非壓縮公鑰，生成的公鑰共65位元組，其中一個位元組是0x04，其中32個位元組是X坐標，另外32個位元組是Y坐標：

公鑰P.X：

06CCAE7536386DA2C5ADD428B099C7658814CA837F94FADE365D0EC6B1519385

公鑰P.Y：

FF83EC5F2C0C8F016A32134589F7B9E97ACBFEFD2EF12A91FA622B38A1449EEB

第三步：計算公鑰的SHA-256哈希值

將上述公鑰地址拼合，得到標準地址：

0406CCAE7536386DA2C5ADD428B099C7658814CA837F94FADE365D0EC6B1519385FF83EC5F2C0C8F016A32134589F7B9E97ACBFEFD2EF12A91FA622B38A1449EEB

對齊進行SHA-256哈希計算，得到結果：

2572e5f4a8e77ddf5bb35b9e61c61f66455a4a24bcfd6cb190a8e8ff48fc097d

第四步：計算 RIPEMD-160哈希值

取上一步結果，進行RIPEMD-160計算，得到結果：

0b14f003d63ab31aef5fedde2b504699547dd1f6

第五步：加入地址版本號（比特幣主網版本號「0x00」）

取上一步結果，在前面加上16進位的00，即：

000b14f003d63ab31aef5fedde2b504699547dd1f6

第六步：計算 SHA-256 哈希值

取上一步結果，進行SHA-256計算，可得：

ddc2270f93cc84cc6869dd373f3c340bbf5cb9a8f5559297cc9e5d947aab2536

然後，對以上結果再次計算 SHA-256 哈希值，得到：

869ac57b83ccf75ca9da8895823562fffb611e3c297d9c2d4612aeeb32850078

第七步：取上一步結果的前4個位元組（8位十六進位）

869ac57b

第八步：把這4個位元組加在第五步的結果後面

作為校驗位，將這4個位元組載入第五步的結果後面，這就是比特幣地址的16進位形態了：

869ac57b000b14f003d63ab31aef5fedde2b504699547dd1f6

第九步：用Base58編碼變換一下地址

對上一步的結果進行Base58編碼，得到：

1QCXRuoxWo5Bya9NxHaVBArBQYhatHJrU7

這就是我們經常看到的傳統意義上的比特幣錢包地址了。

以上步驟可以簡化為下圖所示：

我們經常說的比特幣公鑰就是指的圖中第二步所產生的結果，而HASH160指的是第四步RIPEMD160簽名所產生的結果，由於RIPEMD也是一種HASH演算法所以就統稱為HASH160了，而我們常用的比特幣地址就是經過BASE58編碼後的結果。

推薦往期閱讀：區塊鏈的地位 | 區塊鏈的來源 | 比特幣的概念 | 瘋狂的ICO | 助力跨境支付

ECC可以看certicom公司的教程，淺顯易懂，而且還有動態演示。

ECC Tutorial

最簡單的描述，

K=kG

作者重新定義了橢圓曲線的加法和乘法。並且保證不可逆。

之後通過一系列複雜的計算算出了公鑰和加密演算法。比如

y^2=Ax^3+Bx^2+Cx+D

然後Alice計算出來一個參數

(x1,y1) 告訴A,B,C,D到Bob,Bob對應的計算出來（x2,y2）

然後雙方通訊，就可以使用公鑰私鑰對進行加解密了。

PS:對不起。具體細節我把書送給老師了。手頭沒有資料可以查

PS:開始了解這個演算法的時候我也看了ECC加密演算法入門介紹。到現在都不懂。我也不是數學系的。

PS:我很後悔當時沒有把這個書上的東西記下來。現在只有一點皮毛的。那本書是《深入淺出密碼學――常用加密技術原理與應用（安全技術經典譯叢）》（美）帕爾，（美）佩爾茨爾　著，馬小婷　譯

PS：最後我很討厭很簡單的東西說的很複雜。在上面這本書大概幾面紙加上最基礎不超過兩位數的算例就解決的問題，上面硬是講的超級複雜。

這個系列寫的非常詳細，且通俗易懂。

Elliptic Curve Cryptography: a gentle introduction

http://mp.weixin.qq.com/s/jOcVk7olBDgBgoy56m5cxQ

萊迪思公眾號一篇文章講得蠻好的。

還是找本密碼學的書看看吧。