LoginSignup
0
0
@kokeshiM0chi

SageMath: elliptic curve - cofactor

Last updated at Posted at 2023-08-06

SageMathで楕円曲線のCofactorを見てみる

このサイトを参考にSageMathで楕円曲線します。

secp256k1

sage: E = EllipticCurve(GF(2 ** 256 - 2 ** 32 - 977), [0, 7])

するとこのように構築されます。

sage: print(E)
Elliptic Curve defined by y^2 = x^3 + 7 over Finite Field of size 115792089237316195423570985008687907853269984665640564039457584007908834671663

スカラー倍算

ベースポイントGを設定し、スカラー倍算してみます。

sage: G = E([55066263022277343669578718895168534326250603453777594175500187360389116729240,32670510020758816978083085130507043184471273380659243275938904335757337482424])

1倍算

sage: 1 * G
(55066263022277343669578718895168534326250603453777594175500187360389116729240 : 32670510020758816978083085130507043184471273380659243275938904335757337482424 : 1)

2倍算

sage: 2 * G
(89565891926547004231252920425935692360644145829622209833684329913297188986597 : 12158399299693830322967808612713398636155367887041628176798871954788371653930 : 1)

楕円曲線上に存在しない点をベースポイントとして定義しようとすると、、

sage: G = E([1,3])

このようにエラーが出力されます。

TypeError: Coordinates [1, 3, 1] do not define a point on Elliptic Curve defined by y^2 = x^3 + 7 over Finite Field of size 115792089237316195423570985008687907853269984665640564039457584007908834671663

長いエラーが出力されますが、最後のメッセージ（上記の箇所）だけ見れば良さそう。

error message 
G = E([1,3])
---------------------------------------------------------------------------
KeyError                                  Traceback (most recent call last)
File /private/var/tmp/sage-10.0-current/local/var/lib/sage/venv-python3.11.1/lib/python3.11/site-packages/sage/structure/category_object.pyx:839, in sage.structure.category_object.CategoryObject.getattr_from_category (build/cythonized/sage/structure/category_object.c:7204)()
    838 try:
--> 839     return self.__cached_methods[name]
    840 except KeyError:

KeyError: 'point_homset'

During handling of the above exception, another exception occurred:

AttributeError                            Traceback (most recent call last)
File /private/var/tmp/sage-10.0-current/local/var/lib/sage/venv-python3.11.1/lib/python3.11/site-packages/sage/schemes/projective/projective_subscheme.py:122, in AlgebraicScheme_subscheme_projective.point(self, v, check)
    121 try:
--> 122     return self._point(self.point_homset(), v, check=check)
    123 except AttributeError:  # legacy code without point_homset

File /private/var/tmp/sage-10.0-current/local/var/lib/sage/venv-python3.11.1/lib/python3.11/site-packages/sage/schemes/elliptic_curves/ell_point.py:259, in EllipticCurvePoint_field.__init__(self, curve, v, check)
    238 """
    239 Constructor for a point on an elliptic curve.
    240 
   (...)
    257     (1 : -2 : 1)
    258 """
--> 259 point_homset = curve.point_homset()
    260 R = point_homset.value_ring()

File /private/var/tmp/sage-10.0-current/local/var/lib/sage/venv-python3.11.1/lib/python3.11/site-packages/sage/structure/category_object.pyx:833, in sage.structure.category_object.CategoryObject.__getattr__ (build/cythonized/sage/structure/category_object.c:7123)()
    832 """
--> 833 return self.getattr_from_category(name)
    834 

File /private/var/tmp/sage-10.0-current/local/var/lib/sage/venv-python3.11.1/lib/python3.11/site-packages/sage/structure/category_object.pyx:848, in sage.structure.category_object.CategoryObject.getattr_from_category (build/cythonized/sage/structure/category_object.c:7289)()
    847 
--> 848             attr = getattr_from_other_class(self, cls, name)
    849             self.__cached_methods[name] = attr

File /private/var/tmp/sage-10.0-current/local/var/lib/sage/venv-python3.11.1/lib/python3.11/site-packages/sage/cpython/getattr.pyx:356, in sage.cpython.getattr.getattr_from_other_class (build/cythonized/sage/cpython/getattr.c:2706)()
    355     dummy_error_message.name = name
--> 356     raise AttributeError(dummy_error_message)
    357 cdef PyObject* attr = instance_getattr(cls, name)

AttributeError: 'sage.rings.finite_rings.integer_mod.IntegerMod_gmp' object has no attribute '__custom_name'

During handling of the above exception, another exception occurred:

TypeError                                 Traceback (most recent call last)
Cell In [5], line 1
----> 1 G = E([Integer(1),Integer(3)])

File /private/var/tmp/sage-10.0-current/local/var/lib/sage/venv-python3.11.1/lib/python3.11/site-packages/sage/schemes/elliptic_curves/ell_generic.py:582, in EllipticCurve_generic.__call__(self, *args, **kwds)
    579             return self._reduce_point(args[0], characteristic)
    580     args = tuple(args[0])
--> 582 return plane_curve.ProjectivePlaneCurve.__call__(self, *args, **kwds)

File /private/var/tmp/sage-10.0-current/local/var/lib/sage/venv-python3.11.1/lib/python3.11/site-packages/sage/schemes/generic/scheme.py:266, in Scheme.__call__(self, *args)
    264             return S
    265         args = S
--> 266 return self.point(args)

File /private/var/tmp/sage-10.0-current/local/var/lib/sage/venv-python3.11.1/lib/python3.11/site-packages/sage/schemes/projective/projective_subscheme.py:124, in AlgebraicScheme_subscheme_projective.point(self, v, check)
    122         return self._point(self.point_homset(), v, check=check)
    123     except AttributeError:  # legacy code without point_homset
--> 124         return self._point(self, v, check=check)
    126 return self.point_homset()(v, check=check)

File /private/var/tmp/sage-10.0-current/local/var/lib/sage/venv-python3.11.1/lib/python3.11/site-packages/sage/schemes/elliptic_curves/ell_point.py:298, in EllipticCurvePoint_field.__init__(self, curve, v, check)
    296         test = y**2 + (a1*x+a3)*y - (((x+a2)*x+a4)*x+a6)
    297     if not test == 0:
--> 298         raise TypeError("Coordinates %s do not define a point on %s" % (list(v), curve))
    300 SchemeMorphism_point_abelian_variety_field.__init__(self, point_homset, v, check=False)

TypeError: Coordinates [1, 3, 1] do not define a point on Elliptic Curve defined by y^2 = x^3 + 7 over Finite Field of size 115792089237316195423570985008687907853269984665640564039457584007908834671663

#Eを計算する

E(GF(F_p))の#Eを算出し、素因数分解します。

sage: E.cardinality().factor()
115792089237316195423570985008687907852837564279074904382605163141518161494337

これは$E(GF(F_p))$の元Gの位数と一致しています。

sage: G.order()
115792089237316195423570985008687907852837564279074904382605163141518161494337
sage:

cofactor

secp256k1はcofactor = 1の曲線であることが簡単に確認できました。

cofactor = 1:


\forall s \in E(GF(F_p)),\exists r \in \mathbb{N}, s.t. \space s^r = G \\

Then, r is called order and the following holds

r =　\#E(GF(F_p))

curve25519

ガロア体上にed25519を構築します。

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

構築された方程式を見てみます。

sage: print(E)
Elliptic Curve defined by y^2 = x^3 + 486662*x^2 + x over Finite Field of size 57896044618658097711785492504343953926634992332820282019728792003956564819949

スカラー倍算

sage: G = E([9, 14781619447589544791020593568409986887264606134616475288964881837755586237401])
sage: 1 * G
(9 : 14781619447589544791020593568409986887264606134616475288964881837755586237401 : 1)
sage: 2 * G
(14847277145635483483963372537557091634710985132825781088887140890597596352251 : 8914613091229147831277935472048643066880067899251840418855181793938505594211 : 1)

base pointが属する部分群の位数は素数

sage: G.order()
7237005577332262213973186563042994240857116359379907606001950938285454250989

#Eを計算する

E(GF(F_p))の#Eを算出し、素因数分解します。

sage: E.cardinality().factor()
2^3 * 7237005577332262213973186563042994240857116359379907606001950938285454250989

cofactor

curve25519はcofactor = 2^3です。

cofactor > 1:


\forall s \in E(GF(F_p)),\exists r \in \mathbb{N}, s.t. \space s^r = G \\

Then,

r \leq　　\#E(GF(F_p))

elements in small subgroup

curve25519のsmall subgroupの点を20個列挙してみる。

sage: for i in range(20):
....:     P = E.random_element()
....:     Q = P.__mul__(2^252 + 0x14def9dea2f79cd65812631a5cf5d3ed)
....:     print (Q.order(), Q)
....: 
8 (325606250916557431795983626356110631294008115727848805560023387167927233504 : 25869741026945134960544184956460972567356779614910045322022475500191642319642 : 1)
1 (0 : 1 : 0)
4 (1 : 9094040566125962849133224048217411091405536248825867518642941381412595940312 : 1)
2 (0 : 0 : 1)
8 (325606250916557431795983626356110631294008115727848805560023387167927233504 : 32026303591712962751241307547882981359278212717910236697706316503764922500307 : 1)
4 (1 : 48802004052532134862652268456126542835229456083994414501085850622543968879637 : 1)

2 (0 : 0 : 1)
8 (325606250916557431795983626356110631294008115727848805560023387167927233504 : 32026303591712962751241307547882981359278212717910236697706316503764922500307 : 1)
8 (39382357235489614581723060781553021112529911719440698176882885853963445705823 : 10506421237558716435988711236408671798265365380393424752549290025458740468278 : 1)
4 (1 : 48802004052532134862652268456126542835229456083994414501085850622543968879637 : 1)
8 (325606250916557431795983626356110631294008115727848805560023387167927233504 : 32026303591712962751241307547882981359278212717910236697706316503764922500307 : 1)
4 (1 : 48802004052532134862652268456126542835229456083994414501085850622543968879637 : 1)
8 (325606250916557431795983626356110631294008115727848805560023387167927233504 : 32026303591712962751241307547882981359278212717910236697706316503764922500307 : 1)
8 (39382357235489614581723060781553021112529911719440698176882885853963445705823 : 10506421237558716435988711236408671798265365380393424752549290025458740468278 : 1)
8 (39382357235489614581723060781553021112529911719440698176882885853963445705823 : 10506421237558716435988711236408671798265365380393424752549290025458740468278 : 1)
1 (0 : 1 : 0)
8 (39382357235489614581723060781553021112529911719440698176882885853963445705823 : 10506421237558716435988711236408671798265365380393424752549290025458740468278 : 1)
4 (1 : 48802004052532134862652268456126542835229456083994414501085850622543968879637 : 1)
8 (325606250916557431795983626356110631294008115727848805560023387167927233504 : 25869741026945134960544184956460972567356779614910045322022475500191642319642 : 1)
4 (1 : 9094040566125962849133224048217411091405536248825867518642941381412595940312 : 1)

上記で算出された点集合のうち、位数4の点はこうなっている

sage: T = E([1 , 9094040566125962849133224048217411091405536248825867518642941381412595940312])
sage: T.order()
4

ed25519

SageMathはツイストエドワーズ曲線をサポートしていません。

なので、次のような変換関数を定義して呼び出します。

sage: p = 0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffed
K = GF(p)
a = K(0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffec)
d = K(0x52036cee2b6ffe738cc740797779e89800700a4d4141d8ab75eb4dca135978a3)
E = EllipticCurve(K, (K(-1/48) * (a^2 + 14*a*d + d^2),K(1/864) * (a + d) * (-a^2 + 34*a*d - d^2)))
def to_weierstrass(a, d, x, y):
	return ((5*a + a*y - 5*d*y - d)/(12 - 12*y), (a + a*y - d*y -d)/(4*x - 4*x*y))
def to_twistededwards(a, d, u, v):
	y = (5*a - 12*u - d)/(-12*u - a + 5*d)
	x = (a + a*y - d*y -d)/(4*v - 4*v*y)
	return (x, y)
G = E(*to_weierstrass(a, d, K(0x216936D3CD6E53FEC0A4E231FDD6DC5C692CC7609525A7B2C9562D608F25D51A), K(0x6666666666666666666666666666666666666666666666666666666666666658)))
E.set_order(0x1000000000000000000000000000000014def9dea2f79cd65812631a5cf5d3ed * 0x08)
# This curve is a Weierstrass curve (SAGE does not support TwistedEdwards curves) birationally equivalent to the intended curve.
# You can use the to_weierstrass and to_twistededwards functions to convert the points.

#Eを計算する

sage: E.cardinality().factor()
2^3 * 7237005577332262213973186563042994240857116359379907606001950938285454250989

cofactor

前出の結果からed25519のcofactorはcurve25519とおなじ2^3となります。

BLS12-381

sage: E = EllipticCurve(GF(0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaab), [0, 4])

sage: print(E)
Elliptic Curve defined by y^2 = x^3 + 4 over Finite Field of size 4002409555221667393417789825735904156556882819939007885332058136124031650490837864442687629129015664037894272559787

#Eを計算する

sage: E.cardinality().factor()
3 * 11^2 * 10177^2 * 859267^2 * 52437899^2 * 52435875175126190479447740508185965837690552500527637822603658699938581184513

cofactor

sage: 3 * 11^2 * 10177^2 * 859267^2 * 52437899^2

cofactor

BLS12-381のEのcofactorは76329603384216526031706109802092473003(= 0x396C8C005555E1568C00AAAB0000AAAB)

Links

https://tex2e.github.io/rfc-translater/html/rfc7748.html
https://en.wikipedia.org/wiki/Curve25519
https://tex2e.github.io/rfc-translater/html/rfc7748.html
https://datatracker.ietf.org/doc/draft-irtf-cfrg-pairing-friendly-curves/08/
https://qiita.com/tnakagawa/items/5c73763e420dc9baddf2
https://eprint.iacr.org/2019/403.pdf
https://hackmd.io/@benjaminion/bls12-381

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0