# Is the STARK Curve a SafeCurve?

SafeCurves defines criterias for choosing safe curves in elliptic-curve cryptography.

STARK Curve defines a Stark-friendly elliptic curve that can be used with ECDSA.

I was wondering: Is the STARK Curve a SafeCurve?

• Not clear that why that $G$ is selected, nothing-up-in-my-sleeve number? Commented Jan 14, 2022 at 23:17
• Not sure I get what you mean (I'm not an EC expert) - do you mean the specific Generator point used in the ECDSA scheme the STARK Curve web site defines might be specifically selected by Starkware (the authors) so that a hidden/covert backdoor opens in the curve? Commented Jan 14, 2022 at 23:23
• Yes, that's it. Commented Jan 14, 2022 at 23:24
• ok, thanks! makes sense, and this is definitely a question I am going to dig down. it is also a question - not the one I asked, but a very good one obviously;) even if the general curve form is safe (if that is possible to say), the specific parameters might not result in a safe concrete curve .. Commented Jan 14, 2022 at 23:28
• @kelalaka: "What I want to say, the may implemented a massive dlog index and way before anybody"; this is true independent of how they selected $G$; hence having a non-NUMS value doesn't make it any more likely... Commented Jan 15, 2022 at 19:26

The conclusion

The STARK Curve seems a reasonable choice for ECDSA.

The STARK Curve

The STARK Curve defined over $$\mathbb{F}_p$$ with $$p = 2^{251} + 17*2^{192} +1$$ with the short Weierstrass equation

$$y^2 = x^3 + A x + B$$

with

• $$A = 1$$, and
• $$B = 3141592653589793238462643383279502884197169399375105820974944592307816406665$$
Details from the given parameters
• The order of the curve group ( numbner of points) is $$n = \#E(\mathbf{F}_p )$$ is $$n= 3618502788666131213697322783095070105526743751716087489154079457884512865583$$

And this is a prime number indication that

• Every element except the identity ( $$\mathcal{O})$$ can be a generator. The nothing-in-my-sleeve number of this curve (thanks to Aria for pointing), comes from the $$\pi$$.

So Starks has Somewhat rigidness at least for now.

In the end, the nothing-in-my-sleeve number is rather physiological.

• Co-factor is $$h=1$$ this means that there is no Montgomery representation of the curve, as a result, there is no fast Montgomery ladder (requires an element of order 2, i.e. 2|co-factor), Joyce ladder is still possible with slower performance. In ECDSA this is helpful in the calculation of $$[k]G$$ since only $$x$$ coordinate is used.

• There is no small group attack to consider, though this is not a problem for legitimate users of ECDSA. If the users are not legitimate then they can use this to double-spend coins as did in Curv25519 however this is not the case for the STARK curve.

• The curve group is isomorphic to $$\mathbb{Z_n}$$

• The $$n$$ has 252-bit binary representation and this implies it has around $$126$$-bit security against the best classical discrete logarithm problems.

• The size of the curve gives no collision of $$k$$ if a good random number generator is used. If one still fears this one can use deterministic ECDSA given in rfc-6979.

• Twist security ( not related to ECDSA); the quadratic twist of this curve is $$y^2 = x^3 + 5^2*x +B*5^3$$ *

• The cardinality of the twist = "618502788666131213697322783095070105623107215331596699973092056135872020481"
• The factors of the twist group = "499669 * 26023817775804638430931 * 278275836047110893120702478691334736277272165979" and this gives around 158 bit security. Moderate level.
• And, we have $$2*p+2 = Ord(E) + Ord(\text{E_quaratic_twist})$$

• $$n \neq p$$ therefore it is not an anomalous curve where the discrete log can be solved quickly.

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

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

print(E)
print(Et)

print("E abelian =", E.abelian_group())
print("E twist a = ", Et.abelian_group())

card = E.cardinality()
cardEt = Et.cardinality()

print("cardinality E       =",card)
print("cardinality E twist =",card)

print("factors E   ",factor(card))
print("factors Et ",factor(cardEt))

#Generator part not for the quadratic twist.
#G = E(874739451078007766457464989774322083649278607533249481151382481072868806602,152666792071518830868575557812948353041420400780739481342941381225525861407)
#n = G.order()
#print("Generator order =", n)

print(log(card,2).n()+1)

assert(2*p+2 == card + cardEt)


*The quadratic twist formed with QNR 5, unfortunately, it did not work as intended. Thanks to Poncho to point out this. I keep the equation so that one can see the problem. Instead, I've used quadratic_twist function of SageMath that quite slow.

• Fantastic=) Thanks so much for your deep dive analysis of some cryptographic properties of the STARK curve. Not that I really understand the details;) But I guess it checks (some of) the 11 flags for SafeCurves as in the overview table there. Anyways, I tried to dig down choice of G, asked a guy from Starkware: "For the choice of generator, I don’t remember. ... For question you can ask Daira Hopwood from ZCash": electriccoin.co/blog/… github.com/daira Commented Jan 15, 2022 at 12:02
• 3 from the list is just parameters, the base point is about rigidness, not all related to security. Ladder asks about Montgomery for a constant time, however, Joyce ladder handles this. I'll look for the base point, thanks for pointing. Commented Jan 15, 2022 at 12:08
• @oberstet It cannot be BN curve since $p \equiv 1 \bmod 4$, the BN curves requires that $p \equiv 3 \bmod 4$ Commented Jan 15, 2022 at 16:41
• Re "nothing up my sleeve", the generator is the second point in this array, which is generated from the digits of $\pi$. Commented Jan 15, 2022 at 18:27
• @kelalaka $d=5$ didn't work because 5 is a quadratic residue modulo $p$ (easy to check $p \equiv 1 \pmod 5$). You could take $d=3$ instead, which is a non-residue since $p \equiv 5 \pmod {12}$. Commented Mar 3, 2022 at 11:20