Question

9.2. Perform the additions

1. (2,7)+(5,2)
2. (3,6)+(3,6)
in the group of the curve y2 ≡ x3+2x+2 mod 17. Use only a pocket calculator.
9.6. In practice, a and k are both in the range p≈2150 · · ·2250, and computing T =a·
P and y0 = k ·P is done using the Double-and-Add algorithm as shown in Sect. 9.2.
1. Illustrate how the algorithm works for a = 19 and for a = 160. Do not perform
elliptic curve operations, but keep P a variable.
2. How many (i) point additions and (ii) point doublings are required on average for
one "multiplication"? Assume that all integers have n = log2 p bit.
3. Assume that all integers have n = 160 bit, i.e., p is a 160-bit prime. Assume one
group operation (addition or doubling) requires 20 μsec. What is the time for one
double-and-add operation?

Answer 1

1. For the elliptic curve group y² ≡ x³+2x+2 mod 17:

- (2,7) + (5,2) = (4,6)

- (3,6) + (3,6) = (11,6)

2. Double-and-Add Algorithm for a = 19 and a = 160:

- For a = 19: 7 additions, 2 doublings

- For a = 160: 8 additions, 6 doublings

3. With n = 160 bits and one group operation taking 20 μsec:

- Time for one double-and-add operation = (8 additions * 20 μsec) + (6 doublings * 20 μsec) = 280 μsec.

Step-by-step explanation:

In the elliptic curve group y² ≡ x³+2x+2 mod 17:

1. For (2,7) + (5,2): Calculate the slope of the line passing through the two points and find the third point on the curve. Result: (4,6).

For (3,6) + (3,6): Use the tangent line at the point to get the third point on the curve. Result: (11,6).

2. Double-and-Add Algorithm:

- For a = 19: Perform the algorithm using binary representation of the scalar a, counting additions and doublings. Result: 7 additions, 2 doublings.

- For a = 160: Similar calculation yields 8 additions, 6 doublings.

3. Time Calculation:

- With n = 160 bits, each addition or doubling operation is assumed to take 20 μsec. For a double-and-add operation, the total time is the sum of the time for additions and doublings, resulting in 280 μsec.

This demonstrates the practical application of the Double-and-Add algorithm, providing clarity on the number of operations required and the time it takes for a double-and-add operation in the specified elliptic curve group.

Answer 2

To perform the additions in the given elliptic curve group modulo 17, we substitute the given coordinates into the curve equation and calculate the result. The first addition yields the point (14,11), and the second addition yields the point (6,6).

Step-by-step explanation:

In order to perform the additions in the given group of the curve, we need to substitute the given coordinates into the curve equation and calculate the result modulo 17. Let's calculate each addition:

1. (2,7) + (5,2)

Substituting the coordinates into the equation:

y2 ≡ x3 + 2x + 2 mod 17

For the first point (2,7):

72 ≡ 23 + 2(2) + 2 mod 17

49 ≡ 8 + 4 + 2 ≡ 14 mod 17

For the second point (5,2):

22 ≡ 53 + 2(5) + 2 mod 17

4 ≡ 125 + 10 + 2 ≡ 11 mod 17

So, the result of the addition (2,7) + (5,2) is the point (14,11).

2. (3,6) + (3,6)

Substituting the coordinates into the equation:

y2 ≡ x3 + 2x + 2 mod 17

For the first point (3,6):

62 ≡ 33 + 2(3) + 2 mod 17

36 ≡ 27 + 6 + 2 ≡ 6 mod 17

For the second point (3,6):

62 ≡ 33 + 2(3) + 2 mod 17

36 ≡ 27 + 6 + 2 ≡ 6 mod 17

So, the result of the addition (3,6) + (3,6) is the point (6,6).