How to find a square root mod $pq$ given that $p \equiv q \equiv 3 \pmod 4$ Let $n = pq$ where $p$ and $q$ are prime. We do not know $p$ and $q$. All we know is that $p \equiv q \equiv 3 \pmod 4$. From this we need to find a number $y$, in terms of $n$ and $x$, such that $y^2 \equiv x \pmod n$.
So $n \equiv 1 \pmod 4$ but I'm not sure that this is helpful at all. Is it possible to find $y$, and if so, how would I go about doing it?
 A: Note:  what follows is not an answer to the question.  It shows how to extract the square root assuming you know $p$ and $q$.  I am leaving it up because in  the comments which follow the OP discuss, and clarify, the actual intent of the question (which is quite different that the stated question).  The intended question was (to paraphrase):  As an authenticity check, person $A$ has a number $n=pq$ on file.  Person $B$, seeking to authenticate $A$ presents a quadratic residue $\pmod n$.  Person $A$, knowing the factoring, extracts a square root and presents that to $B$ as proof.  The problem asks if this is secure.  The answer is:  No...$A$ has a $50-50$ chance of giving $B$ the wrong square root, that is, the one $B$ does not already know.  In that event, $B$ will be able to factor $n$ and permanently compromise the code.
Side note: how can $A$ produce a square root (knowing $p,q$).
If you have established that $x$ is a square, then we know that $x^{(p-1)/2}\equiv 1 \pmod p$ so $x^{1+(p-1)/2}\equiv x \pmod p$.  But if $p=4k+3$ then $1+\frac {p-1}2=2k+2$ is even  whence $y_p=x^{k+1}$ is a square root of $x\pmod p$.  Similarly we can find $y_q$ and then use the Chinese Remainder theorem to find $y$ such that $y\equiv y_p\pmod p$ and $y\equiv y_q \pmod q$.
