由淺及深了解區塊鍊之：（9）淺談橢圓曲線加密算法及其原理

在比特币交易系統中，産生的每一筆交易都需要交易者的數字簽名以驗證其身份，數字簽名要用到相應的公鑰和私鑰，上一節講解了如何産生私鑰以及如何由公鑰得到相應的比特位址，這一節來講解下如何由私鑰得到公鑰。

一般來說由私鑰得到公鑰可以經過兩種算法，RSA算法和橢圓曲線法ECC。

關于RSA算法在之前的小節中有介紹，比較兩種算法可以得到如下資訊：

1：ECC在私鑰的處理上要比RSA要快的多。

2：ECC的安全系數更高，160位的ECC和2048位的RSA安全系數一緻

因而在私鑰推導公鑰中用到的是ECC算法。

ECC算法首先用到的是橢圓曲線的形式：y2mod T=(x3+ax+b)mod T.(a,b是方程系數，T是橢圓曲線的有限域)

取橢圓曲線上的一點G（x0,y0）,則公鑰K=kG （公鑰用（x，y）的坐标形式表示）。

如何了解這個公式呢 ，k是私鑰，可以用一串256位二進制數表示（1101010100……）

在K=kG中·可以表示為:

K=(d0+2w*d1+22w*d2+23Wd3+……)G ，其中{d0,d1,d2……}的元素取值為0或1. （d0,d1,d2,d3,d4,d5……）對應着私鑰對應的二進制數（110001101010010），然後未知數w代表其相應的寬度，一般來說過w可以取1.

這是橢圓曲線的相應的四個定理

1：K=-P

xk=xp

yk=(-yp)mod T (T表示橢圓曲線的有限域)

2:K=P+Q(當橢圓上P點坐标不等于橢圓上的Q點坐标的時候)

P(xp,yp),Q(xq,yq),

入=（yp-yq）/(xp-xq)

設K坐标（xk,yk）

則xk=(入2-xp-xq)mod T

yk=(入(xp-xk)-yp)mod T

3:K=P+P

入=（3xp2+a）/(2yp)

則xk=(入2-2xp)mod T

yk=(入(xp-xk)-yp)mod T

4:K=G+G+G+……=2G+G+……=G+2G+……

這裡還有一個最大階數的概念，定義：如果存在一個最小正整數n，使得K=nG不存在，則這個n就是這個橢圓曲線的階數，反之就說明這個橢圓的階不存在。如果存在n，則要滿足k<n

下面我将給出一個具體執行個體：

已知條件，私鑰k，橢圓曲線E(4，11）,有限域為17，最大階數為6，以及曲線上的随機一點G（3，4）.求K=3G.

根據已知條件可以衍生出來以下資訊

1：橢圓曲線方程 y2%17=（x3+4x+11）%17.

正常法：

求解過程如下：
先計算K1=2G的值：
G(3,4)
入=(3*3^2+4)/(2*4)mod17=31/8 mod 17
(1/8)*=>8*x mod 17=1 =>x=15
入=31*15 mod 17=6
x~2p~=(6^2 -3-3)mod 17=13
y~2p~=[6*(3-13)-4]mod 17=4
K1=2G=(13,4)
再計算K=K1+G的值
入=（4-4）/（13-3）=0
x~3p~=(0^2-3-13)mod 17=1
y~3p~=(0-4)mod 17=13
K=3G=(1,13)
           

是以按照這種規則就可以求出相應的公鑰(1,13)

還有一種幾何法，可以更加直覺的求解這個公鑰，感興趣的同學可以查找資料，筆者就不介紹了。

橢圓曲線的加密解密

已知條件：橢圓曲線E(4，20),基點G（13，23）公鑰K（14，6），明文3，橢圓曲線域為29.

首先對明文數字3進行加密：

首先我們對明文來通過某種編碼轉換為橢圓曲線上的某個點M（3，y）并産生一個随機數r（r<n,n為G的階數），假設r=6,接着将點M代入橢圓方程得到M（3，28）.

計算C1=M+rK=(6,12)

計算C2=rG=(5,7)

接下來是相應的解密過程·

已知條件：C1，C2，私鑰k

M=C1-kC2=（3，28）