[以太坊源代码分析] IV. 椭圆曲线密码学和以太坊中的椭圆曲线数字签名算法应用
數字簽名算法在Ethereum中的應用不少，目前已知至少有兩處：一是在生成每個交易(Transaction， tx)對象時，對整個tx對象進行數字簽名；二是在共識算法的Clique算法實現中，在針對新區塊進行授權/封印的Seal()函數里，對新創建區塊做了數字簽名。這兩處應用的簽名算法都是橢圓曲線數字簽名加密算法(Elliptic Curve Digital Signature Algorithm,ECDSA)。Ethereum 在采用ECDSA進行數字簽名的基礎上，基于自身的業務需求，又將數字簽名過程所用的公鑰作為地址類型(common.Address)對象，在許多應用場景下作為地址（即賬戶的唯一標識符）使用。
有關ECDSA的幾個理論概念的關系是這樣的：橢圓曲線數字加密算法ECDSA是數字簽名算法(DSA)的變例之一，ECDSA的基礎是橢圓曲線密碼學(Elliptic-curve cryptography，ECC)，而ECC的理論前提是橢圓曲線上點的倍積(Elliptic curve point multiplication)。本文將從這些概念的原理講起，試圖講解一下Ethereum所采用ECDSA的來龍去脈。
1.橢圓曲線點的倍積
概念知識
橢圓曲線的點倍積(point multiplication)，指的是橢圓曲線上一個點沿著這條曲線不斷的與自身相加，最終落在曲線另一個點上的(計算)過程。也許有些地方會把這里的multiplication翻譯成“乘積”或“乘法”，那樣的話就要特別注意，這種所謂的“點乘積”，是特指一個標量與一個點的乘積，它屬于一種標量乘法(scalar multiplication)。所以，個人覺得將這里的point multiplication翻譯成“點倍積”會更準確些，本文會沿用這種翻譯。
假設起點是橢圓曲線點P，終點是曲線上點R，于是我們有如下點倍積公式，注意此時標量一定要寫在點的左邊。
R = nP
上式中的結果R點暫時還計算不出來，我們需要多一些準備。理論上，這里的橢圓曲線所選擇的幾何方程是固定的，它可以表示為：
y^2 = x^3 + ax + b
上式中a和b都是普通標量參數，以上方程所繪出的幾何曲線如下圖所示，其中紅色曲線表示(a, b) = (-7, 6)時的橢圓曲線，藍色曲線表示 (a, b) = (-6, 6)時的橢圓曲線。顯然，a和b的取值對曲線形狀還是有影響的。
現在有了橢圓曲線的具體形狀和方程，假設曲線上有一個點P，我們想計算它的倍積nP，該怎么做呢？
這里需要再引入一個概念：橢圓曲線點的相加(point addition)。以上圖為例，紅色橢圓曲線上有兩個點P和Q，設定這兩個點相加得到一個同樣處于曲線上的R點，這個R點來自P, Q兩點直連延長線與橢圓曲線的交點(T點)的共軛點，也就是T點沿X軸的對稱點R。由于上述橢圓曲線本身必定沿X軸對稱，所以這個R點也必定處于曲線上。
我們從代數的角度重新看下這個問題：
這里我們用XY坐標來表示P，Q，R每個點，結合設定的橢圓曲線公式?y^2 = x^3 + ax + b，可以得到如下解答：
通過引入一個參數lambda，我們可以得到P，Q兩點相加得到R點的坐標。
很好，我們再往前跨出一步，如果P點和Q點重合，那么它們相加R點是怎樣的呢？這種情況被稱之為橢圓曲線點的翻倍或疊加(point double)，根據上式，R點的x,y相對坐標不變，我們只需要用一個特殊的lambda值就行了，不過要留意此時的lambda取值跟曲線方程參數a有關：
好的，在擁有了以上這些基礎知識之后，我們終于可以計算出橢圓曲線點的倍積，因為對于?R = nP，無論n取何值，我們都可以通過上述“點相加”和“點翻倍”的方法計算出R點坐標。
計算方法
我們來看下具體的如何計算橢圓曲線點倍積?Q = dP，即已知橢圓曲線點P和標量d，計算出曲線點Q。
開始寫代碼前需要將標量d以二進制的方式表示出來，以便于應用“點相加”和“點翻倍”方法。
上式就是d的二進制表示，代碼中將各個系數表示成一個長度為(m+1)的數組d[]即可，d[i]對應于第i個bit位的取值0或1。下列偽代碼均來自wiki-PointMultiplication。
最直觀的就是迭代型的，比如自底向上的迭代：
除了迭代型，當然還有遞歸型的
[plain]?view plain?copy這樣得到的m更小，也就是系數數組d[]的長度更小，這就意味著僅需更少的迭代(遞歸)次數。相關偽代碼可見wiki。
2. 橢圓曲線密碼學
橢圓曲線密碼學(Elliptic-curve cryptography，ECC)同當前流行的其他幾種密碼學類型，也是通過一個公鑰 + 一個私鑰組成的一對鑰匙來進行加密相關操作。它基于有限域上特定橢圓曲線進行操作，最重要的操作是橢圓曲線的點倍積，不夸張的說，橢圓曲線點倍積正是橢圓曲線密碼學的基石。
為什么這么說呢？因為對于點倍積的計算式Q = nP?而言， 在已知起點P和終點Q的情況下，想要計算出n，理論上在目前計算條件下近乎是不可能的！這個數學證明過程比較復雜，這里只想舉一個極端的例子。回看上一章節中那幅圖，如果這里選用了圖中紅色橢圓曲線作點倍積運算，注意到它的左邊部分是一個封閉的不規則圓弧，如果倍積運算的終點Q恰好落在這個圓弧上面，那么參數n是死活都算不出來的，因為如果增大n，讓Q在圓弧上多循環幾圈后依舊保持在Q點...
加密用橢圓曲線的參數組
ECC的使用場景包括數字簽名，安全的偽隨機數生成等。在應用中，所采用的橢圓曲線必須用一組完整的參數來加以定義，這組參數被稱為域參數。一般的，ECC定義的這組參數可表為
(p, a, b, G, n, h)
其中?p?是一個極大的質數，用來表示曲線所有點的范圍；?a, b?分別是橢圓曲線方程?y^2 = x^3 + ax + b?中的系數；G?是該橢圓曲線上點倍積的基點，對于所有通過點倍積運算得到的曲線上點的集合來說，G可算是它們的生成器(generator)；n?是基點G的可倍積階數，定義為能夠使得點倍積nG?不存在的最小的整數n；h?是一個整數常量，它跟橢圓曲線運算中得到點的集合以及?n?有關，h?一般取值為1。
在下一章節中，我們可以看到這些橢圓曲線參數在橢圓曲線數字簽名中的應用。
3. 橢圓曲線數字簽名算法理論
橢圓曲線數字簽名算法(ECDSA)是數字簽名算法(DSA)的變例之一，它基于橢圓曲線密碼學。相比于基于RSA密碼學的DSA，ECDSA在計算數字簽名時所需的公鑰長度可以大大縮短。比如，對于一項安全級別為80 bits的數字簽名來說，ECDSA需要的公鑰長度僅僅為安全級別的2倍，即160 bits，而同樣安全級別要求下的RSA所需公鑰長度至少為1024 bits；同時算法所生成的簽名長度，不論是ECDSA還是RSA都大約是320 bits，這樣一來，ECDSA相對于RSA在應用上的優勢就很明顯了。
注：安全級別(security level)的概念是：N bits的安全級別，意味著攻擊者大約要經過2^N的運算才能獲得本次加密用的私鑰。安全級別所代表的bits越長，意味著安全性能越好，越難以被攻破，當然同時在加密時的代價，包括公鑰長度和生成簽名長度，自然也會相應增加。
ECDSA基于DSA，DSA定義了數字簽名生成過程和驗證過程的基本步驟，通過比較可以看出，ECDSA遵循了DSA的這些定義，并在一些特定步驟中，轉而采用了橢圓曲線的相關操作。這里由于篇幅所限，就不詳細介紹DSA的內容了，有興趣的朋友可以去wiki上一看。
數字簽名的生成
下面來看一下ECDSA的簽名生成過程，以下內容主要來自wiki_ECDSA
假設Alice要給Bob發一個經過數字簽名的消息，他們首先需要定義一組共同接受的橢圓曲線加密用參數，簡單的，這組參數可表示為
(CURVE, G, n)
其中，CURVE表示橢圓曲線點域和幾何方程；G是所有點倍積運算的基點；n是該橢圓曲線的可倍積階數(multiplicative order)，作為一個很大的質數，n的幾何意義在于，nG = 0，即點倍積nG的結果不存在，而對于小于n的任何一個正整數 m = [1，n-1]，點倍積mG都可以得到一個合理的處于該橢圓曲線上的點。
其次，Alice要創建一對鑰，即一個私鑰和一個公鑰。私鑰來自于[1, n-1]范圍內一個隨機數：
公鑰如下，它來自私鑰和基點的橢圓曲線點倍積：
好，準備工作就緒，假設Alice想要對消息m作數字簽名，有以下步驟：
特別需要注意的是步驟3中 k 的選擇，它不僅要滿足加密學的隨機安全性要求，要像私鑰一樣保護起來，更重要的是，在每次生成一個新的數字簽名時，這個 k 必須每次都要更新。否則，通過上述數字簽名過程中的算式相互換算，很容易從中破譯出私鑰！具體換算過程可見wiki_ECDSA。
數字簽名的驗證
對于消息的接收方Bob來說，他除了收到數字簽名文件外，還會有一份公鑰。所以Bob的驗證分兩部分，首先驗證公鑰，然后驗證簽名文件(r, s)。
公鑰的驗證
簽名文件的驗證
以上就是橢圓曲線數字簽名算法(ECDSA)的生成和驗證的完整過程，在wiki_ECDSA還可以看到關于上述驗證方法正確性的證明過程。無論用何種編程語言實現，其中數字簽名的生成和驗證必然要遵循以上的理論和步驟。
4. go-ethereum中的橢圓曲線數字簽名算法
go語言安裝包中自帶的crypto/ecdsa包中包含了關于橢圓曲線的結構體聲明和操作函數，以及ECDSA的簽名生成和驗證到的完整實現代碼。不過，以太坊(go-ethereum)并沒有采用這個crypto/ecdsa包來實現它自己的數字簽名算法。盡管如此，這部分代碼仍然很有閱讀的必要，原因有二：1.它里面定義的一些行為接口和結構體類型，依然在被go-ethereum中的代碼所使用，以方便調用；2. 它關于ECDSA的實現代碼寫的簡潔清晰，非常適合ECDSA的初學者加以研習。
go語言包中的ecdsa代碼包
go語言包自帶的crypto/ecdsa相關的結構體如以下UML圖所示：
對照著上一章節中ECDSA的算法理論，以上的結構體和接口的聲明就非常易于理解了。
- ecdsa.PublicKey結構體通過持有一個elliptic,Curve接口的實現體，可以提供橢圓曲線的所有屬性，和相關操作；PublicKey的成員（X，Y），對應于算法理論中公鑰?的坐標。
- elliptic.Curve接口聲明了橢圓曲線的相關操作方法，其中Add()方法就是橢圓曲線點倍積中的“點相加”操作，Double()就是點倍積中的“點翻倍”操作，ScalarMult()根本就是一個點倍積運算（參數k是標量），IsOnCurve()檢查參數所代表的點是否在該橢圓曲線上；
- elliptic.CurveParams結構體實現了<Curve>接口的所有方法，另外用成員屬性定義了一個具體的橢圓曲線，比如(Gx, Gy) 表示該橢圓曲線的基點，即算法理論中的G點； N 是與基點對應的可倍積階數n；B是橢圓曲線幾何方程中的參數b，注意此處ecdsa代碼包中隱含的橢圓曲線方程為y^2 = x^3 - 3x + b，故只需一項參數b即可。
- ecdsa.PrivateKey是暴露給外部使用的主要結構體類型，它其實是算法理論中的私鑰和公鑰的集合。它的成員D，才真正對應于算法理論中的(標量)私鑰。
- ecdsa.ecdsaSignature對應于生成的數字簽名(r, s)。
由此可見，go語言自帶的crypto/ecdsa代碼包從結構體的成員到方法的聲明，都力圖使得其所代表的ECDSA算法理論清晰易懂。關于實現函數，重點推薦ecdsa/ecdsa.go中的兩個函數Sign()和Verify()
[plain]?view plain?copygo-ethereum中對ECDSA的調用
go-ethereum中實際采用的ECDSA函數實現，來自于第三方庫libsecp256k1，它是一個C++庫，在比特幣代碼(github_bitcoin)中就有應用，被視為一個經過優化的，針對橢圓曲線secp256k1的一個實現庫。secp256k1對應于一組特定的橢圓曲線數字簽名參數，包括曲線方程以及簽名運算所需的一系列參數等，secp256k1被率先應用在比特幣中，關于它的參數細節可見secp256k1,其中所指定的曲線方程為y^2 = x^3 + 7，它的形狀如下圖所示：
在go-ethereum源代碼中，路徑在/crypto/下的代碼包負責所有與加密相關的操作，libsecp256k1庫的源代碼也在其中/secp256k1/的子路徑下存放，待編譯后以C++庫文件的方式被調用。
處理數字簽名
以go-ethereum中交易對象的代碼為例，與ECDSA簽名相關的操作，都被放在一個名叫Signer的接口以及它的實現體里了。
接口<Signer>聲明的方法中，Sender()用來從tx對象攜帶的數字簽名里解析出公鑰并轉換成Address類型變量；SignatureValues()從tx對象里取出數字簽名的三個部分R，S，V；Hash()返回當前tx對象需要做數字簽名的內容，即tx對象中的部分成員變量作RLP編碼后取Hash值；Equal()用來比較Signer實現體對象。由此可見，<Signer>接口及其實現體主要提供對已生成數字簽名進行操作的方法，
Signer的三個實現類中，HomesteadSigner通過持有FrontierSigner對象，可以節省代碼。關于EIP155: EIP(Ethereum Improvement Proposals,EIP)是Ethereum的需求匯總。EIP155是其中一個比較重要的需求，加入了一種抵御重現攻擊(Replay Attack)的簡單方法，要求在對tx作簽名(或恢復簽名時)，在Hash(*Transaction)函數里的RLP編碼環節多選擇幾個成員變量，所以EIP155Signer中的Hash()是重新定義的。
從數字簽名中恢復出公鑰(地址)
從數字簽名中恢復(解析)出地址變量的函數叫recoverPlain()：
[plain]?view plain?copy首先調用crypto.ValidateSignatureValues()來驗證數字簽名是否正確有效，crypto包的這個方法正是通過調用libsecp256k1庫的API，遵循ECDSA算法理論中有關數字簽名驗證部分來完成的；
其次，將R，S，V拼接出所需的數字簽名字符串；
接著，調用crypto.Ecrecover()，憑借被數字簽名的內容sighash和簽名字符串sig，從中恢復出數字簽名所用的公鑰，當然，crypto包的方法依然調用libsecp256k1庫的API來完成；
最后，在返回的公鑰里，去掉標志頭所在的第一個byte(值為4)，生成它的SHA-3（256 bits）哈希值，再截取其中的后20bytes，此即最終返回的Address類型變量。
生成數字簽名
針對某個tx對象生成數字簽名的函數叫SignTx()
[plain]?view plain?copy[plain]?view plain?copy
可見crypto.Sign()函數正是通過調用libsecp256k1庫的API來完成橢圓曲線數字簽名的生成。
公鑰和地址
以太坊中用到的Address類型地址變量，比如每個賬戶的地址，都來自于橢圓曲線數字簽名用的公鑰。在數字簽名中，公鑰可以在多次簽名中重復使用，這反映到以太坊的賬戶上，就是一個賬戶下的多次交易，即多個不同的Transaction對象，它們所作的數字簽名均使用同一個公鑰。
具體到變量類型上，Address類型是一個長度為20 bytes的字符串，而橢圓曲線數字簽名中的公鑰，原生含義應該是曲線上的一個點的坐標(X, Y)，那么它們之間必然存在格式上的相互轉換。在代碼中，這涉及到三種不同格式(類型)：地址變量是Address類型，長度為20bytes的字符串；publicKey變量是一個字符串，長度未知；橢圓曲線上的公鑰，是一個點的坐標，在ecdsa.PublicKey{}中以成員X，Y表示。
publicKey變量轉換成Address類型，在之前提到的core.types.recoverPlain()函數體里介紹過（函數末尾）。
publicKey字符串類型和ecdsa.PublicKey{}類型的格式轉換函數，由crypto代碼包定義。
[plain]?view plain?copyps, 上述代碼中的S256()，是本地代碼寫的一個轉換函數，返回一個elliptic.Curve接口的實現類，它基于secp256k1的橢圓曲線參數，自己實現了<Curve>接口聲明的所有曲線操作函數，以方便用go語言包中的結構體/接口類型，去使用secp256k1橢圓曲線。
小結：
- 以太坊中的數字簽名全部采用橢圓曲線數字加密算法(ECDSA)， 它的理論基礎是橢圓曲線密碼學(ECC)，而ECC存在的理論基礎是點倍積(point multiplication)算式?Q = dP?中的私鑰 d (幾乎)不可能被破譯。ECC相對于基于大質數分解的RSA，在提供相同安全級別的情況下，僅需長度更短的公鑰。
- 以太坊中調用的橢圓曲線數字簽名算法實現，來自己libsecp256k1庫，這是一個針對特定橢圓曲線secp256k1的、經過優化的C++庫，并早已被比特幣系統采用。
- 以太坊中的使用的Address類型，比如每個賬戶的地址，均來自于橢圓曲線數字簽名的公鑰。
原文：http://blog.csdn.net/teaspring/article/details/77834360
總結
以上是生活随笔為你收集整理的[以太坊源代码分析] IV. 椭圆曲线密码学和以太坊中的椭圆曲线数字签名算法应用的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： [以太坊源代码分析] V. 从钱包到客户
- 下一篇： [以太坊源代码分析] VI. 基于p2p