1
$\begingroup$

I have some basic cryptography question but I don't know if my calculations are not overcomplicated and if there's some simpler solution. Following algorithm is explained here.

Problem

There are two elliptic curves in $F_5$ with equations:

a) $y^2 = x^3 + 2x + 1 \pmod{5}$

b) $y^2 = x^3 + x + 1 \pmod{5}$

Find points that are in these two eliptic curves.

My approach is to determine points on these eliptic curves separately and then check for duplicates.

Determining quadratic residue in $\mod{5}$

For every value in $\mod{5}$ calculate square for it, so

$ (\pm 1)^2 \pmod{5} = 1 \\ (\pm 2)^2 \pmod{5} = 4 \\ (\pm 3)^2 \pmod{5} = 9 \pmod{5} = 4 \\ (\pm 4)^2 \pmod{5} = 16 \pmod{5} = 1 \\ $

So our quadratic residue set is $QR = \{1, 4 \}$

Determining points in a)

Equation is: $ y^2 = x^3 + 2x + 1 \pmod{5} $

Let's build table:

table a

  1. In column $x$ we have all possible $x$.
  2. In second column we calculate curve equation.
  3. In third column we check if value is quadratic residue. So we check if its in $QR$. There is also option to check this with Euler theorem. For $y=3$ we check if $y^{(p-1)/2} \equiv 1 \pmod{p}$ so $3^2 \equiv 1 \pmod{5}$ is false because $3^2 \pmod{5} = 4$.
  4. For all quadratic residues we calculate square roots. We can get them from step where we determined quadratic residues. For example we have $1$ for $1^2$ and $4^2$. So $1$ and $4$ are square roots of $1$.

So points on this elliptic curve are:

$(0, 1)$, $(0, 4)$, $(1, 2)$, $(1, 3)$, $(3, 2)$, $(3, 3)$

Determining points in b)

Equation is: $ y^2 = x^3 + x + 1 \pmod{5} $

Let's build table:

enter image description here

So points on this eliptic curve are:

$(0, 1)$, $(0, 4)$, $(2, 1)$, $(2, 4)$, $(3, 1)$, $(3, 4)$, $(4, 2)$, $(4, 3)$.

Result

Points $(0, 1)$ and $(0, 4)$ are on these two functions.

Checking if correct

I've found website that generate points for given EC. Solution that I've found is correct. Is there faster way to found these points?

EC a)

enter image description here

EC b)

enter image description here

$\endgroup$
0

1 Answer 1

2
$\begingroup$

Since you are working on the same field for both the curves. To get the common points $(x_0,y_0)$ that lie on both the curves, you just need to to equate the following (think in terms of intersection of two curves) \begin{align*} y_0^2 =x_0^3+2x_0+1 &\equiv x_0^3+x_0+1 \pmod{5}\\ x_0 & \equiv 0 \pmod{5}. \end{align*} Thus $x_0=0$. Now this gives us that $y_0^2 \equiv 1 \pmod{5}$, which has only two solutions, namely $y_0=1,4$. Thus the common points are $(0,1)$ and $(0,4)$ and $\color{blue}{\text{the point at infinity } \mathcal{O}}$.

Note: If the task was to find the points on each curve separately, then what you did would be a good approach.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .