兄弟連區塊鏈教程Fabric1.0原始碼分析ECDSA橢圓曲線數字簽名演算法

摘要： ##兄弟連區塊鏈教程Fabric1.0原始碼分析ECDSA橢圓曲線數字簽名演算法，2018年下半年，區塊鏈行業正逐漸褪去發展之初的浮躁、迴歸理性，表面上看相關人才需求與身價似乎正在回落。但事實上，正是初期泡沫的漸退，讓人們更多的關注點放在了區塊鏈真正的技術之上。 Fabric 1.0原始碼...

##兄弟連區塊鏈教程Fabric1.0原始碼分析ECDSA橢圓曲線數字簽名演算法，2018年下半年，區塊鏈行業正逐漸褪去發展之初的浮躁、迴歸理性，表面上看相關人才需求與身價似乎正在回落。但事實上，正是初期泡沫的漸退，讓人們更多的關注點放在了區塊鏈真正的技術之上。

Fabric 1.0原始碼筆記 之 ECDSA（橢圓曲線數字簽名演算法）

1、橢圓曲線演算法概述

1.1、無窮遠點、無窮遠直線、射影平面

• 平行線相交於無窮遠點；
• 直線上有且只有一個無窮遠點；
• 一組相互平行的直線有公共的無窮遠點；
• 平面上任何相交的兩直線，有不同的無窮遠點；
• 全部無窮遠點溝通一條無窮遠直線；
• 平面上全部無窮遠點和全部普通點構成射影平面。

1.2、射影平面點定義

對於普通平面上點(x, y)，令x=X/Z，y=Y/Z，Z≠0，則投影為射影平面上的點為(X : Y : Z)。 如點(1，2)在射影平面的座標為：(Z : 2Z : Z) Z≠0，即(1 : 2 : 1)或(2 : 4 : 2)均為(1, 2)在射影平面上的點。 Z=0時，(X : Y : 0)即為無窮遠點，Z=0即為無窮遠直線。

1.3、橢圓曲線方程

橢圓曲線的定義： 一條橢圓曲線是在射影平面上滿足方程Y²Z+a1XYZ+a3YZ²=X³+a2X²Z+a4XZ²+a6Z³的所有點的集合，且曲線上的每個點都是非奇異（或光滑）的。 該方程為維爾斯特拉斯方程，是一個齊次方程。 所謂“非奇異”或“光滑”的，即滿足方程的任意一點都存在切線。

橢圓曲線存在無窮遠點(0, Y, 0)，可以在平面座標系中用橢圓曲線、加一個無窮遠點來表示。 令x=X/Z，y=Y/Z，代入橢圓曲線方程，即橢圓曲線普通方程：y²+a1xy+a3y = x³+a2x²+a4x+a6。

1.4、橢圓曲線上的加法

任意取橢圓曲線上兩點P、Q （若P、Q兩點重合，則做P點的切線）做直線交於橢圓曲線的另一點R’，過R’做y軸的平行線交於R。我們規定P+Q=R。

根據這個法則，可以知道橢圓曲線無窮遠點O∞與橢圓曲線上一點P的連線交於P’，過P’作y軸的平行線交於P，所以有 無窮遠點 O∞+ P = P 。 這樣，無窮遠點 O∞的作用與普通加法中零的作用相當（0+2=2），我們把無窮遠點 O∞ 稱為 零元。同時我們把P’稱為P的負元（簡稱，負P；記作，-P）。

根據這個法則，可以得到如下結論 ：如果橢圓曲線上的三個點A、B、C，處於同一條直線上，那麼他們的和等於零元，即A+B+C= O∞ 。 k個相同的點P相加，我們記作kP。如：P+P+P = 2P+P = 3P。

1.5、有限域橢圓曲線

橢圓曲線是連續的，並不適合用於加密；所以，我們必須把橢圓曲線變成離散的點，我們要把橢圓曲線定義在有限域上。

• 我們給出一個有限域Fp
• Fp中有p（p為質數）個元素0,1,2,…, p-2,p-1
• Fp的加法是a+b≡c(mod p)
• Fp的乘法是a×b≡c(mod p)
• Fp的除法是a÷b≡c(mod p)，即 a×b^(-1)≡c (mod p)，b^(-1)也是一個0到p-1之間的整數，但滿足b×b^(-1)≡1 (mod p)
• Fp的單位元是1，零元是0

同時，並不是所有的橢圓曲線都適合加密。y²=x³+ax+b是一類可以用來加密的橢圓曲線，也是最為簡單的一類。 下面我們就把y²=x³+ax+b這條曲線定義在Fp上：

選擇兩個滿足下列條件的小於p(p為素數)的非負整數a、b，4a³+27b²≠0(mod p) 。 則滿足下列方程的所有點(x,y)，再加上 無窮遠點O∞ ，構成一條橢圓曲線。 y²=x³+ax+b(mod p) 其中 x,y屬於0到p-1間的整數，並將這條橢圓曲線記為Ep(a,b)。

Fp上的橢圓曲線同樣有加法，但已經不能給以幾何意義的解釋。

無窮遠點 O∞是零元，有O∞+ O∞= O∞，O∞+P=P 
P(x,y)的負元是 (x,-y)，有P+(-P)= O∞ 
P(x1,y1),Q(x2,y2)的和R(x3,y3) 有如下關係： 
　　x3≡k2-x1-x2(mod p) 
　　y3≡k(x1-x3)-y1(mod p) 
　　其中若P=Q 則 k=(3x1²+a)/2y1若P≠Q，則k=(y2-y1)/(x2-x1)

例 已知E23(1,1)上兩點P(3,10)，Q(9,7)，求1)-P，2)P+Q，3) 2P。

1)–P的值為(3,-10) 
2)k=(7-10)/(9-3)=-1/2，2的乘法逆元為12 因為2*12≡1 (mod 23) 
k≡-1*12 (mod 23) 故 k=11。 
x=112-3-9=109≡17 (mod 23); 
y=11[3-(-6)]-10=89≡20 (mod 23) 
故P+Q的座標為(17,20) 
3)k=[3(3²)+1]/(2*10)=1/4≡6 (mod 23) 
x=62-3-3=30≡20 (mod 23) 
y=6(3-7)-10=-34≡12 (mod 23) 
故2P的座標為(7,12)

如果橢圓曲線上一點P，存在最小的正整數n，使得數乘nP=O∞，則將n稱為P的階，若n不存在，我們說P是無限階的。 事實上，在有限域上定義的橢圓曲線上所有的點的階n都是存在的。

1.6、橢圓曲線上簡單的加密/解密

考慮如下等式： K=kG[其中 K,G為Ep(a,b)上的點，k為小於n（n是點G的階）的整數]。 不難發現，給定k和G，根據加法法則，計算K很容易；但給定K和G，求k就相對困難了。 這就是橢圓曲線加密演算法採用的難題。 我們把點G稱為基點（base point），k（k<n，n為基點G的階）稱為私有金鑰（privte key），K稱為公開金鑰（public key)。

2、橢圓曲線介面及實現

2.1、橢圓曲線介面定義

type Curve interface {
Params() *CurveParams //返回曲線引數
IsOnCurve(x, y *big.Int) bool //(x,y)是否在曲線上
Add(x1, y1, x2, y2 *big.Int) (x, y *big.Int) //(x1,y1)和(x2,y2)求和
Double(x1, y1 *big.Int) (x, y *big.Int) //2*(x,y)
ScalarMult(x1, y1 *big.Int, k []byte) (x, y *big.Int) //返回k*(Bx,By)
ScalarBaseMult(k []byte) (x, y *big.Int) //返回k*G，其中G為基點
}
//程式碼在crypto/elliptic/elliptic.go

2.2、CurveParams結構體定義及通用實現

CurveParams包括橢圓曲線的引數，並提供了一個通用橢圓曲線實現。程式碼如下：

type CurveParams struct {
P*big.Int //% p中的p
N*big.Int //基點的階，如果橢圓曲線上一點P，存在最小的正整數n，使得數乘nP=O∞，則將n稱為P的階
B*big.Int //曲線方程中常數b，如y² = x³ - 3x + b
Gx, Gy*big.Int //基點G(x,y)
BitSize int//基礎欄位的大小
Namestring//橢圓曲線的名稱
}
//程式碼在crypto/elliptic/elliptic.go

CurveParams涉及如下方法：

func (curve *CurveParams) Params() *CurveParams //返回曲線引數，即curve
func (curve *CurveParams) IsOnCurve(x, y *big.Int) bool //(x,y)是否在曲線上
func (curve *CurveParams) Add(x1, y1, x2, y2 *big.Int) (*big.Int, *big.Int) //(x1,y1)和(x2,y2)求和
func (curve *CurveParams) Double(x1, y1 *big.Int) (*big.Int, *big.Int) //2*(x,y)
func (curve *CurveParams) ScalarMult(Bx, By *big.Int, k []byte) (*big.Int, *big.Int) //返回k*(Bx,By)
func (curve *CurveParams) ScalarBaseMult(k []byte) (*big.Int, *big.Int) //返回k*G，其中G為基點
//程式碼在crypto/elliptic/elliptic.go

2.3、幾種曲線

func P224() Curve //實現了P-224的曲線
func P256() Curve //實現了P-256的曲線
func P384() Curve //實現了P-384的曲線
func P521() Curve //實現了P-512的曲線
//程式碼在crypto/elliptic/elliptic.go

3、橢圓曲線數字簽名演算法

結構體定義：

type PublicKey struct { //公鑰
elliptic.Curve
X, Y *big.Int
}
type PrivateKey struct { //私鑰
PublicKey
D *big.Int
}
type ecdsaSignature struct { //橢圓曲線簽名
R, S *big.Int
}
//程式碼在crypto/ecdsa/ecdsa.go

涉及如下方法：

func (priv *PrivateKey) Public() crypto.PublicKey //獲取公鑰
func (priv *PrivateKey) Sign(rand io.Reader, msg []byte, opts crypto.SignerOpts) ([]byte, error) //使用私鑰對任意長度的hash值進行簽名
func GenerateKey(c elliptic.Curve, rand io.Reader) (*PrivateKey, error) //生成一對公鑰/私鑰
func Sign(rand io.Reader, priv *PrivateKey, hash []byte) (r, s *big.Int, err error) //使用私鑰對任意長度的hash值進行簽名
func Verify(pub *PublicKey, hash []byte, r, s *big.Int) bool //使用公鑰驗證hash值和兩個大整數r、s構成的簽名
//程式碼在crypto/ecdsa/ecdsa.go