# ECDSA Public Key generation

Referring to both

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?

-
Note that $\mathbb{F}_{2^m}$ is a field, not a group. It has two operations, addition and multiplication. The points on the elliptic curve are pairs of elements of that field. The points form a group, which has just one operation. The operation could be denoted as either addition or multiplication, but by convention we use additive notation because the operation is commutative. Multiplying a positive integer by an elliptic curve point means to add the point to itself that many times. – Brock Hansen Apr 16 '14 at 21:19

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.

-