什么是椭圆曲线？
我们在《几何》课本里学过二元一次方程表示直线，二元二次方程表示圆锥曲线(圆，椭圆，双曲线和抛物线)，那么二元三次方程表示什么曲线呢？答案自然就是椭圆曲线。为了方便研究，大部分的二元三次方程可以简化成魏尔斯特拉斯方程的形式，见公式(4)。其中，系数a 和b 需要满足条件4a3 + 27b2 ≠ 0，该条件保证方程中不会出现非奇异点以获得平滑的椭圆曲线。
ax + by + z = 0 (1)
ax2 + by2 + cxy + dx + ey + f = 0 (2)
ax3 + bx2y + cxy2 + dy3 + ex2 + fxy + gy2 + hx + iy + j = 0 (3)
y2 = x3 + ax + b (4)
一个违反直觉的事实是：椭圆曲线的形状跟椭圆毫无关系。当初数学家们在研究如何计算椭圆弧长的时候发现需要求解如下类型的积分, 由于和椭圆相关，积分中的分母项y =√(x3+ax+b) 便被称作椭圆曲线。
下图展示了一些合法的椭圆曲线，
下图展示了两种非法的椭圆曲线，分别存在一个尖点和叉点使曲线不平滑。
密码学与有限循环群
现代密码学算法和协议中，消息是作为有限空间中的数字或元素来处理的。加密和解密的各种操作必须在消息之间进行变换，以使变换服从有限消息空间内部的封闭性。然而，数的一般运算诸如加减乘除并不满足有限空间内部的封闭性。所以密码算法通常运行于具有某些保持封闭性的代数结构的空间中，这种代数结构就是有限循环群。在数学中，群是一种代数结构，由一个集合以及一个二元运算组成。群必须满足以下四个条件：封闭性，结合律，存在单位元和存在逆元。
最常见的群之一是整数集Z以及加法操作。
有限循环群在群的基础上满足两个额外条件：群元素个数有限以及交换律。循环群由单个元素（产生元）的叠加操作生成，最常见的有限循环群为模拟时钟。
椭圆曲线群定义
1985年，Neal Koblitz和Victor S.Miller分别独立提出利用椭圆曲线产生椭圆曲线循环群用于密码学。在数学上，椭圆曲线群的元素为椭圆曲线上的点，群操作为”+”,”+”的定义为，给定曲线两点P，Q，P+Q等于P和Q两点的连线与曲线交点沿X轴的对称点，如果P=Q，则P+P等于P在曲线上的切线与曲线交点沿X轴的对称点。该群的单位元为无穷远零点记作O=(0,0)，有P+O=P，点P的逆元为其沿X轴的对称点，记作-P。
下图演示了如何计算P+Q=R(P≠Q)。
下图演示了如何计算P+Q=2P=R(P=Q)。
下图演示了如何计算P的逆元-P。
椭圆曲线有限循环群
前面介绍的椭圆曲线都是基于有理数的，但是计算机运算浮点数(小数)的速度较慢，更重要的是四舍五入浮点数会产生误差，导致多次加密解密操作后原始消息不能被还原。故考虑到加密算法的可实现性，密码学上使用基于整数的模加运算产生椭圆曲线有限循环群。
本文不涉及具体的数学计算，将用具体的例子展示如何产生ECC有限循环群。例如考虑y2=x3-7x+10(mod 19)的集合，该集合中所有的元素如下图所示。模运算把发散的椭圆曲线映射到19*19的正方形空间中，并且保持了原有曲线的上下对称特性。
下图展示了y2=x3-7x+10(mod19)集合中的元素和椭圆曲线的关系。
点Q’映射到点Q，点P的对称点也由点-P’映射到点-P。
如果取一个更大的质数p进行模运算，集合中的元素点也会相应地增多。下图展示了利用同一个曲线方程进行不同模运算的结果。在实际的椭圆曲线加密算法中，使用长度为192-256位的质数p进行模运算。
现在我们基于y2=x3-7x+10(mod19)，利用产生元P=(2,2)来生成ECC有限循环群。如下图所示。具体的计算使用在线的ECC计算器(链接见参考资料)。
G={nP|P=(2,2)}完整的集合为{p=(2,2),2P=(13,8),3P=(1,2),4P=(16,17),5P=(10,3),6P=(18,15),7P=(3,15),8P=(12,1),9P=(9,12),10P=(5,10),11P=(17,15),12P=(7,0),13P=(17,4),14P=(5,9),15P=(9,7),16P=(12,18),17P=(3,4),18P=(18,4),19P=(10,16),20P=(16,2),21P=(1,17),22P=(13,11),23P=(2,17),24P=O=(0,0)}。如下图所示，随着n的连续增加，元素点的分布没有任何特征，这正是密码学需要的特性。
椭圆曲线离散对数问题ECDLP
请问上图中与点Q相对应的n值为多少？查找集合G={nP|P=(2,2)}中的元素可知答案是Q=(5,10)=10P，但是实际应用中没有现成的集合可供查表。若已知某个点Q，只能用比较原始的方法演算可能的n值，目前可实现的效率最高的算法为Baby-step giant-step算法，计算复杂度为O(√n)。反过来，如果已知n计算n*P则简单的多，因为有限循环群满足结合律，可以使用square and multiply算法，计算复杂度为O(<2log2n)。例如，比特币使用名为secp256k1的标准ECC曲线，n的长度为256位. Baby-step giant-step算法的计算复杂度为O(2128)，而square and multiply算法的计算复杂度仅为O(<512)。
用密码学术语描述为：ECC有限循环群构成了一个单向函数Q=nP，已知n,P可以很容易计算Q；反过来已知P，Q则难以计算n.于是(n,Q=n*P )构成了一对私钥和公钥。
举个具体的例子，利用square and multiply 算法计算Q=137P，仅需9步便得到计算结果。
ECDH基于椭圆曲线的Diffie-Hellman密钥交换
ECC可以用于加密解密，但是由于其算法复杂计算速度慢，故莱迪思iCE40 UltraPlus系列芯片综合使用ECDH算法进行密钥交换，再通过AES进行消息的快速加密/解密助力于IoT通信。故本文以iCE40 UltraPlus芯片的Security IP为例介绍ECDH密钥交换。下图为ECDH密钥交换算法的示意图，iCE40Plus和Host分别产生自己的私钥和公钥，然后通过公共网络把公钥分享给对方，再各自使用私钥在本地计算出相同的密钥进行AES加密通信。
由于有限循环群满足交换律，我们可以验证KEYHost=m*n*P=n*m*P=KEYFPGA.
总结
相比于RSA和经典DL加密，ECC使用更短的密钥实现更安全的非对称加密。莱迪思首先在低功耗低成本FPGA中实现了ECC密钥交换算法助力于IoT通信。本文简要介绍了ECC的相关知识，希望能对大家在具体实施加密方案的时候提供一定的帮助与指导。
8参考资料
Blog: Andrea Corbellini. Elliptic Curve Cryptography: a gentle introduction. Link: andrea.corbellini.name/2015/05/17/elliptic-curve-cryptography-a-gentle-introduction/
Book: Wenbo Mao. Modern Cryptography: Theory and Practice.
Blog: Certicom. ECC tutorial. Link: www.certicom.com/content/certicom/en/ecc-tutorial.html
Online Tool: Online tool: ECC calculator. Link: christelbach.com/ECCalculator.aspx
Paper: 陆俊，浅说椭圆曲线。
Paper: Mahesh Agarwal. Elliptic Curves do arise from ellipses.
Online Course: Christof Paar. Understanding Cryptography. Link: www.crpto-textbook.com
https://mp.weixin.qq.com/s/jOcVk7olBDgBgoy56m5cxQ
网友评论