/ DISCRETE-MATH

Fields - Elliptical Curves Over Finite Fields

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:

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          
—————- —- —- —- —- —-
x 0 1 2 3 4
x3 + 4x + 1 1 1 2 0 1
—————- —- —- —- —- —-
y 1 1   0 1
y’ 4 4   4  

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

P x y 2y (2y)’ z x’’ y’’ 2P
A 4 1 2 3 1 3 0 O
A’ 4 4 3 2 4 3 0 O
B 1 1 2 3 1 4 1 A
B’ 1 4 3 2 4 4 4 A’
C 0 4 3 2 3 4 4 A’
C’ 0 1 2 3 2 4 1 A’

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

    A O A’ B C C’ B’
  A O A’ B C C’ B’
(4,1) A A O          
(3,0) O O            
(4,4) A’ A’   O        
(1,1) B B       A    
(0,4) C C         A’  
(0,1) C’ C’         A  
(1,4) B’ B’           A’

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:

                 
x 0 1 2 3 4 5 6
x3 0 3 6 2 5 1 4
0 ⊗ x2 0 2 4 6 1 3 5
x3 ⊕ 0 ⊗ x2 ⊕ 2 2 3 5 6 0 6 6 2
y 4 0 1       1 1
y’ 5 3 4     5    

#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.
xavier

Xavier Geerinck

Xavier works as a Cloud Solution Architect at Microsoft, helping its customer unlock the full potential of the cloud. Even though he is still considered a young graduate, he achieved his first success at the age 16, by creating and selling his first startup. He then took this knowledge to create and help more startups in different markets such as technology, social media, philanthropy and home care. While in the meantime gaining more enterprise insights at renowned enterprises such as Nokia, Cisco and now Microsoft.

Read More