ECDSA Public Key generation

Question

Referring to both

• Wikipedia page and
• ECDSA-cert paper

I can understand that, given $\mathcal{E} = \mathcal{E}(a,\,b,\,\mathbb{F}_{2^m})$ as our elliptic curve on $\mathbb{F}_{2^m}$ group

• $G \in \mathcal{E}$ is a generator of the group, i.e. $\exists n: n\times G = O$
• $n$ is the order of point $G$ with respect to the group
• choosen randomly $d_A\in[1,n-1]$ as a private key, $Q_A\triangleq n \times d_A$ is the public one.

Got it, but in the "Key pair validation from Bob" process, I see that $Q_A$ must respect these bounds:

• $Q_A \neq O$ (trivial)
• $Q_A \in \mathcal{E}$ (trivial)
• $Q_A\times n = O$

I can't really understand the last thing. I'm not very acquainted with EC algebra, but comparing $Q_A\times n = O$ with $n\times G = O$ seems the same thing, so I would conclude that $Q_A=G$, which is clearly false.

What am I missing?

Answer 1

Actually you have a bug in your step of key generation, it should be $Q_A=d_A \times G$ and you want to have a point $G$ of large prime order $n$ such that the ECDLP is hard on the group.

The last check ensures that the public key $Q_A$ is a point of order $n$. If this is the case, then $Q_A\times n = (d_A \times G)\times n = d_A\times(n\times G)=d_A\times O=O$.

This check seems simply to rule out the generation of public keys that lie in a small order subgroup (and thus could be easy to break) - which makes no sense if you have a prime order group but can happen if you have an almost prime order group (you have subgroups of order of divisors of the cofactor). Just a mechanisms to check if the key generation did not generate such a key for you (it should not happen in practice that you generate such a keypair), but the implementation may be messy and you can check that with this test.