 Xavier Geerinck

My thoughts, tutorials and learnings

June 5, 2015 - discrete-math

Fields - Elliptical Curves Over Finite Fields Xavier Geerinck

@XavierGeerinck

Did you enjoy reading? Or do you want to stay up-to-date of new Articles?

Consider sponsoring me or providing feedback so I can continue creating high-quality articles!

1.1 Weierstrass Equations

1.1.1 Introduction

A weierstrass equation is an elliptical curve with a collection of points (x, y) (xεF and yεF) and is of the third grade with the form:

$$y^2 + a_1xy + a_3y = x^3 + a_2x^2 + a_4x + a_6, a_i\epsilon F$$

and ∞ always added as a point.

1.1.2 Notions

• We have an interaction ⊞ or + that converts (E/F, ⊞) to an abelian group (see groups). We can create formulas to interpret P1⊞P2.
• ∞ is the neutral element
• The inverse of P is -P or P' (Noted as P⊞P'=∞)
• P n times itself is written as nP (Example: 2P is the doubling of the point P)

We will create formulas for P1⊞P2 for the elliptical curbes (E/Fpn) over the finite fields (Fpn). Which allows us to reduce the amount of Weirstrass equations to 5 cases:

Supersingular Cases

• (E/F2n, ⊞), E: y2 + cy = x3 + ax + b
• (E/F3n, ⊞), E: y2 = x3 + ax + b

Not-Supersingular Cases

• (E/F2n, ⊞), E: y2 + xy = x3 + ax2 + b
• (E/F3n, ⊞), E: y2 = x3 + ax2 + b

Over fields with characteristic p ≥ 5

• (E/Fpn, ⊞), E: y2 = x3 + ax + b

1.2 Number of points

The number of points (#E) on a elliptical curbe (E/Fq=pn, ⊞) depends on the coefficients (a, b, c) in the equations from our previous point.

To get #E we need to know the number of points for #(E/Fp, ⊞), if we know this we can get the number of points for #(E/Fpn, ⊞), this if our coefficients a, b and c are still the same.

Once we know this we can create a recursion equation for #E:

• ε1 = (p + 1) - #(E/Fp, ⊞) and ε0 = 2
• εn = ε1εn - 1 - pεn - 2

Example: Coefficients are: a = 0, b = 1 and (E/F2, ⊞) = {(1,0), (0,1), (1,1), (∞, ∞)}. Calculate the number of points for F65536

What do we know:

• We know that by applying Fq = pn that F65536 = 216, so q = 65536, p = 2 and n = 16.
• The number of points for when n = 1 and p = 2 is 4 (this is given).
• ε0 = 2

We can fill this into a table already. If we do this we get:

| q | | 2 | 4 | 8 | 16 | 32 | 64 | 128 | 256 | 512 | 1024 | 2048 | 4096 | 8192 | 16384 | 32768 | 65536 |:-:||:-:||:-:||:-:||:-:||:-:||:-:||:-:||:-:||:-:||:-:||:-:||:-:||:-:||:-:||:-:||:-:||:-:| | ε | 2 | #E | |

If we now apply the 2 formulas for ε1 and εn we get:

| q | | 2 | 4 | 8 | 16 | 32 | 64 | 128 | 256 | 512 | 1024 | 2048 | 4096 | 8192 | 16384 | 32768 | 65536 |:-:||:-:||:-:||:-:||:-:||:-:||:-:||:-:||:-:||:-:||:-:||:-:||:-:||:-:||:-:||:-:||:-:||:-:| | ε | 2 | -1 | -3 | 5 | 1 | -11 | 9 | 13 | -31 | 5 | 57 | -67 | -47 | 181 | -87 | -275 | 449 | #E | | 4 | 8 | 4 | 16 | 44 | 56 | 116 | 288 | 508 | 968 | 2116 | 4144 | 8012 | 16472 | 33044| 65088

> Note: We can check find out the range the points lie in by checking the Hasse Interval, you do this by saying ε = (q + 1) - #E, then |ε| is always smaller or equal to 2√q. (Example: for (E/F37, ⊞) |ε| ≤ 12 ==> 26 ≤ #E ≤ 50)

1.3 Curves over Characteristic (F) ≥ 5

Let's say we got a Weirstrass Equation that is of the form: E: y2 = x3 + ax + b, we know that this is a (E/F3n, ⊞) Supersingular equation. Because we are working with fields, we can write the + and the * as the additive and multiplicative interactions between the elements. Now we get: E: y2 = x3 ⊕ a⊗x ⊕ b (Note: the power is also multiplicative!).

1.3.1 Formulas

2P = ∞

1. z = (3⊗x2 ⊕ a) ⊘ (2⊗y)
2. 2P ≡ (x”,y”)
3. x” = z2 ⊖ 2⊗x
4. y” = z ⊗(x ⊖ x”) ⊖ y

We can now calculate (x3, y3) = (x1, y1) ⊞ (x1, y1)

1. z = (y2 ⊖ y1) ⊘ (x2 ⊖ x1)
2. x3 = z2 ⊖ x1 ⊖ x2
3. y3 = z ⊗ (x1 ⊖ x3) ⊖ y1

1.3.2 Example

Question: We have (E/F5), a=4, b=1, n=1 (so we have modulo 5) and E: y2 = x3 + ax + b

We know that E: y2 = x3 + ax + b = E: y2 = x3 + 4x + 1

We can calculate x3 + 4x + 1 by executing the equation on the X'es given, and y by taking the root from the right side of our equation, do note that this can be non existant (if the root can't be taken). Another way to calculate y would be to check where y * y in our multiplication table is equal to our right side of the equation.

So if we put this into a table to calculate the points:

Calculations
Calculating x3 + 4x + 1

| 03 + 4 0 + 1 mod 5 = 1 | 13 + 4 1 + 1 mod 5 = 1 | 23 + 4 2 + 1 mod 5 = 2 | 33 + 4 3 + 1 mod 5 = 0 | 43 + 4 * 4 + 1 mod 5 = 1 | Calculating y| | sqrt(1) = 1 | | sqrt(1) = 1 | | sqrt(2) = / | | sqrt(0) = 0 | | sqrt(1) = 1 | | Calculating y' | | 1' = 4 | | 1' = 4 | | /' = / | | 0' = / | | 1' = 4 |

Putting it into a simple table:

Formula
------------------------------------
x01234
x3 + 4x + 111201
------------------------------------
y1101
y'444

Out of this table we can read that our points are:

• #E = 8
• A(4, 1) and A'(4, 4)
• B(1, 1) and B'(1, 4)
• C(0, 4) and C'(0, 1)
• O(3, 0) = O' --> O ⊞ O' = ∞

Now we can apply everything that we calculated on the formulas in point 1.3.1 and we can get the 2P, or the doubling of our point P

Pxy2y(2y)'zx''y''2P
A4123130O
A'4432430O
B1123141A
B'1432444A'
C0432344A'
C'0123241A'

and last but not least, we can fill in the group table.

AOA'BCC'
AOA'BCC'
(4,1)AAO
(3,0)OO
(4,4)A'A'O
(1,1)BBA
(0,4)CCA'
(0,1)C'C'A
(1,4)B'B'

1.4 Not-supersingular curves E/F2n

By applying the same method as in point 1.3 we will be able to do this for the not supersingular curves.

Only this time we have different formulas:

1.4.1 Formulas

2P = ∞

1. z = x ⊕ (y ⊘ x)
2. 2P ≡ (x”,y”)
3. x” = z2 ⊕ z ⊕ a
4. y” = x2 ⊕ (z ⊗ x'') ⊕ x''

We can now calculate (x3, y3) = (x1, y1) ⊞ (x1, y1)

1. z = (y1 ⊕ y2) ⊘ (x1 ⊕ x2)
2. x3 = z2 ⊕ z ⊕ x1 ⊕ x2 ⊕ a
3. y3 = z ⊗ (x1 ⊕ x3) ⊕ x3 ⊕ y1

1.4.2 Example

Question: We have (E/F23), a=1, b=element 2, n is NOT equal to 1

We can now calculate the points by E: y ⊗ (x ⊕ y) = x3 ⊕ element 0 ⊗ x2 ⊕ element 2

Note: We are using the additive table here for the field F23

After solving this like we did in 1.3, we get the following result:

x0123456
x30362514
0 ⊗ x20246135
x3 ⊕ 0 ⊗ x2 ⊕ 223560662
y40111
y'5345

#E = 10

And the points are:

• A(0,4) and A'(0,5)
• B(6,1) and B'(6,5)
• C(1,0) and C'(1,3)
• D(2,1) and D'(2,4)
• O(∞,1)=O' --> O ⊞ O' = ∞

The same goes for the doubling of the points (2P), see 1.3 for this.

1.5 Cyclical group or not?

We can check if a group is cyclical by using the following methods:

• μ(#E)≠0, then (E/Fq=pn, ⊞) is cyclical
• μ(#E)=0, then we need to check this, check the methods 1.3 and 1.4 for this.

Did you enjoy reading? Or do you want to stay up-to-date of new Articles?

Consider sponsoring me or providing feedback so I can continue creating high-quality articles!