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 (mod 5). To find the list of all the points you run through 0 < x <= 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 = (3x_1^2)(2y_1) -1mod p

  2. for the new x and y:

    x_3 = m^2 - x_1 - x_2 mod p
    y_3 = m(x_1 - x_3) - y_1 mod 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 (mod 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
add comment

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.