Score:6

How to determine if a point is just a point or a valid public key?

cn flag

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?

Score:7
my flag

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.

TonyK avatar
us flag
Why "(usually) not true"? It's never true if the cofactor is > 1, surely?
poncho avatar
my flag
@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...
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.