橢圓曲線加密演算法 ECDSA 與 RFC6979 改進提案
橢圓曲線加密演算法 ECDSA 與 RFC6979 改進提案
橢圓曲線加密演算法（Elliptic Curve Digital Signature Algorithm，ECDSA）是比特幣、以太坊區塊鏈所使用的非對稱式金鑰加密技術，
可輕易讓貨幣持有者透過私鑰 Private Key（變數：d_A）對資訊進行簽章（Digital Signature），讓所有人使用 Public Key（變數：d, e, p, n, G, Q_A）來進行驗證（或是反向進行秘密傳遞）。
然而，早期的 ECDSA 演算法中，有一個僅產生一次性使用的臨時簽名變數 k（Ephemeral Key）
因不夠隨機，又或是忽略了其重要性（如每次收發訊息都使用相同的 k 值），導致駭客可透過反推方式求得 k 值，
一旦 k 值遭洩，持幣者的 Private Key 也可輕易的被回推計算出來。
像是早期 Sony PS3 就是每次都使用相同的 k 值，導致遊戲機遭人破解。
1、流程
而這篇文章，將會簡介什麼是 ECDSA，以及它是如何產生非對稱式金鑰
接著再介紹如何使用 Private Key、Public Key 進行簽章與檢驗
以及展示透過 k 值取得 Private Key 推導過程
最後再說明 RFC6979 針對產生 k 值的改進提案
2、橢圓曲線
橢圓曲線一般式如下：
而在 ECDSA 內所使用的是特殊規範的橢圓曲線：
條件的設定目的是在為讓 x^3 + dx + e = 0 方程式的 x 能夠存在三個不同的（實數或複數）解好處是 ECDSA 在使用此特殊規範的曲線，總是可以同時找到 P、Q、R 三個點，並且這三個點又符合交換群（Abelian Commutative Group）的特性
3、交換群
什麼是交換群？就是這個群內的所有元素符合下面 5 條規範
以現實世界來說，其實就是我們習以為常的「乘法運算」、「加法運算」，像是「2 * 1 = 1 * 2」、「1 +（-1）=（-1）+ 1」等
而在線性代數的世界裡，我們是可以自己定義「運算」的，像是「P 點＊Q 點 = P 點＊Q 點」。
在這邊，我們也定義特殊規範的橢圓曲線，它的每一個點都要符合交換群的特性，我們定義一下這個群的符號
而交換群的特性，下面僅列出 ECDSA 會用到的部份
4、點的加法運算
我們如何進行 ECDSA 點的加法運算呢？因為 ECDSA 一定會找到三個點符合 P + Q +（-R）= O
我們透過兩種不同的橢圓曲線，分別將 P、Q、R 三點繪畫在座標上，就會很清楚知道它們之間的關係
當 P ≠ Q 時：
當 P = Q 時：
當 P ≠ Q 時：
當 P = Q 時：
5、已知 R = P + Q，求 R
因為 P、Q、（-R）三點共線，所以我們可以透過求 P、Q 斜率，計算出 R 點。
6、點的乘法運算
那我們如何進行 ECDSA 點的乘法運算呢？可以視做連續的加法來比照辦理就好
7、質數有限體
雖然在橢圓曲線上能夠取得無限多種不同的 P 點及 Q 點，但我們在使用 ECDSA 時並不會無限制的擴張，所以這時會將質數有限體 GF（p）的特性帶入，符號如下：
而符合質數有限體的橢圓曲線，符號如下：
使得 ECDSA 用的橢圓曲線會有如下特性：
8、反元素測試
有點混亂了嗎？沒關係，我們來舉個例子吧！
我們考慮使用 d = 1，e = 1，p = 13 的橢圓曲線如下
註：因為所有的變數會被限制在 13 - 1 = 12 內，所以均要在計算完畢後進行取餘（mod）運算，以限制範圍
來小小測試一下在橢圓曲線上的（1, 4）這一個點，是符合上述條件的
有了限制條件，我們就可以列舉出所有符合 d = 1，e = 1，p = 13 的橢圓曲線的點，如下：
還記得群的概念嗎？所有的元素都會有一個反元素
那我們就來測試看看是否所有的點都有符合這個特性，找了一個點（4, 2）來進行測試
可以發現（4, 11）這個點也在 d = 1，e = 1，p = 13 的橢圓曲線內，得以證明確實有符合群的各大特性，所以經過計算，我們就可以列出一個反元素速查表：
| P | -P |
|---|---|
| (0, 1) | (0, 12) |
| (1, 4) | (1, 9) |
| (4, 2) | (4, 11) |
| (5, 1) | (5, 12) |
| (7, 0) | (7, 0) |
| (8, 1) | (8, 12) |
| (10, 6) | (10, 7) |
| (11, 2) | (11, 11) |
9、加法測試，已知 R = P + Q，求 R
接下來就可以依樣畫葫蘆，透過 P + Q 來計算 R 點了
假設 P 點為（4, 2），Q 點為（10, 6）
這邊會讓人不知道如何進行的是分數的取餘計算，下方為計算方法：
接下來繼續計算 R 點
計算出來的 R 點也確實在 d = 1，e = 1，p = 13 的橢圓曲線內，同樣符合質數有限體的規範。
10、乘法測試
接下來要介紹點的乘法，上面有提到點的乘法可以看作是連續的點的加法，在這邊同樣以 P 點為（4, 2）來做計算
首先計算（4, 2）+（4, 2）
我們可以得到 （4, 2）+（4, 2）=（8, 1），仍在體的規範內，再來我們計算（8, 1）+（4, 2）
最後我們得到（4, 2）+（4, 2）+（4, 2）的答案為（10, 6），證實整個 d = 1，e = 1，p = 13 的橢圓曲線內的點都在體的規範內
11、數位簽章及驗章
在我們了解了橢圓曲線的概論後
我們接著就要透過橢圓曲線來進行資訊簽章，以下是概念圖：
首先我們要先透過橢圓曲線及私鑰來建立公鑰
透過橢圓曲線、私鑰來進行簽章
透過橢圓曲線、公鑰來進行驗章
以下證明為何 r = x_c 就代表證明驗章通過
12、Ephemeral Key k 的重要性
為什麼 Ephemeral Key k 那麼重要？假設我們每次在進行簽章時都使用相同的 k 值，或是選擇一個沒有那麼隨機產生出來的 k 值，導致駭客可透過反推方式求得 k 值，
一旦 k 值遭洩，持幣者的 Private Key 也可輕易的被回推計算出來。
所以這就是為什麼 RFC6979 提出我們需要有較佳的 k 值選法，以下是最簡式，
使用私鑰、每次都不一樣的資訊來進行 k 值選定，以確保 k 值足夠隨機
13、結語
經過了一大串的說明，我們不論在離線的冷錢包（Cold Wallet）、在線的熱錢包（Hot Wallet）、印在紙上的紙錢包（Paper Wallet）…等選擇上
都一定要選用符合 RFC6979 提案的 k 值選定，以確保私鑰不會遭人破解
14、參考資料
（歡迎社群分享。但引用至政大【以太坊原理與應用開發】課程中的作業一請註明來自 oneleo Steemit，及附上原文連結：橢圓曲線加密演算法 ECDSA 與 RFC6979 改進提案）
Donate Cardano ADA：
DdzFFzCqrhsup2Q4nnhKJJZ5BRuPkYUSPqDJn72t2dtHtVqsz5kQQmopMQR16Sv9qS5NC4w8Kv5P8XrDH2n2FD2akxtrntjc8hbgAmTz