密码学基础知识_密码学专业就业前景

椭圆曲线运算：从理论到实践　　引言　　数据已成为经济关键生产要素，“数据孤岛”问题是数据价值流转的最大挑战。由于数据安全、隐私保护的法律法规要求，不能将数据简单整合。安全多方计算（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协议主要使用的还是标准离散对数群
$\mathbb{Z}_p$ 。为了保证协议的安全性，离散对数群的模数
要选得足够大，这引入了较大的通信和计算开销。2001年左右，椭圆曲线密码学（Elliptic Curve Cryptography，ECC）正式进入了密码学家的视野。密码学家找到了一个效率更高、群表示长度更短、可以替代标准离散对数群
$\mathbb{Z}_p$ 的ECC群
$E(\mathbb{F})$ 。一般将使用ECC代替标准离散对数群
$\mathbb{Z}_p$ 实现的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%的麻省理工毕业生无法解决的问题”。但这个问题不是标题党。这个问题的确可解，但解决方法非常难。　　我们需要求解的是下述方程的整数解：　　
$\frac{a}{b + c} + \frac{b}{a + c} + \frac{c}{a + b} = 4$ 　　但这道题的解决过程就需要使用到椭圆曲线的知识。实际上，这道题的其中一组解为：　　如果想了解这道题的具体解决过程，可以参见知乎上的文章《史上最贱的数学题》。这篇文章通过解决此问题，介绍了椭圆曲线的基本概念。这篇文章还给出了多个关联文章，给出了实数域椭圆曲线（参见《新手上路：实数上的椭圆曲线和群论》）、有限域椭圆曲线（参见《Elliptic Curve Cryptography: finite fields and discrete logarithms》）的基本定义。下面仅介绍本文要用到的一些非常基础的概念。本章的部分描述来自于《新手上路：实数上的椭圆曲线和群论》，本章所使用的图像和例子来自于幻灯片《Elliptic Curve Cryptography》。　　椭圆曲线是由方程
描述的曲线，其中
$4a^3 + 27b^2 \neq 0$ 。一般称此方程是椭圆曲线的魏尔斯特拉斯形式。根据椭圆曲线坐标类型的不同，可以将椭圆曲线分为实数域椭圆曲线和有限域椭圆曲线。简单来说，实数域椭圆曲线是指方程
的坐标
(x,y) 均可以为实数。典型的实数域椭圆曲线形状如下图所示。

典型的实数域椭圆曲线形状　　有限域椭圆曲线是指方程
的坐标
(x, y) 是有限域
$\mathbb{F}$ 中的素，一般称有限域
$\mathbb{F}$ 为椭圆曲线的基域。基域
$\mathbb{F}$ 一般有两种情况，一种是阶为
2^m 的有限域，称为二扩域，用
$\mathbb{F}_{2^m}$ 表示。一种是阶为质数
的有限域，称为素域，用
$\mathbb{F}_p$ 表示。这里我们只考虑素域，素域中一共包括
共
个素，代数运算在标准运算的基础上在模
。　　这里可能会为读者带来误导。对于
$\mathbb{F}_{2^m}$ 定义下的椭圆曲线，其形式不为
。可参考《SM2椭圆曲线公钥密码算法推荐曲线参数》的附录A.3，了解
$\mathbb{F}_{2^m}$ 定义下的椭圆曲线。　　举个例子，考虑坐标
(x, y) 定义
$\mathbb{F}_5$ 在上的有限域椭圆曲线
。此时，坐标
(x, y) 都只能在
[0, 4] 之间选取。满足方程
所有可能的坐标为：
x = 0 ，要求
$0^3 + 2 \times 0 + 3 = 3 \pmod 5$ ，
无解。
x = 1 ，要求
$1^3 + 2 \times 1 + 3 = 6 = 1 \pmod 5$ ，
y = 1,4 。
x = 2 ，要求
$2^3 + 2 \times 2 + 3 = 15 = 0 \pmod 5$ ，
y = 0 。
x = 3 ，要求
$3^3 + 2 \times 3 + 3 = 36 = 1 \pmod 5$ ，
y = 1,4 。
x = 4 ，要求
$4^3 + 2 \times 4 + 3 = 75 = 0 \pmod 5$ ，
y = 0 。　　因此，定义在基域
$\mathbb{F}_5$ 上的有限域椭圆曲线
可以包含点
。在椭圆曲线中还需要定义一个无穷远点
$\mathcal{O}$ 。特别要注意
x = 0 的情况，此时找不到一个满足
$y^2 =3 \pmod 5$ 的
。　　椭圆曲线基础运算　　给定椭圆曲线上的两个点
，定义
，其中：　　
$m = \begin{cases}\frac{y_1 - y_2}{x_1 - x_2} & \text{ 如果 } P_1 \neq P_2 \\\frac{3x_1^2 + a}{2y_1} & \text{ 如果 } P_1 = P_2\end{cases}$ 　　根据
P, Q 的不同情况，有加运算、逆运算、标量乘运算这三种可能。这里为更直观地演示运算过程，示意图选用实数域椭圆曲线。再次强调，基域为
$\mathbb{F}_p$ 的有限域椭圆曲线坐标均为
$\mathbb{F}_p$ 的素，因此椭圆曲线实际的图像应该如下图所示。

有限域椭圆曲线图像　　加运算　　当
$P \neq Q$ 时，
相当于在图像上连接
P, Q 两点，交椭圆曲线到第三个点
，并取
相对于横轴的对称点得到
，如下图所示。

椭圆曲线加运算　　此运算称为椭圆曲线下的加运算（add）。　　逆运算　　既然定义了加法运算，也就需要定义减法运算。两个椭圆曲线点的减法运算可以看成一个椭圆曲线点加上一个椭圆曲线点的逆，即
。给定椭圆曲线点
，则定义
为
相对于横轴的对称点，即
，如下图所示。

椭圆曲线逆运算　　此运算称为椭圆曲线下的逆运算（negate）（也称逆运算）。注意到前面的表格中，当
x = 1 和
x = 3 时，
有两个可能的取值
1, 4 ，这是因为
1, 4 在
$\mathbb{F}_5$ 下为逆。换句话说，
$-1 = 4 \pmod 5$ 且
$-4 = 1 \pmod 5$ ，原因是
$1 + 4 = 0 \pmod 5$ 。　　根据加法的定义，
应该为在图像上连接
P, -P 两点，交椭圆曲线到第三个点。然而，此时
P, -P 两点的连线无法在椭圆曲线上与第三个点相交。而根据逆的定义，我们应该要求
。为此，数学上将无穷远点定义为椭圆曲线上的零
$\mathcal{O}$ 。　　乘运算　　当
P = Q 时，
相当于计算
在椭圆曲线上的切线，交椭圆曲线到另一个点
，并取相对于横轴的对称点得到
，如下图所示。

椭圆曲线乘运算　　注意到此时
R = 2P 。按照相同的计算方法，可以继续定义
$3P, 4P, \ldots, kP$ 等运算。此运算称为椭圆曲线下的乘运算（Multiply）。　　标准离散对数群一般不使用加法，而是用乘法运算和幂运算来构造密码学算法。这是因为当满足一定的条件时，标准离散对数群
$\mathbb{Z}_p$ 在幂运算
$h^r \pmod p$ 下满足离散对数（Discrete Logarithm，DLog）困难问题。ECC最重要的作用是替代标准离散对数群
$\mathbb{Z}_p$ 。然而，椭圆曲线在乘运算（而不是幂运算）下满足离散对数以及相关困难问题（感谢@thyyyy的建议，这里增加了离散对数问题的参考链接）。因此，目前很多密码学领域的论文仍然会使用乘法运算和幂运算来描述与标准离散对数群
$\mathbb{Z}_p$ 运算相关的方案，并指出此方案可以换为椭圆曲线。这里更换时，幂运算指的就是椭圆曲线乘法运算，而乘法运算对应的就是椭圆曲线加法运算。　　后续描述中，为了更符合密码学领域的惯用表示方法，我们分别用幂运算和乘法运算表示椭圆曲线上的乘法运算和加法运算，即用乘法运算符号
$g_3 = g_1 \cdot g_2$ 表示椭圆曲线加法运算
，用幂运算（感谢评论区@thyyyy的指正，这里之前写成了加法运算符号，不过不知道为什么这里艾特不了，可能是因为公式太多了？）符号
表示椭圆曲线乘法运算
$G_2 = r \cdot G_1$ 。　　知友 @刘醉白在评论区给出了他为解释有限域椭圆曲线加法和乘法运算原理的动图，相当生动。我认为这是一个很不错的理解资料，特在本文中引用，感兴趣的知友可以访问原回答查看动图，形象地理解椭圆曲线的基础运算。密码学里椭圆曲线的倍点计算是怎么保证结果是整数的？　　生成与椭圆曲线群　　有限域椭圆曲线还有一个很重要的概念，称为生成（Generator）。简单来说，给定椭圆曲线上的一个点
，可以找到一个最小的
n < p ，使得对于任意
$k \in [1, n)$ ，
$g^k \neq \mathcal{O}$ ，且
$g^n = \mathcal{O}$ 。此时，
$g^0 = \mathcal{O}, g^1, \ldots, g^{n - 1}$ 所得到的
个椭圆曲线点形成了有限域椭圆曲线群
$E(\mathbb{F}_p)$ 。在密码学中，我们实际使用的是给定生成
的有限域椭圆曲线群
$E(\mathbb{F}_p)$ ，此群的阶为
。在论文中，一般将这个群
$E(\mathbb{F}_p)$ 简单地表示为
$\mathbb{G}$ 。　　压缩表示　　注意到，需要用坐标
(x, y) 表示椭圆曲线上的一个点，且每个坐标都是基域
$\mathbb{F}_p$ 中的一个素。当质数
有256比特长时，这意味着需要用大约为2个256比特，即64字节来表示坐标
(x, y) 。实际实现中，还可能涉及到一个辅助参数
的计算，因此实际使用的字节数会比64字节更多一些，至少为65字节。　　当已知椭圆曲线点的横坐标
时，纵坐标
只可能有两种取值。从有限域角度看，这两个取值一个为正数
，一个为负数
。因此，可以进一步将椭圆曲线点表示为
$(x, \pm 1)$ ，从而进一步压缩椭圆曲线点的表示长度。当质数
有256比特长时，理论上只需要一个256比特，即32字节表示
，再用1比特长的数表示
，即可表示坐标
(x, y) 。然而，由于计算机最小的存储单位是包含8个比特信息量的字节，因此实际需要33字节来表示坐标
(x, y) 。　　常见椭圆曲线参数　　有了上面的概念，就可以知道如何定义一个椭圆曲线了。定义一个有限域
$\mathbb{F}_p$ 来完成椭圆曲线坐标的运算，即需要定义一个质数
。定义椭圆曲线方程
中的参数
$a, b \in \mathbb{F}_p$ 。此时，我们已经定义好了椭圆曲线群
$E(\mathbb{F}_p)$ 。定义椭圆曲线的生成
。注意，生成也是椭圆曲线上的一个点，因此生成要定义成坐标，即
，并得到生成
的阶
。还有一个称为协因子（cofactor）的重要参数，一般用符号
表示。实际上，通过生成
得到的椭圆曲线群并不一定是椭圆曲线群
$E(\mathbb{F}_p)$ 本身，还可能是椭圆曲线群
$E(\mathbb{F}_p)$ 的某个子群。根据群论，子群的阶一定可以被群阶整除。此时，可以定义
$h = \frac{1}{n} |E(\mathbb{F}_p)|$ 。　　椭圆曲线的参数都是可以公开的。密码学领域常用的椭圆曲线有Secp256k1（也称为Prime256k1）、国产公钥密码学算法SM2使用的椭圆曲线称为Sm2p256v1、还有上述提到的Curve25519椭圆曲线。椭圆曲线的具体参数如下。　　Secp256k1 　　在比特币诞生之前，secp256k1基本未得到使用。出于性能、安全性等考虑，比特币使用secp256k1椭圆曲线构建椭圆曲线数字签名算法（ECDSA），至此secp256k1才得到了广泛的应用。secp256k1的质数
$p = 2^{256} - 2^{32} - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1$ 为256比特长，参数的具体来源和背景参见《Secp256k1 – Bitcoin Wiki》。　　sm2p256v1 　　sm2p256v1是我国国产密码学算法SM2使用的椭圆曲线，参数的具体来源和背景参见《SM2椭圆曲线公钥密码算法推荐曲线参数》。如果实际业务中有国产密码学算法的要求，可以使用此参数构建椭圆曲线。　　在《SM2椭圆曲线公钥密码算法—第1部分：总则》的附录C.2也可以找到实例参数，但此实例只用于演示椭圆曲线的计算过程，并给出样例计算结果。总则也详细介绍了椭圆曲线的核心原理。如果想深入了解椭圆曲线，这是个很好的学习材料。　　Curve25519 　　Curve25519不是用魏尔斯特拉斯一般形式来定义椭圆曲线的，而是采用蒙哥马利曲线形式：
。此椭圆曲线关联的质数
$p = 2^{255} - 19$ ，这也是25519这个数字的由来。需要特别注意的是，Curve25519的协因子
h = 8 。　　HashToCurve 　　ECC中一个非常重要的运算是哈希到椭圆曲线（HashToCurve）：给定任意一个数据，如何将其映射到椭圆曲线上？　　不安全的方法　　直观看，一种最简单的方式是：应用一个安全哈希函数（如SHA256）哈希数据，并将哈希结果映射到
$r \in [0, n)$ 中。将
作为幂，计算
h = g^r 。　　这样就把任意一个数据映射到椭圆曲线上了。然而，在绝大多数情况下，这种映射方法都会带来安全问题。特别地，如果在ECDH-PSI上使用这种方法，则得到的PSI将不再安全。　　安全的方法：HashToCurve标准草案　　实际上，HashToCurve有标准草案，称为《Hashing to Elliptic Curves》。截至2021年12月21日，此标准的最新更新时间为2021年12月11日，仍然是一个演进中的标准，相应的标准实现参见《Hashing to Elliptic Curves》。　　一般的方法：HashToX 　　标准草案提供的HashToCurve，其核心目的是使实现的方案可以抵御侧信道攻击。然而，标准草案的方法效率相对较低，而且实现起来相对比较困难。一般来说，常见的方法是：应用一个安全哈希函数（如SHA256）哈希数据，并将哈希结果映射到椭圆曲线的
坐标。根据椭圆曲线的定义和
坐标计算
坐标。如果失败，则对
再次哈希，重复步骤2。注意：有的实现会令
。如果成功，返回椭圆曲线点
(x, y) 。　　实际上，谷歌的PSI衍生协议Private intersection-sum-with-cardinality[1]使用的就是这一算法。论文的第3.2节：参数选择（Parameter Choice）写到：For our deployment, we use OpenSSL’s implementation “prime256v1”, a NIST elliptic curve with 256-bit group elements, as the group $\mathcal{G}$. For the random oracle, we use SHA-256 applied to the input, and re-applied until the resulting output lies on the elliptic curve. In order to simulate a new random oracle for each execution, the parties choose a common random seed and prepend it to each input before hashing. 　　其中，谷歌的实现“prime256v1”指的就是secp256k1，其使用了OpenSSL的实现。上述英文段落描述的就是这样一个哈希算法。特别地，在论文的脚注3写到：We note that this method of hashing to the curve is susceptible to timing attacks, however these attacks don’t apply in our scenario since items are hashed to the curve before protocol execution. Methods of hashing to a curve that are free from timing attacks can be found at https://datatracker.ietf.org/doc/draft-irtf-cfrg-hash-to-curve. 　　明确说明了这一方法会遇到侧信道攻击，并描述在谷歌的应用场景中无法实施这一攻击。实际上，我非常推荐大家阅读谷歌的这篇论文《On deploying secure computing: Private intersection-sum-with-cardinality》。虽然这篇论文并没有中稿安全领域四大顶级会议，但从论文可以看到谷歌对于MPC这类高安全技术的应用花费了非常多的精力，各个细节点都描述的非常透彻。　　Bouncy Castle椭圆曲线运算　　出于性能考虑，绝大多数密码学算法的实现都是基于C/C++的。这里特别介绍Java下的一个著名密码学工具库Bouncy Castle。Bouncy Castle提供了纯Java的完备椭圆曲线运算实现。经过测试，此实现是线程安全的，可以放心大胆地启用并发来提高性能。与C/C++追求极致性能优化的方式不同，Bouncy Castle的代码想对更加容易理解（这也是因为Java在性能优化层面实在无法做得更多，这使得更易读的实现方式变得可能）。此外，可以在CustomNamedCurves.java查看支持的椭圆曲线类型，这里包括了国产密码学算法sm2p256v1。可以在ECPoint.java查看Bouncy Castle封装的椭圆曲线运算。　　椭圆曲线基础运算演示　　我们用代码来简单演示椭圆曲线运算，以secp256k1为例。　　上述代码的输出结果如下。仔细观察，此输出结果与secpk256k1的参数定义是相同的。　　如果想更换椭圆曲线，只需要修改CustomNamedCurves.getByName(“secp256k1”)中的椭圆曲线名称。例如，如果把椭圆曲线名称修改为sm2p256v1，输出结果如下。仔细观察，此输出结果与sm2p256v1的参数定义是相同的。　　一般HashToCurve的实现　　下述代码演示了使用Bouncy Castle实现HashToCurve的方法。我们也可以在代码中看到如何应用Bouncy Castle构造椭圆曲线点。　　总结　　本文介绍了椭圆曲线的基本概念和基本原理，并应用Bouncy Castle演示了如何实现椭圆曲线的运算。然而，本文还遗留了不少需要进一步回答的问题：除了由方程
描述的维尔斯特拉斯型曲线外，还有什么类型的椭圆曲线？我们总看到Curve25519，Ed25519的概念，这两个曲线有什么特性？　　我们将在后续文章中介绍相应的概念。　　参考文献　　[1] Ion, Mihaela, Ben Kreuter, Ahmet Erhan Nergiz, Sarvar Patel, Shobhit Saxena, Karn Seth, Mariana Raykova, David Shanahan, and Moti Yung. On deploying secure computing: Private intersection-sum-with-cardinality. In Proceddings of the 2021 IEEE European Symposium on Security and Privacy (EuroS&P), pp. 370-389, IEEE, 2021. 　　[2] Buddhavarapu, Prasad, Andrew Knox, Payman Mohassel, Shubho Sengupta, Erik Taubeneck, and Vlad Vlaskin. Private Matching for Compute. IACR Cryptol. ePrint Arch. 2020: 599. 　　[3] Movahedi, Mahnush, Benjamin M. Case, James Honaker, Andrew Knox, Li Li, Yiming Paul Li, Sanjay Saravanan, Shubho Sengupta, and Erik Taubeneck. Privacy-Preserving Randomized Controlled Trials: A Protocol for Industry Scale Deployment. In Proceedings of the 2021 Cloud Computing Security Workshop, pp. 59-69. 2021. 　　[4] Huberman, Bernardo A., Matt Franklin, and Tad Hogg. Enhancing privacy and trust in electronic communities. In Proceedings of the 1st ACM conference on Electronic commerce, pp. 78-86. 1999. 　　[5] Meadows, Catherine. A more efficient cryptographic matchmaking protocol for use in the absence of a continuously available third party. In Proceedings of the 1986 IEEE Symposium on Security and Privacy, pp. 134-134. IEEE, 1986. 　　[6] Diffie, Whitfield, and Martin Hellman. New directions in cryptography. IEEE transactions on Information Theory 22, no. 6 (1976): 644-654. 　　[7] Koblitz, Neal, Alfred Menezes, and Scott Vanstone. The state of elliptic curve cryptography. Designs, codes and cryptography 19, no. 2 (2000): 173-193. 　　[8] Joux, Antoine. The Weil and Tate pairings as building blocks for public key cryptosystems. In Proceeding of the 2022 International Algorithmic Number Theory Symposium, pp. 20-32. Springer, Berlin, Heidelberg, 2002. 　　[9] Boneh, Dan, and Matt Franklin. Identity-based encryption from the Weil pairing. In Proceeding of the 2001 Annual international cryptology conference (CRYPTO 2001), pp. 213-229. Springer, Berlin, Heidelberg, 2001. 　　[10] Sahai, Amit, and Brent Waters. Fuzzy identity-based encryption. In Proceeding of the 2005 Annual international conference on the theory and applications of cryptographic techniques (EUROCRYPT 2005), pp. 457-473. Springer, Berlin, Heidelberg, 2005. 　　[11] Boneh, Dan, Amit Sahai, and Brent Waters. Functional encryption: Definitions and challenges. In Proceeding of the 2011 Theory of Cryptography Conference (TCC 2011), pp. 253-273. Springer, Berlin, Heidelberg, 2011. 　　[12] Jain, Aayush, Huijia Lin, and Amit Sahai. Indistinguishability obfuscation from well-founded assumptions. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC 2021), pp. 60-73. 2021. 　　[13] Popa, Lucian, Bogdan Groza, and Pal-Stefan Murvay. Performance evaluation of elliptic curve libraries on automotive-grade microcontrollers. In Proceedings of the 14th International Conference on Availability, Reliability and Security, pp. 1-7. 2019.

密码学基础知识_密码学专业就业前景

相关推荐