Cryptography Reference
In-Depth Information
Problems
9.1. Show that the condition 4 a 3 + 27 b 2
= 0mod p is fulfilled for the curve
y 2
x 3 + 2 x + 2 mod 17
(9.3)
9.2. Perform the additions
1. (2 , 7)+(5 , 2)
2. (3 , 6)+(3 , 6)
in the group of the curve y 2
x 3 + 2 x + 2 mod 17. Use only a pocket calculator.
9.3. In this chapter the elliptic curve y 2
x 3 + 2 x + 2 mod 17 is given with # E = 19.
Verify Hasse's theorem for this curve.
9.4. Let us again consider the elliptic curve y 2
x 3 + 2 x + 2 mod 17. Why are all
points primitive elements?
Note : In general it is not true that all elements of an elliptic curve are primitive.
9.5. Let E be an elliptic curve defined over
Z
7 :
E : y 2 = x 3 + 3 x + 2 .
1. Compute all points on E over
Z 7 .
2. What is the order of the group? (Hint: Do not miss the neutral element
O
.)
3. Given the element
α
=(0 , 3), determine the order of
α
.Is
α
a primitive element?
2 150
2 250 , and computing T = a
9.6. In practice, a and k are both in the range p
···
·
P and y 0 = 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 =
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
log 2 p
μ
sec. What is the time for one
double-and-add operation?
9.7. Given an elliptic curve E over
Z 29 and the base point P =(8 , 10):
E : y 2 = x 3 + 4 x + 20 mod 29 .
·
Calculate the following point multiplication k
P using the Double-and-Add algo-
rithm. Provide the intermediate results after each step.
1. k = 9
2. k = 20
Search WWH ::




Custom Search