Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
    
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 at 21:19

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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