主页 > imtoken下载app > 咖啡谈话 | 大白话椭圆曲线加密算法（下）
咖啡谈话 | 大白话椭圆曲线加密算法（下）
“
汇聚一批行业大咖的意见，共同探讨区块链业务和应用。 百家争鸣，百花齐放，推理、破译、预测、八卦，了解行业内幕，看咖聊！
投稿请联系：tougao@conflux-chain.org
本文作者：余双奇比特币非对称加密算法，区块链技术CTO，登录学院合伙人。
“
您应该听说过 ECC、ECDH 或 ECDSA。 ECC是Elliptic curve cryptography（椭圆曲线密码学）的缩写，后两者都是基于其算法实现的。
在数字货币加密技术中，不得不说ECC，它是数字货币安全的基石。 本文不涉及ECC中复杂的数学知识，作者将尽量用通俗易懂的语言来讲解ECC是如何提供和保证加密安全的。
整篇文章首先讲解涉及的基础理论知识，然后讲解ECC的定义，然后通过实例讲解ECC的加解密原理和ECDSA的签名原理。 不了解理论基础的读者，请务必先掌握理论基础再继续阅读，不建议跳过。
一、椭圆曲线的理论基础
本节链接：
2. ECC椭圆曲线加密算法
2.1. 定义
椭圆曲线加密算法描述了一条Fp的椭圆曲线，记为：T=(p,a,b,G,n,h)。
在：
1.p,a,b用于确定一条有限域椭圆曲线Ep(a,b)；
2、G为基点；
3、n为G点的阶数；
4.h为椭圆曲线上所有点的个数m和n相除的整数部分。
这些参数的取值直接影响加密的安全性。 参数值一般满足以下条件：
1.p 当然越大越安全。 但是越大，计算速度会越慢，200位左右可以满足一般的安全要求；
2. p ≠ nh ；
3. pt ≠ 1 (mod n), t ∈ [1,20];
4.4a^3+27b^2≠0(mod p)；
5、n为素数；
6、h≤4。
2.2. 安全
如果已知k和G，则根据乘法法则很容易求出K，反之，只知道K和G，则很难求出k。
在普通代数中，假设你有一个数字 10，有人告诉你他乘以 5 得到 10，你知道另一个乘数一定是 2。但是在 ECC 中，很难找到 k。
为了找到k，需要暴力枚举，直到找到满足条件的点。 以目前人类文明的计算能力，这是不可能的，尤其是当你使用一个非常大的值n时。
原则上，实际应用中的ECC会使k很大，n也很大。 不可能一个一个计算n个节点。 这个求k的逆过程的难点是离散对数问题。 这个问题的难度保证了ECC的安全性。
这里k是私钥（private key），K是公钥（public key）。 从私钥推算出公钥非常容易，但是从公钥反推私钥就非常困难了。
非常困难并不意味着不可能。 科学家们试图通过量子计算机的强力枚举来找到k值。 不过也不用太担心。 现有的量子计算机还处于婴儿期，科学家们也在研究抗量子计算机破解的加密算法。
2.3. 加解密原理及演示
在ECC之前，有RSA等非对称加密算法，但ECC是一种更优越的非对称加密算法。
假设情报人员葛尔丹需要将一条信息加密传输到延安司令部。 如果葛二蛋掌握了椭圆曲线加密算法，就可以通过这种方式加密传输信息。
第一部分：延安司令部告诉葛二蛋用哪把公钥加密信息。
1、延安指挥部选取一条椭圆曲线Ep(a,b)和一个基点G。假设选取E23(4,20)，基点G(13,23)，G的阶数为n =37。
2. 使用私钥k，生成公钥K=kG。 假设k=25，则K=25G=(14,6)。
3、将椭圆曲线E23(4,20),n=37,K(14,6),G(4,20)传给二蛋哥。
第二部分：葛尔丹使用公钥K加密信息。
1. 葛二蛋对要传递的信息进行编码。 假设编码结果为3；
2、在椭圆曲线E23(4,20)上，当x=3时，y=28。 将此点M(3, 28)作为智能码在曲线上的映射；
3.生成一个随机数r(r
4、计算点C1=M+rK和C2=rG；
1）C1=M+6K=M+6*25G=M+150G=（3,28）+（27,27）=（6,12）；
2) C2=rG=6G=(5,7);
5、将C1(6,12)、C2(5,7)点转移到延安指挥部；
第三部分：延安司令部解密资料。
延安司令部收到C1和C2后，计算C1-kC2，计算结果应为智能在曲线上的映射点M。
C1 - kC2= C1- 25C2= (6,12) - 25(5,7)=(6,12) - (27,27)= (6,12) + (27,2)=(3,28) .
延安司令部之所以能够解密资料，是因为：
在这个加解密过程中，如果有偷窥者H，他只能看到Ep(a,b)、K、G、C1、C2。
通过K=kG找到k或通过C2=rG找到r相对困难。 因此，H 无法得到 A 和 B 发送的明文消息。
需要强调的是，如果延安指挥部需要对葛二蛋进行加密下达指令，也可以按同样的方式进行。 唯一不同的是，延安指挥部需要使用葛二蛋提供的公钥进行加密。 只要不泄露双方的私钥，他们之间的信息交换就是安全的，即使落入他人之手，也无法解密。
2.4. ECDSA数字签名原理
有一次，延安司令部需要紧急通知所有情报人员，“国共合作宣告破裂，请务必保护好自己，躲藏起来。” 情况紧急，如果延安司令部把加密通知一一发给所有情报人员，效率低下。 延安司令部可以把这个通知登在报纸上，让各地的情报人员一大早起床就能看到。
但问题是，情报人员如何确定通报真的来自延安司令部？ 这里，我们需要用到数字签名技术。
ECC是一种加密算法，不能直接用于数字签名。 在ECC之前，已经有数字签名（digital signature）技术比特币非对称加密算法，比如DSA。
椭圆曲线签名算法（ECDSA）使用ECC模拟DSA数字签名算法，最终签名可以得到两个值r和s。 验证签名只需要解出一个值，判断该值是否与r相同，如果相同则为有效签名。
对于 ECDSA 签名，Ep(a,b)、基点 G 和 G 的阶数 n 是已知的。
第 1 部分：生成摘要
待签名内容其实并不是待签名数据的明文，而是待签名数据的哈希值。
称为是：
第 2 部分：生成签名
1、产生一个随机数k，k是一个小于n的正整数。
2.计算
3.计算
如果 x mod n 为 0，则返回步骤 1 并再次尝试随机数。
4.计算
其中 dA 是私钥。 这里的k^-1不是k的-1次方，而是k的倒数。 ECC中有a·a-1 (mod n)=O∞=1
5、签名结果为r,s。 公开签署数据消息和 r 和 s 值。
第 3 部分：验证签名
1.计算
2.计算
3.计算点R，
其中 K 是签名者的公钥。
4.判断R点是否等于rG。 如果两者相同，则签名是合法的。 验证求解的R的计算过程如下：
为什么说只需要解决R呢？ 这是因为：
这里的关键是在签名中引入了随机数k来提供安全性。 即使是同一条消息，只要改变随机数k，得到的签名也会随之改变。
2.5. 签名演示
现在，延安总部将使用ECDSA签名的通知刊登在报纸上。 假设已知信息如下：
·延安指挥部签字
1、假设延安总部私钥为7，则K=kG=7(2,6)=(3,28)；
2.生成一个随机数k = 11；
3、计算P=kG=11(2,6)=(16,2)；
4. 计算 r= 16 mod 37 = 16；
5.计算s= k-1(h+rk) mod 37 = k-1 (88+16*7) mod 37 = 200 k-1 mod 37。因为k•k-1 (mod 37)=11•k -1 (mod 37)=1, k-1为27. 所以s= 5400 mod 37 =35;
6、在报纸上刊登通知及签字结果（r、s）；
·智能验证签名
1、计算u1= s-1 *88 mod 37 = 18*88 mod 37 =30；
2、计算u2 = s-1 *16 mod 37 = 18 *16 mod 37 =29；
3、计算R=30G+29K=(3,1)+(14,23)=(16,2)；
4、计算16 mod 37 = 16等于r，说明签名合法；
2.6.secp256k1
secp256k1是由高效密码组标准（SECG）协会制定的一套高效椭圆曲线签名算法标准。 直到比特币流行起来，secp256k1 才真正被使用。 从比特币开始，secp2256k1成为数字货币默认的数字签名算法。 最常用的曲线具有随机结构，但 secp256k1 构建非随机结构以提高计算效率。 因此，如果对该算法的实现进行适当的优化，其计算效率可以比其他曲线快30%以上。 同时，与常用的NIST曲线不同的是，secp256k1的常数是以可预测的方式选取的，可以有效降低防止曲线设计者安装后门的可能性。
secp256k1是基于有限域的Koblitz椭圆曲线，T = (p,a,b,G,n,h)的参数定义如下：
1.p是无限接近2256的大数；
p = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F
= 2256 - 232 - 29 - 28 - 27 - 26 - 24 - 1。
2.a=0,b=0;
3.G= 04 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D
4. n = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141
5.h=01
为什么比特币选择secp256k1签名算法而不是其他算法？ 比特币开发者社区已经讨论过 secp256k1 是否安全。 中本聪并没有解释清楚，只是说了“有根据的猜测”。
社区里的讨论无非就是安全和效率之间的权衡。 选择不受任何政府控制、没有后门的签名算法是比特币的首要考虑； 其次，它还需要提供计算速度。 毕竟比特币签名验证中的签名是一个不断被处理的东西（大约 60% 的 CPU 时间几乎全部花在上面），具有可预测性和高计算效率的 Koblitz 曲线是一个不错的选择。
除了椭圆曲线签名算法使用非常短的私钥和签名值。 基于安全第一，效率第二的原则，secp256k1是一个最优解。 以太坊的签名算法也是使用secp256k1。
结语
椭圆曲线加密算法是一种非对称加密算法，比RSA效率更高，私钥更短。 有效解决“提高安全强度需要增加密钥长度”的工程实现难题。 并得到了广泛的支持和使用。 使用ECC作为加密算法成为首选。
参考
掘金《椭圆曲线加密原理及应用》
·掘金《椭圆曲线机密算法》
· 博客园-ECC椭圆曲线详解
结尾
了解最新动态
（向上滑动查看内容）
官方网站
confluxnetwork.org网站
赏金网站
bounty.conflux-chain.org
抖音关注@烧子
在微博上关注@Conflux中文社区
weibo.com/confluxchain
知乎关注@Conflux中文社区
www.zhihu.com/org/confluxzhong-wen-she-qu/activities
在百度贴吧关注@Conflux中文社区
tieba.baidu.com/f?kw=conflux%E4%B8%AD%E6%96%87%E7%A4%BE%E5%8C%BA
在推特上关注@ConfluxChain
twitter.com/Conflux_Network
红迪网
www.reddit.com/user/ConfluxChain
电报
t.me/Conflux_English
GitHub 开源交流
github.com/Conflux-链
中等的
medium.com/@ConfluxNetwork
