Course 374 (Cryptography) Sample Paper 1

Dr Timothy Murphy

GMB ??  Friday, ?? 2007  ??:00–??:00

Attempt 4 questions from Part A, and 2 questions from Part B.

Part B

9. Prove that the multiplicative group F^{×} of a finite field F is cyclic. Find all the primitive roots mod17, ie the generators of (ℤ/17)^{×}. How many primitive elements does 𝔽_{3^{3}} possess? Answer:

(a) Let

∥F ∥ = q.

Lemma 1. The exponent of F^{×} is q − 1.

Proof. By Lagrange’s Theorem,

e | q − 1

On the other hand, since the equation x^{e} − 1 = 0 has at most e roots in F,

q − 1 ≤ e.

Hence

e = q − 1.

Lemma 2. If A is an abelian group, and g, h ∈ A are of orders m, n, where

gcd(m, n) = 1,

then gh is or order mn.

Proof. Suppose the order of gh is d. Then

d | mn,

since

(gh)^{mn} = g^{mn}h^{mn} = 1,

On the other hand,

(gh)^{d} = 1 ⟹ (gh)^{md} = h^{md} = 1.

Thus

n | md ⟹ n | d,

since gcd(m, n) = 1. Similarly

m | d.

Hence

mn | d,

since gcd(m, n) = 1; and so

d = mn.

Lemma 3. A finite abelian group A of exponent e contains an element of order e.

Proof. Suppose

e = p_{1}^{e_{1}} ⋯ p_{r}^{e_{r}}.

For each i ∈ [1, r], A contains an element α_{i} of order divisible by p_{i}^{e_{i}}, say of order p_{i}^{e_{i}}q_{i}. But then

β_{i} = α_{i}^{q_{i}}

is of order p_{i}^{e_{i}}. Hence by the previous Lemma,

β = β_{1} ⋯ β_{r}

is of order

e = p_{1}^{e_{1}} ⋯ p_{r}^{e_{r}}.

It follows from this Lemma that F^{×} contains an element of order e = q − 1, and so is cyclic.

(b) (ℤ/17)^{×} is a cyclic group of order 16. So each element has order 1,2,4,8 or 16. There is 1 element of order 1, namely 1; 1 element of order 2, namely -1; ϕ(4) = 2 elements of order 4; ϕ(8) = 4 elements of order 8; and ϕ(16) = 8 elements of order 28, If x has order 16 then

x^{8} = −1.

Hence

(−x)^{8} = −1,

and so the 4 elements ±x, ±x^{−1} all have order 16. Since

2^{4} = −1 mod 17

it follows that 2 has order 8 mod 17. Since

(−2)^{4} = 2^{4} = −1 mod 17

it follows that the 4 elements of order 8 are

±2, ±2^{−1},

ie

2, 15, 9, 8.

Also, since 2 is of order 8, 4 = 2^{2} is of order 4. Thus the 2 elements of order 4 are

±4,

ie

4, 13.

Thus the 8 elements of order 16 (ie the primitive roots) are:

3, 5, 6, 7, 10, 11, 12, 14.

(c) The number of primitive elements in 𝔽_{3^{3}} is

ϕ(3^{3} − 1) = ϕ(26)
= ϕ(2)ϕ(13)
= 1 · 12
= 12.

10. Explain what is meant by a singular point on a curve, and show that

the curve

y^{2} = x^{3} + ax^{2} + bx + c

is always singular over a field of characteristic 2. What is the condition for the curve to be singular over a field of characteristic ≠ 2? Determine whether the equation

y^{2} = x^{3} + x^{2} + x + 1

defines an elliptic curve over each of the fields 𝔽_{3}, 𝔽_{5}, 𝔽_{7}, 𝔽_{8}; and in those cases where it does, determine the group on the curve (as eg ℤ/(2) ⊕ ℤ/(2)). Answer:

(a) Suppose the curve is given by

F (X, Y, Z) = 0

in homogeneous coordinates. Then the point P = [X_{0}, Y_{0}, Z_{0}] on the curve is said to be singular if

∂F/∂X = ∂F/∂Y = ∂F/∂Z = 0

at P. [In other words, P is singular if the tangent at P is undefined.] (b) In homogeneous coordinates the curve is given by

F (X, Y, Z) ≡ Y^{2}Z + X^{3} + aX^{2}Z + bXZ^{2} + cZ^{3} = 0.

Thus

∂F/∂X = X^{2} + bZ^{2},
∂F/∂Y = 0∂F/∂Z  = aX^{2} + cZ^{2}.

It follows that the point O = [0, 1,], which is on the curve, is singular. Hence the curve is singular.

(c) If char k ≠ 2 then the curve

y^{2} = x^{3} + ax^{2} + bx + c

is singular if and only if the polynomial

p(x) = x^{3} + ax^{2} + bx + c

has a multiple root. The condition for this is that

gcd(p(x), p′(x)) ≠ 1.

k = 𝔽_{3} Then

p(x) = x^{3} + x^{2} + x + 1, p′(x) = 2x + 1.

Since

p′(x) = 0 ⟹ x = −1/2 = 1

and

p(1) = 1 ≠ 0,

the curve is non-singular, and so is an elliptic curve. The quadratic residues mod3 are {0, 1}. Let us draw up a table for x, p(x), y:

\begin{matrix}x & p(x) & y \\ 0 & 1 & ±1 \\ 1 & 1 & ±1 \\ −1 & 0 & 0 \end{matrix}

We deduce that the curve has 6 points: (0, ±1), (1, ±1), (0, 0) and the point [0, 1, 0] at infinity. There is only 1 abelian group of order 6, namely ℤ/(6) = ℤ/(2) ⊕ ℤ/(3), so we deduce that

E(𝔽_{3}) ≅ ℤ/(6).

k = 𝔽_{5} Then

p(x) = x^{3} + x^{2} + x + 1, p′(x) = 3x^{2} + 2x + 1.

Now

3p(x) − xp′(x) = x^{2} + 2x + 3,

while

3(x^{2} + 2x + 3) − p(x) = 4x + 8.

Thus

gcd(p(x), p′(x)) = 1 ⟺ p(−2) ≠ 0.x = −2.

In fact

p(−2) = −8 + 4 − 2 + 1 = 2 − 1 − 2 + 1 = 0.

Thus the curve is singular in this case, and so is not an elliptic curve.

k = 𝔽_{7} As before,

3p(x) − xp′(x) = x^{2} + 2x + 3,
3(x^{2} + 2x + 3) − p(x) = 4x + 8.

But in this case

p(−2) = −8 + 4 − 2 + 1 = −1 − 3 − 2 + 1 = 2 ≠ 0.

Thus the curve is non-singular, ie it is an elliptic curve. The quadratic residues mod7 are {0, 1, 2, 4} = {0, 1, 2, −3}. We draw up the table for x, p(x), y:

\begin{matrix}x & p(x) & y \\ 0 & 1 & ±1 \\ 1 & −3 & ±3 \\ 2 & 1 & ±1 \\ 3 & −2 & − \\ −3 & 1 & ±1 \\ −2 & 2 & ±3 \\ −1 & 0 & 0 \end{matrix}

We deduce that the curve has 12 points: (0, ±1), (1, ±3), (2, ±1), (−3, ±1), (−2, ±3), (−1, 0) and the point [0, 1, 0] at infinity.

There are 2 abelian groups of order 12, namely ℤ/(4)⊕ℤ/(3) = ℤ/12 and ℤ/(2) ⊕ ℤ(2) ⊕ ℤ(3) = ℤ/(6) ⊕ ℤ/(2). The first of these has just 1 element of order 2, while the second has 3 elements of order 2. But if P = (x, y) then

−P = (x, −y).

It follows that P is of order 2 if and only if y = 0. Since (−1, 0) is the only such point in this case, we deduce that

E(𝔽_{3}) ≅ ℤ/(12).

𝔽_{8} The curve in this case is singular. [More generally, the curve

y^{2} = f(x),

where f(x) is a cubic, is always singular in characteristic 2. To get an elliptic curve in characteristic 2, there must be a term in xy or y, or both, on the left. If the characteristic is not 2 then one can complete the square on the left,

y^{2} + Axy + By = (y + Ax/2 + B/2)^{2} + g(x).]

To verify singularity in this case, we write the equation in projective form:

F (X, Y, Z) ≡ Y^{2}Z + X^{3} + X^{2}Z + XZ^{2} + Z^{3} = 0.

Now

∂F/∂X = X^{2} + Z^{2},
∂F/∂Y = 0,
∂F/∂Z = Y^{2} + X^{2} + Z^{2}.

The fact the ∂F/∂Y vanishes identically means that a singular point can be found by solving 2 equations in 3 unkowns, which is always possible. In general the solution does not lie in the ground field, but in this case it does: (1, 0) = [1, 0, 1] is a singular point on the curve.

11. Show that a polynomial f(x) of degree n over the finite field 𝔽_{p} is irreducible if and only if

gcd(f(x), x^{p^{m}} − x) = 1

for m = 1, 2, …, [n/2].

Find an irreducible polynomial p(x) of degree 6 over 𝔽_{2}.

Show that

y^{2} + y = x^{3} + 1

defines an elliptic curve over 𝔽_{2^{6}}, and determine the group on this curve.

Answer:

(a) If f(x) is composite, it must have a factor g(x) of degree m ≤ [n/2]. Recall that

U_{m}(x) = x^{p^{m}} − x = ∏ π(x)

where π(x) runs over all irreducible polynomials of degree d | m. In particular

g(x) | U_{m}(x)

and so

gcd(f(x), U_{m}(x)) ≠ 1.

Conversely, suppose

gcd(f(x), U_{m}(x)) ≠ 1.

Then some irreducible factor π(x) of U_{m}(x) must divide f(x). This factor has degree d ≤ m, and so is not f(x). Hence f(x) is composite.

(b) Consider the polynomial

f(x) = x^{6} + x + 1

in 𝔽_{2}[x]. Since x is not a factor of f(x), this will be irreducible if and only if

gcd(f(x), x^{2^{m}−1} − 1) = 1

for m = 2, 3. Now

x^{6} ≡ 1 mod x^{3} − 1,

and so

f(x) ≡ x mod x^{3} − 1.

Hence

gcd(f(x), x^{3} − 1) = 1

Also

xf(x) = x^{7} + x^{2} + x ≡ x^{2} + x + 1 mod x^{7} − 1,

while

x^{3} − 1 = (x − 1)(x^{2} + x + 1) ≡ 0 mod x^{2} + x + 1.

Hence

x^{6} ≡ 1 mod x^{2} + x + 1,

and so

x^{6} + x + 1 ≡ x^{2} mod x^{2} + x + 1.

Thus

gcd(f(x), x^{7} − 1) = 1.

We conclude that

f(x) = x^{6} + x + 1

is irreducible over 𝔽_{2}.

(c) The curve

y^{2} + y = x^{3} + 1

takes homogeneous form

F (X, Y, Z) = Y^{2}Z + Y Z^{2} + X^{3} + Z^{3}.

Now

∂F/∂X = X^{2},
∂F/∂Y = Z^{2},
∂F/∂Z = Y^{2} + Z^{2}.

Thus

∂F/∂X = ∂F/∂Y = ∂F/∂Z = 0 ⟹ X = Y = Z = 0.

Hence the curve is non-singular (since [0, 0, 0] is not a point in the projective plane).

(d) We want to determine the number of points, N say, on the curve E(𝔽_{2^{6}}). Note first that the left-hand side of the equation, y^{2} +y = y(y +1), is invariant under y ↦ y + 1. Thus

(x, y) ∈ E(𝔽_{2^{6}}) ⟺ (x, y + 1) ∈ E(𝔽_{2^{6}}).

[In fact, since the line x = c passing through these two points also passes through O = [0, 1, 0], these points are the negatives of each other:

−(x, y) = (x, y + 1).]

On adding the point [0, 1, 0] at infinity on the curve, it follows that N is odd. The points defined over 𝔽_{2}, 𝔽_{2^{2}}, 𝔽_{2^{3}} give subgroups of E(𝔽_{2^{6}}:

E(𝔽_{2}) ⊂ E(𝔽_{2^{2}}) ⊂ E(𝔽_{2^{6}}), E(𝔽_{2}) ⊂ E(𝔽_{2^{3}}) ⊂ E(𝔽_{2^{6}}).

We start by looking at the smaller groups, since this will probably give useful information about the large group.

𝔽_{2} By inspection the curve E(𝔽_{2}) contains the points (1, 0), (1, 1), together with the point at infinity. Thus

E(𝔽_{2}) = ℤ/(3).

𝔽_{2^{2}} If x = 0 the equation becomes

y^{2} + y + 1 = 0.

This polynomial is irreducible over 𝔽_{2}, but has two roots in 𝔽_{2^{2}}, since we could take

𝔽_{2^{2}} = 𝔽_{2}[x]/(x^{2} + x + 1).

We know that the number of points on the curve is divisible by 3 (since E(𝔽_{2}) = ℤ/(3) is a subgroup). So there is at least one more point, with x ∈ 𝔽_{2^{2}} \ 𝔽_{2}. But in fact, as we have seen, if there is one such point for a given x then there are two. This implies that both values of x must provide 2 new points, giving 9 points in all. [Concretely, the elements of 𝔽_{2^{2}} \ 𝔽_{2} are the roots of

x^{2} + x + 1 = 0.

If one root is ω then the other is ω^{2}. The 9 points on the curve are:

(0, ω), (0, ω^{2}), (1, 0), (1, 1), (ω, 0), (ω, 1), (ω^{2}, 0), (ω^{2}, 1),

together with the point [0, 1, 0] at infinity.] It follows that

E(𝔽_{2^{2}}) = ℤ/(9) or ℤ/(3) ⊕ ℤ/(3).

To distinguish between these, we use a little geometry to identify the points of order 3 on the curve. A point P on an elliptic curve has order 3 if and only if it is a point of inflexion, ie the tangent at P meets the curve in 3 points P, P, P. For 2P = −Q, where Q is the point where the tangent meets the curve again. Thus

3P = 0 ⟺ 2P = −P ⟺ Q = P,

ie the tangent meets the curve again at P. The tangent at P = (x, y) is

y = mx + c,

where m = dy/dx. In our case

(2y + 1)\frac{dy}{dx} = 3x^{2},

ie

m = x^{2}.

This meets the curve where

(mx + c)^{2} + (mx + c) = x^{3} + 1.

If the roots of this cubic are x_{1}, x_{2}, x_{3} then

x_{1} + x_{2} + x_{3} = m^{2}.

Thus

3P = 0 ⟺ 3x = m^{2}
⟺ x = x^{4}
⟺ x^{3} = 1,

if we ignore the case x = 0 (which we know from E(𝔽_{2}) does actually give 2 points of order 3). But we know (from Lagrange’s Theorem) that

x ∈ 𝔽_{2^{3}}^{×} ⟹ x^{3} = 1.

We conclude that all the points on E(𝔽_{2^{2}}) are of order 3, and so

E(𝔽_{2^{2}}) = ℤ/(3) ⊕ ℤ(3).

𝔽_{2^{3}} The map

θ : x ↦ x^{3} : 𝔽_{2^{3}} → 𝔽_{2^{3}}

has ker θ = {1} (since the group has order 8). Thus each element of F_{2^{3}} has a unique cube root. It follows that the equation, which can be written

x^{3} = y^{2} + y + 1,

has a unique solution for each y. Thus there are 8 + 1 = 9 points on the curve; and so

E(𝔽_{2^{3}}) = ℤ/(9) or ℤ/(3) ⊕ ℤ/(3).

But as we saw in the case 𝔽_{2^{2}}, the point P = (x, y) is of order 3 if and only if x = 0 or x^{3} = 1. As we just saw, if x ∈ 𝔽_{2^{3}}^{×} then

x^{3} = 1 ⟹ x = 1 ⟹ y = 0 or 1.

Thus there are just 2 points of order 3 on E(𝔽_{2^{3}}), namely E(𝔽_{2}) \ O, and so

E(𝔽_{2^{3}}) = ℤ/(9).

Now let us turn to E(𝔽_{2^{6}}). Since

E(𝔽_{2^{2}}) ∩ E(𝔽_{2^{2}}) = E(𝔽_{2})

it follows that the subgroup

E(𝔽_{2^{2}}) + E(𝔽_{2^{2}}) = ℤ/(3) ⊕ ℤ/(9).

(This is the only one of the 3 abelian groups of order 3^{3} with subgroups ℤ/(9) and ℤ/(3) ⊕ ℤ/(3)). In particular, if E(𝔽_{2^{6}} has N points then

27 | N.

Also, by Hasse’s theorem,

|N − 65| ≤ 2\sqrt{64} = 16,

49 ≤ N ≤ 81.

ie

Since N is odd, it follows that N = 81 = 3^{4}.

There are three possibilities: E(𝔽_{2^{6}}) = ℤ/(27)⊕ℤ/(3) or ℤ/(9)⊕ℤ/(9) or ℤ/(9)⊕ℤ/(3)⊕ℤ/(3).

The first two of these groups have 3^{2} −1 elements of order 3, while the last has 3^{3} − 1 = 26. As we have seen, if P = (x, y) then

3P = 0 ⟺ x = 0 or x^{3} = 1.

Thus the only points of order 3 are the 8 in E(𝔽_{2^{2}}), ruling out the third group. To distinguish between the first 2 cases, let us determine the number of points of order 9. We have seen that if P = (x, y) ∈ E(𝔽_{2^{6}}) then

2P = (x^{4}, y_{1}) ⟹ 4P = (x^{16}, y_{2})
⟹ 8P = (x^{64}, y_{3}).

But

x^{6}4 = x

for all x ∈ 𝔽_{2^{6}}. Hence

8P = ±P

for all points on the curve. Now

8P = P ⟹ 7P = 0

is impossible (since the group has order 3^{4}). We conclude that

9P = 0

for all P ∈ E(𝔽_{2^{5}}). Hence

E(𝔽_{2^{6}}) = ℤ/(9) ⊕ ℤ/(9).

[That was much more difficult than intended!]