Set the target let the sha- hash function

meandering.

Notes
• Assumptions (if any) must be stated clearly in your answers.

An encryption system is considered malleable if given a ciphertext of some unknown plaintext, it is possible to obtain a valid ciphertext of a related plaintext without even knowing the contents of the plaintext. This is problematic depending on the application. For instance, in bidding for a contract, a company might outbid its competitor by simply multiplying it’s rival company’s encrypted bid by 0.9, without even knowing the bid [DDN03]. The following questions relates to the malleability of the Elgamal cryptosystem taught in the lecture.

(b) Suppose we are given the ciphertext c = (c1; c2) of some unknown message m, where c1 ≡ gk (mod p) for some unknown random integer k 2 Zp-1 and c2 ≡ m · hk (mod p), where h is the public key of some unknown private key x, in the Elgamal cryptosystem. Let m0 be a message that you know. Can you obtain a valid ciphertext of the message m · m0 without knowing m?

(a) Show that if X is not uniformly distributed then necessarily one of the pi’s is > 1=n.

(b) Show that if X is not uniformly distributed then E1(X) < n.

In lecture 10, we saw that the initial value for block reward for bitcoins was 50 Bitcoins, which halves every 210,000 blocks. Recall that the sum of an infinite geometric series is
S = a + ar + ar2 + ar3 + · · · = a
1 - r ;
where a is the starting coefficient, and r is the common ratio between adjacent terms. Since new Bitcoins can only be created if a new block is created, using the above formula, calculate the final number of Bitcoins that will ever be created. Your answer should explain your choice of a and r.

Question 5
Recall from Lecture 10 that a 51% attacker is an attacker who holds at least 51% of the total hash power.

4
(b) Modify the program from part (a) by adding i to s, where i = 0 to 999 inclusive, and for each i computing the hash until the value falls before the target. What is the average number of attempts (over 1,000) before you found the target? You need to provide your program.

(c) If you drew random values between 0 and 2255 inclusive, how many attempts on average it would take before you find a value below the target? What does it tell you about SHA-256?

2016.

Nigel P Smart. Cryptography made simple, volume 481. Springer, 2016.