北大沙龙 | 椭圆曲线加密与并行性的研究

2019年3月29日，第十二期北大软微-八分量协同实验室学术沙龙活动如期展开。本次技术沙龙讨论的主题是安全椭圆曲线加密算法的选取。北京大学的沈晴霓教授、方跃坚副教授、Trias胡志琳以及软微学院众位博士生、硕士生参与了此次沙龙，并由博士生冯新宇做出分享。

上期的沙龙介绍了椭圆曲线，并对椭圆曲线数字签名算法（ECDSA）和椭圆曲线密码学（ECC）做出了简述，并分享了一下最受外界关注的领域，如门限签名技术等。在此基础上，本期的沙龙对椭圆曲线加密技术做出进一步挖掘。

学术界已经提出了很多不同的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，这是曲线选取的必要条件。异常曲线和超奇异曲线已经被证明是不安全曲线，一定要避免使用。

在沙龙的后半段，大家提到安全快速的椭圆曲线密码并行的实现方法。目前的实现方法都是串行的，而关于新的并行设计椭圆曲线加密方法的研究也为数不多，如果能在这个领域有所突破，无论理论上还是实践中，都会是一件非常引人瞩目的事。另外，倘若能在单点的基础上，发展为多点并行，毫无疑问还会大大提升椭圆曲线加密的处理效率。或者，通过软硬件结合的方式来提高安全性，比如已经有项目通过SGX与区块链的结合来实现安全高效的方案。

下一期沙龙除了对有创新价值的学术论文进行分析，还将对并行的实现思路进行讨论。Trias每周都会和北大举办沙龙活动，对区块链技术以及Trias项目有疑问的小伙伴可以随时将问题抛在技术交流群里，我们会及时作出回应噢。