CS-235. Problem Set 9

1. Exercise 13.1. What is the complexity of this algorithm?

2. Evaluate (11|37), (5|160465489), (3083|3911), (43691|65537)

3. Extra credit:  Prove that if p=5(mod 8), congruence x2=a(mod p) has solution x=2k(p-1)/4 a(p+3)/8 (mod p) for some k from {0,1}.

4. A computer performs Rabin's decryptions and/or signatures, using the standard square root of x mod n algorithm we discussed in class. Suppose a hacker can induce a random error ("kicking the computer") during an unknown computational step, likely to occur in the sections of the program that take more time.  Is it likely that the result r of such a corrupted computation can enable the hacker to factor n? How? Illustrate by factoring n=104411, given also x=3 and r=48851.
(This is a follow up to the previous problem set, except here no correct square roots are known to the attacker)

5. We know that computing square roots modulo n (without factorization of n) is hard for large n (this is equivalent to factoring n, as we have shown in class and last problem set).
Similarly computing other roots modulo n is hard (without factorization of n), as well (this is not equivalent to factoring n, but this is our RSA assumption which seems to be supported by our knowledge so far). One might think that computing, say, a square root and cubic roots at the same time can only be harder, but consider this:
Given y=x2 mod n and z=x3 mod n, compute x.
That was easy, was it not? Now, how about Given y=x2 mod n and z=x5 mod n, compute x. That also is not to difficult, right?
Now, Given y=xa mod n and z=xb mod n, such that gcd(a,b)=1, compute x. Hint: use extended gcd of a and b.

6. Extra Credit: Ex. 11.10
7. Extra Credit: Ex. 11.11

8. Encrypt and then decrypt message 7 using ElGamal encryption (as we discussed in class, directly obtained from Diffie-Hellman protocol)  with public key <p=23, g=2, x=9> and the corresponding secret <p=23, g=2, a=5>. Pretend that the numbers are really large and exhaustive search is out of the question, as well as computing Discrete Logarithm.
Prove that the El Gamal encryption leaks no information assuming Decisional Diffie-Hellman (DDH) assumption: Given p, g, x=ga mod p, y=gb mod p, and {z,z'}, it is impossible to distinguish z=gab mod p from z'=gc mod p, for a randomly chosen c (the set notation {z,z'} indicates that these two values are given in random order).