CS-235. Problem Set 8
- In the Fiat-Shamir protocol, what
- Verifier uses predictable coins?
- Prover uses predictable coins? (e.g. does not change coins)
- a) My Public Key for Rabin Encryption is n=45173. You sneak into my office
and compute square root of 4 is 32236. Factor n.
Suppose now that a random error was induced in an unknown step of square root of
1 mod 32236 computation that outputs 399 (assume the standard square root
algorithm discussed in class and the error is likely to occur in the
sections of the algorithm that take longer). Is it possible for you as a
hacker to factor n? If yes, do it.
- Extra credit: Ex. 13.7
- Ex. 13.11 (you can use the algorithm we used in class - it is
essentially the same)