top of page
All
Articles

Adding and Doubling Points in a Finite field

The operations of adding and doubling points on elliptic curves defined over finite fields form the cornerstone of elliptic curve cryptography (ECC), a key area of modern cryptographic systems. These operations are not only mathematically interesting but also critical for ensuring secure digital communications, encryption, and digital signatures. The relevance of these operations in finite fields, particularly in contrast to real fields (where real numbers are used), highlights their applicability and efficiency in computational cryptography.



Importance in Cryptography


Efficiency and Security

Finite Field Operations: When elliptic curves are defined over finite fields (such as Fp where p is a prime number), the group operations (addition and doubling of points) are discrete and cyclic. This discreteness provides a controlled environment conducive to defining hard problems like the Elliptic Curve Discrete Logarithm Problem (ECDLP), which is computationally infeasible to solve efficiently with current technology and forms the basis of security in ECC.


Hard Problems: The security of ECC relies on the difficulty of reversing these group operations, particularly the ECDLP, where given two points P and Q on the curve, finding an integer k such that Q = kP (i.e., P added to itself k times) is computationally hard.


Practical Application

Digital Signatures and Key Exchange: Operations like point addition and doubling are fundamental for algorithms like ECDSA (Elliptic Curve Digital Signature Algorithm) and ECDH (Elliptic Curve Diffie-Hellman). These protocols utilise the properties of elliptic curves over finite fields to create secure digital signatures and facilitate secure key exchange mechanisms, respectively.


Differences from Real Fields


Closure and Finite Nature

Finite Fields: In finite fields, the values of the points and coefficients are taken modulo a prime p ensuring that all possible results of point operations remain within a finite set of values. This provides the necessary closure and finiteness that is ideal for digital systems, which inherently rely on finite data representations.


Real Fields: In contrast, operations in real fields involve continuous values and do not naturally lend themselves to the modular arithmetic crucial for defining and securing cryptographic operations. Real numbers lead to issues with precision and practical implementation in digital systems due to their infinite decimal expansions.


Visualisation and Computation

Discrete vs. Continuous: Points on elliptic curves over real numbers can be visualised as smooth continuous curves, making them great for theoretical analysis and understanding. However, elliptic curves over finite fields look quite different; they consist of discrete points which do not form a continuous line, aligning better with digital computation that requires discrete steps and finite states.





Predictability and Security: The predictable nature of real number operations can be a drawback in security contexts, where unpredictability and hardness of problem-solving are crucial. Finite fields introduce a level of unpredictability, and irreversibility essential for cryptographic security.


The Process - an example

Take a specific elliptic curve, say:

modulus 13.


Find all the integer values of x and y for which the equation of the elliptic curve holds true. These points are not always as obvious, intuitively - or as easy to calculate - as they are for the elliptic curve defined in the field of Real numbers.


For example, when y = 11, and x = 4:

and:

However, when taken modulus 13:

And so (4, 11) is a solution (a valid point) on the elliptic curve.


NOTE: because of the symmetrical nature of the curve, if (x, y) is on the curve, so is (x, -y) = (x, p-y) mod p. And so we know immediately that (4, -11) = (4, p-11) = (4, 2) mod 13 is on the curve - which can be confirmed by calculating: 2^2 = 4.


The list of points on this elliptic curve is:

(0, 1), (0, 12), (1, 4), (1, 9), (4, 2), (4, 11), (5, 1), (5, 12),

(7, 0), (8, 1), (8, 12), (10, 6), (10, 7), (11, 2), (11, 11), (12, 5), (12, 8)


As seen graphed here:


Finding The Tangent To The Curve

In a finite field, the gradient can be found by the same method as for an elliptic curve in the field of real numbers. Except that all division, in the calculations, must be done in a way that adheres to the process of division for modular arithmetic.


In modular arithmetic, we focus on the fact that division should "undo multiplication". This is achieved by multiplying the dividend by the modular inverse of the divisor. We know that the modular inverse must exist, because the elliptic curve is defined on a field - and all values in a field have a modular (multiplicative) inverse.


This would mean:

Substituting in the values for the point we used before, (4, 11), we get:

But (and this is the important bit), in order to divide by 9, you multiply by its modular multiplicative inverse. The modular multiplicative inverse is the number, which when multiplied by 9 is equal to 1, mod 13.


To work out the modular multiplicative inverse of 9 mod 13, we can use a few different approaches. In this case, we will use Fermat's Little Theorem. That is:

That is, the modular multiplicative inverse of 9 mod 13 is 3.


And so now we can calculate the integer (mod 13) value for dy/dx - that is:

and so, the gradient of:

mod 13, is 4. Leading us to conclude that the tangent line to the curve that passes through (4, 11) has a gradient of 4, and therefore has the equation:



This line y = 4x + 8 is:

  1. tangent to the curve y^2 = x^3 + x + 1 at P = (4, 11)

  2. guaranteed to pass through one other point on the curve (see previous calculations)

  3. will ONLY pass through ONE other point on the curve (see the fact that a line, passing through more than 2 points on (or that is tangent to) an elliptic an elliptic curve describes a cubic, and therefore has a maximum of three solutions, in previous calculations)


NOTE: we take the point that it crosses to be:

R = -2P


and its point of reflection (mod p) is:

-R = (x_r, -y_r) = (x_r, p-y_r) = 2P


and so, we have found the position of 2P.


Visualising the tangent to the Curve in the Finite Field

Following is an animation, that helps to visualise the behaviour of the tangent to an elliptic curve:

in as finite field (modulus 13).


By drawing a tangent line from our "point of interest, on the curve", we see the following:



Note:

  1. the point we are doubling, at P = (4, 11)

  2. the line coming from it, at a slope of 4, traversing the space between 0 < x < 13, and 0 < y < 13

  3. the fact that, like the physics of the 80s game Asteroids, when the line reaches a border of the space, it re-enters the space, on the opposite side of the space, at the same slope (NOTE: the idea to visualise the tangent line as a line that crosses the border of the space, and back in the other side was taken from here: "A (relatively easy to understand) primer on elliptic curve cryptography" - no references to where this came from are given, and no other reference to this process, other than articles that reference that URL, were found).

  4. the points R = (8, 1), and 2P = (8, 12), and the vertical line joining them, appear as the tangent crosses the point R, because this indicates that 2P + R = the point at infinity and that the additive inverse of R is 2P

  5. the tangent line eventually crosses the y-axis at y = 8 - as clear from the equation y = 4x + 8

  6. the tangent line continues through the space and eventually ends up back at P, having passed through the top/bottom of the space 4 times (the same as the value of the tangent slope)


To show that the point at which the tangent line intersects with the curve again is the right point, see the following:



Showing that the three points of intersection of the curve and the tangent line at P = (4, 11) are:

x = 4 (twice), and

x = 8

Putting x = 8 back into the equation for the tangent line, we get:

Showing that the other point of intersection between the tangent line and the curve is:

R = (8, 1)

as shown in the animation above.


Other Examples

Here are a number of other examples, starting from other points in the same curve.


Note, with each one:

  1. the point we are doubling, P - marked in red

  2. the slope of the line is variable - always an integer value (mod 13)

  3. the tangent line, in the form y = mx + b, will always re-enter the left-hand side of the space at y = b

  4. the tangent line generated from each point crosses the top/bottom border the same number of times as the value of the tangent, m

  5. R and 2P are always each other's additive inverse, reflected across the line of reflection, at y = p/2

  6. the tangent line always ends up back at the starting point


4, 5, and 6, above, are all attributes of the facts that:

  1. we are working in a integer-sized "square" space, of size "p x p"

  2. all values related to the curve and its tangent must be integer values, and can always be converted to values between 0 <= x < p

  3. the tangent line must repeat after m number of interactions with the top/bottom border.


The simplest way to understand this 3rd limitation is to see that the triangles, created by the tangent line are p units high, and, in order to be the correct angle, the triangle they create must be p/m units wide at the top/bottom (so that the "rise over run" calculation for the slope of the lines works). As the length of that side of each triangle equals p/m, there must be m of them, to fill the space.


P = (0, 1)


P = (0, 12)


P = (1, 4)


P = (1, 9)


P = (4, 2)


For animation purposes - sometimes it makes more sense to go "backwards". When R is "on the left" of P - that is, when the x value for R is less than the x value for P, then it makes more sense, in an animation of the connection between them, to draw the line downward and to the left first.


NOTE: it doesn't matter which direction you start. In the end the tangent line will meet the correct point. It's just it gets there "faster" if you happen to know what value R is, compared to P, and you can move in the correct direction first.


P = (5, 1)


P = (5, 12)


The singular (non-reflected) points at y = 0, have a tangent that is a vertical line. This can be understood loosely, by thinking about what happens with an elliptic curve in the Reals, when y = 0, at the point of reflection on the x-axis - that is the, the tangent line approaches a vertical line, as y approaches 0, from both directions, and clearly becomes a vertical line (on the smooth curve), at that point.


It can also be understood loosely by considering the equation of the slope of the tangent:

which approaches infinity (or -ve infinity), as y approaches 0. This concept of "approaches" in a discrete field is not as clear, but still works to support the idea of vertical tangent.


Finally a more rigorous investigation of the definition of a tangent in a finite field, for an elliptic curve, using Homogenous Equations, and The Project Plane, is not covered, in these documents, but may be added at a later date.


P = (7, 0)


P = (8, 1)


P = (8, 12)


Sometimes, the value of R is P itself - for example, at the point P = (10, 6):

That is, in general, when:

then the tangent line from P = (x_1, y_1) will meet itself back at R= (x_1, y_1). Leading to the idea that:

That is:

This is equivelan

Two examples: P = (10, 6), P(11, 6)



Final Points











Comments


Green Juices
bottom of page