7
$\begingroup$

I'm having a hard time understanding the elliptic curve encryption. One thing thing I don't understand is listing all the points on the curve mod p. Suppose I have the following elliptic curve: $y^2 = x^3 + 2x + 3 \pmod 5$. To find the list of all the points you run through $0 < x \leq 4$ and solve for $y$.

I know the output is the following:

x = 0 => $y^2 = 3$ => no solution mod 5
x = 1 => $y^2 = 6$ = 1 => y = 1,4 mod 5
x = 2 => $y^2 = 15$ = 0 => y = 0 mod 5
x = 3 => $y^2 = 36$ = 1 => y = 1,4 mod 5
x = 4 => $y^2 = 75$ = 0 => y = 0 mod 5

So the points are: (1,1) (1,4) (2,0) (3,1) (3,4) (4,0) and the point at infinity. But I have no idea what is happening here, for example at x=1 solving $y^2$ becomes 6 (mod 5) is one. But why does it say y = 1 and 4 for x=1?

I'm also having trouble understanding point doubling, I'm using the following algorithm:

  1. compute $m$:

    $$m \equiv (3x_1^2)(2y_1) -1 \pmod p$$

  2. for the new x and y:

    $$x_3 = m^2 - x_1 - x_2 \pmod p$$
    $$y_3 = m(x_1 - x_3) - y_1 \pmod p$$

Though this doesn't seem to work. Can someone give me an example of point doubling for e.g. the following equation $y^2 = x^3 + 2x + 1 \pmod 5$ with point P(1, 3) and compute 2P?

$\endgroup$
4
  • 2
    $\begingroup$ You do not have enough familiarity with modular arithmetic to tackle Elliptic Curves (much less Elliptic Curve Encryption or other forms of Elliptic Curve Cryptography), if you do not understand that $y=4$ is a solution to $1\equiv y^2\pmod 5$. Hint: apply the definition of $a\equiv b\pmod c$, which is that $c$ divides $b-a$. $\endgroup$
    – fgrieu
    Oct 1, 2013 at 6:52
  • $\begingroup$ Thank you, well I do have a basic understanding of modular arithmetic, but you are right, allthough I was mostly confused by the notation, I do have a better understanding now of what is happening. I see now that 1 and 4 are solutions to 1 = y^2 (mod 5). $\endgroup$
    – SilverTear
    Nov 6, 2013 at 22:56
  • 1
    $\begingroup$ $1=y^2\pmod 5$ IS a confusion in notation. Use either $1\equiv y^2\pmod 5$ or $1=y^2\bmod 5$, the former meaning that $y^2-1$ is a multiple of $5$, the later that the remainder of the division of $y^2$ by $5$ is $1$. Notice that $6\equiv y^2\pmod 5$ is true, but $6=y^2\bmod 5$ is false. $\endgroup$
    – fgrieu
    Nov 7, 2013 at 10:32
  • 3
    $\begingroup$ I'm voting to close this question as off-topic because this was about a simple misunderstanding about modular arithmetic. $\endgroup$
    – Maarten Bodewes
    Jul 31, 2015 at 12:53

2 Answers 2

4
$\begingroup$

Note: For $y^2 \equiv x^3 + ax + b$, you want $$m\equiv(3x^2+a)*(2y)^{-1}$$ which is a shortcut that only makes sense once you understand how elliptic curves work.

"Why does it say y=1 and 4 for x=1?"

Like you said, plug in & solve: $$y^2 \equiv 1^3 + 2(1) + 3 \equiv 6 \equiv 1\space(mod\space5)$$

Ask yourself "Is there a square such that it is $\equiv 1 \space(mod\space 5)$?"

$$1^2\equiv1 \space \space and\space\space 4^2\equiv16\equiv1\space (mod \space5).$$

This means (1,1) and (1,4) are points on the discrete version (mod 5) of the curve.

If we weren't working (mod 5), plugging in 1 would give us (1,2) and (1,-2), which are points on the continuous version of the elliptic curve.

Below on the left is the continuous version of an arbitrary elliptic curve; on the right is what happens when you start working mod a number. enter image description here

Example: Find 2P on the curve $E: y^2 \equiv x^3 + 2x + 3 \space(mod\space5)$ where P = (1,3)

2P = (1,3) + (1,3). When adding two points on an elliptic curve, there are two cases:

Case 1: The points are not the same: Find the line that includes both of the points on the curve. This line will have a third point on the curve. Find that point and reflect about the x-axis to have the final point.

Case 2: The points are the same: Find the line tangent to our point on the curve. This line will intersect the curve at one more point. Find that point and reflect about the x-axis to have the final point.

Now what is the line tangent to (1,3) on E?

Use implicit differentiation (simple calculus):

$$dy/dx = (3x^2 + 2)/(2y)$$.

Now at our point (1,3): $$dy/dx = 5/6 = 5*6^{-1} (mod \space5)$$

It is easy to see (and find) that $6^{-1} \equiv 1 \space(mod\space 5)$

So m = 5 is the slope for our line tangent to (1,3): $$L: y-3 = 5(x - 1)$$

So $$y = 5x - 2.$$

Now where else do E and L intersect?

We have

  • $E: y^2 \equiv x^3 + 2x + 3 \space(mod\space5)$

  • $L: y = 5x - 2$

Plug L into E: $$(5x-2)^2 \equiv x^3 + 2x + 3$$

Expand: $$25x^2 - 20x + 4 \equiv x^3 + 2x + 3$$

There is a useful algebraic property for cubic polynomials that is fun and not hard to prove: The summation of the polynomial's roots equal the negative of the $x^2$ term's coefficient. That is,

$$\sum roots = -(coeff.\space of\space x^2\space term)$$

So in rearranging the polynomial further, we care only about the $x^2$ terms:

$$0 \equiv x^3 - 25x^2 ...$$

We already added (1,3) to itself, so it must be that 1 is a root of multiplicity 2.

$$1 + 1 + r_3 = -(-25) = 25$$ implies the last root is 23. Recall we are working (mod 5) though, so our last root is 23 $\equiv 3$

Now plug $r_3$ into our linear equation: $$y = 5(3) - 2 = 13 \equiv 3\space(mod\space5)$$

Reflect

Lastly, reflect our point (3,3) about the x-axis to get (3,-3). Recall again we're working (mod 5), so add the modulus to -3 until is it in the range $[0,4]$.

$\therefore$ 2P = (3,2)

$\endgroup$
2
$\begingroup$

"Elliptic curve encryption" is somewhat popular wording; one better be specific like ElGamal encryption with a group of points on elliptic curve. So, start with ElGamal to understand what kind of group is expected. Try ElGamal with multiplicative group modulo a (large) prime. At last, consider objects named points on a curve as an unusual set with highly counter-intuitive operation named "point addition" that makes them a group.

In particular, (1,1) and (1,4) are just different points (elements of the group).

For a large group, listing all points is impractical, still "counting" makes sense.

$\endgroup$

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