Rabin encryption when M is not Disjoint to n

Question

I need help with proving that the encryption going well when the message $M$ is not Disjoint to $n$ (public key).

Encryption message $\ C= M^2 \bmod n$

Decryption message $\ C^{(p+1)/4} \equiv ±M \bmod p$ and $\ C^{(q+1)/4} \equiv ±M \bmod q$.

Now, we can't use Fermat's little theorem. Suppose that $M \neq 0 \pmod p$ and $M \equiv 0 \bmod q$

(because $n = pq$ and $p,q$ are primes)

Answer 1

The definition of the Rabin cryptosystem in the question likely is similar to:

• Setup:
  • choose $p$ and $q$ large distinct primes with $p\equiv q\equiv 3\pmod 4$ ;
  • compute and publish public modulus $n=p\;q$, and publish it as the public key;
  • the private key is $p,q$ .
• Encryption of message (representative) $M$ with $0\le M<n$ :
  • compute ciphertext $C=M^2\bmod n$ [implying by definition $0\le C<n$ ]
• Decryption of ciphertext $C$ :
  • compute $M_p=C^{(p+1)/4}\bmod p$ and $M_q=C^{(q+1)/4}\bmod q$ ;
  • deduce that $M\equiv\pm M_p\pmod p$ and $M\equiv\pm M_q\pmod q$ [see proof at end];
  • noticing that $\gcd(p,q)=1$ by construction, use the Chinese Remainder Theorem to find the set $\mathcal M$ of possible $M$ as follows:
    • compute $q_\text{inv}=q^{-1}\bmod p$ [this value can be reused for multiple $C$ ];
    • compute these 4 values: $$\begin{align} M_0&=(q((q_\text{inv}(M_p-M_q))\bmod p)+M_q)\bmod n\\ M_1&=-M_0\bmod n\\ M_2&=(q((q_\text{inv}(M_p+M_q))\bmod p)-M_q)\bmod n\\ M_3&=-M_2\bmod n \end{align}$$
    • the set $\mathcal M$ is $\{M_0,M_1,M_2,M_3\}$ ;
  • select $M$ as the message in $\mathcal M$ that pass some consistency check.

Further, it is commonly restricted to $p\ne q\pmod8$ at setup, yielding $n\equiv5\pmod8$; and $M\equiv4\pmod8$ [or some other value $\pmod8$ ], which then is enough to always allow recognition of which element of the set $\mathcal M$ is $M$.

Depending on $M$ or $C$, the set $\mathcal M$ will have one, two or four distinct elements. One element only occurs for $M=0$ ($M_p=M_q=0$); two elements occur when otherwise $\gcd(M,n)\ne1$ [equivalently, when a single of $M_p=0$ (x)or $M_q=0$ holds; or in other words, when $M\ne0$ is not disjoint to $n$ ; ]; four elements occurs otherwise, that is for overwhelmingly most $M$.

The original reference on the Rabin encryption scheme is: Michael O. Rabin; Digitized Signatures and Public Key Functions as Intractable a Factorization, MIT-LCS-TR-212 (1979). It defines $C=M(M+b)\bmod n$ for some public $b$ with $0\le b<n$, which makes the cryptosystem somewhat less malleable; also, it is not restricted to $p\equiv q\equiv 3\pmod 4$.

---

Proof that for all $M$, it holds $C^{(p+1)/4}\equiv\pm M\pmod p$ [same for $q$ rather than $p$ ]

• By construction, $C=M^2\bmod n$, and $p$ divides $n$; therefore $C\equiv M^2\pmod p$
• $p\equiv3\pmod4$ therefore $(p+1)/4$ is an integer, and we can raise the above to that power, giving $$\begin{align} C^{(p+1)/4}&\equiv(M^2)^{(p+1)/4}&&\pmod p\\ C^{(p+1)/4}&\equiv M^{(p+1)/2}&&\pmod p\\ C^{(p+1)/4}&\equiv M\cdot M^{(p-1)/2}&&\pmod p&&(1) \end{align}$$
• If $M\equiv0\pmod p$ :
  • by Fermat's little theorem, and since $p$ is prime, $M^{p-1}\equiv1\pmod p$ holds;
  • define $X=M^{(p-1)/2}\bmod p$ [implying by definition $0\le X<p$ ]; the above becomes $X^2\equiv1\pmod p$, that is $(X+1)(X-1)\equiv0\pmod p$, which has exactly two solutions $X=1$ and $X=p-1$ ;
  • therefore $M\cdot M^{(p-1)/2}\equiv\pm M\pmod p$ ;
• Otherwise [ that is, when $M\equiv0\pmod p$ ]
  • $M\cdot M^{(p-1)/2}\equiv\pm M\pmod p$ holds [both sides are $0\pmod p$ ];
• Replacing in $(1)$, it comes $C^{(p+1)/4}\equiv\pm M\pmod p$ for both cases.