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 have a hard time learning exactly how the elliptic curve equation is used in the ECC.

$$y^2 = x^3+ax+b$$

If someone knows and could explain to me in simple steps how this is done or a link to it that would just be amazing. I know how point addition is done, so I know the mathematical side to it.

This is a high school project so it does not have to be very specific, just like a general idea.

share|improve this question
3  
You want info on Elliptic Curve Cryptography (not cryptology); let me Google that for you. –  fgrieu Mar 29 at 21:27
    
A (relatively easy to understand) primer on elliptic curve cryptography arstechnica.com/security/2013/10/… –  ddddavidee Mar 29 at 22:57

1 Answer 1

up vote 3 down vote accepted

In fact the equation is not used directly.

If you work in the field of integers modulo $p$, both the $x$ and $y$ coordinates are integers in the $0$ to $p-1$ range, so there are $p^2$ possible points. The equation tells you which points are part of the curve (the $(x,y)$ such that $y^2 = x^3 + ax + b$) and which points are not. In that sense, the equation defines the playground. The size of the curve (number of points which match the equation) is close to $p$, so the vast majority of possible points are not part of the curve.

However, if you just want to use the curve for adding points together, then the usual formulas (as seen e.g. here) do not use the curve equation: the $a$ parameter appears only in the formula for doubling, the $b$ parameter does not show up at all. The curve equation is used implicitly by virtue of the input points being part of the curve, i.e. fulfilling the equation.


So, in practice, the curve equation is used to verify that the input points are valid, i.e. part of the curve. When doing elliptic-curve Diffie-Hellman, each party sends to the other a curve point, as two coordinates $x$ and $y$. When receiving such values, you must first check that they define a point which is indeed a curve point, i.e. you compute both $y^2$ and $x^3 + ax + b$ to see if they match. If they don't, then the input points are not on the curve (or, rather, not on the curve you believe them to be), and bad things may occur.

As an optimization, the systems who do ECDH may send to each other only the $x$ coordinates. Indeed, when you receive $x$, you can compute $x^3 + ax + b$, which is equal to $y^2$. By computing the two (at most) square roots of that value, you recover $y$ and $-y$. In other words, from $x$ alone, you can use the curve equation to work out the (at most) two curve points which have that $x$ value. This is sufficient to do the ECDH. This is an optimization because it allows the two systems to send less bytes over the wire. This is called point compression and it directly uses the curve equation.

share|improve this answer
    
Thomas Pornin's related answer might also be of interest. –  fgrieu Mar 31 at 6:44

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.