Cybernetica

Menu

Elliptic Curve Cryptography - Elliptic Curves (Part 2)

Without further ado, let’s continue where we left off in our previous post.

As we know, all basic Pythagorean triples are given in a form (k2 – l2, 2kl, k2 + l2), where k > l > 0, GCD (k, l) = 1, and k and l have different parity. Experimenting with small values for k and l, we get that the pairs (k, l) = (6, 1) and (k, l) = (5, 2) give Pythagorean triples (35, 12, 37) and (21, 20, 29), both sharing the same triangle area 210. Theorem 1 gives the two corresponding rational points (1260, 44100) and (525, 11025) on the curve y2 = x3 – 2102x.

The line with the equation y = 45x – 12600 goes through these points. It turns out that this line also intersects our elliptic curve in a third rational point. By replacing y from the equation of the line to the equation of the elliptic curve, we get

Based on Viéte formulae, we know that the sum of the solutions for the last equation is 2025, so the third solution is

and the respective y-coordinate is

The point (240, -1800) gives negative values for a, b, and c that cannot be the sides of the triangle. But the point (240, 1800), that is symmetrical to the point we just found with respect to the x-axis, also lies on the same elliptic curve with the equation y2 = x3 – 2102x. Using Theorem 1, this point gives a new triangle (15/2, 56, 113/2). You can easily check that this is a right angled tirangle with the area of 210, and that it is not congruent with either of the inital triangles.

The method we just described – a line drawn through two points of an elliptic curve and its third intersection point with the curve reflected with respect to the x-axis – is of fundamental importance in the theory of elliptic curves. This way, we define a binary operation, giving us a third point from the two given points, P and Q, of the curve. This operation is illustrated in figure 1.

Figure 1: Operation on the points of the elliptic curve, using intersection

What if P = Q? In that case, instead of looking at the intersection, we focus on the tangent at the point P, and find the reflection of the second intersection point of the tangent and the curve across the x-axis (see figure 2)1.

Figure 2: Operation on the points of the elliptic curve, using a tangent

The operation is obviously commutative, but, surprisingly, it is also associative. Proving associativity is technical and complex, which is why we won’t cover it here, but an interested reader can find proof, using methods of elementary mathematics in an article by Friedl2. A proof of associativity relying on deeper background can be found in the classical monograph by Lawrence Washington3.

Is there a neutral element with respect to the operation ? It turns out, that by default, there isn’t, but it can be added. Let’s take a point P on the curve, and think where should a point O be placed, so that P O = P? According to the definition of the operation , the line joining the points P and O should intersect P in a point symmetrical to the x-axis, i.e. the line should be vertical. Since the vertical intersection of the elliptic curve does not have a third intersection point with the curve besides P and the point symmetrical with it, a new formal infinity point is defined. It acts as if it was placed infinitely far in the vertical direction. Now it is clear that the role of an opposite element to P, with respect to the operation , is fulfilled by a point symmetrical to it with respect to the x-axis. These concepts are illustrated in figure 3.

Figure 3: The neutral element and opposite elements of the points of the elliptic curve

To sum up, we can say that the following result holds:

Theorem 2 The set of points of an elliptic curve is a commutative group with a neutral element in an infinity point with respect to the operation .

The operation is called adding of the points of the elliptic curve and often marked as just +.

Good job – you made it to the end! You’ve just been introduced to the history of cryptography, cryptography in groups, and elliptic curves. So, it’s about time you get acquainted with the cryptography of elliptic curves in detail, which will be covered in our next post.

Written by Jan Willemson

1 Examining the task of congruent numbers, the intersection with the elliptic curve enabled to form a third triangle, based on the two, already known, triangles with the same rational area. Figure 2 shows that, in order to find a new point/triangle, it is actually enough to know only one triangle. You can, for example, take the (3,4,5)-triangle with the area 6, find a corresponding point using Theorem 1, calculate a tangent drawn from this point to the curve y2 = x3 – 36x, find another intersection point of the tangent and the curve, and calculate side lengths of the new triangle that corresponds to the point found using Theorem 1.
2 Stefan Friedl. An elementary proof of the group law for elliptic curves. Groups Complexity Cryptology, 9(2):117–123, 2017.
3 Lawrence C Washington. Elliptic curves: number theory and cryptography. Chapman and Hall/CRC, 2003.