6
$\begingroup$

In ECC, specifically over finite fields, in my mind there must be other points that exist that still yield $y^2 \bmod p=x^3 + ax + b \bmod p$ to be true but are never used because the Generator Point (or base point) never "lands" on that point before reaching the order and effectively starting over. How can we calculate if a point is actually part of the order (not sure if thats the correct term) and not just a point that satisfies the equation?

$\endgroup$
7
$\begingroup$

in my mind there must be other points that exist that still yield $y^2 \bmod p=x^3 + ax + b \bmod p$ to be true but are never used

Actually, that's not true if the order of the curve is prime; examples of such curves are P256 and Sec256k1. In those curves, every single point can be expressed as $xG$ for some integer $x$.

Now, this is (usually) not true for curves with a cofactor > 1; in those curves, we generally work in a prime-sized subgroup; there will be points that are 'missed'. To determine whether a point $H$ we've been handed is such a point, one way (which works with the curves we use in cryptography) would be to compute $qH$ (where $q$ is the size of the prime subgroup) - if that is not the neutral element, then $H$ cannot be generated by the generator.

Obviously, this is not a cheap check; what we usually do when working with a cofactor > 1 curve is to arrange things so that things don't break if we're handed a non-subgroup point.

$\endgroup$
2
  • $\begingroup$ Why "(usually) not true"? It's never true if the cofactor is > 1, surely? $\endgroup$
    – TonyK
    Aug 4 at 10:39
  • $\begingroup$ @TonyK: well, if we picked a generator of the entire group, rather than a prime sized subgroup (and there is such a generator), then this would be true. Now, we generally don't much such selections; however it's possible... $\endgroup$
    – poncho
    Aug 4 at 13:12

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.