Elliptic Curves

Find another type of group and operation in which the DLP is hard

$ax^2+by^2=r^2$

• By curves here, really mean the set of points that are solutions to the equations
• Elements on these curves are real numbers
• Consider the points in Zp

For DLP problem, need a cyclic group

• Elements within the group
• A group operation For ECs the elements are points on the curve The operation is point addition

Point Addition

$P+Q=R$

• Any line through two points intersects a third point
• Reflect this point about the x-axis

Point Doubling

$P+P=2P$

• The tangent at a point will intersect another point on the curve
• Reflect this point about the x-axis

Group Laws

$2P+P=3P$ $3P+P=4P$ $2P+2P=4P$

Point Addition Equations

• Can derive equations for this based on the equation for a line that intersects the curve in three places

...???

The Point at Infinity

• The point at infinity is the neutral element on an elliptic curve
• In practice the point doesn't have coordinates, and cant be used within the normal formula.
• When implementing have to detect when the x values are equal and y values are inverses mod p

Cyclic Groups

• Points on an elliptic curve including the neutral element O form cyclic subgroups
• Under certain conditions all points form a cyclic group