SageMathで見るelliptic curvesの諸性質
SageMathで楕円曲線の諸性質を探る
このサイトを参考に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])このように「Coordinates [1, 3, 1]（入力した座標）はかくかくシカジカのサイズの有限体上に定義されていない点です」というエラーが出力されます。
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 115792089237316195423570985008687907853269984665640564039457584007908834671663E(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()
7237005577332262213973186563042994240857116359379907606001950938285454250989E(GF(F_p))の#Eを算出し、素因数分解します。
sage: E.cardinality().factor()
2^3 * 7237005577332262213973186563042994240857116359379907606001950938285454250989cofactor
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.
sage: E.cardinality().factor()
2^3 * 7237005577332262213973186563042994240857116359379907606001950938285454250989cofactor
前出の結果からed25519のcofactorはcurve25519とおなじ2^3となります。
paring friendly curves
BN254 (also called alt_bn_128 or BN128)
BN254 parameter:
u = -0xd201000000010000
k = 12
q = 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaab
r = 0x73eda753299d7d483339d80809a1d80553bda402fffe5bfeffffffff00000001
E: y^2 = x^3 + b
E': y^2 = x^3 + b' (b' = b / m または b' = b * m) で計算します。BN 曲線は、b' = b / m の場合は D タイプと呼ばれ、b' = b * m の場合は M タイプと呼ばれます。埋め込み次数 k は 12 です。
G_1 を次数 r の E(GF(p)) の部分群として、G_2 を E'(GF(p^2)) の部分群として、G_T を乗法群 (GF) の部分群として定義.
E' はE'から E(GF(p^k))へ同型写像がとれるツイストです。
かつてzcashがparingに使用していた曲線。BLS12-381の方が処理が速い。
BN254は位数が大きいので、これが累乗や高速フーリエ変換や他の暗号学的な演算(zk-SNARKやmulti-partyの計算を効率的にするための処理)を遅くしている。
However, the larger group order r impairs the performance of multi-exponentiation, fast fourier transforms and other cryptographic operations that we need to perform efficiently in zk-SNARK schemes and multi-party computations. Additionally, the larger scalar field $${\mathbb F_r}$$ makes keying material unnecessarily large.
sage: E = EllipticCurve(GF(21888242871839275222246405745257275088696311157297823
....: 662689037894645226208583), [0, 3])
sage: print(E)
Elliptic Curve defined by y^2 = x^3 + 3 over Finite Field of size 21888242871839275222246405745257275088696311157297823662689037894645226208583sage: E.cardinality().factor()
21888242871839275222246405745257275088548364400416034343698204186575808495617BN254はcofactor 1。素数位数の曲線。
(座標変換したE'のcofactorは別記事で後述予定。)
Ethereum上でプリコンパイルされた曲線でもあります。
次に紹介するのは、さらに速い曲線として考案されたBLS12-381。
BLS12-381
Parameter
u = -0xd201000000010000
k = 12
q = 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaab
r = 0x73eda753299d7d483339d80809a1d80553bda402fffe5bfeffffffff00000001
E(Fq) := y^2 = x^3 + 4
Fq2 := Fq[i]/(x^2 + 1)
E'(Fq2) := y^2 = x^3 + 4(i + 1)sage: E = EllipticCurve(GF(0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaab), [0, 4])sage: print(E)
Elliptic Curve defined by y^2 = x^3 + 4 over Finite Field of size 4002409555221667393417789825735904156556882819939007885332058136124031650490837864442687629129015664037894272559787sage: E.cardinality().factor()
3 * 11^2 * 10177^2 * 859267^2 * 52437899^2 * 52435875175126190479447740508185965837690552500527637822603658699938581184513sage: 3 * 11^2 * 10177^2 * 859267^2 * 52437899^2cofactor
BLS12-381のEのcofactorは76329603384216526031706109802092473003(= 0x396C8C005555E1568C00AAAB0000AAAB)
(座標変換したE'のcofactorは別記事で後述予定。)
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://hackmd.io/@jpw/bn254#How-to-find-b-from-parameter-x
https://eprint.iacr.org/2010/134.pdf