5
$\begingroup$

I am trying to handle when a parsers goes off the rails and reads an EC public keys wrong (just the X and Y components, I know the curve prior).

Right now I check for the following (false means invalid):

  1. Is the key even on the Curve?
  2. Is the Public Key X component less than the Curve's Base Point X?

I am pretty confident in #1, but not as confident in #2. #2 was just made by never seeing a case that contradicted it.

So my question is, 1) are these two checks correct? 2) are there other checks that can detect bad public keys?

$\endgroup$
1
  • $\begingroup$ Yeah that's not the curve I am using, but still useful. I am currently looking at P256. $\endgroup$
    – Liam Kelly
    Apr 12 at 17:27
9
$\begingroup$

The general rule for curves is given in;

  • 2003 - Validation of Elliptic Curve Public Keys by Adrian Antipa,Daniel Brown, Alfred Menezes, and René StruikScott Vanstone

    They defined a point is valid if

    1. $P \neq \mathcal{O}$
    2. The $x$ and $y$ coordinates of $P$, $x(P),y(P)$ are valid elements of the field.
    3. $P$ satisfies the curve equation - against the twist attack
    4. Check $[n]P = \mathcal{O}$ for prime curves ($h=1$) and check $[h]P \neq \mathcal{O}$ for non-prime curves ($h>1$) where $h$ is the cofactor $h = \#E(k)/n$

if 1,2, and 3 are verified and $h=1$ (i.e. prime curve) then the 4th is already satisfied.

$\endgroup$
2
  • 1
    $\begingroup$ First off, thank you. Ok to dumb these down greatly: 1) Make sure the public key is not an identify/infinity point 2) Make sure the X and Y of the public key are greater than 0 and less than the curve's prime 3) Make sure the point is on the curve I am dealing with h=1 so I did not look into #4. $\endgroup$
    – Liam Kelly
    Apr 13 at 20:31
  • $\begingroup$ @LiamKelly Valid includes 0, the first case eliminated the identity, see here that there are 3 points with $x=0$ with one of them is the identity. $\endgroup$
    – kelalaka
    Apr 13 at 20:49

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.