2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Brock Hansen Apr 16 '14 at 21:19
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.