数据已成为经济关键生产要素，“数据孤岛”问题是数据价值流转的最大挑战。由于数据安全、隐私保护的法律法规要求，不能将数据简单整合。安全多方计算（Secure Multi-Party Computation，MPC）技术使得数据要素流通成为可能。MPC可以在可证明安全（Provable Security）层面实现“数据可用不可见”，从而打破“数据孤岛”。
MPC是指一组相互独立的数据所有方在互不信任、且不信任任何第三方的条件下，应用各自的私有输入联合完成某个函数的计算。安全多方计算采用现实-理想范式（Real-Ideal Paradigm）严格定义协议的安全性，具有密码学层面的可证明安全性（Provable Security）。当定义好攻击者的攻击能力后，可以从数学层面严格证明MPC在此攻击者的攻击下满足安全定义。
可以用姚氏乱码电路（Yao's Garbled Circuit）、基于秘密分享（Secret Sharing）的GMW协议等通用MPC协议，将任意一个离散函数转换为MPC协议。然而，通用转换一般会引入比较大的通信和计算开销。目前，实际中得到广泛应用的方法为专门定制化设计的专用MPC协议。在这些专用MPC协议中，最著名的协议就是隐私集合求交（Private Set Intersection，PSI）了。Google[1]、Facebook[2][3]等著名企业都在研究、实现、部署PSI或以PSI为基础的衍生协议。
近年来，PSI协议得到了密码学领域的广泛关注，更高效的PSI协议层出不穷。但如果仔细阅读上述企业发表的论文，会发现他们所应用的协议仍然是Huberman、Franklin、Hogg在1999年提出的协议[4]，而此协议的提出最早可追溯到1986年[5]。由于此协议与著名的Diffie-Hellman密钥协商协议[6]结构非常相似，一般将这一协议称为DH-PSI协议。
在那时，构造DH-PSI协议主要使用的还是标准离散对数群 。为了保证协议的安全性，离散对数群的模数 要选得足够大，这引入了较大的通信和计算开销。2001年左右，椭圆曲线密码学（Elliptic Curve Cryptography，ECC）正式进入了密码学家的视野。密码学家找到了一个效率更高、群表示长度更短、可以替代标准离散对数群 的ECC群 。一般将使用ECC代替标准离散对数群 实现的DH-PSI协议成为ECDH-PSI。
ECC的研究还为密码学领域带来了新的方向。在同一时间，基于ECC构造的双线性映射（Bilinear Map）得到了广泛的研究[8]。基于双线性映射，密码学家们构造出了多种新的密码学方案，如基于身份加密（Identity-Based Encryption，IBE）[9]、基于属性加密（Attribute-Based Encryption，ABE）[10]。2010年，密码学家正式提出了函数加密（Functional Encryption，FE）[11]的概念，并以此为基础扩展出了多种重要的密码学原语[12]。著名计算机科学家Boaz Barak在Twitter上发布了一张密码学世界的全图，形象地展示出了当前密码学领域的发展情况。此图的左上角上，RSA、DH、ECC会画在了一个特殊的大陆上，只不过这个大陆的信息不太正面：可被量子计算机破解的密码学工具。由此可见，ECC是密码学领域非常有代表性、也是应用非常成功的密码学工具。
虽然ECC已经是密码学领域比较成熟的技术了，但对于未深入接触过密码学领域的同学来说，使用椭圆曲线相对来说仍然比较复杂。本文希望给出一个入门性的介绍，透过实际的代码深入到ECC的具体实现中，并给出我们的一些最佳实践。
本文首先介绍椭圆曲线的基本概念、基本参数、基本运算。随后，本文通过著名Java密码学函数库Bouncy Castle的代码，深入介绍实现各个运算背后的一些细节问题。希望读完本文后，大家可以更好地使用ECC，快速实现如ECDH-PSI等基于ECC的MPC协议。
在介绍椭圆曲线的基本概念之前，我想先请大家浏览一个看起来像是小学奥数题的题目。题目如下：
相信大家在朋友圈中经常看到类似的题目。大多数情况下，类似的题目都是标题党，例如：“95%的麻省理工毕业生无法解决的问题”。但这个问题不是标题党。这个问题的确可解，但解决方法非常难。
我们需要求解的是下述方程的整数解：
但这道题的解决过程就需要使用到椭圆曲线的知识。实际上，这道题的其中一组解为：
如果想了解这道题的具体解决过程，可以参见知乎上的文章《史上最贱的数学题》。这篇文章通过解决此问题，介绍了椭圆曲线的基本概念。这篇文章还给出了多个关联文章，给出了实数域椭圆曲线（参见《新手上路：实数上的椭圆曲线和群论》）、有限域椭圆曲线（参见《Elliptic Curve Cryptography: finite fields and discrete logarithms》）的基本定义。下面仅介绍本文要用到的一些非常基础的概念。本章的部分描述来自于《新手上路：实数上的椭圆曲线和群论》，本章所使用的图像和例子来自于幻灯片《Elliptic Curve Cryptography》。
椭圆曲线是由方程 描述的曲线，其中 。一般称此方程是椭圆曲线的魏尔斯特拉斯形式。根据椭圆曲线坐标类型的不同，可以将椭圆曲线分为实数域椭圆曲线和有限域椭圆曲线。简单来说，实数域椭圆曲线是指方程 的坐标 均可以为实数。典型的实数域椭圆曲线形状如下图所示。
有限域椭圆曲线是指方程 的坐标 是有限域 中的元素，一般称有限域 为椭圆曲线的基域。基域 一般有两种情况，一种是阶为 的有限域，称为二元扩域，用 表示。一种是阶为质数 的有限域，称为素域，用 表示。这里我们只考虑素域，素域中一共包括 共 个元素，代数运算在标准运算的基础上在模 。
这里可能会为读者带来误导。对于定义下的椭圆曲线，其形式不为。可参考《SM2椭圆曲线公钥密码算法推荐曲线参数》的附录A.3，了解 定义下的椭圆曲线。
举个例子，考虑坐标 定义 在上的有限域椭圆曲线 。此时，坐标 都只能在 之间选取。满足方程 所有可能的坐标为：
因此，定义在基域 上的有限域椭圆曲线 可以包含点 。在椭圆曲线中还需要定义一个无穷远点 。特别要注意 的情况，此时找不到一个满足 的 。
给定椭圆曲线上的两个点 ，定义 ，其中：
根据 的不同情况，有加运算、逆运算、标量乘运算这三种可能。这里为更直观地演示运算过程，示意图选用实数域椭圆曲线。再次强调，基域为 的有限域椭圆曲线坐标均为 的元素，因此椭圆曲线实际的图像应该如下图所示。
当 时， 相当于在图像上连接 两点，交椭圆曲线到第三个点 ，并取 相对于横轴的对称点得到 ，如下图所示。
此运算称为椭圆曲线下的加运算（add）。
既然定义了加法运算，也就需要定义减法运算。两个椭圆曲线点的减法运算可以看成一个椭圆曲线点加上一个椭圆曲线点的逆元，即 。给定椭圆曲线点 ，则定义 为 相对于横轴的对称点，即 ，如下图所示。
此运算称为椭圆曲线下的逆运算（negate）（也称逆元运算）。注意到前面的表格中，当 和 时， 有两个可能的取值 ，这是因为 在 下为逆元。换句话说， 且 ，原因是 。
根据加法的定义， 应该为在图像上连接 两点，交椭圆曲线到第三个点。然而，此时 两点的连线无法在椭圆曲线上与第三个点相交。而根据逆元的定义，我们应该要求 。为此，数学上将无穷远点定义为椭圆曲线上的零元 。
当 时， 相当于计算 在椭圆曲线上的切线，交椭圆曲线到另一个点 ，并取相对于横轴的对称点得到 ，如下图所示。
注意到此时 。按照相同的计算方法，可以继续定义 等运算。此运算称为椭圆曲线下的乘运算（Multiply）。
标准离散对数群一般不使用加法，而是用乘法运算和幂运算来构造密码学算法。这是因为当满足一定的条件时，标准离散对数群 在幂运算 下满足离散对数（Discrete Logarithm，DLog）困难问题。ECC最重要的作用是替代标准离散对数群 。然而，椭圆曲线在乘运算下满足离散对数困难问题。因此，目前很多密码学领域的论文仍然会使用乘法运算和幂运算来描述与标准离散对数群 运算相关的方案，并指出此方案可以换为椭圆曲线。这里更换时，幂运算指的就是椭圆曲线乘法运算，而乘法运算对应的就是椭圆曲线加法运算。
后续描述中，为了更符合密码学领域的惯用表示方法，我们分别用幂运算和乘法运算表示椭圆曲线上的乘法运算和加法运算，即用乘法运算符号 表示椭圆曲线加法运算 ，用加法运算符号 表示椭圆曲线乘法运算 。
有限域椭圆曲线还有一个很重要的概念，称为生成元（Generator）。简单来说，给定椭圆曲线上的一个点 ，可以找到一个最小的 ，使得对于任意 ， ，且 。此时， 所得到的 个椭圆曲线点形成了有限域椭圆曲线群 。在密码学中，我们实际使用的是给定生成元 的有限域椭圆曲线群 ，此群的阶为 。在论文中，一般将这个群 简单地表示为 。
注意到，需要用坐标 表示椭圆曲线上的一个点，且每个坐标都是基域 中的一个元素。当质数 有256比特长时，这意味着需要用大约为2个256比特，即64字节来表示坐标 。实际实现中，还可能涉及到一个辅助参数 的计算，因此实际使用的字节数会比64字节更多一些，至少为65字节。
当已知椭圆曲线点的横坐标 时，纵坐标 只可能有两种取值。从有限域角度看，这两个取值一个为正数 ，一个为负数 。因此，可以进一步将椭圆曲线点表示为 ，从而进一步压缩椭圆曲线点的表示长度。当质数 有256比特长时，理论上只需要一个256比特，即32字节表示 ，再用1比特长的数表示 ，即可表示坐标 。然而，由于计算机最小的存储单位是包含8个比特信息量的字节，因此实际需要33字节来表示坐标 。
有了上面的概念，就可以知道如何定义一个椭圆曲线了。
椭圆曲线的参数都是可以公开的。密码学领域常用的椭圆曲线有Secp256k1（也称为Prime256k1）、国产公钥密码学算法SM2使用的椭圆曲线称为Sm2p256v1、还有上述提到的Curve25519椭圆曲线。椭圆曲线的具体参数如下。
在比特币诞生之前，secp256k1基本未得到使用。出于性能、安全性等考虑，比特币使用secp256k1椭圆曲线构建椭圆曲线数字签名算法（ECDSA），至此secp256k1才得到了广泛的应用。secp256k1的质数 为256比特长，参数的具体来源和背景参见《Secp256k1 - Bitcoin Wiki》。
sm2p256v1是我国国产密码学算法SM2使用的椭圆曲线，参数的具体来源和背景参见《SM2椭圆曲线公钥密码算法推荐曲线参数》。如果实际业务中有国产密码学算法的要求，可以使用此参数构建椭圆曲线。
在《SM2椭圆曲线公钥密码算法—第1部分：总则》的附录C.2也可以找到实例参数，但此实例只用于演示椭圆曲线的计算过程，并给出样例计算结果。总则也详细介绍了椭圆曲线的核心原理。如果想深入了解椭圆曲线，这是个很好的学习材料。
Curve25519不是用魏尔斯特拉斯一般形式来定义椭圆曲线的，而是采用蒙哥马利曲线形式： 。此椭圆曲线关联的质数 ，这也是25519这个数字的由来。需要特别注意的是，Curve25519的协因子 。
ECC中一个非常重要的运算是哈希到椭圆曲线（HashToCurve）：给定任意一个数据，如何将其映射到椭圆曲线上？
直观看，一种最简单的方式是：
这样就把任意一个数据映射到椭圆曲线上了。然而，在绝大多数情况下，这种映射方法都会带来安全问题。特别地，如果在ECDH-PSI上使用这种方法，则得到的PSI将不再安全。
实际上，HashToCurve有标准草案，称为《Hashing to Elliptic Curves》。截至2021年12月21日，此标准的最新更新时间为2021年12月11日，仍然是一个演进中的标准，相应的标准实现参见《Hashing to Elliptic Curves》。
标准草案提供的HashToCurve，其核心目的是使实现的方案可以抵御侧信道攻击。然而，标准草案的方法效率相对较低，而且实现起来相对比较困难。一般来说，常见的方法是：
实际上，谷歌的PSI衍生协议Private intersection-sum-with-cardinality[1]使用的就是这一算法。论文的第3.2节：参数选择（Parameter Choice）写到：
其中，谷歌的实现“prime256v1”指的就是secp256k1，其使用了OpenSSL的实现。上述英文段落描述的就是这样一个哈希算法。特别地，在论文的脚注3写到：
明确说明了这一方法会遇到侧信道攻击，并描述在谷歌的应用场景中无法实施这一攻击。实际上，我非常推荐大家阅读谷歌的这篇论文《On deploying secure computing: Private intersection-sum-with-cardinality》。虽然这篇论文并没有中稿安全领域四大顶级会议，但从论文可以看到谷歌对于MPC这类高安全技术的应用花费了非常多的精力，各个细节点都描述的非常透彻。
出于性能考虑，绝大多数密码学算法的实现都是基于C/C++的。这里特别介绍Java下的一个著名密码学工具库Bouncy Castle。Bouncy Castle提供了纯Java的完备椭圆曲线运算实现。经过测试，此实现是线程安全的，可以放心大胆地启用并发来提高性能。与C/C++追求极致性能优化的方式不同，Bouncy Castle的代码想对更加容易理解（这也是因为Java在性能优化层面实在无法做得更多，这使得更易读的实现方式变得可能）。此外，
我们用代码来简单演示椭圆曲线运算，以secp256k1为例。
上述代码的输出结果如下。仔细观察，此输出结果与secpk256k1的参数定义是相同的。
如果想更换椭圆曲线，只需要修改CustomNamedCurves.getByName("secp256k1")中的椭圆曲线名称。例如，如果把椭圆曲线名称修改为sm2p256v1，输出结果如下。仔细观察，此输出结果与sm2p256v1的参数定义是相同的。
下述代码演示了使用Bouncy Castle实现HashToCurve的方法。我们也可以在代码中看到如何应用Bouncy Castle构造椭圆曲线点。
本文介绍了椭圆曲线的基本概念和基本原理，并应用Bouncy Castle演示了如何实现椭圆曲线的运算。然而，本文还遗留了不少需要进一步回答的问题：
我们将在后续文章中介绍相应的概念。
