[区块链] 密码学——椭圆曲线密码算法（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  椭圆曲线上的加法

　　上一节，给有人歌词 有人歌词 有人歌词 将会看过了椭圆曲线的图象，但点与点之间好象不都还上能 有哪些联系。给有人歌词 有人歌词 有人歌词 可不也能 建立六个 累似 于于在实数轴打上去法的运算法则呢？天才的数学家找到了这俩运算法则

　　自从近世纪代数学引入了群、环、域的概念，使得代数运算达到了深度1的统一。比如数学家总结了普通加法的主要底部形态，提出了加群（也叫交换群，或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 当然越大越安全，但越大，计算速率单位会很快，150位左右可不也能 满足一般安全要求；

　　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/73921505.html