# Paillier cryptosystem break with random number

In the Paillier cryptosystem we choose $$n=p\,q$$ where $$p$$ and $$q$$ are primes, $$g=n+1$$, $$\lambda=\phi(n)$$, $$\mu=\lambda^{-1}\bmod n$$.

The public key is: $$(n,g)$$.

The private key is: $$(\lambda,\mu)$$.

Encryption: choose random $$r$$ ($$0), encryption of message $$m$$ is $$c=(g^m)(r^n)\bmod n^2$$

Decryption: $$m=((c^\lambda\bmod n^2-1)/n)\,\mu\bmod n$$.

I am asking: is it possible to decrypt the ciphertext of the Paillier cryptosystem with knowledge of the random number $$r$$?

• Welcome to crypto-SE. I reformatted the question using MathJax. I have not changed to the usual decryption formula: $m=\bigl\lfloor((c^\lambda\bmod n^2)-1)/n\bigr\rfloor\,\mu\bmod n$, nor added the usual additional requirements $p\ne q$ and $p<2q<4p$. You can of course edit the question, perhaps adding where you are stuck.
– fgrieu
Commented Feb 3, 2023 at 10:46
• Is that homework? That would make the question off-topic unless effort to solve the problem is shown in the question. For now I'll only give hints: with $r$ known, what remains unknown in the equation $c=(g^m)(r^n)\bmod n^2$ ? Work that out using the binomial theorem and elementary properties of$\bmod$.
– fgrieu
Commented Feb 3, 2023 at 11:17
• I've reached this point: c = (nm+1) % (n2) + (rn) % (n**2). what should i do next? Commented Feb 3, 2023 at 13:05
• First, fix it; where did the second + creep in? Next, try to isolate the one unknown. Hint: almost all integers have a multiplicative inverse modulo $n^2$, and it can be efficiently computed, e.g. by the (half) extended Euclidean algorithm. Note: MathJax mostly works in comment too, e.g. $c=(g^m)(r^n)\bmod n^2$ is written $c=(g^m)(r^n)\bmod n^2$.
– fgrieu
Commented Feb 3, 2023 at 13:16
• @poncho: I wrote my proof using the binomial theorem. I scratch my head for another argument that $(n+1)^m\equiv m\,n+1\bmod{n^2}$, or another proof altogether, but nothing happens.
– fgrieu
Commented Feb 19, 2023 at 20:44

Yes, it would be possible to decrypt the ciphertext of the Paillier cryptosystem if the random number $$r$$ leaked.

Encryption if per $$c=(g^m)(r^n)\bmod n^2$$. We know that $$g=n+1$$. Thus $$c=((n+1)^m)(r^n)\bmod n^2$$. By the binomial theorem, $$(n+1)^m=\sum_{k=0}^m\binom n k n^k$$ and $$n^k\bmod n^2=0$$ when $$k>1$$. Therefore, $$(n+1)^m\bmod n^2$$ reduces to $$m\,n+1\bmod n^2$$, and we get $$c=(m\,n+1)(r^n)\bmod n^2$$.

Knowing $$r$$, and $$n$$ being public, we can computes $$s=r^{-1}\bmod n$$, e.g. by the (half) extended Euclidean algorithm. We can then compute $$t=s^n\,c\bmod n^2$$ which is such that $$t=m\,n+1\bmod n^2$$.

And then, since $$0\le m, we can compute $$m$$ as $$(t-1)/n$$.

A comment asks what if $$g$$ is a public generator other than $$n+1$$. We now have $$g^m\equiv r^{-n}\,c\pmod{n^2}$$ where we can compute the Right Hand Side. That allows at least:

• checking a guess of $$m$$
• computing $$m$$ by Baby Step/Giant Step or Pollard's rho for small-enough $$m$$, e.g. when we can perform about $$\mathcal O(\sqrt m)$$ modular multiplications modulo $$n$$ (or modulo $$n^2$$).

I don't rule out there are better attacks that work for larger $$m$$.

• Would a similar attack exist given a different choice of (public) $g$? Commented Mar 19 at 12:09
• @FWDekker: Good question! I expanded the answer, but do not reach a full conclusion.
– fgrieu
Commented Mar 19 at 13:51

Once you know $$r$$, you can remove it from the ciphertext. If $$c=(1+n)^m\bmod n^2$$ then $$m=(c-1)/n\mod n.$$