Online Tutorial
4.4 QUIZ 3 ~ Solutions

Elliptic Curve Groups over F2m

1. Does the elliptic curve equation y2 + xy = x3 + g5x2 + g6 define a group over F23?

Since the parameter b = 6 is not zero, the equation y2 + xy = x3 + g5x2 + g6 does define an elliptic curve group over F23

2. Do the points P(g3, g6) and Q(g5, g2) lie on the elliptic curve y2 + xy = x3 + g2x2 + g6 over F23?

The point P(g3,g6) is on the elliptic curve y2 + xy = x3 + g2x2 + g6 over F23 since that equation holds true:

(g6)2 + (g3)(g6) = (g3)3 + g2(g3)2 + g6

g5 + g2 = g2 + g + g6

(111) + (100) = (100) + (010) + (101)

(011) = (011)

g3 = g3

However, the point Q(g5)(g2) is not on the elliptic curve, since the equation disagrees:

(g2)2 + (g5)(g2) = (g5)3 + g2(g5)2 + g6

g4 + 1 = g + g5 + g6

(110) + (001) = (001) + (111) + (101)

(111) = (000)

g5 = 0 which is false.

3. What are the negatives of the following elliptic curve points over F23?

P(g3,g6) Q(g,0) R(0,g3)

The negatives of the points are defined by (xP, xP + yP)

-P = (g3, g3 + g6) = (g3, g4)

-Q = (g, g + 0) = (g, g)

-R = (0, 0 + g3) = (0, g3)

4. In the elliptic curve group defined by y2 + xy = x3 + g2x2 + g6 over F23, what is P + Q if P = (g2,g6) and Q = (g5,g5)?

P + Q = R where:

s = (yP - yQ) / (xP + xQ) = (g6 + g5) / (g2 + g5) = g / g3 = g-2 = g5

xR = s2 + s + xP + xQ + a = g3 + g5 +g2 + g5 + g2 = g3

yR = s(xP + xR) + xR + yP = g5 * (g2 + g3) + g5 + g6 = g5 * g5 + g3 + g6 = g3 + g3 + g6 = g6

Thus P + Q = (g3, g6)

5. In the elliptic curve group defined by y2 + xy = x3 + g2x2 + g6 over F23, what is 2P if P = (g3, g4)?

2P = R where:

s = xP + yP / 2xP = g3 + g4 / g3 = g3 + g = 1

xR = s2 + s + a = 1 + 1 + g2 = g2

yR = xP + (s + 1) * xR = g3 + 0 * g2 = g3

Thus 2P = (g2, g3)

Next