初识椭圆曲线

1.圆的定义

平面上到一个固定点的距离为常数的点的集合

2.椭圆的定义

平面上到两个不同点的距离之和为常数的点的集合

3.椭圆曲线

椭圆曲线是一条二元三次曲线，如下图所示。

对于该曲线上的点，若是定义在实数域，则是我们学过的初等数学中的形式，点(x,y) 中的分量可以是小数或是负数。

但密码学中的椭圆曲线是定义在有限域下，即点 (x,y) 属于一个有限集合内，且需要满足某些性质。

密码学中常用的椭圆曲线形式为 

, 其中p是整除求余的模数。

可以使用符号 

来表示一条有限域椭圆曲线。例如

有限域中的元素性质

有限域是为了满足某些目的而构造出来的元素集合和元素上的运算法则。为了方便理解，我们可以参照实数域的四则运算来进行理解。想象有一个元素集合。这个集合中的元素和元素运算符合下面的特征。

1.支持加法和乘法操作

2.支持加法和乘法结合律，加法和乘法交换律

3.支持乘法分配律

4.每个元素都有逆元。即元素A和另一个元素B相乘，结果为单位元。例如实数域中的 

，在有限域（假设域为：mod(11)）中，元素5的逆元是 9。因为

5.每个元素都有负元。即元素A和另一个元素B相加，结果为0。在有限域（假设域为：模11）中，元素5的负元是 6。因为

6.有限域减法：

，其中 –b是b的负元

7.有限域除法：

，其中是b的逆元

8.注意，无论是逆元还是负元，都必须是有限域中的值。即对于有限域mod(11)来说，所有元素都位于整数区间 [0-10]

域mod(11)是一个一维的有限域，元素都位于整数区间 [0-10]。二维有限域的元素都是平面上的点坐标，因此有限域内椭圆曲线上的点，也满足上面的全部元素运算性质。

椭圆曲线上的点

来看一看有限域中椭圆曲线上面点的样子。

有椭圆曲线

，即曲线方程

，首先计算第一个点

设 x=2，得

，而

因此可知 (2, 4) 是该曲线上的一个点。但同样也可发现

，因此(2, 7)都是该曲线的一个点。同样可以计算出x=3，x=4，x=10的点。并且这些点的数量是有限的。

椭圆曲线上的点的运算法则

点加法

椭圆曲线在有限域中的解除了拥有上述有限域元素性质之外，和我们熟悉的实数域直角坐标两点各分量直接相加相比，椭圆曲线在有限域中点加法略显复杂。

其中

有了点加法的铺垫，就可以引出点倍乘运算了。

点的倍乘

倍乘运算可用连加的形式实现，即

椭圆曲线加密

类似RSA加密依赖的大素数分解问题，椭圆曲线加密也需要依赖数学np问题的计算复杂性，来抵御数学攻击。因此引出了椭圆曲线离散对数问题。该问题形式为有限域中椭圆曲线的倍乘运算。即

K为随机整数，P和Q是椭圆曲线的两个点。

椭圆曲线的安全性

在上式(1)中，椭圆加密算法将整数k作为私钥，点Q作为公钥。有限域中椭圆曲线的安全性背后的数学逻辑是来自点倍乘运算的循环集合特性，倍乘操作出现循环结果的原因是由于模运算的存在。考虑曲线

, 设

得到的倍乘结果Q都是(6,4)，即无法通过公钥推出私钥。有限域椭圆曲线的倍乘运算具有单向性。无法只根据Q，P来反推出精确的k的值。

结合这个例子，给定曲线，p点(3,10)，Q点(6,4)，则推出的k值有无数种可能。当k选取超大值时则更加困难。

加密算法

在查阅椭圆曲线相关文章时包含ElGamal和ECElGamal两种加密算法的内容。首先这两个加密算法虽然曲线不同，但在加密计算时都加入了随机数，同时在解密计算中将随机数通过计算步骤约掉，进而可以在解密步恢复出明文。

跳出椭圆曲线这个话题，更通用来说，一条曲线至少要满足下面的条件才可能被作为加密曲线所使用。

1.加密时随机加入的数据保障了安全性。同时该数据会在解密过程的计算中被消掉。反过来，如何消掉随机数据的方法决定了加密和解密的计算过程。这部分是设计加密曲线的核心工作。

2.为了保证解密可以正常进行，必须是在一个有限域内来进行运算，有限域提供了加密方和解密方之间约定的一个合法解空间。解密失败和无法解密的点都会落在有限域之外。

加密时明文的编码

还有一个问题，加密时明文是如何进行处理的？以ElGamal算法为例，算法描述如下。

因为公钥pk是使用点倍乘后的结果，是曲线上一点。k*pk做点倍乘后也是点，明文M需要进行编码映射为椭圆曲线上面的点，才可以完成加密过程中的C2的计算。而对明文M进行编码需要保证编码后的点是一个在当前曲线上的一个合法点才行，因此不能简单的做映射。这块有现行的算法例如Koblitz编码算法可做参考学习。

下一篇：ECIES 集成加密框架和应用

原文始发于微信公众号（青木生长）：密码学浅入浅出ECIES之椭圆曲线加密算法