2
$\begingroup$

Is it possible to find a secure curve which's base field is the scalar field of secp256k1?

In general, can you find a secure curve defined over the scalar field of any secure curve? (For example, a secure curve defined over the scalar field of ed25519?)

Edit: Using the same parameters as secp256k1 (in short Weierstrass form), $a = 0$ and $b = 7$, yields a curve of prime order in the scalar field $\mathbb{F}_n$ of secp256k1. Its order is the order of the base field of secp256k1 $\mathbb{F}_p$. Not sure if it is secure though. At least it looks like the curve doesn't have any singularities (i.e., the discriminant $4a^3 + 27b^2 \neq 0 \pmod n)$.

Edit: See also this question.

$\endgroup$

2 Answers 2

1
$\begingroup$

If by the scalar field you mean the prime field for the prime which is the largest prime divisor of the group order, then the answer is (we strongly believe) "yes, though the process of finding the curve might not be straightforward.

I general, we can write down many elliptic curves over a prime field. These will be appropriate for cryptography if:-

  • the number of points is sufficiently large
  • the largest prime divisor of the number of points is sufficiently large
  • the curve is not anomalous
  • the curve does not have small embedding degree (so that the MOV attack does not apply) The chances of the last two exceptions are vanishingly small and easy to check if we have counted the number of points on the curve. The number of points on the curve can be computed in polynomial time using the Schoof-Elkies-Atkin method. A naive approach to finding a secure curve for a given prime field is therefore to generate random $a$ and $b$ values; count the points using SEA; test the number of points for primality; if successful check the anomalous and embedding degree criteria; if successful, return the curve.

This will succeed if there exist an elliptic curve where the number of points is prime, which raises the question of the distribution of the number of points on the curve. The Hasse-Weil bound tells us that for a prime $q$ the number of points on an elliptic curve over $\mathbb F_q$ lies in the interval $(q+1-2\sqrt q,q+1+2\sqrt q)$ and we strongly believe that there are about $4\sqrt q/\log q$ primes in this interval. The distribution of point counts is not uniform (it is approximately semi-circular), but heuristically we would still hope to find a suitable curve with $O(\log q)$ random choices of $a$ and $b$.

Note that Koblitz curves have complex multiplication by $\sqrt{-3}$ which makes it easy to use the same curve equation when the number of points on the curve is prime. In the case of secp256k1 the associated curve is secure, being neither anomalous nt of small embedding degree.

$\endgroup$
2
$\begingroup$

Yes. There is a curve called secq256k1. And its order is even the order of the base field of secp256k1. The equation is basically the same as for secp256k1 $$y^2 = x^3 + 7 \pmod{n}$$ but here we use the field $\mathbb{F}_n$, whereas $n$ is the order of secp256k1.

$\endgroup$
3

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.