Proving property of Modified Rabin Signature

Question

I'm trying to prove one of the properties of the “Modified Rabin Signature Scheme”:

If $\gcd(x, n) = 1$, then $x^{\frac{(p−1)(q−1)}{2}} \equiv 1 \pmod n$

This is what I’ve got so far…

Proof

Let $p$ and $q$ be primes such that $p \equiv 3 \pmod 4$ and $q \equiv 3 \pmod 4$

$$p = 4 t_1 + 3 , \, q = 4 t_2 + 3 \,\,\,\,\,\,\,\,\,\,-(I)$$

Then ($s$ = odd)

$$\frac{\phi(n)}{2} = 2 s\\$$

From the “Euler theorem” we know that

$$x^{\phi(n)} \equiv 1 \pmod n$$

Taking square root both sides

$$x^{\frac{\phi(n)}{2}} \equiv \sqrt{1} \pmod n$$

assuming

$$x^{\frac{\phi(n)}{2}} \equiv -1 \pmod n \, \text{ i.e. } \, x^{2s} \equiv -1 \pmod n\\ \implies x^{2s} -1 = nk$$

subsituting values of $p, q$ from $(I)$ we get

$$x^{\text{even}} = (\text{odd})k + 1$$

Now, I want to show that

$$x^{\text{even}} \neq (\text{odd})k + 1$$

… but I'm kind of stuck here.

Can anybody help me complete this proof of one of the properties of Modified Rabin Signature?

Answer 1

In short words: when you compute things modulo $n = pq$, you are really computing things simultaneously modulo $p$ and modulo $q$. That's the gist of the Chinese Remainder Theorem. So to prove that $a = b \pmod n$, you just have to prove that $a = b \pmod p$ and $a = b \pmod q$.

Modulo $p$, for any $x$ that is not a multiple of $p$, $x^{p-1} = 1 \pmod p$ (this is Fermat's little theorem). Therefore, $x^{k(p-1)} = 1^k = 1 \pmod p$ for any integer $k$. Now, $p$ and $q$ are big primes, so they are odd. It follows that $q-1$ is even, therefore $(q-1)/2$ is an integer. So $x^{(p-1)(q-1)/2} = 1 \pmod p$. The same holds modulo $q$ for the same reason. By the CRT, you get the result modulo $n$.

Note that while Rabin's cryptosystem is defined with $p = 3 \pmod 4$ and $q = 3 \pmod 4$, these properties are not necessary to demonstrate that $x^{(p-1)(q-1)/2} = 1 \pmod n$. It also works when $p = 1 \pmod 4$ or $q = 1 \pmod 4$. The only requirement is that $x$ is relatively prime to both $p$ and $q$, which is exactly what $\mathrm{gcd}(x,n) = 1$ means.