Montgomery curves 和 Curve25519满足Montgomery curve特征的magma脚本验证

1. 引言 1.1 Weierstrass curve定义

Elliptic curves of Weierstrass form: E : y 2 = x 3 + A x + B , 其 中 A 和 B 为 常 量 。 E: y^2 = x^3 + Ax + B, 其中A和B为常量。 E:y2=x3+Ax+B,其中A和B为常量。 Weierstrass curve的j-invariant为： j = j ( E ) = 1728 4 A 3 4 A 3 + 27 B 3 j = j(E) = 1728 \frac{4A^3}{4A^3+27B^3} j=j(E)=17284A3+27B34A3​

1.2 Montgomery curve定义

Montgomery curve为椭圆曲线的一种，基于Fq的仿射方程表示为： E ( A ; B ) : B y 2 = x ( x 2 + A x + 1 ) E(A;B) : By^2 = x(x^2 + Ax + 1) E(A;B):By2=x(x2+Ax+1) 其中参数A和B为在域Fq内的值，同时满足 B != 0, A2 != 4。

将上述方程转换为投影坐标系下(X : Y : Z)，其中x = X/Z, y = Y/Z，则对应的投影模型： E ( A ; B ) : B Y 2 Z = X ( X 2 + A X Z + Z 2 ) ⊆ P 2 E(A;B) : BY^2Z = X(X^2 + AXZ + Z^2) \subseteq P^2 E(A;B):BY2Z=X(X2+AXZ+Z2)⊆P2

对于投影模型的表示下，E(A;B) 上有一个无穷远点 O = (0 : 1 : 0)，该点为E(A;B) 上唯一的一个Z=0点。

Montgomery curve E(A;B) 中有A、B两个参数，其中最重要的是参数A，参数A将控制E(A;B)的几何图形。 Montgomery curve E(A;B)的j-invariant为： j ( E ( A ; B ) ) = 256 ( 4 A 2 − 3 ) 3 A 2 − 4 j(E(A;B)) = \frac{256(4A^2-3)^3}{A^2-4} j(E(A;B))=A2−4256(4A2−3)3​

所以E(A;B)的 F q ‾ \overline{F_q} Fq​​同构类是完全由A2决定的，与B参数无关。

B参数可认为是‘twisting因子’。

1.3 Weierstrass curve与Montgomery curve相互转换

E ( A ; B ) : B y 2 = x ( x 2 + A x + 1 ) E(A;B) : By^2 = x(x^2 + Ax + 1) E(A;B):By2=x(x2+Ax+1)

E W : v 2 = u 3 + ( B 2 ( 1 − A 2 / 3 ) ) u + B 3 A / 3 ( 2 A 2 / 9 − 1 ) E^W : v^2 = u^3+(B^2(1-A^2/3))u+B^3A/3(2A^2/9-1) EW:v2=u3+(B2(1−A2/3))u+B3A/3(2A2/9−1)

相应的转换关系为： ( x , y ) ↦ ( u , v ) = ( B ( x + A / 3 ) , B 2 y ) (x, y) \mapsto (u,v) = (B(x+A/3),B^2y) (x,y)↦(u,v)=(B(x+A/3),B2y)

( u , v ) ↦ ( x , y ) = ( u / B − A / 3 , v / B 2 ) (u,v) \mapsto (x, y) = (u/B-A/3,v/B^2) (u,v)↦(x,y)=(u/B−A/3,v/B2)

2. Montgomery curve的特征/条件

• 1）Montgomery curve E(A;B)的order总是能被4整除，即B(A+2)、B(A-2)、A2-4 三者必须有其一为Fq域内的平方值，4 | #E(A;B)(Fq) 且#E(A;B)(Fq) = 4r，r为prime素数；
• 2）Montgomery curve E(A;B)总是存在有理数点，具有order为2， T : = ( 0 : 0 : 1 ) ∈ E ( A ; B ) [ 2 ] ( F q ) T := (0 : 0 : 1) \in E(A;B)[2](F_q) T:=(0:0:1)∈E(A;B)[2](Fq​)； 由 P to P ⨁ T P \bigoplus T P⨁T 的转换为： τ T : ( x , y ) ↦ ( 1 / x , − y / x 2 ) \tau_T : (x, y) \mapsto (1/x, -y/x^2) τT​:(x,y)↦(1/x,−y/x2)

3. Curve25519 as a Montgomery curve

The Curve25519 function is Fp-restricted x-coordinate scalar multiplication on E(Fp2 ), where p is the prime number p = 2255 − 19 and E is the elliptic curve y2 = x3 + 486662x2 + x. 对应的base point为(9,…)。 The order of the base point is a prime, namely 2252 + 27742317777372353535851937790883648493. FieldElement对应的域空间为[0, p-1)，即为[0, 2255-19 - 1)。

针对Montgomery curve的条件1），实际是判断B(A+2)、B(A-2)、A2-4 三者至少有一个是 module q的 quadratic residue。 以上可转换为求Legendre symbol值来判断，若该值为-1，则说明不是quadratic residue，若为1，则是quadratic residue。

magma脚本为：

clear;
q:=2^255-19;
LegendreSymbol(486662^2-4, q); //-1，即A^2-4不是域Fq内的平方值。
LegendreSymbol(486662+2, q); //1，即A+2是域Fq内的平方值。
LegendreSymbol(486662-2, q); //-1，即A-2不是域Fq内的平方值。

对应的运行结果说明A+2为域Fq内的平方值，满足条件1。

-1
1
-1

由此可知，Curve25519为Montgomery curve。

参考资料： [1] 论文《Montgomery curves and their arithmetic》 [2] 书 《Elliptic Curves Number Theory And Cryptography 2n》 [3] https://asecuritysite.com/comms/plot06 [4] https://www.maths.tcd.ie/pub/Maths/Courseware/NumberTheory/QuadraticResidues.pdf