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)


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.
| improve this answer | |
  • $\begingroup$ the first case is when M is not equal to 0 modp... then use can use Fermat $\endgroup$ – Talor T Jul 25 '17 at 7:33

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.