橢圓曲線加密演算法 ECDSA 與 RFC6979 改進提案

in #cryptography6 years ago (edited)

橢圓曲線加密演算法 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