【密码专栏】动手计算双线性对（中）

前言
上一篇分享了“模运算”相关的知识，并且计算了一些有限域的例子，这一篇我们讨论在通用零知识证明中经常提到的椭圆曲线和双线性配对。椭圆曲线作为双线性对的基础和前置知识，我们首先介绍一下其在实数域上的表现形式，然后通过计算的方法列出 ” F_101 ” 和其扩域 “ F_101^2” 上的全部元素的列表。

椭圆曲线相关知识—曲线方程
椭圆曲线的一般形式的方程其实比较复杂，称为Weierstrass方程，形如下面的形式：

我们先将 a,b,c,d,e 随意的取值为1,2,3,4,5，并通过画图来查看曲线在直角坐标系上的表现形式。根据二次方程求根公式（假设求根公式可用），我们将其变换为x关于y的函数:

根据方程作图如下：

根据上面的方程（1）和作图过程了解道，曲线由上下两个半支组成，关于y=0.5对称。

对称的总是美的，但是这个曲线却有一点瑕疵，他的对称轴并不是 x 轴而是 y=0.5。考虑到Weierstrass太过复杂，人们更经常使用的是在Weierstrass方程的基础上进行一些坐标变换（平移和缩放）和参数化简后的形式。新的形式关于 x 轴对称。

当取a=0，b=3时，画出曲线如下图，容易验证（1，2）是曲线上一点，对称的（1，-2）也是。

通过方程我们画出了曲线 y^2=x3+3 的图像，但是说这就是椭圆曲线的图像其实并不准确。准确地说，我们画的是在实数域上这个方程的图像。在复数域上当然有更多的点也满足曲线方程但是我们的图像中并没有体现，例如（-2，√5i）。如果把曲线看作点的集合，那数域的扩张直接影响到我们要讨论的这个集合的大小，这在本文后半部分我们还会看到。

另外为了让其拥有更多的性质，我们认为椭圆曲线其实还包括一个“无穷远”点。这个点在图中并不能体现出来，我们也不能以直角坐标的形式写出这个点的坐标，但是当我们说椭圆曲线时默认其点的集合中包含这个点。“无穷远点”一般用 " O "表示。

椭圆曲线相关知识—点的运算

就像讨论 “ F_7 ”时那样，有了元素的集合还需要有在集合上的运算。这条曲线就是椭圆曲线点的集合，但是为了构建密码算法还需要定义点的运算。不同于域中需要两种基本运算，这里我们只需要定义一种特殊的基本运算就可以，不妨将这种运算称作加法，用 “+” 表示。

通过几何意义可以清楚的理解这种运算的定义，例如我们选取了曲线上的两个点A和B计算加法，把A+B的结果记为C，过程如下：
1）过AB做直线，交曲线于T；
2）过T做x轴垂线，交曲线于C点，C即为所求；

需要说明的是，当两个“加数”位置的点为同一个点时，步骤一中所做的其实是过该点的切线。另外，当AB的连线本身就垂直于x轴时，我们规定AB和曲线的第三个交点是无穷远点“O”。

在这样的规则下容易发现，任何点 P 都有一个对应的 P’ ,使得 P+P’=O ；并且任何点 A 和 O 的运算的结果都是 A 本身。而且因为连线AB和连线BA其实是同一条直线，因此我们也能够得知这里定义的点的加法是满足交换率的。

根据定义再结合一些解析几何的知识，就可以求出点加法的坐标计算公式。例如假设 A 和 B 的坐标分别为 (Xa,Yb) 和 (Xa,Yb) ,那么 C 点坐标如下：

其中 " λ " 是直线 AB 连线的斜率，或者当 A、B 重合时是 A 点的切线斜率。

现在我们将转而讨论有限域上的椭圆曲线，其上的椭圆曲线表现为一些散布的点。在有限域上 A+B 虽然已经没有明确的几何意义，但是有同样的计算公式。我们已经验证过（1，2）是椭圆曲线上的点，那么我们就把该点记为 G ，并且从该点开始，计算 G, G+G，G+G+G… 看看会有怎样的规律。

以G+G为例，我们进行演算,首先计算 λ ，也就是G点的斜率：

然后计算C点坐标：

因此 G+G 的坐标为（68，74）。而 G+2G 稍稍有不同，主要是λ需要从切线斜率修改为过 AB 的直线斜率：

因此我们也计算出 G+2G=3G 的坐标（26，45），以此类推进行计算，我们得到下表：

读者可以选择表中的点，例如 (32,42) ，来验证其是否在曲线上，也就是是否满足曲线方程y^2=x3+3 mod 101，相关演算我们不在本文赘述。

经过计算和验证可以发现，这一系列点构成了一个周期为17的循环。如果我们将 k 个 G 相加记为kG，并且将 O 看作 0G ，那么有17 G= O。这像极了模17加法的规律，并且在模17加法和为0的两个数对应的两个椭圆曲线点的和正好是 O ，我们说这样的17个点和加法一起构成一个有17个元素的循环群。因为这只是一篇科普性质的文章，我们不给出循环群的严格定义，但是正如它的名字中强调的“循环”，循环群最突出的性质就是能够由某个元素不断运算从而得到全部。

需要强调的是这17个点并不是 F_101 上椭圆曲线的全部，但仅利用这17个元素组成的集合我们已经能够在其中完成点的加法运算，也就是说任意选择集合中两个点进行加法，其结果不会跳出到集合之外。

在本篇最后，我们展示17个点在直角坐标系中的分布（无法展现 O ），读者可以体会其中的对称之美。下一篇我们将找到另一个17个元素的循环群并且在其基础上计算双线性映射，敬请期待。

附录

▲表2：模101元素逆元表

乔沛杨
趣链科技基础平台 区块链底层密码学小组

最后

以上就是忧伤钻石为你收集整理的【密码专栏】动手计算双线性对（中）的全部内容，希望文章能够帮你解决【密码专栏】动手计算双线性对（中）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。