Search in book...
Toggle Font Controls
Create new playlist

Name your new playlist

Playlist description (optional)
Sign In

Email address

Password

Forgot Password?

or

Continue with Facebook

Continue with Google
Sign Up

Full Name

Email address

Confirm Email Address

Password

or

Continue with Facebook

Continue with Google

21.4 Elliptic Curves in Characteristic 2

Many applications use elliptic curves mod 2, or elliptic curves defined over the finite fields $G F (2^{n})$ $G F (2^{n})$ (these are described in Section 3.11). This is often because mod 2 adapts well to computers. In 1999, NIST recommended 15 elliptic curves for cryptographic uses (see [FIPS 186-2]). Of these, 10 are over finite fields $G F (2^{n}) .$ $G F (2^{n}) .$

If we’re working mod 2, the equations for elliptic curves need to be modified slightly. There are many reasons for this. For example, the derivative of $y^{2}$ $y^{2}$ is $2 y y^{'} = 0,$ $2 y y^{'} = 0,$ since $2$ $2$ is the same as 0. This means that the tangent lines we compute are vertical, so $2 P = ∞$ $2 P = ∞$ for all points $P .$ $P .$ A more sophisticated explanation is that the curve $y^{2} \equiv x^{3} + b x + c (m o d 2)$ $y^{2} \equiv x^{3} + b x + c (m o d 2)$ has singularities (points where the partial derivatives with respect to $x$ $x$ and $y$ $y$ simultaneously vanish).

The equations we need are of the form

E : y^{2} + a_{1} x y + a_{3} y = x^{3} + a_{2} x^{2} + a_{4} x + a_{6},

$E : y^{2} + a_{1} x y + a_{3} y = x^{3} + a_{2} x^{2} + a_{4} x + a_{6},$

where $a_{1}, \dots, a_{6}$ $a_{1}, \dots, a_{6}$ are constants. The addition law is slightly more complicated. We still have three points adding to infinity if and only if they lie on a line. Also, the lines through $∞$ $∞$ are vertical. But, as we’ll see in the following example, finding $- P$ $- P$ from $P$ $P$ is not the same as before.

Example

Let $E : y^{2} + y \equiv x^{3} + x (m o d 2) .$ $E : y^{2} + y \equiv x^{3} + x (m o d 2) .$ As before, we can list the points on $E :$ $E :$

\begin{array}{l} (0, 0), & (0, 1), & (1, 0), & (1, 1), & ∞ . \end{array}

$\begin{array}{l} (0, 0), & (0, 1), & (1, 0), & (1, 1), & ∞ . \end{array}$

Let’s compute $(0, 0) + (1, 1) .$ $(0, 0) + (1, 1) .$ The line through these two points is $y = x .$ $y = x .$ Substituting into the equation for $E$ $E$ yields $x^{2} + x \equiv x^{3} + x,$ $x^{2} + x \equiv x^{3} + x,$ which can rewritten as $x^{2} (x + 1) \equiv 0 .$ $x^{2} (x + 1) \equiv 0 .$ The roots are $x = 0, 0, 1 (m o d 2) .$ $x = 0, 0, 1 (m o d 2) .$ Therefore, the third point of intersection also has $x = 0 .$ $x = 0 .$ Since it lies on the line $y = x,$ $y = x,$ it must be $(0, 0) .$ $(0, 0) .$ (This might be puzzling. What is happening is that the line is tangent to $E$ $E$ at $(0, 0)$ $(0, 0)$ and also intersects $E$ $E$ in the point $(1, 1) .$ $(1, 1) .$ ) As before, we now have

(0, 0) + (0, 0) + (1, 1) = ∞ .

$(0, 0) + (0, 0) + (1, 1) = ∞ .$

To get $(0, 0) + (1, 1)$ $(0, 0) + (1, 1)$ we need to compute $∞ - (0, 0) .$ $∞ - (0, 0) .$ This means we need to find $P$ $P$ such that $P + (0, 0) = ∞ .$ $P + (0, 0) = ∞ .$ A line through $∞$ $∞$ is still a vertical line. In this case, we need one through $(0, 0),$ $(0, 0),$ so we take $x = 0 .$ $x = 0 .$ This intersects $E$ $E$ in the point $P = (0, 1) .$ $P = (0, 1) .$ We conclude that $(0, 0) + (0, 1) = ∞ .$ $(0, 0) + (0, 1) = ∞ .$ Putting everything together, we see that

(0, 0) + (1, 1) = (0, 1) .

$(0, 0) + (1, 1) = (0, 1) .$

In most applications, elliptic curves mod 2 are not large enough. Therefore, elliptic curves over finite fields are used. For an introduction to finite fields, see Section 3.11. However, in the present section, we only need the field $G F (4),$ $G F (4),$ which we now describe.

Let

G F (4) = {0, 1, ω, ω^{2}},

$G F (4) = {0, 1, ω, ω^{2}},$

with the following laws:

$0 + x = x$ $0 + x = x$ for all $x .$ $x .$
$x + x = 0$ $x + x = 0$ for all $x .$ $x .$
$1 \cdot x = x$ $1 \cdot x = x$ for all $x .$ $x .$
$1 + ω = ω^{2} .$ $1 + ω = ω^{2} .$
Addition and multiplication are commutative and associative, and the distributive law holds: $x (y + z) = x y + x z$ $x (y + z) = x y + x z$ for all $x, y, z .$ $x, y, z .$

Since

ω^{3} = ω \cdot ω^{2} = ω \cdot (1 + ω) = ω + ω^{2} = ω + (1 + ω) = 1,

$ω^{3} = ω \cdot ω^{2} = ω \cdot (1 + ω) = ω + ω^{2} = ω + (1 + ω) = 1,$

we see that $ω^{2}$ $ω^{2}$ is the multiplicative inverse of $ω .$ $ω .$ Therefore, every nonzero element of $G F (4)$ $G F (4)$ has a multiplicative inverse.

Elliptic curves with coefficients in finite fields are treated just like elliptic curves with integer coefficients.

Example

Consider

E : y^{2} + x y = x^{3} + ω,

$E : y^{2} + x y = x^{3} + ω,$

where $ω \in G F (4)$ $ω \in G F (4)$ is as before. Let’s list the points of $E$ $E$ with coordinates in $G F (4) :$ $G F (4) :$

\begin{array}{l} x = 0 \Rightarrow y^{2} = ω \Rightarrow y = ω^{2} \\ x = 1 \Rightarrow y^{2} + y = 1 + ω = ω^{2} \Rightarrow no solutions \\ x = ω \Rightarrow y^{2} + ω y = ω^{2} \Rightarrow y = 1, ω^{2} \\ x = ω^{2} \Rightarrow y^{2} + ω^{2} y = 1 + ω = ω^{2} \Rightarrow no solutions \\ x = ∞ \Rightarrow y = ∞ . \end{array}

$\begin{array}{l} x = 0 \Rightarrow y^{2} = ω \Rightarrow y = ω^{2} \\ x = 1 \Rightarrow y^{2} + y = 1 + ω = ω^{2} \Rightarrow no solutions \\ x = ω \Rightarrow y^{2} + ω y = ω^{2} \Rightarrow y = 1, ω^{2} \\ x = ω^{2} \Rightarrow y^{2} + ω^{2} y = 1 + ω = ω^{2} \Rightarrow no solutions \\ x = ∞ \Rightarrow y = ∞ . \end{array}$

The points on $E$ $E$ are therefore

\begin{matrix} (0, ω^{2}), & (ω, 1), & (ω, ω^{2}), & ∞ . \end{matrix}

$\begin{matrix} (0, ω^{2}), & (ω, 1), & (ω, ω^{2}), & ∞ . \end{matrix}$

Let’s compute $(0, ω^{2}) + (ω, ω^{2}) .$ $(0, ω^{2}) + (ω, ω^{2}) .$ The line through these two points is $y = ω^{2} .$ $y = ω^{2} .$ Substitute this into the equation for $E :$ $E :$

ω^{4} + ω^{2} x = x^{3} + ω,

$ω^{4} + ω^{2} x = x^{3} + ω,$

which becomes $x^{3} + ω^{2} x = 0 .$ $x^{3} + ω^{2} x = 0 .$ This has the roots $x = 0, ω, ω .$ $x = 0, ω, ω .$ The third point of intersection of the line and $E$ $E$ is therefore $(ω, ω^{2}),$ $(ω, ω^{2}),$ so

(0, ω^{2}) + (ω, ω^{2}) + (ω, ω^{2}) = ∞ .

$(0, ω^{2}) + (ω, ω^{2}) + (ω, ω^{2}) = ∞ .$

We need $- (ω, ω^{2}),$ $- (ω, ω^{2}),$ namely the point $P$ $P$ with $P + (ω, ω^{2}) = ∞ .$ $P + (ω, ω^{2}) = ∞ .$ The vertical line $x = ω$ $x = ω$ intersects $E$ $E$ in $P = (ω, 1),$ $P = (ω, 1),$ so

(0, ω^{2}) + (ω, ω^{2}) = (ω, 1) .

$(0, ω^{2}) + (ω, ω^{2}) = (ω, 1) .$

For cryptographic purposes, elliptic curves are used over fields $G F (2^{n})$ $G F (2^{n})$ with $n$ $n$ large, say at least 150.

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.

Table of Contents for 21.4 Elliptic Curves in Characteristic 2

Create new playlist

Sign In

Sign Up

Table of Contents for
21.4 Elliptic Curves in Characteristic 2