首发于数据安全、隐私保护与密码学技术专栏

Ed25519与Curve25519：概念与相互转换

写在前面

本文的主要作者为彭力强，次要作者为刘巍然。经过与原作者讨论，特将文章同步至本专栏中。其中，彭力强完成了原理研究、代码实验和大部分内容的撰写。我主要对文章结构进行了调整，并对内容进行了细微的修改。

引言

椭圆曲线（Elliptic Curve，EC）是密码学中非常重要的代数结构。在公钥加密、数字签名、密钥协商、安全多方计算等领域均有非常广泛的应用。椭圆曲线数字签名ECDSA、椭圆曲线Diffie-Hellman隐私集合求交协议（EC-DH PSI）等都是椭圆曲线在密码学中的实际应用。

在应用椭圆曲线构建并实现密码学方案时，首先需要选择适当的椭圆曲线类型。常见的椭圆曲线有secp256k1、Curve25519、Ed25519，以及国产密码学算法SM2所依赖的椭圆曲线sm2p256v1。secp256k1和sm2p256v1这类椭圆曲线相对更好理解。与之相比，Curve25519、Ed25519的定义更加复杂。经过查找，相关概念也缺乏清晰中文文档解释，理解和使用时容易混淆。

本文将主要介绍Curve25519和Ed25519椭圆曲线。我们希望从原理和实现角度展开介绍，从而帮助开发人员理解并掌握这两个椭圆曲线。本文将介绍两个曲线涉及的基本概念，使用过程中的注意事项，以及两个椭圆曲线之间的转换方法。最后，我们结合著名Java密码学库Bouncy Castle，介绍如何应用纯Java实现并使用Curve25519和Ed25519。

三种椭圆曲线

一般材料会以维尔斯特拉斯曲线（Weierstrass Curve）为例介绍椭圆曲线的基本概念和运算原理，这是因为任意椭圆曲线都可以写为维尔斯特拉斯曲线形式。实际上，椭圆曲线还包括多种其他的类型，如蒙哥马利曲线（Montgomery Curve）、扭曲爱德华曲线（Twisted Edwards Curve）等。Curve25519就是在蒙哥马利曲线上定义的椭圆曲线，而Ed25519是在扭曲爱德华曲线上定义的椭圆曲线。

一些约定

本文描述的椭圆曲线并非定义在实数上的椭圆曲线，而是定义在有限域上的椭圆曲线。我们用我们用 F_p 表示椭圆曲线坐标所属的有限域，其中 p 是一个质数。我们令 E(F_p) 表示椭圆曲线上点的集合。在集合 E(F_p) 上可以定义无穷远点（零点）、生成元（基点）、加法运算、逆运算等，就可以使椭圆曲线上点的集合构成一个群。

维尔斯特拉斯曲线

椭圆曲线的一般形式可表示为：

E: y^2=x^3+Ax+B

其中 A,B\in F_p, 4A^3 + 27B^2 \neq 0 。一般称上式为维尔斯特拉斯形式的椭圆曲线方程。

蒙哥马利曲线

蒙哥马利形式的椭圆曲线方程定义为：

Kt^2 = s^3 + Js^2 + s

其中 K, J \in F_p, B(A^2 - 4) \neq 0 。

扭曲爱德华曲线

扭曲爱德华形式的椭圆曲线方程定义为：

av^2+w^2 = 1 + dv^2w^2

其中 a,d \neq 0, a \neq d 。

椭圆曲线间的转换

维尔斯特拉斯曲线、蒙哥马利曲线、扭曲爱德华曲线这三类椭圆曲线之间可以相互转换。

蒙哥马利曲线 <-> 维尔斯特拉斯曲线

任何椭圆曲线都可以写为维尔斯特拉斯形式。反之，当满足特定条件时，维尔斯特拉斯椭圆曲线可以转换为蒙哥马利椭圆曲线。具体转换条件参见《Montgomery Curve》的Equivalence with Weierstrass curves部分。

蒙哥马利曲线（ Kt^2 = s^3 + Js^2 + s ）转换为等价维尔斯特拉斯曲线（ y^2=x^3+Ax+B ）的方法为：

  • A = \frac{3 - J^2}{3K^2}
  • B = \frac{2J^3 - 9J}{27K^3}

蒙哥马利曲线点 (s, t) 转换为等价维尔斯特拉斯曲线点 (x, y) 的方法为：

  • x = \frac{3s + J}{3K}
  • y=\frac{t}{K}

反之，维尔斯特拉斯曲线点 (x, y) 转换为等价蒙哥马利曲线点 (s, t) 的方法为：

  • s = \frac{3Kx-J}{3}
  • t = \frac{y}{K}

扭曲爱德华曲线 <-> 蒙哥马利曲线

所有扭曲爱德华曲线都与蒙哥马利曲线双向有理等价（Birationally Equivalent），反之亦然。所谓双向有理等价，可以理解为除了个别点外，扭曲爱德华曲线的点和蒙哥马利曲线的点存在相互映射关系。

扭曲爱德华曲线（ av^2+w^2 = 1 + dv^2w^2 ）转换为等价蒙哥马利曲线（ Kt^2 = s^3 + Js^2 + s ）的方法为：

  • J = \frac{2(a+d)}{a - d}
  • K = \frac{4}{a - d}

扭曲爱德华曲线点 (v, w) 转换为等价蒙哥马利曲线点 (s, t) 的方法为：

  • s = \frac{1 + w}{1 - w}
  • t = \frac{s}{v}

当 v = 0 或者 w = 1 时，映射方法为 (s, t) = (0, 0) 。

蒙哥马利曲线点 (s, t) 转换为扭曲爱德华曲线点 (v, w) 的方法为：

  • v = \frac{s}{t}
  • w = \frac{s - 1}{s + 1}

当 t = 0 或者 s = -1 时，映射方法为 (v, w) = (0, -1) 。

Curve25519与Ed25519

Curve25519

Curve25519椭圆曲线是由著名密码学家Daniel J. Bernstein在2006年设计提出的[Bern06]。Curve25519是蒙哥马利椭圆曲线椭圆曲线（ Kt^2 = s^3 + Js^2 + s ）的一个实例[RFC7748]，其中 p=2^{255} - 19 （这也是25519这个名字的由来）， K = 1 ， J = 486662 ，基点定义为：

(9, 14781619447589544791020593568409986887264606134616475288964881837755586237401)

利用上文给出的转换方法，可以得到Curve25519曲线对应的威尔斯特拉斯椭圆曲线参数：

A = 19298681539552699237261830834781317975544997444273427339909597334573241639236

B = 55751746669818908907645289078257140818241103727901012315294400837956729358436

维尔斯特拉斯形式椭圆曲线对应的基点为：

g_x = 19298681539552699237261830834781317975544997444273427339909597334652188435546

g_y = 14781619447589544791020593568409986887264606134616475288964881837755586237401

Curve25519一般用于椭圆曲线密钥交换协议（ECDH）。安全多方计算领域中实现基于椭圆曲线基础不经意传输（Base Oblivious Transfer，Base OT）时一般也会使用Curve25519[CO15]。

Ed25519

Ed25519椭圆曲线也是由Bernstein设计提出的。Ed25519是扭曲爱德华椭圆曲线（ av^2+w^2 = 1 + dv^2w^2 ）的一个实例，其中 p=2^{255} - 19 （因此也为25519系列曲线），且：

a = -1

d = 37095705934669439343138083508754565189542113879843219016388785533085940283555

基点定义为：

v = 15112221349535400772501151409588531511454012693041857206046113283949847762202

w = 46316835694926478169428394003475163141307993866256225615783033603165251855960

2011年，Bernstein等学者在Edwards25519曲线上构建了高效安全的Schnorr变种签名机制，EdDSA（Edwards-curve Digital Signature Algorithm）方案[BDLS11]。[RFC8032]给出了EdDSA签名的具体规范，包括基于Edwards25519曲线的签名机制测试结果。另外，EdDSA签名机制的公钥和签名值的字节长度都相对较小，基于Edwards25519曲线的EdDSA签名算法的公钥为32个字节，签名值为64个字节。除此之外，EdDSA还有签名过程不需要外部随机数、可以抵抗侧信道攻击等优点。换句话说，Ed25519提出的核心目的主要是为了设计并实现非常高效的数字签名方案。有关Ed25519的详细介绍，可以参考《Ed25519: High-Speed High-Security Signatures》。

相互转换

Curve25519和Ed25519存在双向有理等价映射，[RFC7748]。换句话说，只要实现了其中一种类型的曲线，就可以利用双向有理等价得到另一种类型的曲线实现。

  • Curve25519曲线点转换为Ed25519曲线点： (v, w) = \left(\frac{\sqrt{-486664}s}{t}, \frac{s - 1}{s + 1}\right)
  • Ed25519曲线点转换为Curve25519曲线点： (s,t) = \left(\frac{1 + w}{1 - w},\frac{\sqrt{-486664}s}{v} \right)

Bouncy Castle中的25519曲线家族

Bouncy Castle是应用纯Java语言实现的密码学算法库。椭圆曲线涉及的运算比较复杂，C/C++乃至汇编语言的实现效率更高。然而，更高的效率，特别是汇编语言的实现，也就意味着跨平台的支持复杂。此外，复杂的实现也意味着代码相对更难以理解。

在隐私计算技术需求强烈的大背景下，相应协议和实现的互联互通是未来我们需要面对的问题，在各个平台上支持服务的部署与应用，意味着要根据不同的环境进行代码的调整和适配。此时，支持跨平台执行的Java程序在应用落地时会帮助我们减少跨平台带来的问题。为此，我们以纯Java实现的Bouncy Castle为例，介绍25519家族曲线的实现方法。

我们在这里需要强调的是，C/C++乃至汇编语言的实现，并打通相应实现的编码格式和运算方法，应是未来高性能应用落地的必经之路。

Bouncy Castle的Curve25519

Bouncy Castle提供了Curve25519的完整实现，仅需要简单的设置即可使用Curve25519：

// 配置椭圆曲线参数
X9ECParameters ecParameters = CustomNamedCurves.getByName("curve25519");
ECParameterSpec ecParameterSpec = new ECParameterSpec(
    ecParameters.getCurve(), ecParameters.getG(), ecParameters.getN(),
    ecParameters.getH(), ecParameters.getSeed()
);
ECDomainParameters ecDomainParameters = new ECDomainParameters(
    ecParameterSpec.getCurve(), ecParameterSpec.getG(), ecParameterSpec.getN()
);

Bouncy Castle也支持自定义椭圆曲线，但默认需要使用维尔斯特拉斯形式表示。下述代码演示了使用维尔斯特拉斯形式配置Curve25519曲线的方法。

static X9ECParametersHolder curve25519 = new X9ECParametersHolder()
{
  	protected X9ECParameters createParameters()
  	{
    	byte[] s = null;
    	ECCurve curve = configureCurve(new Curve25519());
        /*
         * NOTE: Curve25519 was specified in Montgomery form. Rewriting in Weierstrass form
         * involves substitution of variables, so the base-point x coordinate is 9 + (486662 / 3).
         * 
         * The Curve25519 paper doesn't say which of the two possible y values the base
         * point has. The choice here is guided by language in the Ed25519 paper.
         * 
         * (The other possible y value is 5F51E65E475F794B1FE122D388B72EB36DC2B28192839E4DD6163A5D81312C14) 
        */
    	X9ECPoint generator = configureBasepoint(curve, 
        "042AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAD245A20AE19A1B8A086B4E01EDD2C7748D14C923D4D7E6D7C61B229E9C5A27ECED3D9");
	    return new X9ECParameters(curve, generator, curve.getOrder(), curve.getCofactor(), s);
  	}
};

上述得到的椭圆曲线与通过默认配置得到的Curve25519椭圆曲线是相同的。

Bouncy Castle的Ed25519

Bouncy Castle的椭圆曲线运算一般抽象为ECPoint形式。遗憾的是，Bouncy Castle并没有提供Ed25519曲线的ECPoint抽象。为了支持Ed25519的数字签名方案，Bouncy Castle提供了Ed25519的单独实现，相应实现代码位于org.bouncycastle.math.ec.rfc8032.Ed25519。

此代码从性能角度考虑应用了大量的技巧，并对外暴露标准的byte[]输出，从而与国际标准兼容。学习此代码的实现会加深性能优化的理解，是一个很不错的资料。

利用Bouncy Castle的Curve25519实现Ed25519曲线运算

既然Bouncy Castle没有提供Ed25519的通用抽象实现，如何才能使用Ed25519曲线实现类似EC-DH-PSI的自定义协议呢？我们可以利用前文提到的等价转换方法，使用Curve25519的抽象表示实现Ed25519椭圆曲线运算。在此特别需要注意，此类转换不可避免地会引入额外的开销。如何给出统一的高性能实现是后续我们需要解决的问题。

编码

Bouncy Castle用ECPoint来表示椭圆曲线上的点。然而，Bouncy Castle库中Curve类和ECPoint类的表示形式均为维尔斯特拉斯形式的曲线和点坐标。因此，我们无法直接用ECPoint的编码接口，通过Curve25519的椭圆曲线点编码得到Ed25519曲线上点坐标的编码。为了实现Ed25519曲线上点坐标的编码，我们应按如下步骤来执行。

// Curve25519点标准化，得到威尔斯特拉斯曲线点的坐标
ECPoint normalizedPoint = ecPoint.normalize();
// 获取威尔斯特拉斯曲线点的坐标，映射成蒙哥马利点坐标
ECFieldElement x = normalizedPoint.getAffineXCoord();
ECFieldElement y = normalizedPoint.getAffineYCoord();
ECFieldElement[] montgomeryPoint = new ECFieldElement[2];
// u = (3x - 486662) / 3
montgomeryPoint[0] = (ecFieldElement3.multiply(x).subtract(ecFieldElement486662)).divide(ecFieldElement3);
// v = y
montgomeryPoint[1] = y;
// 将Curve25519点的坐标映射为Ed25519点的坐标 
ECFieldElement[] edwardsPoint = new ECFieldElement[2];
// x = √a * u / v
edwardsPoint[0] = aSqrt.multiply(montgomeryPoint[0]).divide(montgomeryPoint[1]);
// y = (u - 1) / (u + 1)
edwardsPoint[1] = u.subtract(one).divide(montgomeryPoint[0].addOne());
// 编码（非压缩表示），坐标包含2个点，每个点32字节，共64字节
// 直接用BigInteger.getBytes()可能会出现转换结果为33字节的情况
// 这是因为如果32字节的最高位为1，则Java会自动补一个字节作为符号位
// 这里我们实现了一个工具，可以指定转换结果的字节长度，并保证转换结果一定不出现补码表示
return ByteBuffer.allocate(64)
    .put(BigIntegerUtils.nonNegBigIntegerToByteArray(t2[0].negate().toBigInteger(), 32))
    .put(BigIntegerUtils.nonNegBigIntegerToByteArray(t2[1].toBigInteger(), 32))
    .array();

解码

在将一个Ed25519点坐标的字节数组解码到ECPoint的实例时，我们也无法直接复用ECPoint的解码接口。为了将Ed25519点坐标的字节数组，解码成ECPoint的一个实例，我们应按如下步骤来执行。

// 这里用到的ecDomainParameters是Curve25519初始化得到的
// 拆分坐标
byte[] encodeEdwardPoint = new byte[POINT_BYTES];
ECFieldElement[] edwardsPoint = new ECFieldElement[2];
// 转换x
System.arraycopy(encoded, 0, encodeEdwardPoint, 0, POINT_BYTES);
edwardsPoint[0] = ecDomainParameters.getCurve().fromBigInteger(
    BigIntegerUtils.byteArrayToNonNegBigInteger(encodeEdwardPoint)
).negate();
// 转换y
System.arraycopy(encoded, POINT_BYTES, encodeEdwardPoint, 0, POINT_BYTES);
edwardsPoint[1] = ecDomainParameters.getCurve().fromBigInteger(
    BigIntegerUtils.byteArrayToNonNegBigInteger(encodeEdwardPoint)
);
// 将Ed25519的扭曲曲线坐标转换为蒙哥马利曲线坐标（即Curve25519坐标）
ECFieldElement[] montgomeryPoint = new ECFieldElement[2];
// u = (1 + y) / (1 - y)
montgomeryPoint[0] = one.add(edwardsPoint[1]).divide(one.subtract(edwardsPoint[1]));
// v = √a * u / x
montgomeryPoint[1] = aSqrt.multiply(montgomeryPoint[0]).divide(edwardsPoint[0]);
// 将蒙哥马利曲线坐标转换为维尔斯特拉斯曲线坐标
ECFieldElement[] weierstrassPoint = new ECFieldElement[2];
// x = (3u + 486662) / 3
weierstrassPoint[0] = (ecFieldElement3.multiply(montgomeryPoint[0]).add(ecFieldElement486662)).divide(ecFieldElement3);
// v = y
weierstrassPoint[1] = montgomeryPoint[1];
// 构建椭圆曲线点
ECPoint ecPoint = ecDomainParameters.getCurve().createPoint(
    weierstrassPoint[0].toBigInteger(), weierstrassPoint[1].toBigInteger()
);

运算

经过上述解码后，我们把Ed25519曲线点坐标映射为Curve25519曲线点坐标，且底层坐标表示是ECPoint所需的维尔斯特拉斯曲线。因此，我们可以复用Curve25519曲线的点乘等算数运算接口。计算结束后，只需要按上述的编码实现方法，再转化为Ed25519点坐标输出即可。

参考文献

[Bern06] Daniel J. Bernstein. Curve25519: new Diffie-Hellman speed records. PKC 2006, pp. 207-228. Springer, Berlin, Heidelberg, 2006.

[BDLS11] Daniel J. Bernstein, Niels Duif, Tanja Lange, Peter Schwabe and Boyin Yang. High-speed high-security signatures. CHES 2011, pp. 124-142. Springer, Berlin, Heidelberg, 2011.

[CO15] Chou, Tung, and Claudio Orlandi. The simplest protocol for oblivious transfer. LATINCRYPT 2015, pp. 40-58. Springer, Cham, 2015.

[RFC7748] Adam Langley and Mike Hamburg and Sean Turner. Elliptic curves for security. RFC 7748, rfc-editor.org/info/rfc, 2016.

[RFC8032] Simon Josefsson and Ilari Liusvaara. Edwards-curve digital signature algorithm eddsa. RFC 8032, rfc-editor.org/info/rfc, 2017.

发布于 2022-06-04 13:40
密码学
椭圆曲线

文章被以下专栏收录