學習區塊鏈，總是無法避開各種加密演算法，因為各種加密演算法在實現區塊鏈當中的各個環節都有著不可替代的作用。這裡介紹一下在比特幣以及以太坊當中被大量使用基於離散對數數學難題的ECDSA演算法。

本文主要翻譯自這篇文章

Understanding how ECDSA protects your data

每個人可能都聽說過

ECDSA

演算法。當我提到

數字簽名

的時候，有些人能夠很好地識別出它，有些人卻不知道我說的是什麼。

我曾經試圖去理解

ECDSA

是如何工作的，但是大部分的線上參考資料都是有缺失的，不足以讓我能夠很好地理解它。他們要麼太基礎了──只是解釋演算法的基礎然後留給你“它是如何工作的？”的疑問──要麼就是太高階了，完全略過那些你本該知道但它卻假設你已經知道的基礎知識。因此，你始終在“它是如何工作的”和“我們如何才能夠理解它的工作原理之間”徘徊。如果你沒有一個數學或者密碼學的學位，但是依然想知道它到底是如何工作的，而不是“魔術發生了，簽名被確認了”，那麼你運氣不夠好，因為哪裡都沒有“新手ECDSA”的教程。

我決定對

ECDSA

進行研究，以便更好地瞭解它是如何保護我的資料以及實際上它有多安全。在做了大量的研究工作並最終弄清楚以後，我打算寫一篇文章來解釋

ECDSA

是如何工作的，具體演算法是如何實現的，以及一個數字簽名是如何進行確認的且在它被確認以後是如何確保它是不可偽造的。說實話，要了解以上所有內容並不容易，但是我將盡我的最大努力進行解釋，並且對於讀者所應該掌握的知識進行最小的假設，希望所有的人都能夠看懂。

Step 1: What is ECDSA？

ECDSA

是

Elliptic Curve Digital Signature Algorithm

的簡稱，主要用於對資料（比如一個檔案）建立數字簽名，以便於你在不破壞它的安全性的前提下對它的真實性進行驗證。可以將它想象成一個實際的簽名，你可以識別部分人的簽名，但是你無法在別人不知道的情況下偽造它。而ECDSA簽名和真實簽名的區別在於，偽造ECDSA簽名是根本不可能的。

你不應該將

ECDSA

與用來對資料進行加密的

AES

（高階加密標準）相混淆。

ECDSA

不會對資料進行加密、或阻止別人看到或訪問你的資料，它可以防止的是確保資料沒有被篡改。

ECDSA

當中有兩個詞需要注意：

Curve

（曲線）和

Algorithm

（演算法），這意味著

ECDSA

基本上是基於數學的。並且，這些涉及非常複雜的數學原理。因此，即便我盡力試著進行簡單化處理以讓非技術背景的人也能夠理解，為了更好地理解你依然需要一些數學方面的背景知識。我將分兩部分講這部分的內容，首先是對它具體的工作原理進行解釋，然後深入其內部工作機理助於你的理解。需要注意的是，雖然我已經很好地理解

ECDSA

，但我不是這方面的專家，不過這篇文件還是由相關專家審議過的。

Step 2: Understanding the Basics

原理非常簡單，有一個數學方程，在圖上畫了一條曲線，然後你在這條曲線上面隨機選取了一個點作為你的

原點（point of origin）

。接著你產生了一個隨機數，作為你的

私鑰（Private key）

，最後你用上面的隨機數和原點透過一些複雜的魔法數學方程得到該條曲線上面的第二個點，這是你的

公鑰（Public key）

。

當你想要對一個檔案進行簽名的時候，你會用這個私鑰（隨機數）和檔案的雜湊（一串獨一無二的代表該檔案的數）組成一個魔法數學方程，這將給出你的簽名。簽名本身將被分成兩部分，稱為

R

和

S

。為了驗證簽名的正確性，你只需要公鑰（用私鑰在曲線上面產生的點）並將公鑰和簽名的一部分

S

一起代入另外一個方程，如果這個簽名是由私鑰正確簽名過的數字簽名，那麼它將給出簽名的另外一部分

R

。簡單來說，一個數字簽名包含兩個數字，

R

和

S

，然後你使用一個私鑰來產生

R

和

S

，如果將公鑰和

S

代入被選定的魔法數學方程給出

R

的話，這個簽名就是有效的。僅僅知道公鑰是無法知道私鑰或者創建出數字簽名。

Step 3: Why Use ECDSA？

現在你可能知道一些基礎，但是還不是特別理解，畢竟它還是太複雜了，公鑰、私鑰這些，都是什麼東西呢？不必擔心，我很快會進行具體解釋。在這之前，我先介紹下為什麼我們使用

ECDSA

以及其具體的應用場景。

除了顯而易見的“我需要對一份檔案/合同進行簽名”，還有一個非常流行的應用場景：讓我們以一個不想自己的資料被使用者修改或者破壞的應用程式為例，比如一個只允許你載入官方地圖和不可修改的模組的遊戲，或者一部只允許你安裝官方應用程式的手機或其它裝置。

在這些案例當中，相關檔案（應用程式、遊戲地圖、資料等）會用

ECDSA

進行簽名，公鑰會隨應用程式/遊戲/裝置一起捆綁並用來驗證簽名來確保資料沒有被修改，而私鑰在本地一個私密的地方進行儲存。由於你可以用公鑰對簽名進行驗證，但是不能用它建立或者偽造新的簽名，你可以無所顧忌地將公鑰隨應用程式/遊戲/裝置一起分發。

這與

AES

相比，區別是顯而易見的。

AES

加密系統允許你對資料進行加密，但是你需要用金鑰來解密，這就要求你將金鑰與應用程式一起捆綁，破壞了對資料進行保護防止資料被使用者修改的目的。

一個很好的例子就是PS3的控制檯，它被大量的破解，所有的檔案可以解密，所有的金鑰可以從解密的檔案當中抽取，但是為了能夠在最新的韌體上面執行程式，你還需要破解一個

ECDSA

的數字簽名。

Step 4: Basic Mathematics and Binary

讓我們從一些最基本的開始，如果你已經知道了會覺得很無聊，但是對於不知道的人則是必須瞭解的：

ECDSA

只使用整數數學，沒有浮點數，這意味著可能的數值是1，2，3……，1。5，2。5……則是不被允許的，並且，整數的範圍由簽名當中所採用的位數決定，更多的位數意味著更大的數字範圍，更高的安全效能，因為這使得“猜”到方程當中所採用的具體數字變得更難。正如你所應該知道的，計算機採用位元來表示資料，一個位元是二進位制當中的一位，八個位元表示一個位元組。每次你增加一個位元，可表示的最大整數就可以翻一倍，使用4個位元，你可以表示0~15，一共16個數字，5個位元，你可以表示32個數字，6個位元，可以表示64個數字……一個位元組，可以表示256個數字，32位元，可以表示4294967296個數字……通常

ECDSA

會總共使用160位元，它可以表示相當大的數，可以由49個數字在裡面。

另外一個需要知道的數學組成是

模運算

，可以簡單地說是整數求除之後的餘數。舉個例子，

x \mod 10

是指

x

除以10以後的餘數，這個餘數總是在0和10之間，

142 \mod 10

的結果是2 。另外一個例子，對於

x \mod 2

的結果，如果

x

偶數則結果為0，如果

x

奇數則結果為1。

Step5：The Hash

ECDSA

與訊息的

SHA-1加密雜湊

一起使用來對檔案進行簽名。一個

雜湊

是你作用於資料的每一個位元組然後給你一個代替該資料的整數的另外一個數學函式。舉個例子，所有位元組所代表的數值之和可以被認為是一個非常簡單的雜湊函式。於是，訊息或檔案當中任何修改，整個雜湊就會變得完全不同。在SHA1雜湊演算法當中，它的輸出結果總是20位元組，即160位元。在驗證檔案是否被修改或者破壞，它非常有用，你可以得到任意大小的檔案的20位元組的雜湊，並且你可以非常方便的重新計算雜湊以確認他們是否匹配得上。而

ECDSA

所簽名的正是那個雜湊，因此，如果檔案或者資料發生了改變，雜湊就會發生改變，然後簽名失效了。

為了便於理解，讓我們舉一個例子。我們用一個最簡單的雜湊函式：將所有的資料求和再對10取模運算。

第一步，你必須理解所有的資料將用整數來進行表示。一個文字檔案就是一系列的位元組，正如我們之前所解釋的，一個位元組表示8個位元，可以表示0~255之間的一個數。因此，如果我們用一個整數來表示每一個位元組，並且將檔案的每一個位元組所代表的數相加，然後將求和後的結果對10取模，我們將能夠得到一個0~9之間的數作為最終的結果雜湊。對於相同的資料我們將總是得到相同的結果，並且假如你修改了檔案中的一個位元組，結果將會不同。當然，你也知道，因為這個雜湊函式的輸出空間只有0~9這10種可能性，你想要獲得相同的輸出，可以非常容易的透過修改檔案內容得到，因此，修改檔案內容將有1/10的機率得到相同的雜湊。

這是SHA1出來扮演重要角色的地方，SHA1演算法比起我們剛才簡單的“對10取模”的雜湊函式要複雜複雜得多，它將給出一個非常巨大的數（160位或者位元，如果用十進位制表示的話將由49個數字組成），並且隨著檔案的一點細微的小變化，它也能夠產生顯著的變化。

這個不可預測的特性讓SHA1演算法成為一個非常好的雜湊演算法，非常安全且產生“碰撞（collision）”（兩個不同檔案有相同的雜湊）的可能性非常低，使得透過偽造資料獲得特定的雜湊的變得不可能。

Step6: The ECDSA Equation

好了，那到底

ECDSA

是如何工作的呢？

橢圓曲線密碼學

是基於以下形式的方程：

y^2 = (x^3+a\times x + b) \mod p \\

第一點你需要注意的是這裡有一個取模運算，然後

y

是進行了平方處理，另外也別忘記這是一條曲線的方程。這意味著對於所有的

x

座標（x只能取整數），你可以得到兩個

y

的值，且曲線關於

X

軸對稱。取模運算的底是一個

素數

且確保所有得到的數值在160位元所能夠表示的範圍之內，允許採用

模平方根

和

模的乘法逆元

來簡化運算。因為我們以

p

為模的底，這意味著

y^2

可能的取值在0~p-1之間，一共有

p

個可能的值空間。不過，因為我們只能處理整數，只有一部分取值能夠滿足

完美平方數

（兩個整數的平方值）的要求，我們只能在曲線上面得到

N

個可能的點，且滿足$N

因為每一個

x

可以得到兩個曲線上的點（

y^2

的兩個正負平方根），這意味著一共有

N/2

個可行的

x

座標是有效的，並在曲線上面給出相關的點。且因為整數運算和模運算的存在，這條橢圓曲線上面只有有限個點。

哈哈，是不是有點難，有點複雜，在繼續之前，讓我們先總結一下。

ECDSA

方程給出了而一條曲線，這條曲線上面一共有

N

個有效的點，因為

Y

軸的取值區間由模底

p

來確定，並且需要滿足完美平方（

Y^2

）並關於

X

軸對稱。我們一共有

N/2

個有效的

x

座標，最後還有滿足$N

Step 7: Point Addition

關於

橢圓曲線

需要了解的另外一個事情是

橢圓曲線點加法

的表示方法。它是這樣定義的：將一個點

P

和另外一個點

Q

相加將得到點

S

，如果我們從

P

到

Q

畫一條線，並延長與曲線相交於第三個點

R

，則

R

為

S

的負值，別忘記曲線是關於

X

軸對稱的。在這種情況下，我們定義

R=-S

來表示

R

在

X

軸上面的對稱點。具體可以看下面這張圖。

一文讀懂ECDSA演算法如何保護資料

這是令

a=-4, b=0

以後的橢圓曲線，關於

X

軸對稱，

P+Q

是

R

關於

X

軸上面的對稱點，且

R

是從

P

到

Q

連線延長線與曲線的第三個交叉點。

Step8: Point Multiplication

同樣的機制，如果你進行

P+P

，其結果為經過

P

的切線與曲線的交點關於

X

軸的對稱點，然後

P+P+P

可以看作是

P+P

點與

P

點相加的結果。這就可以用來對

橢圓曲線點乘法

進行定義：

k \times P

就是點

P

自身進行

k

次相加，以以下兩幅圖為例。

一文讀懂ECDSA演算法如何保護資料

一文讀懂ECDSA演算法如何保護資料

這裡你可以看到兩個橢圓曲線和一個用來作切線的點

P

，它與曲線相交於第三點，然後其對稱點是

2P

，接著從這個點開始，你畫一條從

2P

到

P

的直線與曲線相交，交點的對稱點為

3P

。你可以類推一直做下去來完成橢圓曲線乘法。你也可以猜出為什麼在做加法時需要取

R

的對稱點，因為只有這樣，才可以避免在做同一點的多次加法的時候得到同一條線和相同的三個交點。

Step 9: The Trap Door Function!

一個橢圓曲線乘法的特性是你有一個點

R=k\times P

，你知道

R

和

P

，但是你無法據此求出

k

，因為這裡並沒有橢圓曲線減法或者橢圓曲線除法可用，你並不能透過

k=R/P

得到

k

。並且，因為你可以做成千上萬次的加法，最終你只是知道在曲線上面結束的點，但是具體是如何到達這個點你也並不知道。你無法進行反向操作，得到與點

P

相乘以後給你點

R

的

k

。

這種即便你知道原點和終點，但是無法知道被乘數是

ECDSA

演算法背後安全性的所有基礎，而這一原則也被稱為

單向陷門函式

。

Step 10: The ECDSA Algorithm

現在已經掌握了基礎，現在讓我們來談談實際的

ECDSA

簽名演算法。

對於

ECDSA

演算法，首先你需要知道你的曲線引數，一共有

a,b,p,N,G

，你已經瞭解

a

和

b

是曲線方程的引數（

y^2=x^3+a \times x + b

），

p

是模運算的底，

N

是曲線上面點的個數，對於

ECDSA

，還需要一個引數

G

，它表示一個你所選中的一個參考的起始點。它可以是曲線上面的任意一點。

這些曲線引數非常重要，如果不能夠事先獲得它們，你顯然無法簽署或者驗證一個簽名。是的，驗證一個簽名並不只是知道公鑰，你還需要知道這個公鑰是從什麼曲線引數推算出來的。

NIST(National Institute of Standards and Technology)

和

SECG(Standards for Efficient Cryptography Group)

已經提供了預處理的已知高效和安全的標準化曲線引數。

總結一下：首先，你有一對金鑰：公鑰和私鑰，私鑰是一個隨機數，也是160位元大小，公鑰是將曲線上的點

G

與私鑰相乘以後的曲線上的點。令

dA

表示私鑰，一個隨機數，

Qa

表示公鑰，曲線上面的一個點，我們有

Qa = dA \times G

，其中

G

是曲線上面的參考點。

Step 11: Creating a Signature

下面的問題來了，那麼我們是如何對一個檔案或者一個資訊進行簽名的呢？

第一步，你需要知道簽名本身是40位元組，由各20位元組的兩個值來進行表示，第一個值叫作

R

，第二個叫作

S

。值對

(R,S)

放到一起就是你的

ECDSA

簽名。

然後來看看為了進行簽名如何建立這一值對：

產生一個隨機數

k

，20位元組

利用點乘法計算

P=k \times G

點

P

的

x

座標即為

R

利用SHA1計算資訊的雜湊，得到一個20位元組的巨大的整數

z

利用方程

S=k^{-1}(z + dA \times R) \mod p

計算

S

其中

k

是用來生成

R

的隨機數，

k^{-1}

是

k

的

模的乘法逆元

。

Step 12: Verifying the Signature

好了，現在有了你的簽名，你想要來驗證它，也非常的簡單，你只需要公鑰和匯出這個公鑰的曲線引數就可以了。你用以下方程來計算點

P

：

P=S^{-1}\times z \times G + S^{-1} \times R \times Qa \\

如果點

P

的

x

座標與

R

相等，則意味著這個簽名是有效的，否則是無效的。

非常簡單，下面來看看如何一步一步從數學上面進行推導的。

首先，我們有：

P=S^{-1}\times z \times G + S^{-1} \times R \times Qa \\

由於

Qa=dA\times G

，代入上式，則有：

P=S^{-1}\times z \times G + S^{-1} \times R \times dA \times G=S^{-1}(z+dA\times R)\times G \\

再由點

P

的

x

座標必須與

R

匹配，且

R

是點

k\times P

的

x

座標，即

P=k\times G

，於是有：

k\times G=S^{-1}(z+dA\times R)\times G \\

兩邊將

G

拿掉，有：

k=S^{-1}(z+dA\times R) \\

兩邊求逆，即：

S=k^{-1}(z + dA \times R) \\

最後這個就是之前用來產生簽名的方程，這是相匹配的，這是我們可以採用本節開頭給出的方程進行簽名驗證的原因。

Step13: The Security of ECDSA

你可以注意到你需要同時知道隨機數

k

和私鑰

dA

才能夠計算出

S

，但是你需要

R

和公鑰

Qa

來對簽名進行確認和驗證。並且由於

R=k\times G

以及

Qa = dA\times G

再加上

ECDSA

點乘法當中的單向陷門函式的特性（在Step9中進行過解釋），我們無法透過

Qa

和

R

來計算

dA

或

k

，這使得

ECDSA

演算法非常安全，沒有辦法找到私鑰，也無法在不知道私鑰的情況下偽造簽名。

Step14: The Importance of a Random K

現在我們來討論一下索尼PS3中使用的

ECDSA

簽名是如何以及為什麼產生問題的，以及它是如何允許駭客訪問PS3的

ECDSA

的私鑰的。

你還記得產生一個簽名的兩個方程，

R=k\times G

和

S=k^{-1}(z+dA\times R) \mod p

，這些方程的強勢在於實際上有一個方程裡面有兩個未知數（

k

和

dA

），因此你是無法確定其中的任意一個。

話又說回來，演算法的安全是基於其實現的。確保隨機數

k

確實是隨機產生的變得非常重要，並且沒有人能夠猜測、計算或者其它任何型別的攻擊來得到隨機數。但是索尼在它們的實現當中犯了一個巨大的錯誤，它們在任何地方都採用了同一個隨機數，然後它們將具有相同的

R

，這意味著你可以使用兩個分別具有雜湊

z

和

z

和簽名

S

和

S

的兩個檔案的

S

簽名來計算隨機數

k

：

S – S’ = k^{-1} (z + dA\times R) – k^{-1} (z’ + dA\times R) = k^{-1} (z + dA\times R – z’ -dA\times R) = k^{-1} (z – z’) \\

於是有：

k = \frac{z-z

一旦你知道了隨機數

k

，求解

S

的方程就變成了一個只含一個未知數的方程，然後可以很容易地解出

dA

：

dA=（S\times k–z）/R \\

而一旦你知道了私鑰

dA

，你現在可以簽署自己的檔案，PS3將承認它是一個由索尼簽署的官方檔案。這就是為什麼重要的是要確保用於生成簽名的隨機數實際上是“加密隨機的”。這也是為什麼不可能有一個3。56版本以上的自定義韌體的原因，因為自從3。56版本以來，索尼已經修復了他們的

ECDSA

演算法實現，並使用了新的金鑰，現在不可能這麼容易找到私鑰。

這個問題的另一個例子是，一些比特幣客戶使用非加密隨機數生成器（在一些瀏覽器和一些Android客戶機上），導致他們以相同的隨機數

k

來簽署交易，惡意使用者能夠據此找到他們比特幣錢包的私鑰並竊取他們的資金。

這表明了每次簽名時使用真正隨機數的重要性，因為如果

(R，S)

簽名對的

R

值在兩個不同簽名上相同，則會暴露私鑰。

下圖展示了一個關於隨機數的笑話。

一文讀懂ECDSA演算法如何保護資料

當然，只要實現是正確合理的，

ECDSA

演算法非常安全，不可能找到私鑰。如果有辦法很容易找到私鑰，那麼每臺計算機、網站、系統的安全都可能受到危害，因為很多系統都依賴

ECDSA

來保證安全，而且不可能破解。

Step15: Conclusion

終於！我希望這能讓很多人更清楚整個演算法。我知道這仍然很複雜、很難理解。我試圖讓非技術人員更容易理解，但這個演算法太複雜，無法用任何簡單的術語解釋。

但是，如果你是一個開發人員或數學家，或者有興趣學習這方面的知識，因為你想幫助或簡單地獲得知識，那麼我確信這包含了足夠的資訊，你可以開始學習，或者至少理解這個名為

ECDSA

的未知野獸背後的概念。

儘管如此，我還是要感謝一些幫助我理解這一切的人，特別是希望保持匿名的人，以及我在這篇文章中連結到的許多維基百科頁面，還有Avi Kak，感謝他解釋

ECDSA

背後的

數學的論文

，我從中借用了上面的這些圖片。