椭圆曲线密码学详细解析

椭圆曲线密码学（ECC），是一种基于椭圆曲线数学诞生的非对称秘钥加密的算法，加密过后只有特定的人才能对其进行解密。例如，ECC可用于确保用户在发送电子邮件时，除了收件人之外，没有人可以阅读这封邮件。

椭圆曲线是近几十年来被广泛探索的一个重要数学新领域。它作为一种解决复杂数字问题的工具，以及在密码学中的应用显示出巨大的潜力。

本文内容整理自Trias技术团队与北大软微学院的学术沙龙活动。

椭圆曲线数学

在探究ECC之前，我们有必要回顾一下椭圆曲线数学。

我们定义平行线相交于无穷远点P∞，使平面上所有直线都统一为有唯一的交点，而区别于无穷远点的原来平面上的点为平常点。通过无穷远点和平常点我们可以引入射影平面的概念。

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

而椭圆曲线，指的就是在射影平面上满足威尔斯特拉斯方程（Weierstrass）所有点的集合，且曲线上所有点都是非奇异的。

所谓非奇异，指的是曲线上任意一点的偏导数不能同时为0。

明白了椭圆曲线的由来，我们再来看椭圆曲线在密码学上应用的方案。首先面对的问题就是椭圆曲线是连续的，并不适合用于加密。因此，椭圆曲线密码学的第一要务就是把椭圆曲线定义在有限域上，（有限域Fp ，p为素数），并提出一条适于加密的曲线：y2=x3+ax+b （modp）。

相比起在商业中被广泛采用的RSA加密算法，ECC优势是可以使用更短的密钥，来实现与RSA相当或更高级别的安全。通过下图我们清楚的发现，160位ECC加密安全性相当于1024位RSA加密，而210位ECC加密安全性甚至相当于2048位RSA加密。

众所周知，比特币中的公私钥生成以及签名算法ECDSA都是基于椭圆曲线加密算法而诞生的。ECDSA算法可以说是应用最广泛的椭圆曲线签名算法，从比特币开始，并且已经被其它区块链项目所广泛使用。在区块链中使用的公钥生成算法是SECP256K1。

其中以太坊和比特币的在ECDSA中的区别在于二者使用的哈希算法不同，在比特币中使用的是SHA2-256，在以太坊中使用的是SHA3-256，同样字节数的SHA3比SHA2更安全。

椭圆曲线加密与并行性

学术界已经提出了很多不同的ECC选择标准，每一个都试图确保椭圆曲线离散对数问题（ECDLP）是困难的。而ECDLP是在给定用户公钥的情况下查找ECC用户密钥的问题。

但遗憾的是，虽然标准曲线在安全实现理论上可行，但实践却表明，ECDLP并不足以完全保障ECC的安全性。人们发现，很多攻击可以绕过困难问题，在不解决ECDLP的情况下破坏了现实中在使用的ECC。

因此，如何选择更优质的曲线来保障安全，并能够比较简单的高效率实现，就成了安全曲线相关课题摆在明面上的难题。

为了达到上述目的，许多解决方案通过各国的学术论文被提了出来。但随后很多的研究表明，许多所谓能提高效率的决策都不靠谱，有的并没有作用，还有的虽然有用，但是会损害安全性。

通过研究发现，基于椭圆曲线的密码系统主要有7个系统参数T=（q，FR，a，b，G，n，h），其中q表示所选择的有限域；FR是有限域上的元素的表示方法；a和b表示椭圆曲线的参数；G是在曲线上选择的基点；n表示该基点的阶，是一个足够大的素数；h是n的余因子，是一个小整数。

在所有椭圆曲线公钥密码体系的实现中，有两种类型的基本运算：一类是在密码体系设计阶段要用到的基本运算，另一类是运行阶段所要用到的。第一类是椭圆曲线密码体系基本参数的选取，包括安全椭圆曲线的寻找和基点的选取两部分；第二类是椭圆曲线有限域上的各种代数运算，包括点加、倍点和数乘三种运算。

另外，曲线系数的选取必须满足判别式δ=4a3+27b2≠0，这是曲线选取的必要条件。异常曲线和超奇异曲线已经被证明是不安全曲线，一定要避免使用。

关于椭圆曲线并行加速

同 RSA 公钥密码相比，椭圆曲线密码提供了更高的单位比特安全强度 ， 160 位密钥长度的椭圆曲线密码提供的安全强度，相当于 1024 位密钥长度的 RSA 密码提供的安全强度。在这种背景下，对运算进行优化便具有重要意义，并行加速便是优化运算的一种方式。

椭圆曲线加密的并行性处理方式到目前尚在学术界讨论阶段，是一个比较前沿的研究方向。就目前从技术角度而言，并行性存在着安全隐患和效率提升不明显等问题，所以这项技术尚未大规模落地投入应用。即便是以比特币为代表的加密货币这样的轻量级应用，出于种种顾虑，也未采用并行加速。

北大方跃坚老师提出了4种提升椭圆加密算法效率的方式：

1、多线程并行

2、GPU并行

3、专用硬件并行处理器

4、SSE指令加速

这4种方法各有优劣，如GPU并行虽然单位时间内总吞吐量较高，但单个运算却不如CPU；专用硬件虽然能较为容易的将点乘转化为点加提升速度，在抗攻击等方面则存在一些问题。

冯新宇博士从等式Q=KP出发，提出了几种可能提高算法效率的方法。在这个等式中，K是一个大整数，P相当于私钥，Q相当于公钥，所有这些算法都是通过对整数K进行转化来减少点运算的次数。想要提升效率，就要找到一个快速计算出K·P结果的办法，既然P不能变，那就只能从K来入手。

二进制算法：将K转换成2进制（即2的幂）的形式，然后再进行背点运算和点加运算，时常和滑动窗口方法结合起来使用。

窗口NAF方法：通过编码来减少比特位中含1的个数，从而减少点加的次数。但是有一个缺点，即不能抗边信道攻击。

边信道攻击（SCA， Side Channel Attack）是一种通过分析密码设备泄露的边信道信息来推测秘钥的密码分析方法。

滑动窗口方法：通过跳过比特值为0的位来减少点加的次数。

Montgomery：Montgomery 型椭圆曲线定义为E ：By2 =x3 +Ax2 +x。此处 ， A ， B ∈ Fpn并且B（A2 -4）≠0。Euclid 加法链是满足如下条件的加法链 ：v1 =1 ， v2=2 ， v3 =v1 +v2，对所有的 3 ≤i ≤l -1 ，如果 vi =vi -1 +vj（j 《i -1），则 vi +1 =vi +vi -1或 vi +1 =vi +vj。通过辗转相减可以求得计算任意整数 k 的加法链，但该加法链的长度取决于选取的减数g ，求最短加法链问题是一个 NP 完全问题。

NP完全问题，是世界七大数学难题之一。NP的英文全称是Non-deterministic Polynomial的问题，即多项式复杂程度的非确定性问题。简单的写法是 NP=P？，问题就在这个问号上，到底是NP等于P，还是NP不等于P。

固定窗口方法：预存P的i倍来减少点加次数。这种方法很容易理解，即将几种可能的情况提前算好，使用的时候直接拿来取用，提升效率的办法。