Problem 1 (40 points)
Implement in Python a secure pseudo-random generator (PRG) by relying on the fact that the Decisional Diffie-Hellman assumption is true. For this you must implement everything from scratch. This means that you must implement a function
add(group element #1, group element #2)
which returns the “addition” (i.e. the group operation) on the first and the second element. Also, implement a add many times function,
add many times(group element g, integer k)
which returns h+h+…+h, k-many times, when you call add many times. Your programs will have a fixed parameter n, say n = 521 bits, and a group generator g.
1. InyourfirstimplementationofthePRGyoumustimplementadd()usingZN ={0,…,N−1} where the operation is addition (mod N). Your task is to experimentally demonstrate that what you implemented is not a PRG, in the sense that you should be able to distinguish its output from random.
2. In your second implementation of the PRG the only thing that changes is add(). For this you should spend time understanding how to use the following class: https://pycryptodome.readthedocs.io/en/latest/src/public_key/ecc.html
Intuitively explain what has happened in your implementations and whether (1) means that DDH is not a true cryptographic assumption.
Problem 2 (20 points)
Research the area of Elliptic-curve cryptography. Do web searches and in particular regarding the material posted at the NIST (National Institute of Standards and Technology). Write an essay
试用版
1
explaining (1) how Elliptic-curve cryptography is relevant to our class and in particular to this problem-set and (2) in which actually deployed products Elliptic curves are used. The essay must be from 500-1000 words long.
Problem 3 (20 points)
Use your secure PRG (part 2 in Problem 1) in order to construct a PRG that stretches a small number of bits (at most 521) to 1 MB.
Intuitively, but with some mathematical rigor, justify why your implementation is a secure PRG.
Problem 4 (20 points)
By relying on the fact that the DDH assumption is true you should perform a secure (public) key-exchange.
Intuitively, but with some mathematical rigor, justify why your implementation is a secure key-exchange protocol.
试用版
2