# Proving property of Modified Rabin Signature

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?

• The square root operation is not well-defined on $Z_n$. For instance, if $n = 5$, then, $1\cdot 1 = 3 \cdot 3 = 4 \cdot 4 = 1 \pmod n$... – Hilder Vitor Lima Pereira Jan 31 '16 at 11:20
• Please, could you write all the hypothesis about the the values $p, q, n,$ and $x$ ? This may help people to understand better the problem. Because you are trying to prove a general implication, but in the proof, you are taking $p$ and $q$ as prime whose residues mod $4$ is $3$... – Hilder Vitor Lima Pereira Jan 31 '16 at 11:24
• I suggest you read chapters 2 and 3 of the Handbook of Applied Cryptography. – fkraiem Jan 31 '16 at 12:08
• Hint: prove that $p=3\pmod4$, $p$ prime, $q=3\pmod4$, $q$ prime, $n=pq$, $\gcd(x,n)=1$ implies $x^{\frac{(p−1)(q−1)}{2}}-1\equiv0\pmod p$ and $x^{\frac{(p−1)(q−1)}{2}}-1\equiv0\pmod q$; then use $p\ne q$ and conclude. – fgrieu Jan 31 '16 at 12:12

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.