[Math] Computing the multiplicative inverse for point addition on an elliptic curve

elliptic-curveseuclidean-algorithm

I'm trying to perform point addition on an elliptic for two points taken from an example in the book "Understanding Cryptography by Christof Paar & Jan Pelzl".

The points I'm trying to add are:
$$6P=(16,13)$$
and
$$P=(5,1)$$

on the curve:
$$E:y^2\equiv x^3+2x +2 \mod 17$$

I know from the book that the result should be:
$$7P=(0,6)$$
but I can't figure out how to arrive at that result, however I think my issue is the way I calculate the inverse for s:
$$s=y_{2}-y_{1}\cdot(x_{2}-x_{1})^{-1}\mod p$$
$$s=1-13 \cdot (5 -16)^{-1}=-12 \cdot (-11)^{-1} \mod 17$$

I calculate $(-11)^{-1}\mod 17$ using the Extended Euclidean Algorithm as follows:

\begin{array}{c|c|c}
\hline
i& r_{i-2} & r_{i}=[s_{i}]r_{0}+[t_{i}]r_{1} \\ \hline
2 & 17=-1 \cdot -11 + 6 & r_{2}=17+1 \cdot -11 \\ \hline
3 & -11=-1 \cdot 6 – 5 & r_{3}=-11+1\cdot 6 = -11 + 1\cdot r_{2} = [1] \cdot 17 + [2] \cdot -11\\ \hline
4 & 6 = -1 \cdot -5 + 1 & r_{4}= 6 + 1 \cdot -5 = r_{2} + 1 \cdot r_{3} = [2] \cdot 17 + [3] \cdot -11
\end{array}
I don't get the correct point using my calculated inverse, $3$, i do however get the correct result using the result from Modular inverse calculator which is $-14$, which is why i believe my inverse calculation is incorrect.

Best Answer

By doing the calculations:

$$s=\frac{y_{2}-y_{1}}{x_{2}-x_{1}} \mod p = (y_{2}-y_{1}) \cdot (x_{2}-x_{1})^{-1} \mod p$$ $$s=(1-13) \cdot 3 = -12 \cdot 3 = -36 \equiv 15 \mod 17$$

I could calculate $x_{3}$: $$x_{3}=s^{2} - x_{1} - x_{2} \mod p$$ $$x_{3}=15^{2}-16-5 = 204 \equiv 0 \mod 17$$ and then calculate $y_{3}$: $$y_{3}=s(x_{1}-x_{3})-y_{1} \mod p$$ $$y_{3}=15\cdot(16-0)-13 = 227 \equiv 6 \mod 17$$ and see that I indeed get $7P=(0,6)$ as expected, and that $3$ and $-14$ behave equivalent $\mod 17$.

Related Solutions

[Math] Under what conditions do all the points on an elliptic curve form a cyclic group? (And group cardinality attacks)

Fix an elliptic curve $E/\Bbb F_q$, where $\Bbb F_q$ is the finite field with $q$ elements. Then the set of points $E(\Bbb F_q)$ form a group, and because $\Bbb F_q$ is finite, $\# E(\Bbb F_q) = n$ is finite. Then $$ E(\Bbb F_q)\subseteq E[n](\overline{\Bbb F}_q) $$ ($E[n](\overline{\Bbb F}_q)$ denotes the set of $n$-torsion points of the elliptic curve in an algebraic closure of $\Bbb F_q$). This follows from Lagrange's theorem, as $E(\Bbb F_q)\subseteq E(\overline{\Bbb F}_q)$ is a subgroup. However, the structure of $E[n](\overline{\Bbb F}_q)$ is well known. For simplicity, let us assume that $n$ and $q$ are relatively prime. Then $$ E[n](\overline{\Bbb F}_q)\cong\Bbb Z/n\Bbb Z\times\Bbb Z/n\Bbb Z. $$ Using this, we get the following more precise version of what you stated:

Theorem: Let $E/\Bbb F_q$ be an elliptic curve, and suppose that $\#E(\Bbb F_q) = n$ is relatively prime to $q$. Then $E(\Bbb F_q)$ is either cyclic or isomorphic to the direct product of two cyclic groups.

In fact, one can even remove the hypothesis that $\#E(\Bbb F_q) = n$ is relatively prime to $q$ above. Of course, you wanted to know when this group is in fact cyclic. I don't know a complete classification, but this will at least provide you with some specific cases in which the group is cyclic.

Theorem: Let $E/\Bbb F_q$ be an elliptic curve, with $q = p^r$ for some prime $p$. Then $E(\Bbb F_q)$ is cyclic if one of the following conditions hold:

$\# E(\Bbb F_q) = p^k$ for some integer $k$. (This is because $\# E[p^k](\overline{\Bbb F_q})$ is either trivial or isomorphic to $\Bbb Z/p^k\Bbb Z$, unlike when you look at $n$-torsion for $n$ prime to the characteristic of the field.)

$E/\Bbb F_q$ is supersingular and $q = p\geq 5$ is prime with $q\equiv 1\pmod{4}$. (This is an exercise in Silverman's "The Arithmetic of Elliptic Curves.")

As for the importance of the cardinality, there are certain types of curves which are particularly vulnerable to attack:

Curves over $\Bbb F_{2^m}$ with $m$ composite are vulnerable to Weil descent attacks.
Curves such that $n$ divides $p^{B}-1$ (where $p$ is the characteristic of the field your curve lives over) for sufficiently small $B$ are vulnerable to Menezes–Okamoto–Vanstone (MOV) attack which applies usual Discrete Logarithm Problem (DLP) in a small degree extension field of $\mathbb {F} _{p}$ to solve the ECDLP. The bound $B$ should be chosen so that discrete logarithms in the field $\mathbb {F} _{p^{B}}$ are at least as difficult to compute as discrete logs on the elliptic curve $E(\mathbb {F} _{q})$.
Curves such that $\#E(\mathbb {F} _{q}) = q$ are vulnerable to the attack that maps the points on the curve to the additive group of $\mathbb {F} _{q}$.

As you can see, the last condition is a condition on the cardinality of $E(\Bbb F_q)$ (which in this case would be cyclic as I noted above, so it's both the cardinality of the group of points and the cyclic group in question). In general, one needs to know the cardinality of both $E(\Bbb F_q)$ and the cyclic subgroup you use, so I think you can assume that both cardinalities are important.

(Note: I'm not an expert in elliptic curve cryptography, and I'm stealing this information from the Wiki page on ECC. I suggest reading that page and the relevant sources for more information on this topic.)

[Math] Elliptic Curve Point Doubling

Your calculations are correct. You can verify it on Sage.

Paste the following into this page and click "Evaluate" to see the result.

E = EllipticCurve(Integers(7919), [1, 1])
P = E([0, 1])

print(E)
print(P)

4*P

Best Answer

Related Solutions

[Math] Under what conditions do all the points on an elliptic curve form a cyclic group? (And group cardinality attacks)

[Math] Elliptic Curve Point Doubling

Related Question