SageMath: curve25519におけるsmall subgroup

curve25519のねじれ点の算出

有限体$${\mathbb F_q}$$上の楕円曲線 E上の点で，m倍すると無限遠点 Oになる点を mねじれ点(m-torsion point) と呼ぶ。

$$
E[m]:= \{P \in E(\mathbb F_q) \space |\space m * P = O \space \}
$$

で定義される。
以下ではcurve25519のtortion-pointを算出してみる。
SageMathの`division_points()`はm倍したら、Oとなる点のリストを返す関数。
次のように呼び出すとm倍したら、Oとなる点のリストを返してくれる。

sage: E = EllipticCurve(GF(2^255-19),[0,486662,0,1,0])
sage: O = E(0)
sage: O.division_points(m)

Points in small subgroups

# 構築された楕円曲線
sage: print(E)
Elliptic Curve defined by y^2 = x^3 + 486662*x^2 + x over Finite Field of size 57896044618658097711785492504343953926634992332820282019728792003956564819949
sage: E = EllipticCurve(GF(2^255-19),[0,486662,0,1,0])
# Eの有理点の数を素因数分解
sage: E.cardinality().factor()
2^3 * 7237005577332262213973186563042994240857116359379907606001950938285454250989
# 無限遠点
sage: O = E(0)
# 2倍してOになる点
sage: O.division_points(2)
[(0 : 0 : 1), (0 : 1 : 0)]
# 4倍してOになる点
sage: O.division_points(4)
[(0 : 0 : 1),
 (0 : 1 : 0),
 (1 : 9094040566125962849133224048217411091405536248825867518642941381412595940312 : 1),
 (1 : 48802004052532134862652268456126542835229456083994414501085850622543968879637 : 1)]
# 8倍してOになる点
sage: O.division_points(8)
[(0 : 0 : 1),
 (0 : 1 : 0),
 (1 : 9094040566125962849133224048217411091405536248825867518642941381412595940312 : 1),
 (1 : 48802004052532134862652268456126542835229456083994414501085850622543968879637 : 1),
 (325606250916557431795983626356110631294008115727848805560023387167927233504 : 25869741026945134960544184956460972567356779614910045322022475500191642319642 : 1),
 (325606250916557431795983626356110631294008115727848805560023387167927233504 : 32026303591712962751241307547882981359278212717910236697706316503764922500307 : 1),
 (39382357235489614581723060781553021112529911719440698176882885853963445705823 : 10506421237558716435988711236408671798265365380393424752549290025458740468278 : 1),
 (39382357235489614581723060781553021112529911719440698176882885853963445705823 : 47389623381099381275796781267935282128369626952426857267179501978497824351671 : 1)]

列挙された点の位数を計算してみる。

# 位数8の点
sage: P8_1 = E([325606250916557431795983626356110631294008115727848805560023387167927233504, 2586974102694
....: 5134960544184956460972567356779614910045322022475500191642319642])
sage: P8_1.order()
8

# 位数8の点
sage: P8_2 = E([325606250916557431795983626356110631294008115727848805560023387167927233504, 3202630359171
....: 2962751241307547882981359278212717910236697706316503764922500307])
sage: P8_2.order()
8

order-2 elements:

0x0
0x0

order-4 elements:

0x0
0x0
0x1
0x1

order-8 elements:

0x0
0x0
0x1
0x1
0xB8495F16056286FDB1329CEB8D09DA6AC49FF1FAE35616AEB8413B7C7AEBE0
0xB8495F16056286FDB1329CEB8D09DA6AC49FF1FAE35616AEB8413B7C7AEBE0
0x57119FD0DD4E22D8868E1C58C45C44045BEF839C55B1D0B1248C50A3BC959C5F
0x57119FD0DD4E22D8868E1C58C45C44045BEF839C55B1D0B1248C50A3BC959C5F

Links

reject points by libsodium
paper referenced by libsodium x25519
https://cr.yp.to/ecdh.html