Does the order n of G refer to the public key?

Question

A thought came across my mind. The order $n$ of the secp256k1 in the elliptic curve refers to and states that the private key is to be smaller than the order ($n$) of the curve when it comes to number length if not so considered invalid. Does it also refer to the public key size/length?

$n = \texttt{FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141}$

Answer 1

secp256k1

According to Recommended Elliptic Curve Domain Parameters, secp256k1 is a Koblitz curve and secp256k1 is defined as $T = (p, a, b, G, n, h)$

• $p$ defines the finite field $\mathbb{F}_p$,

  $p=2^{256} − 2^{32} − 2^{9} − 2^8 − 2^7 − 2^6 − 2^4 − 1$ or in hex

  FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F

• The curve equation $E: y^2 = x^3 + ax + b$ over $\mathbb{F}_p$ is defined with

• a = 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000

• b = 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000007

• The Base point $G$ in compressed form

  02 79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798

  From the compressed form, it is possible to find the $y$ with Tonelli–Shanks algorithm. With high probability, it will yield 2 values for $y$. To make the distinction one bit or one byte is enough. In this encoding, the leading 02 says select even $y$, 03 says select odd $y$ so that one can fully recover $y$.

  and in uncompressed form 04079BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8

• The order $n$ of $G$, i.e. $[n]G = \mathcal{O}$, where $\mathcal{O}$ is point at infinity, or the identity element in additive elliptic curve group.

  FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141

• with co-factor h is 01

Scalar multiplication

$[k]P$ is the scalar multiplication, that is one adds a point $P$ $k$-times.

\begin{align} [k]:& E \to E\\ &P\mapsto [k]P=\underbrace{P+P+\cdots+P}_{\text{$k$ times}}.\end{align}

When you add an element according to the group law if one of the coordinates exceeds the $p$ take mod $p$.

For the scalar, one can use $\mod n$ if $x>n$

$$[x]G = [x \bmod n]G$$

public-private keys

Given the base point, $G$ one select a random integer $k \in [1..n-1]$, then the public key is $[k]G$ and your secret/private key is $k$.

The correct random selection prevents $k>n$. If $k>n$ than one can either reject or take modulo $n$ as above. Rejection is preferable since one can assume that there is already a problem during the generation for $k$ and this might indicate more problems.

Does it also refers to the public key size/length

If the $k$ size is correct and there is no error/miscalculation in the scalar multiplication the result will be a point in the curve. Also, since we are adding the $G$ itself, it will in the group $\langle G\rangle$ generated by $P$. The $n$ is actually the order of $\langle G\rangle$. Since the cofactor is 1 the order of $G$ is equal to the order of the elliptic curve $\#E(\mathbb{F}_p)$, which is the number of points.

Answer 2

There is the order of the group of points of the total curve, and the order $n$ of the base point $P$ (which is a divisor of the former, but ideally they'd be the same or just a small factor apart) and the secret key is the "exponent/multiple" $k$ such that $k[P]$ is the public key. It makes no sense to have $k > n$ as $k[P] = (k-n)[P]$ when $k > n$ anyway (by definition $n[P]=0$). So the effictive number of public keys we can have is about $n$, one for each multiple $k[P]$ of $[P]$, where $k \in \{1,2,3,4,\ldots, n-1\}$ (but $k=1$ will not be chosen of course; it should be random from this range, so $1$ would be very unlikely, and some extra vetting could take place to eliminate $k=1,n-1$ and some other trivially breakable instances).

The size of the public key will be the size of any encoded point on that curve (depends on the software implementation a.o.). The size of the secret key will be that of an integer of around 256 bits, in this case. So quite large.