Extra credit: Prove that if p=5(mod 8), congruence
x^{2}=a(mod
p) has solution x=2^{k(p-1)/4 }a^{(p+3)/8 }(mod p) for
some k from {0,1}.
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)
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=x^{2} mod n and z=x^{3} mod n, compute
x.
That was easy, was it not? Now, how about Given y=x^{2} mod n
and z=x^{5} mod n, compute x. That also is not to
difficult, right?
Now, Given y=x^{a} mod n and z=x^{b} mod n,
such that gcd(a,b)=1, compute x. Hint: use extended gcd of a
and b.
Extra Credit: Ex. 11.10
Extra Credit: Ex. 11.11
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=g^{a }mod
p, y=g^{b }mod p, and {z,z'}, it is impossible to distinguish
z=g^{ab }mod p from z'=g^{c}^{ }mod p,
for a randomly chosen c (the set notation {z,z'} indicates that these two
values are given in random order).