secp256k1 prime modulus vs order

Question

For curve secp256k1 prime modulus is $2^{256}-2^{32}-977$ and order is smaller number but has near half of starting bits set. If I draw number to be private key, it must be less than order. All field operations are modulo prime modulus and it means they must be smaller than modulus but can be >= order? (or not?). Coordinates of public key point can exceeds order? A very interesting case is in signing and verifying: in pseudocode: from nayuki library is modulo order.

 * if (nonce outside range [1, order-1]) return false
 * p = nonce * G
 * r = p.x % order
 * if (r == 0) return false
 * s = nonce^-1 * (msgHash + r * privateKey) % order
 * if (s == 0) return false
 * s = min(s, order - s)

This means, operations are done, first modulo modulus p, next modulo order?

Answer 1

Yes, field operations may involve numbers that are larger than the order. Public key point coordinates may exceed the order.

Parts of the protocol that handle scalars work modulo the curve order, while the parts that handle elliptic curve points work modulo the prime modulus.

Sometimes, as you noted, some information "crosses" between these domains: the main case being inside the ECDSA protocol, in the r value which is obtained from a X coordinate and reduced modulo the order to enter in the computation of s.

Answer 2

All field operations are modulo prime modulus and it means they must be smaller than modulus but can be $\ge$ order?

Yes, in theory that could happen, but it is rare. All quantities manipulated in the field usually are about uniformly random in $[0,p)$ when reduced modulo $p$. Therefore they seldom exceed $n$. The probability is about $1-n/p\approx2^{-127.65}$. That is, in practice never.

I do not see how that could be triggered on purpose in unmodified key generator or signature code, even in light of the special form of the base point. But that's easily added to point addition/multiplication test code, if desired. It can be exercised to some degree for signature verification code, albeit with a public key with no known matching private key or valid signature.

This means, operations are done, first modulo modulus $p$, next modulo order?

Yes. Arithmetic on point coordinates is modulo $p$, the field order. Arithmetic on multiplier, random number, and signature components is modulo $n$, the Elliptic Curve group order. The one exception is when the X coordinate in $[0,p)$ gets reduced modulo $n$. Here there is room for a coding error if the coordinate is in $[n,p)$. The lower bound $n$ is excluded by the definition of ECDSA, but $(n,p)$ is valid.

Answer 3

Elliptic curves confuse many in the beginning because of its construction. The elliptic curve can be defined in any field, however, in cryptography, we are interested in curves over finite fields. This can be a prime field $\Bbb F_p$, or an extension field $\Bbb F_q$, where $q=p^m$ for some positive integer $m$. The prime can be 2 that we called a binary field and it has a binary extension field. The binary extension field is no longer secure in Cryptography.

Take a finite field, $K$, and define the Weierstrass equation

$$Y^2 + a_1 XY + a_3 Y = X^3 + a_2 X^2 + a_4 X + a_6 \ne0$$

We want the discriminant non-zero;

$$\Delta = -b_2^2 b_8 - 8b_4^3 - 27b_4^2 + 9b_2 b_4 b_6$$ so that we don't have singular curves. If the field $K$ has characteristics other than $2$ or $3$ then we can make the curve a short version of the Weierstrass equation.

$$y^2 = x^3 + ax + b.$$

With the discriminant $4a^3+27b^2\ne0$

To form an elliptic curve, we select a field $\Bbb F_q$and an equation, in the short version we select the $a$ and $b$ as in Secp256k1.

Any pair $(x,y)$ with $x,y \in K$ is called the rational points of the curve if $(x,y)$ satisfies the curve equation.

Addition Laws

With the point addition law, the points form an additive group. The formulas for affine coordinates are;

Let $P=(x_1,x_2)$ and $Q=(x_2,y_2)$ be two point in the elliptic curve.

1. $P+O=O+P=P$
2. If $x_1 = x_2 $ and $y_1 = - y_2$ and $Q =(x_2,y_2)=(x_1,−y_1)=−P$ then $P + (-P) = O$
3. If $Q \neq -P$ then the addition $P+Q = (x_3,y_3)$ and the coordinate can be calculated by;

\begin{align} x_3 = & \lambda^2 -x_1 - x_2 \mod p\\ y_3 = & \lambda(x_1-x_3) -y_1 \mod p \end{align}

$$ \lambda = \begin{cases} \frac{y_2-y_1}{x_2-x_1}, & \text{if $P \neq Q$} \\[2ex] \frac{3 x_1^2+a}{2y_1}, & \text{if $P = Q$} \\[2ex] \end{cases}$$

Now the common confusion is the fact that we have two groups, the first one is actually a field. The point's coordinates are defined on the field, however, they form a group and this group has special addition law that contains reduction to modulo $q$

If I draw number to be private key, it must be less than order. All field operations are modulo prime modulus and it means they must be smaller than modulus but can be >= order? (or not?). Coordinates of public key point can exceeds order?

In the end, all operations are performed according to the modulus of the finite field. One can make them larger during the calculations, however, making them larger has no point. Remember $(x,y) = (x \bmod p, y \bmod p)$

This means, operations are done, first modulo modulus p, next modulo order?

The modulo to order is helpful in the case of scalar multiplication. The addition laws already have its modulus (see above)

$$[a]G = \overbrace{G+\cdots+G}^{{k\hbox{ - }times}}$$ if $a$ is larger than the order of $G$ then first take mod

$$[a]G = [a \bmod ord(G) ]G = \overbrace{G+\cdots+G}^{{a \bmod ord(G)\hbox{ - }times}}$$