introduction to cryptography cs assignment 7 questions

Please SEE the photo carefully!

Q1 [3] Compute (124x134x23x49x13) mod 3 using modular arithmatic.

Q2 [4] What is the last digit of 1717 ?

Q3 [8] Find a) multiplicative and b) additive inverses of each non zero elements in Z9 (Note: Z9 = {0,1,2,3,4,5,6,7,8}). Show your steps.

Q4 [8] In a public-key system using RSA. You intercept the cipher text C = 10 sent to a user whose public key is e = 5, n =35. Find plaintext M and private key d.

Q5 [5] Consider the following MAC for messages of length n bits designed from a PRF F : the MAC key is a shared truely random n -bit PRF key k .To authenticate a message m = m1km2k…..kml where each mi is an n/2 bit string , choose a random r ∈{0,1} n and compute t := Fk(r) ⊕ Fk(< 1 > km1) ⊕ …… ⊕ Fk(< l > kml) the tag foe m is then (r, t). Here < i > is an n/2 bit encoding of the integer i. is this MAC secure? Explain.

Q6 [5] In the DLog problem, we make the group generator g and the element y = g x public and argue that computing x is hard. Will the same hold if we make x public and keep g private and demand that computing g is difficult ? More specifically, consider the following problem: let p be a prime and fix an x from Z ∗ p−1 . Pick a random g from the set {1, ….., p − 1} and compute y := [g xmodp]. Then given p, x and y, is computing g hard? explain

Q7 [7] Suppose you are given a 2-round secure key-exchange protocol Π, where each party communicates once with the other party (for example the Diffie-Hellman key-exchange protocol). Suppose Π outputs n-bit keys. Now using Π, can you construct a CPA-secure public-key encryption scheme for n-bit messages? Give complete formal details.