3
$\begingroup$

The equation for a finite field Elliptic Curve is of this form:

$$y^2 \equiv x^3 + a * x + b \pmod{P}$$

When we do common EC operations like point doubling or point addition we need to calculate the inverse of a number.

For example this is the formula to calculate the slope for the point addition.

$$(Y_1 - Y_2) * ( X_1 - X_2 )^{-1}$$

Now here is the thing. If the $\mathop{GCD}(X_1 - X_2 , P) \neq 1$ , then there is no solution for the inverse (Basic finite field math rule).

First I thought that this could never happen because P was a primary number, but then I discovered that in the cryptography libraries the GCD was tested and if it was not equal to 1 the resulting point would be a virtual point : the point at infinity.

So here Are my questions : Is $P$ a primary number for all the standard Curves Nist,Secp... and by the way if I just want to use this standard curves do I need to test the GCD?

Secondly, if P is not a primary number and if I decide to use this point at infinity "Technic" and I encounter a $\mathop{GCD} \neq 1$, will the public key resulting be a weaker one? (Knowing that the point at infinity has some tricky properties).

$\endgroup$
0

1 Answer 1

2
$\begingroup$

First of all, I would like to note that the statements you make up front are not universally true -- sometimes we use Elliptic Curves with different equations, and with a bit of cleverness, we can do a long series of point additions/doubles and compute a single multiplicative inverse at the end. These cavaets don't really change the answers; they do indicate that what you're learning right now isn't everything there are to elliptic curves.

However, you have to start learning somewhere, and where you are isn't a bad place to start.

Now, to address your questions:

Is $P$ a primary number for all the standard Curves Nist,Secp...

The answer is effectively "yes". Now, here is why I say "effectively": there are some curves, called "even characteristic", where the number of values $x$ and $y$ can take on is $2^k$, for some integer $k$; however the multiplication operation is not "modulo $2^k$", and what I say below about inverses is still true.

If the $GCD(X_1 - X_2, P) \neq 1$ then there is no solution for the inverse. Can this actually happen?

Yes, it can, even though $P$ is prime. $(X_1-X_2)^{-1}$ will always exist, no matter what $X_1-X_2$ is...., unless it happens to be 0. That is, if $X_1-X_2=0$, or equivalently, if $X_1 = X_2$, then that inverse won't exist.

Can this happen in practice? Well, yes, there are two different ways this can happen:

  • $Y_1 = Y_2$ as well; in that case, you're adding a point to itself. In other words, you're doing a point doubling; with the standard Weierstrauss elliptic curve equations, there's a distinct algorithm to do that.

  • $Y_1 = -Y_2$; in that case, you're adding a point to its additive inverse; in that case, the result really will be "the point at infinity".

I just want to use this standard curves do I need to test the GCD?

Well, you need to compare $X_1$ and $X_2$ to see if you fall into either of the above conditions. If $X_1 \neq X_2$, then you'll always have $GCD = 1$.

And, if you're asking why the library you're looking at explicitly tests the GCD, well, I have no idea -- I didn't write that library. However, one possibility is that they are using the Extended Euclidean Algorithm to compute the inverse -- that algorithm does the same logic that's used to compute the GCD (and keeping track of some extra information that is used to compute the inverse).

Finally,

I decide to use this point at infinity and I encounter a GCD≠1, will the public key resulting be a weaker one?

Depends; if you're doing a long chain of point additions/doubles, and an intermediate point happens to be the point-at-infinity, that's not actually a problem -- that point works algebraically like any other point.

However, if the final point (that is, your "public key") is the point-at-infinity, well, that would be bad.

$\endgroup$
1
  • $\begingroup$ Thank you for your answer. That library confused me a little bit with this GCD stuff but now everything is clear to me. $\endgroup$
    – Jan Moritz
    May 28, 2014 at 16:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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