[区块链] 密码学——椭圆曲线密码算法（ECC）

　　今天在学椭圆曲线密码（Elliptic Curve Cryptography，ECC）算法，我本人手里缺少介绍该算法的专业书籍，故在网上查了本来我博文与书籍，一点大多数博客写的真的是。。。你懂的。。。真不愧是 ‘天下文章一大抄’ 啊！ 雷同不说，关键是介绍的都都会很清楚，是我在阅读过程中、产生的本来我大问题无法防止！类似于于：只来句‘P+Q=R’，一点为你类似于于于等于呢？是根据你类似于于于计算出来的呢？ 本来我查了几时，才发现：这是规定的、是定义！瞬间很是无语！

　　好了，不吐槽了，为了方便朋友对椭圆曲线密码算法有系统的了解，我下发了几篇较好的博文，并加在了我本人的见解！

　　[  时间有限、见解不深，如总出 错误，欢迎指正！]

---

　　比特币使用椭圆曲线算法生成公钥和私钥，选用的是secp256k1曲线。

　　椭圆曲线密码学（Elliptic Curve Cryptography） 的缩写。该算法是基于椭圆曲线数学的三种公钥密码的算法，其安全性依赖于椭圆曲线离散对数大问题的困难性。

　　在ECC流行起来以前，几乎所有的公钥算法都会基于RSA、DSA和DH ———— 基于模运算的可选加密系统。RSA及其友类算法在当前仍非常重要，总爱与ECC一并使用。不过，RSA及其友类算法面前的原理很容易解释，因而被广泛理解，一点简单的实现也都要很容易编写出来；但ECC的实现基础对于大多数人来说仍很神秘。

 　　具体来说，我将触及以下主题：

　　1. 数学上的椭圆曲线及相关概念

　　2. 密码学中的椭圆曲线

　　3. 椭圆曲线上的加密/解密

　　4. 椭圆曲线签名与验证签名

---

一、数学上的椭圆曲线及相关概念

 　　1.1  从平行线谈起

　　平行线，永不相交。不过到了近代你类似于于于结论遭到了质疑。平行线会不必在很远很远的地方相交？事实上越来越 人见到过。本来我“平行线，永不相交”本来我假设（朋友想想初中学习的平行公理，是越来越 证明的）。既然都要假设平行线永不相交，也都要假设平行线在很远很远的地方相交了。即平行线相交于无穷远点P∞（请朋友闭上眼睛，想象一下那个无穷远点P∞，P∞是都会很虚幻，我我着实与其说数学锻炼人的抽象能力，还不如说是锻炼人的想象力）。给个图帮助理解一下：

  

　　直线上总出 P∞点，所带来的好处是所有的直线都相交了，且只能好几个 多多交点。这就把直线的平行与相交统一了。为与无穷远点相区别把从前平面上的点叫做平常点。

　　以下是无穷远点的几个性质。

　　▲直线L上的无穷远点只能有好几个 多多。（从定义可直接得出）

　　▲平面上一组相互平行的直线有公共的无穷远点。（从定义可直接得出）

　　▲ 平面上任何相交的两直线L1,L2有不同的无穷远点。（一点L1和L2有公共的无穷远点P ，则L1和L2有好几个 多多交点A、P，故假设错误。）

　　▲平面上全体无穷远点构成根小无穷远直线。（我本人想象一下这条直线吧）

　　▲平面上全体无穷远点与全体平常点构成射影平面。

　　1.2  射影平面坐标系

　　射影平面坐标系是对普通平面直角坐标系（本来我朋友初中学到的那个笛卡儿平面直角坐标系）的扩展。朋友知道普通平面直角坐标系越来越 为无穷远点设计坐标，只能表示无穷远点。为了表示无穷远点，产生了射影平面坐标系，当然射影平面坐标系同样能很好的表示旧有的平常点（数学也是“向下兼容”的）。

　　朋友对普通平面直角坐标系上的点A的坐标（x,y）做如下改造：

　　令x=X/Z ，y=Y/Z（Z≠0）；则A点都要表示为（X:Y:Z）。

　　变成了有好几个 多多参量的坐标点，这就对平面上的点建立了有好几个 多新的坐标体系。

　　例1：求点（1,2）在新的坐标体系下的坐标。

　　解：∵X/Z=1 ，Y/Z=2（Z≠0）∴X=Z，Y=2Z ∴坐标为（Z:2Z:Z），Z≠0。即（1:2:1）（2:4:2）（1.2:2.4:1.2）等形如（Z:2Z:Z），Z≠0的坐标，都会（1,2）在新的坐标体系下的坐标。

　　朋友也都要得到直线的方程aX+bY+cZ=0（想想为你类似于于于？提示：普通平面直角坐标系下直线一般方程是ax+by+c=0）。新的坐标体系后能 表示无穷远点么？那要让朋友先想想无穷远点在哪里。根据上一节的知识，朋友知道无穷远点是两条平行直线的交点。越来越 ，咋样求两条直线的交点坐标？这是初中的知识，本来我将两条直线对应的方程联立求解。平行直线的方程是：aX+bY+c1Z =0； aX+bY+c2Z =0  (c1≠c2)；

　　（为你类似于于于？提示：都要从斜率考虑，可能平行线斜率相同）；

　　将二方程联立，求解。有c2Z= c1Z= -（aX+bY），∵c1≠c2 ∴Z=0  ∴aX+bY=0；

　　本来我无穷远点本来我你类似于于于形式（X：Y：0）表示。注意，平常点Z≠0，无穷远点Z=0，一点无穷远直线对应的方程是Z=0。

　　例2：求平行线L1：X+2Y+3Z=0 与L2：X+2Y+Z=0 相交的无穷远点。

　　解：可能L1∥L2 本来我有Z=0， X+2Y=0；本来我坐标为（-2Y:Y:0），Y≠0。即（-2:1:0）（-4:2:0）（-2.4:1.2:0）等形如（-2Y:Y:0），Y≠0的坐标，都表示你类似于于于无穷远点。

　　看来你类似于于于新的坐标体系后能 表示射影平面上所有的点，朋友就把你类似于于于后能 表示射影平面上所一阵一阵的坐标体系叫做射影平面坐标系。

　　1.3  椭圆曲线

　　上一节，朋友建立了射影平面坐标系，你类似于于于节朋友将在你类似于于于坐标系下建立椭圆曲线方程。可能朋友知道，坐标中的曲线是都要用方程来表示的（比如：单位圆方程是x²+y²=1）。椭圆曲线是曲线，自然椭圆曲线都会方程。

　　椭圆曲线的定义：

　　根小椭圆曲线是在射影平面上满足方程---------------------------[1-1]的所一阵一阵的集合，且曲线上的每个点都会非奇异（或光滑）的。

　　定义详解：

　　▲[1-1] 是Weierstrass方程（维尔斯特拉斯，Karl Theodor Wilhelm Weierstrass,1815-1897），是有好几个 多齐次方程。

　　▲ 椭圆曲线的行态，并都会椭圆的。本来我可能椭圆曲线的描述方程，类似于于于计算有好几个 多椭圆周长的方程，故得名。

　　朋友来看看椭圆曲线是你类似于于于样的。

  

　　▲ 所谓“非奇异”或“光滑”的，在数学中是指曲线上任意一点的偏导数F_x(x,y,z)，F_y(x,y,z)，F_z(x,y,z)只能一并为0。可能你越来越 学欠缺等数学，都要从前理解你类似于于于词，即满足方程的任意一点都处在切线。

　　下面有好几个 多方程都都会椭圆曲线，尽管朋友是方程[3-1]的形式。

 

 

　　可能朋友在（0:0:1）点处（即原点）越来越 切线。

　　▲椭圆曲线上有好几个 多多无穷远点O∞（0:1:0），可能你类似于于于点满足方程[1-1]。

　　知道了椭圆曲线上的无穷远点。朋友就都要把椭圆曲线倒进普通平面直角坐标系上了。可能普通平面直角坐标系只比射影平面坐标系少无穷远点。朋友在普通平面直角坐标系上，求出椭圆曲线上所有平常点组成的曲线方程，加在在无穷远点O∞（0:1:0），不就构成椭圆曲线了么？

　　朋友设x=X/Z ，y=Y/Z代入方程[1-1]得到：

　　y²+a₁xy+a₃y = x³+a₂x²+a₄x+a₆ -------------------------[1-2]

　　也本来我说满足方程[1-2]的光滑曲线加在有好几个 多无穷远点O∞，组成了椭圆曲线。为了方便运算，表述，以及理解，今后论述椭圆曲线将主要使用[1-2]的形式。

　　本节的最后，朋友谈一下求椭圆曲线一点的切线斜率大问题。

　　由椭圆曲线的定义都要知道，椭圆曲线是光滑的，本来我椭圆曲线上的平常点都会切线。而切线最重要的有好几个 多参数本来我斜率k。

　　例3：求椭圆曲线方程上，平常点A(x,y)的切线的斜率k。

　　解：令F(x,y)= y²+a₁xy+a₃y-x³-a₂x²-a₄x-a₆

　　求偏导数

　　F_x(x,y)= a₁y-3x²-2a₂x-a₄

　　F_y(x,y)= 2y+a₁x +a₃

　　则导数为：f'(x)=- F_x(x,y)/ F_y(x,y)=-( a1y-3x2-2a2x-a4)/(2y+a1x +a3)

　　　　　　　　 = (3x2+2a2x+a4-a1y) /(2y+a1x +a3)

　　本来我 -------------[1-3]

　　看不懂解题过程越来越 关系，记住结论[1-3]就都要了。

　　1.4  椭圆曲线上的加法

　　上一节，朋友可能看到了椭圆曲线的图象，但点与点之间好象越来越 你类似于于于联系。朋友都要建立有好几个 多类似于于于在实数轴加在法的运算法则呢？天才的数学家找到了你类似于于于运算法则

　　自从近世纪代数学引入了群、环、域的概念，使得代数运算达到了深层的统一。比如数学家总结了普通加法的主要行态，提出了加群（也叫交换群，或Abel（阿贝尔）群），在加群的眼中。实数的加法和椭圆曲线的上的加法越来越 你类似于于于区别。这他说本来我数学抽象把：）。关于群以及加群的具体概念请参考近世代数方面的数学书。

　　运算法则：任意取椭圆曲线上两点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∞

同总爱线上的有好几个 多点之和等于0.

　　注：朋友都要的本来我有好几个 多点同线，与点的次序无关。这导致 ，可能P、Q和R同线，越来越 P + (Q + R) = Q + (P + R) = R + (P + Q) = • • • = 0. 从前，朋友直观地证明了朋友的“+”运算既满足结合律也满足交换律。　　

　　▲k个相同的点P相加，朋友记作kP。如下图：P+P+P = 2P+P = 3P。

　　下面，朋友利用P、Q点的坐标(x₁,y₁)，(x₂,y₂)，求出R=P+Q的坐标(x₄,y₄)。

　　例4：求椭圆曲线方y²+a₁xy+a₃y = x³+a₂x²+a₄x+a₆上，平常点P(x1,y1)，Q(x2,y2)的和R(x4,y4)的坐标。

　　解：（1）先求点-R(x₃,y₃)

　　可能P,Q,-R三点共线，故设共线方程为y=kx+b,其中

　　若P≠Q(P,Q两点不重合) 则

　　直线斜率k=(y1-y2)/(x1-x2)

　　若P=Q(P,Q两点重合) 则直线为椭圆曲线的切线，故由例3.1可知：

　　k=(3x2+2a2x+a4 -a1y) /(2y+a1x+a3)

　　一点P,Q,-R三点的坐标值本来我方程组：

　　y2+a1xy+a3y=x3+a2x2+a4x+a6    -----------------[1] 

　　y=(kx+b)                     -----------------[2]

的解。

　　将[2]，代入[1] 有

　　(kx+b)2+a1x(kx+b)+a3(kx+b) =x3+a2x2+a4x+a6    --------[3]

　　对[3]化为一般方程，根据三次方程根与系数关系（当三次项系数为1时；-x1x2x3 等于常数项系数， x1x2+x2x3+x3x1等于一次项系数，-(x1+x2+x3)等于二次项系数。）

　　本来我-(x1+x2+x3)=a2-ka1-k2

　　x3=k2+ka1+a2+x1+x2;---------------------求出点-R的横坐标

　　可能k=(y1-y3)/(x1-x3) 故

　　y3=y1-k(x1-x3);-------------------------------求出点-R的纵坐标

　　（2）利用-R求R

　　显然有 x4=x3= k2+ka1+a2+x1+x2; ------------求出点R的横坐标

　　而y3 y4 为 x=x4时 方程y2+a1xy+a3y=x3+a2x2+a4x+a6的解

　　化为一般方程y2+(a1x+a3)y-(x3+a2x2+a4x+a6)=0 , 根据二次方程根与系数关系得：

　　-(a1x+a3)=y3+y4

　　故y4=-y3-(a1x+a3)=k(x1-x4)-y1-(a1x4+a3); ---------------求出点R的纵坐标

　　即：

　　x4=k2+ka1+a2+x1+x2;

　　y4=k(x1-x4)-y1-a1x4-a3;

　　本节的最后，提醒朋友注意一点，以前提供的图像可能会给朋友产生三种错觉，即椭圆曲线是关于x轴对称的。事实上，椭圆曲线三种一定关于x轴对称。如下图的y2-xy=x3+1

---

二、密码学中的椭圆曲线　

　　朋友现在基本上对椭圆曲线有了初步的认识，这是值得高兴的。

　　但请朋友注意，前面学到的椭圆曲线是连续的，并不适合用于加密；本来我，朋友都要把椭圆曲线变成离散的点, 要把椭圆曲线定义在有限域上。

　　让朋友想一想，为你类似于于于椭圆曲线为你类似于于于连续？是可能椭圆曲线上点的坐标，是实数的（也本来我说前面讲到的椭圆曲线是定义在实数域上的），实数是连续的，导致 了曲线的连续。一点，朋友要把椭圆曲线定义在有限域上（顾名思义，有限域是三种只能由有限个元素组成的域）。

　　域的概念是从朋友的有理数，实数的运算中抽象出来的，严格的定义请参考近世代数方面的数。简单的说，域中的元素同有理数一样，有我本人得加法、乘法、除法、单位元(1)，零元(0),并满足交换率、分配率。

　　下面，朋友给出有好几个 多有限域Fp，你类似于于于域只能有限个元素。

   

　　Fp中只能p（p为素数）个元素0,1,2 …… p-2,p-1；

　　Fp 的加法（a+b）法则是 a+b≡c (mod p)；即，(a+b)÷p的余数 和c÷p的余数相同。

　　Fp 的乘法(a×b)法则是  a×b≡c (mod p)；

　　Fp 的除法(a÷b)法则是  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(mod p) 这条曲线定义在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)。

　　朋友看一下y2=x3+x+1  (mod 23)的图像

　　是都会我着实不可思议？椭圆曲线，咋样在么在变成了这般模样，成了有好几个 多有好几个 多离散的点？

　　椭圆曲线在不同的数域中会呈现出不同的样子，但其本质仍是根小椭圆曲线。举有好几个 多不太恰当的例子，好比是水，在常温下，是二氧化碳；到了零下，水就变成冰，成了二氧化碳；而温度上升到一百度，水又变成了水蒸气。但其本质仍是H₂O。

　　Fp上的椭圆曲线同样有加法，但可都要给以几何意义的解释。不过，加法法则和实数域上的差太满，请读者自行对比。

　　1. 无穷远点 O∞是零元，有O∞+ O∞= O∞，O∞+P=P

　　2. P(x,y)的负元是 (x,-y)，有P+(-P)= O∞

　　3. 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=(3x2+a)/2y1  若P≠Q，则k=(y2-y1)/(x2-x1)

　　例5： 已知椭圆曲线已知E23(1,1)上两点P(3,10)，Q(9,7)，求(1)-P，(2)P+Q，(3) 2P

          

        

解：

      

　　最后，朋友讲一下椭圆曲线上点的阶。

　　可能椭圆曲线上一点P，处在最小的正整数n，使得数乘nP=O∞，则将n称为P的 阶，若n不处在，朋友说P是无限阶的。

　　事实上，在有限域上定义的椭圆曲线上所有的点的阶n都会处在的。

       

　　计算可得27P=-P=(3,13)

　　本来我28P=O ∞ P的阶为28

　　你类似于于于点做成了有好几个 多循环阿贝尔群，其中生成元为P，阶数为29。显然点的分布与顺序都会杂乱无章

---

三、椭圆曲线上的加密/解密

　　公开密钥算法总爱要基于有好几个 多数学上的大问题。比如RSA 依据的是：给定有好几个 多素数p、q 很容易相乘得到n，而对n进行因式分解却相对困难。那椭圆曲线上有你类似于于于大问题呢？

　　考虑如下等式：

　　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)。<="" p="">

　　现在朋友描述有好几个 多利用椭圆曲线进行加密通信的过程：

　　1、用户A选定根小椭圆曲线Ep(a,b)，并取椭圆曲线上一点，作为基点G。

　　2、用户A选用有好几个 多私有密钥k，并生成公开密钥K=kG。

　　3、用户A将Ep(a,b)和点K，G传给用户B。

　　4、用户B接到信息后 ，将待传输的明文编码到Ep(a,b)上一点M（编码依据本来我，这里不作讨论），并产生有好几个 多随机整数r（r<n）。

　　5、用户B计算点C1=M+rK；C2=rG。

　　6、用户B将C1、C2传给用户A。

　　7、用户A接到信息后，计算C1-kC2，结果本来我点M。

　　可能C1-kC2=M+rK-k(rG)=M+rK-r(kG)=M再对点M进行解码就都要得到明文。

　　在你类似于于于加密通信中，可能有好几个 多多偷窥者H ，他只能看到Ep(a,b)、K、G、C1、C2 而通过K、G 求k 或通过C2、G求r 都会相对困难的。一点，H无法得到A、B间传送的明文信息。

总结：   

设私钥、公钥分别为k、K，即K = kG，其中G为G点。
 
　　公钥加密：
　　选用随机数r，将消息M生成密文C，该密文是有好几个



多点对，即：
　　C = {rG, M+rK}，其中K为公钥
 
　　私钥解密：
　　M + rK - k(rG) = M + r(kG) - k(rG) = M
　　其中k、K分别为私钥、公钥。

       ECC技术要求：

　　密码学中，描述根小Fp上的椭圆曲线，常用到好几个 参量：

       T=(p,a,b,G,n,h)。

　　（p 、a 、b 用来选用根小椭圆曲线，G为基点，n为点G的阶，h 是椭圆曲线上所一阵一阵的个数m与n相除的整数次要）

　　这几个参量取值的选用，直接影响了加密的安全性。参量值一般要求满足以下几个条件：

　　1、p 当然越大越安全，但越大，计算时延会变慢，400位左右都要满足一般安全要求；

　　2、p≠n×h；

　　3、pt≠1 (mod n)，1≤t<20；

　　4、4a3+27b2≠0 (mod p)；

　　5、n 为素数；

　　6、h≤4。

---

四、椭圆曲线签名与验证签名

 　　椭圆曲线签名算法，即ECDSA。

　　设私钥、公钥分别为k、K，即K = kG，其中G为G点。

 

　　私钥签名：

　　1、选用随机数r，计算点rG(x, y)。

　　2、根据随机数r、消息M的哈希h、私钥k，计算s = (h + kx)/r。

　　3、将消息M、和签名{rG, s}发给接收方。

 

　　公钥验证签名：

　　1、接收方收到消息M、以及签名{rG=(x,y), s}。

　　2、根据消息求哈希h。

　　3、使用发送方公钥K计算：hG/s + xK/s，并与rG比较，如相等即验签成功。

 

　　原理如下：

　　hG/s + xK/s = hG/s + x(kG)/s = (h+xk)G/s

　　= r(h+xk)G / (h+kx) = rG

---

【时间仓促，如有错误，欢迎指正！ ||   欢迎留下您的评语！  朋友一并探讨、学习区块链!】

【转载请注明出处！http://www.cnblogs.com/X-knight/】

---

REFERENCE

1.巴比特论坛 作者：ZMWorm http://8btc.com/article-138-1.html

2.张禾瑞，《近世代数基础》，高等教育出版社，1978

3.闵嗣鹤 严士健，《初等数论》，高等教育出版社，1982

4. ECC详解 https://www.cnblogs.com/Kalafinaian/p/73924005.html