Part 2 – Elliptic Curves Over Finite Fields

In the previous topic, we already know what is Elliptic Curves. Now, we go further with the Elliptic Curves Over Finite Fields.

Modulo

Picture 1. Modulo

Refer to this link to get more about the Modulo operation.

Elliptic Curves Over Finite Fields

By mod an Elliptic Curve for a prime number we have the result y is a group of points that have the value inside the range 0 – (p-1). See the example below.

E.g.:

Picture 2. Elliptic Curves Over Finite Fields Example

Access this link to see more shapes of Elliptic Curves over Finite Fields (graui.de)

Now, we already know what the Elliptic Curves Over Finite Fields look like. Next, let see what is the change in point additions.

Point Addition and Point Doubling

We see the point operations formula also added mod p.

Modular of a fraction

When calculating a fraction modulo m, we need to find the modular inverse of the denominator to multiply by the inverse instead of dividing. This is because the division is not directly defined in modular arithmetic. Instead, we use multiplication by the modular inverse to achieve the same result.

E.g.: 9/5 mod 17

1. We find that 7 is the modular inverse of 5 modulo 17, because (5 * 7) mod 17 = 1.
2. Now, we can rewrite 9/5 as 9 * 7 mod 17, equivalent to 63 mod 17. Finally, the result is 12.

Below is the source code that helps us calculate the modular result.

def modular_inverse(a, m):
    # This function finds the modular inverse of a modulo m using the Extended Euclidean Algorithm
    # It returns the modular inverse if it exists, otherwise it returns None
    a = a % m
    for x in range(1, m):
        if (a * x) % m == 1:
            return x
    return None

def modular_division(numerator, denominator, modulus):
    # This function performs modular division of numerator by denominator modulo modulus
    inv_denominator = modular_inverse(denominator, modulus)
    if inv_denominator is None:
        raise ValueError(f"No modular inverse for {denominator} modulo {modulus}")
    return (numerator * inv_denominator) % modulus

# Example usage:
modulus = 17
numerator = 9
denominator = 5

result = modular_division(numerator, denominator, modulus)
print(f"The result of {numerator}/{denominator} mod {modulus} is {result}")

Example

To verify the results of the Point Addition and Point Doubling, please access Elliptic Curve scalar multiplication (𝔽ₚ) (corbellini.name)

The calculation method above is trouble when we calculate many points nP. It takes a lot of time and is very complicated.

For example, given a P find nP. Normally, we find 2P=P*P, 3P=2P+P, …, nP=(n-1)P+P.

Double-and-Add Algorithm

To understand what is Double-and-Add Algorithm, we take an example: find 30P.

30 = 11110

Ignore the first MSB bit. with 1 we do Doubling and Addition, with 0 we only do Doubling. We have:

Following the table above, we need only 5 steps to calculate 30P.

In the next topic, we will see how the Elliptic Curves In Finite Field are used in TLS handshake. This also is the purpose of this series. Thanks for reading!