Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
1  
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$. –  fgrieu Oct 1 '13 at 6:52
    
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). –  SilverTear Nov 6 '13 at 22:56
    
$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. –  fgrieu Nov 7 '13 at 10:32

1 Answer 1

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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