Sub Dev 分享 | 签名曲线——椭圆曲线secp256k1
一块链习是首家区块链技术学习社区，提供最系统的区块链技术课程学习，定期出品有深度的技术观察 + 评论。
《从0到1学会Substrate区块链应用开发》是由Parity 和一块+ 联合出品的全球首个Parity 官方合作课程。
每周日晚8点，作为课程内容知识拓展——助教技术分享会，由各位第一期的助教们自发轮流在线上进行分享，为学员们详细解读一个 Substrate 技术相关内容。
上周日晚，由上海泰砥科技有限公司，区块链底层研发者 ——冯力全在直播间为大家带来第四讲「Substrate 椭圆曲线签名介绍」。
内容复盘如下
大家好，今天和大家分享一下substrate签名时用到的曲线之一，椭圆曲线secp256k1，它也被应用在比特币，以太坊的签名中，在区块链领域里面应用还是很广泛的。
这里是substrate的代码库，里面好几个地方都依赖了这条曲线的rust实现，libsecp256k1。
| ECC简介
ECC就是指椭圆曲线密码学。
如上的y，x 的三次方程方程，其中a,b需要满足这样的三次条件。
左边这个图就是当b=1，a分别取2，1，0，-1，-2，-3的时候，对应的椭圆曲线是这个样子。可以想象一下，如果从图中画一条直线，去劈开这个椭圆曲线的图形，一般就会和这个椭圆曲线有三个交点。这个是从几何直觉上来看的。
从代数上来看，把一条直线的方程，y=kx+b代入到这个方程里面，这样就会得到一个关于x的三次方程，满足相关的条件x就会有三个解，对应着三个交点。这个特点很重要，可以留意一下。
然后为什么a,b需要满足这样的三次条件呢，因为当它们等于0的时候，椭圆曲线上面有奇异的点或者相交的点。
最后，我们就得到了一个这样关于点的集合，就是满足要求的椭圆曲线上的所有的点，再加上最后这个，我们用0来表示的无穷远点。这里的0就不是平时我们认为的数字里面的0了，它现在代表的含义是无穷远点。
为什么要引入无穷远点，是为了所有的点组成的点集有更好的性质，而且即使出现一些棘手的情况，我们就可以把统统归纳为无穷远点。
| Group简介
当然，这些性质比较抽象，不方便理解，我们可以结合例子来看，比如整数以及整数之间的加法可以构成群。首先它满足了封闭性：任意一个整数，加上另外一个整数，结果还是一个整数。就像不管孙悟空怎么变来变去，都是在已经定义好了的72种形态里面的一种。
满足以上五条性质的群，我们就叫做交换群，也叫做阿贝尔群。阿贝尔是一个挪威的数学家，在群论有很多贡献，因此为了纪念他把可交换群命名阿贝尔群。
这里的加号，以及这里的五角星，都是代表某一种运算而已，而不仅仅只是平时理解的数字之间的加法。当然也可以用来表示加法。
然后用整数和加法来做实例，主要是为了方便理解，因为集合可以是任意事物的集合，运算规则也可以是任意的，因此群可以表示非常抽象的数学概念。
为什么要引入群呢，主要还是为了方便对椭圆曲线进行研究，因为一旦把研究对象纳入群的框架里面，就可以直接运用很多关于群的定理之类的。
| EC的Group
现在我们考虑把椭圆曲线和群结合起来。按照群的定义，只要一个集合和一个运算规则，就可以构成一个群了。
首先，我们需要有一个集合，那就是椭圆曲线上点的集合再加上无穷远点。
然后我们定义一个运算规则，那就是椭圆曲线和某条直线的三个点PQR，规定它们加起来等于0，也就是无穷远点。这个加法有点不好理解，它代表的不是数字之间的加法，你可以理解为点之间的一种运算，然后正好用加号这个符合来表示了。
接着我们看一下群对应的性质。
第0个，封闭性，那显然是成立的，因为PQR这三点不管怎么变都还是在这条曲线上，或者最多也就是无穷远点了。
第1个，存在单位元。还记得单位元的特点吗，就是其他元素和它运算，结果还是之前那个元素。这里我们为了得到这样的一个点，我们规定无穷远点加上其他点结果仍为其他点。
就像画家可以按照自己的想法画一幅画，建筑师可以按照自己的想法设计一个建筑一样，数学家也可以规定他们的世界。比如这里规定无穷远点加上其他点为仍为其他点。这不就是单位元的性质吗？因此无穷远点有了这个性质之后，就可以用它来做单位元了。
第2个，存在逆元。逆元其实是有点对称的意思，比如刚刚那个整数加法群，里面的元素和对应的逆元在数轴上关于原点对称。而这个椭圆曲线，正好关于x轴对称，因此我们规定一个点的逆元是它关于x轴对称的点，比如这里的R和-R。无穷远点的逆元就是它自身了。
第3个，满足结合律，这个天然满足，因为PQR里面这三点，确定了其中任意两点，那么这条直线就确定了，这条直线和椭圆曲线的第三个交点也确定了。同理第4点交换律也是满足的。
现在，我们通过构造集合，引入三个规定来完善运算规则，最后得到了一个椭圆曲线的阿贝尔群。
| EC的几何加法
接下来我们尝试计算任意两点的和。
第1种情况，我们讨论一般情况，我们从对应的集合里任意取两点，P，Q，将其连线后，我们将得到第三个交点R，并找到它的逆元-R。根据刚刚的规定介绍，P+Q+R=0，并根据运算规则，可推导出P+Q=-R。
接下来讨论特殊情况：
第2种情况是，P或者Q是无穷远点。这个时候我们就无法画出对应的图形了，但是根据我们之前定义时的规定，无穷远点是单位元，可以得到P+0=P,Q+0=Q。
第3种情况是，P等于Q的逆，这个时候的图形是这条红色的线，垂直于x轴的，此时没用和椭圆曲线相交于第三点。但是根据定义里面关于逆元的规定，可以得到P+Q=0
第4种情况是，P等于Q，这时这条直线和椭圆曲线相切，可以根据这个动图理解结合微积分，同样是能够求出对应的P+Q的
第5种情况是，P不等于Q，并且直线和椭圆曲线没有交点，这种情形，根据这个动图可以知道，这是应该是P或者Q正好是切点。因此根据动图可以看出，P+Q的结果就是其中某个节点，比如这里是P的逆元。
实际操作演示：
https://andrea.corbellini.name/ecc/interactive/reals-add.html
| EC的代数加法
我们通过几何的方法理解椭圆曲线上的点加法是怎么回事后，接下来就介绍椭圆曲线的代数加法。
然后我们来看第一种情况，就是最一般的情况，因为这两个P和Q不相等的，我们看一下条件是什么，知道两个点，P，Q，并且Xp不等于Xq，知道一条椭圆曲线，也就是说a,b都是已知参数，我们要求的是第三点-R的坐标。求-R的坐标其实就是求R的坐标呗，因为他们关于X轴对称。
我们联立（1）（2）这两个方程，得到一个新的方程（3）。现在m和t是可以根据这两点求出来，然后a,b是已知的，因此我们只需要求解这个三次方程的第三个根，那个根就是Xr。
如果直接去解这个三次方程还是有点麻烦的，因此这里有个简便方法。我们知道Xp,Xq,Xr是这个方程的三个根，因此上面这个方程和下面这个方程是等价的。下面这个方程化简出来是这个形式。方程3和5的系数应该是一一对应的，因此可以得到 –m^2 = -(Xp+Xq+XR)。
然后m是pq直线的斜率，因此就能够得到等式7。最后我们就求出了Xr,Yr。因此-R这点就是Xr，-Yr。
第2种情况，我们假设P=0，Q属于椭圆曲线上的点，这样直接根据定义得到解是Xq，Yq。
第3种情况，P，Q互为逆的情况下，根据定义直接得到结果为0，也就是说是无穷远点。
第4种情况，我们就可以根据这个动图，Q向P逼近，然后P+Q也慢慢向相切时的结果逼近。最后PQ重合，就发现得到一条切线，然后P+Q也固定在下面了。
但是我们的斜率公式需要换一下。
得到斜率之后，我们可以复用一般情况下推到出来的公式进行计算。这里不做证明了，但是直观来看，我们用渐进法的逼近，从一般情况，到相切，这过程没发生什么突变之类的，所以还是属于一般情况下的特例而已，自然可以复用之前Xr,Yr的公式，得到5，和6的结果。
第5种情况，其实之前的第1种情况已经涵盖了。所以你可以按照第一张情况去求对应的R。
也可以通过对比对应的斜率，看2和3里面哪一个和第一个相等，相等的就是说明R就是对应的点。比如这里可以知道是在点P处相切，那么就是第二个等式会等于第一个等式，所以R的坐标将会等于P的坐标，结果就是-P。
| EC的标量乘法
标量乘法就是一个结合律的扩展。它就是说以后这种形式，nP，它表示的意义是n个P相加，每一个加法都是遵循刚刚我们介绍的加法运算。
我们来看一下例子。这里面有个简便方法，比如求Q=4P，可以2P加2P。
现在的问题是，如果我们给定n，比如这里是151，那么得到nP点是有简便方法的。这里得到2^0P到2^7一共八个点，需要7次加法。
然后我们从中选取我们需要的，然后相加，这里就只剩下4次加法，因此应该只需要11加法。而如果是按照遍历去做的话，需要150次加法，所以简便方法的运算数量是log（N)级别。
但是如果我们给定Q，给定P，怎么得到5，也就是说怎么求这个n，目前来看没有什么好的办法，需要从1到5遍历过来。然后一个一个对应。当这个n的数字非常大的时候，比如有2^256这种级别的数字，遍历法基本上求不出来的。这也是椭圆曲线密码学里面，公开了公钥，就是Q点，公开了P点，但是无法求出私钥n的原理。
| 模运算简介
| 有限域简介
有限: 具有有限数量元素的集合。
域: 群、环、域
| 有限域里的EC
前面我可以看到，实数范围内的椭圆曲线有一些问题，一个是随意一个范围内的点都有无穷个，不方便研究。另一个是，很多点是小数，分数之类的，无法进行模运算，无法进行模运算就无法进行签名之类的。
因此我们把x，y都局限于某个范围内的自然数。这样，图像就从一条连续的曲线变成了一堆离散的点。
比如这四个图。
同样的，我们试试之前在实数域上推导出来的公式尝试求P+Q的结果。首先，根据两点求出斜率m，然后根据Xr求出Yr。
最后求出结果是（86，81），然后我们去这里验证一下。
结果正好对得上。这不是巧合，而是说我们之前在实数域上推导出来的公式同样适用于有限域。具体原因，大家可以去查看这篇论文。
https://andrea.corbellini.name/ecc/interactive/modk-add.html
https://www.uni-regensburg.de/Fakultaeten/nat_Fak_I/friedl/papers/elliptic_2017.pdf
| 群的order
群的order就是指群里面包含的元素个数。
| 标量乘法与循环子群
同样的，模运算下的椭圆曲线也满足标量乘法。
https://andrea.corbellini.name/ecc/interactive/modk-mul.html
根据观察直观的得出，nP = （n mod 5）P。既然是这样，也就是说无论n怎么变，np结果永远只涉及到五个点。那么，np是在这五点里面的，mP也是在这5点里面的，n+m。
P也是在这五点里面的，这不就是群的封闭性性质吗？因此这五点也满足群的基本性质，称之为子群。而子群的元素不断的循环，所以又叫做循环群。
子群也有order，就是子群里面的元素个数，比如这里就是5。还有个Generator/base point的概念，可以称之为生成元，就是子群里面的所有其他元素都是由这个元素生成的。
但是我们可以发现，其实其他的2P,3P,4P，只要不是那个无穷远点就行.
https://en.bitcoin.it/wiki/Secp256k1
| 签名
其中G为生成元，因此我们可以看到公钥H也是一个点。现在我们从私钥求公钥，xxxxx，最多运算255次即可得到所有需要的中间结果，然后直接选取这些中间结果再次相加运算即可，因此大概就是进行500左右的点的加法。
这基本是不可能的。因为2的256次方是10的77次方了，和已知宇宙间的原子有得一拼了。
ECDLP 椭圆曲线离散对数问题：
https://en.wikipedia.org/wiki/Elliptic-curve_cryptography
现在我们知道公开公钥是不会暴露私钥了。那签名是怎么做的呢？
第1步，得到一个 k，可以看出这个k和私钥d的地位是等价的，都是从这个集合里面找到一个随机数。但是待遇不同，私钥可以一直持有，需要保管好，而k每次签名都要临时先生成，并且不能公开。同一个k不要签名不同的消息，否则可以根据公开信息推到出私钥。
第2步 计算点P。
第3步，计算 r，其中Xp是P点的横坐标。如果r等于0，再重新选取K再次计算。可以从数轴看出，Xp的取值范围是0到p的整数，只有等于n时r才等于0，概率可以说是非常小了。而且n也只比p小一点点，需要模n的概率也是非常小的。
第4步 计算消息的哈希，因为第五步里面的对z的长度由要求，因此一般对消息做一个哈希，如果消息内容是交易，那就是对交易签名。
第5步，计算s，如果s等于0，需要重新选取k重新计算
最后（r，s）是私钥dA对消息z的签名，把这个公开了别人就能验证签名了。
| 验签
如果成立，那么就相等。
原理是什么呢
| 危险的k
虽然k是一次性使用，但是不能泄露，一旦泄露了某次签名使用到的k，那么私钥dA也泄露了。直接可以公开信息算出私钥。
而且k不能相同。2011年索尼PS3被攻破，可以在上面运行未经授权的游戏之类的。原因就是索尼使用了secp256k1签名时，使用了相同的k。
现在我们假设用相同的k签名了不同的消息，得到两组签名。可以得到r1=r2。然后我们只需要两组签名就可以推导出k来，进而推导出私钥。
libsecp256k1库简介
这个是一个用纯Rust实现的secp256k1这条曲线的密码学库，还有个Rust库只是用Rust封装了C语言实现的密码学原语。这个库感兴趣的可以自己去看。
参考资料：
https://andrea.corbellini.name/2015/05/17/elliptic-curve-cryptography-a-gentle-introduction/ https://latex.codecogs.com/eqneditor/editor.php https://andrea.corbellini.name/ecc/interactive/modk-mul.html https://en.bitcoin.it/wiki/Secp256k1 https://www.uni-regensburg.de/Fakultaeten/nat_Fak_I/friedl/papers/elliptic_2017.pdf https://en.wikipedia.org/wiki/Elliptic-curve_cryptography https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm https://docs.rs/libsecp256k1/0.3.5/secp256k1/index.html https://www.bbc.com/news/technology-12116051 https://math.berkeley.edu/~apaulin/AbstractAlgebra.pdf https://epdf.pub/an-introduction-to-mathematical-cryptography.html https://web.math.rochester.edu/people/faculty/doug/otherpapers/Husemoller.pdf
扫码进直播间，回看完整分享！
体系完善的技术开发课——在2个月的时间内，致力于通过每周1/2次的线上课程+高强度的课后代码作业任务，帮助课程中的每一位成员，实现具备入门Substrate开发的能力。
有含金量的烧脑课——虽然这是入门课，四位老师在课程中也尽量用最直白的语言讲解，并多穿插案例，但是如果想要完全理解，需要花工夫多思考和补充学习。
循序渐进的视频课 ——我们将课程按知识模块安排成12节内容，使用视频的形式，方便同学们利用碎片化时间学习；每周更新1/2节，保证之前听的能够有时间消化，循序渐进地学习。