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:
$$ y^2 + a1xy + a3y = x^3 + a2x^2 + a4x + a6, ai\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/F_{2n}, ⊞), E: y^2 + cy = x^3 + ax + b$
- $(E/F_{3n}, ⊞), E: y^2 = x^3 + ax + b$
Not-Supersingular Cases
- $(E/F_{2n}, ⊞), E: y^2 + xy = x^3 + ax^2 + b$
- $(E/F_{3n}, ⊞), E: y^2 = x^3 + ax^2 + b$
Over fields with characteristic p ≥ 5
- $(E/F_{p^n}, ⊞), E: y^2 = x^3 + 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/F_2, ⊞) = {(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 = ∞
- z = (3⊗x2 ⊕ a) ⊘ (2⊗y)
- 2P ≡ (x”,y”)
- x” = z2 ⊖ 2⊗x
- y” = z ⊗(x ⊖ x”) ⊖ y
We can now calculate (x3, y3) = (x1, y1) ⊞ (x1, y1)
- z = (y2 ⊖ y1) ⊘ (x2 ⊖ x1)
- x3 = z2 ⊖ x1 ⊖ x2
- 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 = ∞
- z = x ⊕ (y ⊘ x)
- 2P ≡ (x”,y”)
- x” = z2 ⊕ z ⊕ a
- y” = x2 ⊕ (z ⊗ x'') ⊕ x''
We can now calculate (x3, y3) = (x1, y1) ⊞ (x1, y1)
- z = (y1 ⊕ y2) ⊘ (x1 ⊕ x2)
- x3 = z2 ⊕ z ⊕ x1 ⊕ x2 ⊕ a
- 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.
Member discussion