Quote from: graphite on January 10, 2025, 01:04:18 AM

I haven't been able to find any resource that explains how the order of Spec256k1 is found or for any other elliptic curve cryptography functions. The only hint Ive read is that the order (n) is usually somewhere near the prime field (p)

p = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F
n = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141

the order and price field are around 2^128 away from each other. This means if you were to brute force search for n using the p as a starting point it would take 2^64 iterations to hit n. Did they brute force n or is there a simpler solution to this?

The order nn of the elliptic curve SECP256k1 is not brute-forced but is determined mathematically during the curve's design. Here’s a detailed explanation of how the order is calculated:
What is the Order of an Elliptic Curve?

The order nn of the curve is the number of points PP (including the point at infinity) that exist on the elliptic curve over the finite field FpFp.
It is a fundamental property and must satisfy certain cryptographic criteria for the curve to be secure.

How is the Order Calculated?

Hasse's Theorem:
Hasse's theorem provides a range for the number of points on the curve: For SECP256k1:
p=2256−232−977
p=2256−232−977 This bounds the number of points to a range close to p+1p+1.

Cofactor (hh):
The total number of points on the curve (NN) is the product of the curve's order (nn) and its cofactor (hh):
N=h⋅n
N=h⋅n
SECP256k1 has a cofactor h=1h=1, meaning the total number of points NN is equal to nn.

Determining nn:
A point-counting algorithm (e.g., Schoof's algorithm) is used to calculate NN, the total number of points on the curve.
For SECP256k1, the calculated NN is:
n=0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
n=0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141

Security Criteria:
nn is chosen to be a large prime number close to pp, ensuring the group of points forms a cyclic group of prime order.
This choice minimizes the risk of small subgroup attacks and ensures robust cryptographic properties.

Why is nn Close to pp?

Efficient Field Arithmetic:
Keeping nn near pp simplifies arithmetic operations on the curve, as both pp and nn have similar bit lengths.

Avoiding Weaknesses:
The prime order nn ensures the curve’s group structure avoids vulnerabilities like small subgroup attacks or factorization-based attacks.

Did They Brute Force nn?

No. nn is derived using mathematical algorithms like Schoof's algorithm or its optimizations (Schoof–Elkies–Atkin). These methods efficiently calculate the number of points on an elliptic curve modulo pp without brute-forcing.