1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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$... $\endgroup$ – Hilder Vítor Lima Pereira Jan 31 '16 at 11:20
  • $\begingroup$ 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$... $\endgroup$ – Hilder Vítor Lima Pereira Jan 31 '16 at 11:24
  • $\begingroup$ I suggest you read chapters 2 and 3 of the Handbook of Applied Cryptography. $\endgroup$ – fkraiem Jan 31 '16 at 12:08
  • 1
    $\begingroup$ 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. $\endgroup$ – fgrieu Jan 31 '16 at 12:12
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ whats wrong with my above approach. Can you tell me where I did it wrong. $\endgroup$ – Atinesh Feb 6 '16 at 13:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.