Problem 5 - An Introduction to Mathematical Cryptography

Question

For each of the following elliptic curves \(E\) and finite fields \(\mathbb{F}_{p}\), make a list of the set of points \(E\left(\mathbb{F}_{p}\right)\). (a) \(E: Y^{2}=X^{3}+3 X+2\) over \(\mathbb{F}_{7}\). (b) \(E: Y^{2}=X^{3}+2 X+7\) over \(\mathbb{F}_{11}\). (c) \(E: Y^{2}=X^{3}+4 X+5\) over \(\mathbb{F}_{11}\). (d) \(E: Y^{2}=X^{3}+9 X+5\) over \(\mathbb{F}_{11}\). (e) \(E: Y^{2}=X^{3}+9 X+5\) over \(\mathbb{F}_{13}\).

Step-by-Step Solution

Answer

For each elliptic curve, substitute each \( x \) in \( \mathbb{F}_p \) into the equation and verify \( Y^2 \equiv X^3 + AX + B \pmod{p} \) has solutions, including the point \( O \).

Step 1: Understanding Elliptic Curves

We are given elliptic curves of the form \( E: Y^2 = X^3 + AX + B \) over finite fields \( \mathbb{F}_p \) where \( p \) is a prime number. Our task is to find the set of points \( (x, y) \) on these curves where \( x, y \in \mathbb{F}_p \) and \( y^2 \equiv x^3 + Ax + B \pmod{p} \).

Step 2: Consider Curve (a)

For curve (a), we have \( E: Y^2 = X^3 + 3X + 2 \) over \( \mathbb{F}_7 \). We need to substitute \( x \) values from 0 to 6 and calculate \( X^3 + 3X + 2 \mod 7 \). Then, check if the result is a quadratic residue modulo 7 (that is, determine if there is a \( Y \) such that \( Y^2 = \text{result} \mod{7} \).

Step 3: List Points on Curve (a)

Calculate and determine \( Y^2 \equiv f(x) \pmod{7} \) for each \( x \) from 0 to 6. For example:- \( x = 0 \): \( Y^2 \equiv 2 \pmod{7} \).- \( x = 1 \): \( Y^2 \equiv 6 \pmod{7} \).- Continue for \( x = 2, 3, 4, 5, 6 \).Check quadratic residues for each to find valid \( (x, y) \) pairs. Include the point at infinity \( O \).

Step 4: Consider Curve (b)

For curve (b), we have \( E: Y^2 = X^3 + 2X + 7 \) over \( \mathbb{F}_{11} \). Again, substitute \( x \) values from 0 to 10 and calculate \( X^3 + 2X + 7 \mod 11 \). Determine if a corresponding \( Y \) exists for \( Y^2 = \text{result} \mod{11} \).

Step 5: List Points on Curve (b)

Compute for each \( x \) to check for quadratic residues and obtain valid \( (x, y) \) pairs over \( \mathbb{F}_{11} \). Include the point at infinity \( O \).

Step 6: Consider Curve (c) and (d)

Repeat the process for curve (c) \( E: Y^2 = X^3 + 4X + 5 \) over \( \mathbb{F}_{11} \) and for curve (d) \( E: Y^2 = X^3 + 9X + 5 \) over \( \mathbb{F}_{11} \). Substitute \( x \), calculate \( Y^2 \equiv f(x) \), and verify quadratic residues.

Step 7: List Points on Curve (c) and (d)

For each curve, list all valid points \( (x, y) \) that satisfy the curve equation over \( \mathbb{F}_{11} \) as well as the point at infinity \( O \).

Step 8: Consider Curve (e)

For curve (e), we have \( E: Y^2 = X^3 + 9X + 5 \) over \( \mathbb{F}_{13} \). Substitute \( x \) values from 0 to 12, calculate \( Y^2 \equiv f(x) \), and check for quadratic residues in \( \mathbb{F}_{13} \).

Step 9: List Points on Curve (e)

Determine valid points \( (x, y) \) over \( \mathbb{F}_{13} \) along with the point at infinity \( O \).

Key Concepts

Finite Fields

Finite fields, also known as Galois fields, are essential in understanding elliptic curve cryptography. A finite field, denoted as \( \mathbb{F}_p \), is a set containing a limited number of elements, where \( p \) is a prime number. These fields provide a structure in which addition, subtraction, multiplication, and division (except by zero) are well-defined and produce results within the field itself.
This mathematical system underpins many cryptographic algorithms, particularly elliptic curves, by ensuring calculations remain predictable within a secure and finite space.
In practical terms, using a finite number of elements allows cryptographers to control and limit the possibilities of calculations. They ensure that the operations needed to encrypt and decrypt data stay manageable and reliable.
In elliptical curve exercises like the one given, finite fields dictate the boundary conditions for point calculations. By systematically evaluating each element within \( \mathbb{F}_p \), it helps determine valid solutions for elliptic curve equations, laying the foundation for more complex cryptographic operations.

Modular Arithmetic

Modular arithmetic is a fundamental part of the cryptographic process, often described as clock arithmetic due to its cyclical nature. It involves performing arithmetic operations like addition, subtraction, multiplication, and finding remainders when divided by a number \( n \), known as the modulus.
In the context of elliptic curves, modular arithmetic enables the calculation of points over a finite field, as seen in equations like \( Y^2 \equiv X^3 + AX + B \pmod{p} \). This relation tells us to compute the right side of the equation, take the remainder when divided by \( p \), and check if it is a quadratic residue.
The application of modular arithmetic ensures that every operation stays within the finite field, maintaining the integrity and security of cryptographic processes.
For example, when solving for points on an elliptic curve over \( \mathbb{F}_7 \), each x value from 0 to 6 uses modular arithmetic to find if it matches possible y values within the same range. Consequently, it creates a secure, consistent way to handle numbers in algorithms essential for encrypting or decrypting data.

Quadratic Residues

Quadratic residues are direct results of modular arithmetic and play a crucial role in solving elliptic curve equations over finite fields. A number \( a \) is a quadratic residue modulo \( n \) if there exists an integer \( x \) such that \( x^2 \equiv a \pmod{n} \). In simpler terms, \( a \) is a quadratic residue if it matches the square of another number within the specified modular system.
This concept is pivotal in verifying possible \( y \) values in the elliptic curve equations \( Y^2 = X^3 + AX + B \) over \( \mathbb{F}_p \).
Determining whether certain numbers in a finite field are quadratic residues helps identify which \( (x, y) \) pairs satisfy the curve equation, essential for listing proper points of elliptic curves.
To test a number for being a quadratic residue, one can use algorithms based on the Legendre symbol. Calculations show whether there exists a \( y \) that squares to equal the result of the mod equation, simplifying the verification process in finite fields such as \( \mathbb{F}_7 \), \( \mathbb{F}_{11} \), or \( \mathbb{F}_{13} \). This forms a necessary validation step in elliptic curve cryptography, ensuring accuracy and security.