Score:2

How to find out what the order of the base point of the elliptic curve is?

us flag

I wanted to use https://github.com/AntonKueltz/fastecdsa library and the function parameters for creating curve are:

p,  # (long): The value of p in the curve equation.
a,  # (long): The value of a in the curve equation.
b,  # (long): The value of b in the curve equation.
q,  # (long): The order of the base point of the curve.
gx,  # (long): The x coordinate of the base point of the curve.
gy,  # (long): The y coordinate of the base point of the curve.

The curve I need is this one: https://docs.starkware.co/starkex-docs-v2-deprecated/crypto/stark-curve It gives info about $p, a, b, gx, gy$. But not the $q$

How to infer the $q$ parameter?

Score:2
in flag

Theoretical answer here

Practically, one can use SageMath to find it;

a = 1
b = 3141592653589793238462643383279502884197169399375105820974944592307816406665
p = 2^251 + 17*2^192 +1

E = EllipticCurve(GF(p), [0,0,0,a,b])
print(E)
print(E.abelian_group())

card = E.cardinality()
print("cardinality =",card)
factor(card)

G = E(874739451078007766457464989774322083649278607533249481151382481072868806602,152666792071518830868575557812948353041420400780739481342941381225525861407)
print("Generator order q=", G.order())

This outputs

    Elliptic Curve defined by y^2 = x^3 + x + 3141592653589793238462643383279502884197169399375105820974944592307816406665 over Finite Field of size 3618502788666131213697322783095070105623107215331596699973092056135872020481
Additive abelian group isomorphic to Z/3618502788666131213697322783095070105526743751716087489154079457884512865583 embedded in Abelian group of points on Elliptic Curve defined by y^2 = x^3 + x + 3141592653589793238462643383279502884197169399375105820974944592307816406665 over Finite Field of size 3618502788666131213697322783095070105623107215331596699973092056135872020481
cardinality = 3618502788666131213697322783095070105526743751716087489154079457884512865583
Generator order q= 3618502788666131213697322783095070105526743751716087489154079457884512865583

Since the order of the curve is prime we have a prime curve, every element is a generator, therefore the order of the basepoint is equal to the order of the curve group.

Also, the cofactor $h$ is 1 since the curve order is prime. Cofactor is defined as the number of the $k$ rational points of the curve $h = \#E(k)/n $ divided by the order of the base element $n$

I couldn't find any information about the magic number (nothing-up-in-my-sleeve). The reason for the choice of $G$ is not clear. Although it is psychological, one should provide it.


SageMath uses sea.gp which is a fast implementation of the SEA algorithm. This library is implemented in pari/GP. A good slide about sea.gp is The SEA algorithm in PARI/GP.

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.