Description of the coin-flipping protocol:
Alice chooses primes p and q and computes $n = pq$. She sends $n$ to Bob while keeping $p$ and $q$ secret.
Bob receives $n$, and chooses $x$ to computer $x^2 = y \bmod n$. Bob sends $y$ to Alice.
Alice uses $p$ and $q$ to compute four square roots of $y \bmod n$ and chooses one at random. she sends it to Bob.
If Alice chose $x$, she wins, otherwise, she loses.
Problem:
In the coin-flipping protocol with $n = pq$, suppose Bob sends a number $y$ such that neither $y$ nor $-y$ has a square root $\bmod n$.
a) show that $y$ cannot be a square both $\bmod p$ and $\bmod q$.
(b) show that $y$ is not a square $\bmod q$. show that $-y$ is a square $\bmod q$.
(c) show that $y$ is a square mod one of the primes and $-y$ is a square mod the other.
(d)Alice decides to correct Bob's "mistake". suppose $y$ is a square $\bmod p$ and $-y$ is a square $\bmod q$. Alice calculates a number $b$ such that $b^2 = y \bmod p$ and $b^2 = -y \bmod q$ and sends $b$ to Bob. (there are two pairs of choices for $b$). show how Bob can use this information to factor $n$.
My question is about parts b, c, and d.
(b) Here is my attempt to show what the problem asks.
$x^2 = -y \bmod q$
$x^2 = q-y \bmod q$
$x^2 + y = 0 \bmod q$
$x^2 = -y \bmod q$
This seems like I just went around in a small circle, it feels like I haven't used the relevant information. Does anyone see what I should be doing?
(c) I'm not sure how to incorporate the right information to prove what the problem is aking. this sounds like an extremely general prompt to me. Does anyone have any pointers?
(d). could he use b^2 as one of the square roots ($\bmod n$) and find $\gcd(x-b, n)$ to factor $n$? I am also not sure how there could be two pairs of choices for $b$, when $b$ is one of two numbers that satisfy both of $b^2 = y \pmod{p}$ and $b^2 = y \pmod{q}$.