Elliptic Curve Cryptosystems - Understanding Cryptography - page 254

9.8. Given is the same curve as in 9.7. The order of this curve is known to be # E =
37. Furthermore, an additional point Q = 15 P =(14 , 23) on this curve is given.

Determine the result of the following point multiplications by using as few group
operations as possible, i.e., make smart use of the known point Q . Specify how you
simplified the calculation each time.
Hint: In addition to using Q , use the fact that it is easy to compute

·

− P .

1. 16 · P

2. 38 · P

3. 53 · P

4. 14 · P + 4 · Q

5. 23 · P + 11 · Q

You should be able to perform the scalar multiplications with considerably fewer
steps than a straightforward application of the double-and-add algorithm would al-
low.

9.9. Your task is to compute a session key in a DHKE protocol based on elliptic
curves. Your private key is a = 6. You receive Bob's public key B =(5 , 9).The
elliptic curve being used is defined by

y 2 x 3 + x + 6 mod 11 .

≡

9.10. An example for an elliptic curve DHKE is given in Sect. 9.3. Verify the two
scalar multiplications that Alice performs. Show the intermediate results within the
group operation.

9.11. After the DHKE, Alice and Bob possess a mutual secret point R =( x , y ).The
modulus of the used elliptic curve is a 64-bit prime. Now, we want to derive a session
key for a 128-bit block cipher. The session key is calculated as follows:

K AB = h ( x || y )

Describe an efficient brute-force attack against the symmetric cipher. How many
of the key bits are truly random in this case? (Hint: You do not need to describe
the mathematical details. Provide a list of the necessary steps. Assume you have a
function that computes square roots modulo p .)

9.12. Derive the formula for addition on elliptic curves. That is, given the coordi-
nates for P and Q , find the coordinates for R =( x 3 , y 3 ).
Hint : First, find the equation of a line through the two points. Insert this equation
in the elliptic curve equation. At some point you have to find the roots of a cubic
polynomial x 3 + a 2 x 2 + a 1 x + a 0 . If the three roots are denoted by x 0 , x 1 , x 2 , you can
use the fact that x 0 + x 1 + x 2 =

− a 2 .