# How to handle the GCD(V,P) != 1 case when doing point addition or point doubling in elliptic curve cryptography

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).

## 1 Answer

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.

• Thank you for your answer. That library confused me a little bit with this GCD stuff but now everything is clear to me. – Jan Moritz May 28 '14 at 16:34