Textbook, page 338, Exercise 8.3
Textbook, page 338, Exercise 8.5
In the previous section on pseudorandom generators (PRGs), the functions took a binary string as input (the “seed”) and produced a longer binary string as the output. However, pseudorandom numbers do not always have to work with just binary strings. Consider a group-generation algorithm 𝒢 that on input 1n outputs a description of a cyclic group 𝔾 with prime order q and generator g. Now consider creating a pseudorandom generator that takes pairs of values from ℤq as input (seed), and produces three values from 𝔾 as output. Note that since 𝔾 is the same size as ℤq, this does provide expansion, as we expect from a PRG. In particular, given values x1, x2 ∈ ℤq, G(x1, x2) computes the three-value tuple (gx1, gx2, gx1x2).
Prove that this is a secure PRG if the Decisional-Diffie-Hellman (DDH) problem is hard relative to 𝒢.
Note: The logic is really simple here, so put your effort into making sure your write-up is as clear and precise as possible!
Determine the points on the elliptic curve E : y2 = x3 + x + 6 with a modulus of p = 11. How many points are on the curve?
For the elliptic curve defined in the previous problem, compute the sum (2, 7) + (7, 2) + (10, 2).
Textbook, page 373, Exercise 10.3
Textbook, page 373, Exercise 10.4