# BTC 学习笔记连载(5)——公钥密码学：ECC

**Published by:** [Crypto 吊车尾](https://paragraph.com/@imsongoku/)
**Published on:** 2022-09-18
**URL:** https://paragraph.com/@imsongoku/btc-5-ecc

## Content

欢迎交流：twitter.com/songoku_web3 写了几篇密码学相关内容了， 我本身也不是技术出身， 这个深度理解BTC也足够了，今天最后一篇， 之前有个问题漏掉了，这里补一下：P问题、NP问题、陷门函数我们经常会提到解某个问题很困难，比如之前2篇中的多次出现的大数质因数分解问题、离散对数问题。 那到底什么是困难问题呢？ 世界上存在很多已解、未解的问题，在可计算性理论与计算复杂性理论中，判断是否存在可行的方法能够解决这些问题的叫判定问题，而求解判定问题方法常被我们称为算法。 一个问题的困难程度可以用算法的复杂度来衡量，而在计算机中运行的算法有两方面的复杂度：时间复杂度、空间复杂度。时间复杂度 任何一个算法都是由很多执行步骤组成的，对于不同配置的计算机而言，运行一个相同的算法所需要的时间不同，也就必然造成耗时不同。 所以只能以算法执行过程中的操作次数来衡量时间复杂度，随便以一个循环为例说明： int a = 0； //执行1次 int i = 0； //执行1次 int j = 0； //执行1次 for(i<n；i++) //执行n+1次 {for(j<n；j++) //执行n(n+1)次 { a++; } //执行n^2次 } 这个例子的时间复杂度为： T(n) = 3+(n+1)+n*(n+1)+n^2 = 2*n^2 +2*n + 4 这个式子当n趋近于∞时，T(n)/n^2 = 2，即T(n) 和 n^2 为同阶无穷大的关系。 用大O表示法就是T(n) = O(n^2) 大O表示法可以更简单地抽象出一个问题的复杂度，比如上面这个循环无论n取多大，它的时间复杂度就是求解一个n^2量级的问题。空间复杂度 任何算法在运行过程中都会占用一定的存储空间，而且超大数的计算还需要先对原数据进行切分再计算，一定程度上又增加了算法的时间复杂度。eg：RSA算法中明文m如果比N大，就需要先将m分成比N小的多个部分再进行加密。 这里空间复杂度就是用来度量算法所占存储空间大小的，这里不展开了。多项式时间算法 如果一个算法的时间复杂度可以表示为： O(n^t) 其中t为常数，n为算法执行次数，那么这个算法就被称为多项式时间算法。 如果一个算法的时间复杂度只能表示为： O(t^n) 其中t为常数，n为算法执行次数，那么这个算法就被称为非多项式时间算法，这种算法随着问题规模的增加复杂度以指数级别膨胀，问题在有限的时间内不可能有解。 比如计算 n^2、2^n 这2个问题，当n比较小的时候都比较容易，但当 n = 10000 的时候就完全不是一个级别的难度了。 P问题、NP问题 如果一个问题存在多项式时间算法解，那这个问题就是P问题 (Polynomial 多项式问题）； 如果一个问题不确定是否存在多项式时间算法解，但可以在多项式时间内验证它的一个解是否正确，那这个问题就是NP问题（Nondeterministic polynominal 非确定性多项式问题）； P问题：易解，易验证； NP问题：难解，易验证； BTC的挖矿求nonce就是一个NP问题，挖矿困难验证容易。 而市面上几乎所有加密算法都是基于计算安全性的，也就是指利用NP问题的难解易验证性来构造密码算法。 随着数学和计算机技术的突破，很多NP问题会转化为P问题，比如量子计算机落地应用的那一天RSA必将寿终正寝，所以密码学也需要不断更新迭代。 讲到这里了，自然要引出另一个重要概念： 陷门函数 在理论计算机科学和密码学中，陷门函数是一种在一个方向上很容易计算，但在没有特殊信息的情况下很难在相反方向上计算的函数，陷门函数是单向函数的一种特殊情况，广泛用于公钥密码学中。 随着Diffie 、Hellman和Merkle在70年代中期发表了公钥加密技术后，陷门函数开始在密码学中崭露头角，事实上是 Diffie & Hellman 在1976年创造了这个术语。 维基百科里有个陷门示例正好用来说明一下大数质因数分解问题： “6895601 是两个素数的乘积，求两个素数分别是多少？” 比较典型的“蛮力”解决方案就是用 6895601 除以2到 √6895601 的素数，直到找到答案。一般人认为这对于计算机来说可能不算是什么困难问题，那我们把这个数换成10^100-1呢？可能很多人对这个计算量其实根本没有概念。 首先我们要说 10^100-1 这个数是一个天文数字，在Crypto的世界里你经常听到的2^256也就差不多 10^77…… Anyway，假设我们除到10^28时找到了1个素数，那么至少我么要做10^28次除法，假设我们动用100台每s可以运算1亿*1亿次（10^16）大整数除法的超级计算机，那么至少需要10^10 s 才能计算出结果。 兄弟们，猜猜这是多久？ 大胆一点！ …… 10^10 / (60*60*24*365) ≈ 317.09 317 年！ 这就是大数质因数分解的困难所在，但是如果已知N是其中一个数，我们可以通过任何计算器很轻松地输入 (10^100-1 / N) 来求得答案。 我们平常工作中很多场景RSA依然是足够安全的算法，谁会吃饱了动用100台超级计算机就为了破解一条无关紧要的信息呢？ 数学就是这么神奇！阿贝尔、伽罗瓦、群论、阿贝尔群方程在数学史上的地位很高，最早的方程就是一元一次方程： ax+b = 0 公元前2000多年的古巴比伦就会解这个方程了： x = - b/a 这直接引入了分数的概念，要知道那个时候人类认知里是只有整数的。 然后到了古希腊时期，毕达哥拉斯学派在研究勾股定理的时候，通过1^2+1^2 = 2^2 发现了： x^2 = 2 x = √2 为了求解一元二次方程又引入了无理数的概念，那个时候欧洲人的概念里是没有负数的，所以只有一个√2的解，历史上最早引入负数概念的还是中国，阴阳五行一正一负…… 直到公元7世纪一元二次方程 ax^2 + bx + c = 0 才有了一般解： x = ( - b ± √( b^2-4ac )) / 2a 于是数学家们就开始寻找3次方程、4次方程的解： ax^3 + bx^2 + cx + d = 0 ax^4 + bx^3 + cx^2 + dx + e = 0 数学就是这么神奇，这一整又是大几百年。 直到16世纪欧洲文艺复兴时期，意大利数学家费罗、塔尔塔利亚才给出了一元三次方程的一般解，由卡尔丹诺著书发表。 这直接引入了复数！ 没过几年卡尔丹诺的学生费拉里有给出了4次方程的一般解。 至此一般一元 1、2、3、4 次方程都有了一般解法，那5次方程呢？ 又是卡在胯下数百年，无解！ 高斯的代数基本定理给出了结论，对于任何一个一元n次复系数方程，都恰好有n个复数根，也就是3次方程有3个根，4次方程有4个根，自然5次方程就应该有5个根……. 直到挪威数学史大神阿贝尔的出现，证明了五次方程不存在根解式！ 神挡杀神佛挡杀佛的高斯，也有漏刀的时候。 这个当时数学家都看不懂的论文寄给高斯的时候高斯根本就没当回事，认为一个21岁的愣头青能写出什么东西呢，而柯西收到之后据说连看都没有看…… 27岁阿贝尔因肺结核过世，然后人们才发现阿贝尔的论文篇篇都是经典，挪威政府从柯西那里要回论文并在挪威皇宫给阿贝尔修建了一座纪念碑。 数学界证明一个东西无解比证明它的解要难得多，而且这个证明还引入了群的思想，可惜当时阿贝尔并没有系统地提出群论。 阿贝尔的一生是悲剧的，同一时期法国还有另一个更加悲剧的神人，过了几年就用相同的思想得出了相同的结论。 这个大神就是：伽罗瓦伽罗瓦正好赶上了法国历史上最黑暗的时期，从法国大革命开始到波旁王朝复辟，最终引发了7月革命，伽罗瓦19岁就作为一名共和党人投身革命了，但因共和党失败20岁就被捕入狱，1832年21岁的伽罗瓦出狱之后因和别人决斗，腹部中枪身亡。 在伽罗瓦短短21年生命中，只有最后5年可以算是在研究数学的，但就是在这有限的几年里将人类数学史推上了一个新的高度。伽罗瓦初中时成绩非常好，本来可以提前1年毕业的，但校长因为他还太小没有同意，于是伽罗瓦在中学最后一年解封了开挂自学模式，勒让德的几何原理、拉格朗日的关于方程代数解的思考、解析函数论、函数演算讲义，还有欧拉、高斯、雅各比的数学巨著。 从14岁开始伽罗瓦就已经严重偏科数学了，最终在巴黎综合理工大学考试中落榜，复读一年后因为老师的极力推荐，学院对他只进行口试，但因为面试官提的问题太简单，伽罗瓦的回答跳过了很多步骤，搞得面试官一脸懵逼，双方自然开始了各种嘴遁垃圾话，据说当时气得伽罗瓦直接把檫黑板的抹布甩到了面试官的脸上。 巴黎综合理工大学只要2次落榜就永不录取，所以伽罗瓦只能再报考这个学院的附属师范学院，正是在这个阶段，影响世界数学史发展的学术论文出现了，但这也是悲剧命运的开始。当论文被提交给法国科学院后，又tm是柯西来审稿，柯西喜欢写又臭又长的论文，所以当他看到一份只有6页纸的论文时压根儿没当回事，带回家就搞丢了。 而正是这篇论文，证明了五次方程不存在根解式，还首次提出了“群”的概念，可以说这份论文直接解答了整个数学界近300年的困惑，柯西绝对是数学界的一大搅屎棍，如果他能认真看一看，伽罗瓦也就不会有后来那么悲惨的命运了，整个数学史也将发生翻天覆地的变化。 伽罗瓦又将整理后的论文发给傅里叶，但整整1年的等待结果确实这个老头子已经去世了，走学术路线的道理从此关闭了，暴脾气的伽罗瓦开始闹革命了。 …… 后来的故事就是出狱后跟情敌决斗身亡，决斗前3天伽罗瓦知道自己可能回不来了，奋笔疾书写下了自己生平的数学研究…… 这些手稿最终被数学家刘维尔发表！ 世界又一次震惊了！ 伽罗瓦使用群的思想去论证方程式的可解性，我们现在称其为伽罗瓦理论，伽罗瓦理论给出了任意高次方程在什么情况下有根解式，什么情况下没有根解式，直接推论的结果也十分丰富：他系统化地阐释了为何五次以上之方程式没有根式解，而四次以下有根式解。他漂亮地证明高斯的论断：对所有质数 p，用尺规作图能作出正 p 边形当且仅当 p=2^(2^(k))+1（所以正十七边形可做图）。他解决了古代三大作图问题中的两个：“不能任意三等分角”，“倍立方不可能”。伽罗瓦给人类研究了4000多年的方程式画上了圆满的句号！ 群论直接开了现代代数的先河，伽罗瓦与尼尔斯·阿贝尔也一并被称为现代群论的创始人。 如果不是传说中那个看似戏剧性的决斗，伽罗瓦绝对可以成为数学史上继高斯、欧拉之后第3位神挡杀神佛挡杀佛的存在。 阿贝尔群 在一个集合上定义一个二元运算，这就是数学中的群，一个群由自身的集合和二元运算符组成，比如二元运算“加法”用符号“+”表示，必须要满足一下几个条件：封闭性 如果a和b被包含于群{G} ，那么a+b也一定在群{G}中。结合律存在一个单位元 单位元：与任意元素运算都不改变其值 a+0 = 0+a = a每个数都存在一个相反数。 如果我们再加上第五个条件:交换律(commutativity):a+b = b+a.这个群就叫做阿贝尔群(abelian group)。 从我们通常的加法二元运算来看，整个整数集{Z}就是一个阿贝尔群。椭圆曲线、群论、ECC什么是椭圆曲线？ 在数学上椭圆曲线就是如下方程定义的一条曲线： y^2 = x^3 + ax + b要满足椭圆曲线无奇点，还需要 4a^3 + 27b^2 ≠ 0，无奇点即曲线即没有尖点或自相交。椭圆曲线的奇点在实数上的椭圆曲线的一些特征可以使用入门级别的代数与几何来描绘，当a、b为实数时，这个方程被称为椭圆曲线的维尔斯特拉斯标准形式（Weierstrass normal form）。 非常明显椭圆曲线都是相对于x轴对称的，这是天然的相反数。 椭圆曲线上的群论 我们可以在椭圆曲线上定义一个群：椭圆曲线上的点构成群中的元素；单位元就是无穷处的点0； (跟欧式几何不同，黎曼几何定义任何平行线都相较于无穷远点，即0点)相对于x轴对称的2个点互为相反数P；定义这个群上的加法规则： 设一条直线穿过椭圆曲线形成三个点 P, Q, R，那么 P + Q + R = 0；请注意这三个相交于椭圆曲线上的点，并没有规定顺序，也就是说： P+(Q+R) = Q+(P+R) = R+(P+Q) = 0 这是是符合交换律和结合律的，显然这就是一个阿贝尔群。 为什么 P + Q + R = 0 呢？ 这是定义的，就像我们在算术中定义 1+1 = 2 一样。 既然它是一个阿贝尔群，那么自然 P+Q+R=0 就可以写成 P+Q=−R，这就派生出了用一个几何方法去计算2个点的和，自然地-R 也就是R相对于x轴对称的那个点。这里面还有些特殊的情况需要说明：P、Q ≠ 0，否则它就是平面上无穷远的点如果P = -Q，那么它是一条垂直x轴的线，不会有肉眼可见的第3个点相交，只能与椭圆曲线相交于无穷远的点如果P = Q，我们可以假设一开始Q ≠ P，而是慢慢地接近P，这条线就会成为椭圆曲线的一条切线，P为切点，自然就有 P + P + R = 0，也就是 P + P=-RQ点在曲线上无限接近P点，最终重合在一起如果P ≠ Q，但没有相交于第3个点呢？我们也可以假设一开始R ≠ Q，而是慢慢地接近Q，这条线也会成为椭圆曲线上的一条切线，Q为切点，自然就有 P + Q = -Q这就是椭圆曲线的几何运算，但是想要一台计算机能够运行这些点的加法，就必须把几何方法转换成代数方法：P = （xp，yp）、Q = （xq，yq）交点R = （xr，yr）这条线的斜率就 = (yp - yq) / (xp - xq)假设椭圆曲线为 y^2 = x^3 - 9x + 10这样就可以通过求解（xr，-yr）求得 P + Q 的结果了。这个计算过程这里不展开了，我本身也不是技术出身，尽量理解得深入一点就可以了。 ECC（Elliptic Curve Cryptography）就是椭圆曲线密码学，即一种基于椭圆曲线的非对称加密算法，在1985年由 Neal Koblitz 和 Victor Miller 分别提出。 上一篇讲过的RSA是公钥密码学的祖师爷，为什么还需要ECC呢？ 安全性！安全性的飞跃提升。 曾经有人做过一种关于密码学的碳排放量的衡量，破解一个228字节的RSA秘钥所需能量少于煮沸一勺水的能量，但破解一个228字节的椭圆曲线秘钥所需能量足以煮沸地球上所有的水，可见ECC比RSA要高效得多。 为什么ECC如此安全呢？ 这里还是从椭圆曲线的标量乘法说起，前面定义过的椭圆曲线上的点的加法运算： G + G = -R = 2G G + G + G = 3G … G + G + … + G = nG 所以nG就是在椭圆曲线上进行n次加法，如果n是一个k位二进制数，那么这个运算的时间复杂度就是O(2^k)，这是一个困难问题。椭圆曲线的倍加算法椭圆曲线有一个天然的倍加算法，可以直接将加法运算指数化：G+G = 2G2G + 2G = 4G…2^(n-1)G + 2^(n-1)G = 2^nG当n为一个二进制数k时，这直接将一个O(2^k)问题转化成了O(k)问题。 ok，到这里我们试想一下如果我们基于点G，经过2^k-1 次加法后得到一个点G’，现在有一个攻击者知道了点G、G’，要算出k，这不开玩笑么？ 怎么可能通过平面上的2个点，反推它是经过多少次运算得到的，可见椭圆曲线函数是一个典型的单向陷门函数。 上面我们讲的都是实数域上连续的椭圆曲线，通常ECC作为非对称加密算法都会将其扩展到了整数有限域上： y^2 mod p =（x^3 + ax + b）mod p (p是一个大素数) 这样椭圆曲线就被扩展为素数阶p的有限域内，在坐标平面上看起来就是一系列离散的点：运算规则和连续的椭圆曲线是完全相同的，如图的 A + B = C，那就有了：椭圆曲线上点的标量乘法相当于幂模运算椭圆曲线上点的”除法”就是离散对数运算BTC 从私钥生成公钥就是基于ECC的，我们掌握一个私钥k，通过一个基点G，就可以直接算出公钥K了： K = k*G mod p p：超大素数 G：椭圆曲线上一个很大的点 k：1个256位的二进制数 显然通过倍加运算从k求得K是简单的，但通过K要想反推k这是一个离散对数问题。 密码学的东西写到这里差不多了，其实这种程度也仅仅是了解一点皮毛而以，我们如果不是研究数学、密码学的工作者，也大可不必研究得太深了，最终我们还是要回归到搞钱上。

## Publication Information

- [Crypto 吊车尾](https://paragraph.com/@imsongoku/): Publication homepage
- [All Posts](https://paragraph.com/@imsongoku/): More posts from this publication
- [RSS Feed](https://api.paragraph.com/blogs/rss/@imsongoku): Subscribe to updates
- [Twitter](https://twitter.com/songoku_web3): Follow on Twitter