本文翻译自V神的Medium文章：椭圆曲线配对。该文详细讲解了椭圆曲线配对的原理，并给出了相关的demo程序。zcash官方博客对椭圆曲线这部分讲解的比较粗糙，V神的这篇文章是个很好的补充。友情提示：本文涉及不少数学知识，适合有一定数学基础的同学阅读。
(本文授权BH好文好报群摘编、转载以及相关转授权推文行为)
椭圆曲线配对，是各种加密构造方法(包括 确定性阀值签名、zk-SNARKs以及相似的零知识证明)的关键元素之一。椭圆曲线配对(也叫“双线性映射”)有了30年的应用历史，然而最近这些年才把它应用在密码学领域。配对带来了一种“加密乘法”的形式，这很大的拓展了椭圆曲线协议的应用范围。本文的目的是详细介绍椭圆曲线配对，并大致解释它的内部原理。
第一次阅读本文，你可能有点地方无法弄明白，甚至是第10次阅读，你也可能无法完全明白；因为这东西实在太难了。不过，希望这个文章能让你稍微了解那么一点点它背后的原理。
椭圆曲线本身就不是一个简单易懂的主题，本文假设你大致知道一些；如果你不知道，我建议你读读这篇文章作为入门。这里咱们做一个快速总结，椭圆曲线加密中涉及到一个数学对象，我们把它叫做"点"(二维的点：有(x, y)坐标)，它有自己特别的加法和减法规则(比如，计算这个坐标R = P + Q)，同时，你也可以给一个点乘以一个整数(如： P*n = P+P+P+...+P，不过当n很大的时候，有更简单快速的方法来计算)。
1_2PxXNwMceh1XC_waAP9NiA.jpeg
这里有一个特殊的点，我们称之为在“无限远处的点”(O)，相当于“零”，所以下面这个式子总是成立的 P+O=P。而且，每个曲线都有阶，也就是说存在一个数字n，对于任意P都能满足Pn = O(当然,由此还能得到 P(n+1) = P，P(7n+5) = p*5，等等)。也有一些被成为“生成元”的点G，它在某种意义上代表着1。理论上，一个曲线的任何点(O除外)都可以是G，就看选择哪一个作为标准。
我们进一步看下配对，它允许你检查曲线上点的某种更为复杂的方程是否成立——例如，如果P = G*p, Q=G*q, R = G*r，那么，当P,Q,R作为输入时，你可以检查p*q = r是否成立(译者注：可以通过检查P*Q = R是否成立来判定p*q = r)。这看起来很不安全，因为p的信息被P泄漏了，如果知道P就知道了p的部分信息了，但事实证明这个泄露是高度包含的——具体的说，离散对数问题(从P恢复p)是不可行的。
第三种看待配对的方式，也是对我们最有启发性的方式。如果将椭圆曲线点视为单向加密数字（即 encrypt(p) = p * G = P），那么传统的椭圆曲线数学可以让我们检查数字的线性约束（例如，如果P = G * p，Q = G * q和R = G * r，检查5 * P + 7 * Q = 11 * R确实是检查5 * p + 7 * q = 11 * r），而配对呢，可以让我们检查二次约束（例如检查e(P,Q)* e(G,G * 5)= 1确实在检查p * q + 5 = 0）。上升到二次方，足以让我们使用确定性阈值签名，二次算术程序（QAP）和所有其他好东西。
那么，我们上面介绍的这个有趣的e(P,Q)运算符是什么？这就是配对。数学家有时也把它称为双线性映射;这里的“双线性”这个词基本上意味着它能满足如下约束条件：
e(P, Q + R) = e(P, Q) * e(P, R)
e(P + S, Q) = e(P, Q) * e(S, Q)
注意+和可以是任意运算符;当你创造奇特的新类型的数学对象时，抽象代数并不关心如何定义+和，只要它们与通常的运算方式保持一致就行，例如 a+b = b+a, (ab)c = a(bc)以及(ac) + (bc) = (a+b)*c。
如果P， Q， R是单纯的数字，那么做个配对就简单了：我们可以定义e(x, y) = 2^{xy}，那么我们可以看到：
e(3, 4+5) = 2^{3*9} = 2^{27}
e(3, 4)*e(3, 5) = 2^{3*4} * 2^{3*5} = 2^{12} * 2^{15} = 2^{27}
它是双线性的。
然而，这种简单的配对不适用于密码学，因为它们所处理的对象是简单的整数，并且太容易分析;整数使得除法、对数运算和各种其他的运算变得容易;简单整数没有“公钥”或“单向函数”的概念。此外，通过上述配对，您可以进行反推—— 知道x和e(x,y)，您可以通过简单地除法和对数计算来确定y。我们希望数学对象尽可能接近“黑盒子”，你可以在其中进行加，减，乘和除，但不做任何其他事情。这正是椭圆曲线和椭圆曲线配对的作用。
事实证明，也可以在椭圆曲线点上制作双线性映射 ——也即得出e(P,Q)函数，其中输入点P和Q，都是椭圆曲线点，并且输出是所谓的F_p¹²元素（至少在下面的情况下是这样的;具体情况因曲线细节而异，稍后会详细介绍），注意，这背后的数学非常复杂。
首先，让我们介绍素数域（素数也叫质数）和扩展域。如果您假设曲线方程是使用常规实数定义的，那么得到的椭圆曲线看上去就是像本文前面图片的那样。但是，如果我们真的在密码学中使用常规实数，那么你就可以使用对数运算进行反推，从而一切都会被破解;此外，存储和表示数字所需的空间也会大幅增长。因此，我们改为使用素数域中的数字。
素数域由数字0,1,2 ... p-1构成的集合组成，其中p为素数，各种操作定义如下：
a+b: (a+b) % p
a*b: (a*b) % p
a-b: (a-b) % p
a/b: (a*b^(p-2)) % p
基本上，所有数学都以模p形式完成（有关模运算的介绍，请参见此处）。除法是一个特例;通常的运算中，3/2的结果不是整数，然而这里我们只想处理整数，所以我们试图找到数x，使得x * 2 = 3，其中*是指如上定义的模乘。感谢Fermat小定理，里面给出的取幂技巧可以帮助我们完成了这个计算，但使用扩展欧几里得算法可以更快一些。假设p = 7;这里有一些例子：
2 + 3 = 5 % 7 = 5
4 + 6 = 10 % 7 = 3
2 - 5 = -3 % 7 = 4
6 * 3 = 18 % 7 = 4
3 / 2 = (3 * 2^5) % 7 = 5
5 * 2 = 10 % 7 = 3
如果你玩一下这类数学计算，你会发现它是完备的并且满足所有通常的规则。上面的最后两个例子显示了(a / b)* b = a;你还可以看到(a + b)+ c = a +(b + c),(a + b)* c = a * c + b * c，而且与你知道和喜爱的所有其他高中代数规律依然相符。在实际的椭圆曲线中，点和方程通常是在素数域中计算的。
现在，我们来谈谈扩展域。您之前可能已经看过一个扩展域;在数学教科书中遇到的最常见的例子是复数域，复数域实际上是，实数域加上sqrt(-1)= i的扩展。基本上，扩展域是，在现有域的基础上，“发明”一个新元素并定义该元素与现有元素之间的关系(比如，i²+ 1 = 0)，并确保此等式不适用于原有域中的任何数字，然后对现有域的元素和新创建的元素做一个线性组合。
我们也可以扩展素数域;例如，我们可以用i扩展我们上面描述的素数域mod 7，然后我们可以这样做：
(2 + 3i) + (4 + 2i) = 6 + 5i
(5 + 2i) + 3 = 1 + 2i
(6 + 2i) * 2 = 5 + 4i
4i * (2 + i) = 3 + i
最后一个计算结果可能有点难懂。我们首先将乘积分解为4i * 2 + 4i * i，得到8i - 4，然后因为我们在mod 7质数域中，所以进行mod 7运算后，变成i + 3。接下来， 对于除法，我们可以这样：
a / b: (a * b^(p^2-2)) % p
请注意，Fermat的小定理的指数现在是p²而不是p，但如果我们想要更高效，我们也可以通过扩展“扩展的欧几里得算法”来完成这项工作。注意，对于该域中的任何x，x ^（p² - 1）= 1，因此我们将p² - 1称为“该域中乘法群的阶”。
在实数域中，代数的基本定理保证了复数的二次扩展是“完备的” ——你不能再进一步扩展它了，因为对于任何数学关系（至少，由代数公式定义的任何数学关系），如果你增加了一个新的元素j, 并观察它与现有复数的关系，你会发现总会有一个已经存在的复数满足了这种关系。然而，对于素数域，我们没有这个问题，所以我们可以进一步做出三次扩展（其中一些新元素w和现有场元素之间的数学关系是一个三次方程，所以1，w和w²都是线性地并彼此独立），高阶扩展，扩展的扩展等。并且正是这种加强的、可求余的复数，行成了椭圆曲线配对的基础。
如果你想看下质数域和扩展域相关的数学计算及其代码实现，可以参考这里
译者注：V神的文章喜欢用长语句，我翻译的比较慢，怕翻译错了。今天先到这里吧，今天是上半部分，明天继续下半部分
早赞声明：为方便早赞、避免乱赞，“BH好文好报群”为点赞者、写作者牵线搭桥，实行“先审后赞、定时发表”的规则，也让作品脱颖而出、速登热门！加群微信：we01230123（天平）。
网友评论