由浅及深了解区块链之：（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）