# Is it possible to calculate the random factor $r$ from a encrypted message and the private key in a Paillier cryptosystem?

I have already done my research and found various sources that state that it is possible but there are also a lot of them that says it is not possible to recover $$r$$. This Q/A on this site for example even states the formula to get it. I don't know if it is wrong or I am missing something since I was not able to make a working implementation of it.

Some friends told me it is impossible to get $$r$$ back since it was raised during encryption to the $$n$$-th power and ended up in a smaller subgroup which results in a loss of information that renders it unable to be recovered.

I asked on reddit and got told the following:

$$r$$ is choosen to be between 0 and $$n^2$$. The plaintext can be between $$0$$ and $$n$$. The Ciphertext is however also between $$0$$ and $$n^2$$. Since the plaintext is fully preserved, the same is impossible for the randomness, as this would otherwise violate the theorem that lossless compression is impossible.

I would like to know whether it is possible to calculate $$r$$ and how it is computed given that I have:

• $$C \to$$ ciphertext
• $$P \to$$ plaintext
• $$N \to$$ public key modulo $$(p\cdot q)$$

Also if it is not possible for all $$r$$ values to be recovered I would like to know if it would be possible to recover $$r$$ values smaller than $$m$$ bits (I know that reducing $$r$$ bit length makes the encryption less secure)

It is strange that Wikipedia propose to choose $$r\mod N^2$$ while $$r^N\mod N^2$$ depends on $$r\mod N$$ only: $$(r+tN)^N=r^N+r^{N-1}tN^2+\ldots\equiv r^N\pmod{ N^2}.$$ It means that you can recover only $$r\mod N.$$ In order to do it you can use the formula from the cited answer $$r\equiv (r^N)^M\pmod{ N},$$ where $$M = N^{-1}\bmod \phi(N)$$.
• So I have: $p = 56039$, $q = 58727$, $n = p·q = 3291002353$, $n^2 = 10830696487451536609$, $\phi(n) = (p-1)·(q-1) = 3290887588$, ciphertext $c$ of $m = 12$ using $r = 7$ $\to c = 6859599884662874753$ I do $P = decrypt(c) = 12$, $c' = c·(1-P·n)\>mod\>n^{2} = 685959988466287475 · (1-12·3291002353)\> mod\> 10830696487451536609 = 2421846566699018322,$ $M = n^{-1}\> mod \>\phi(n) = 3291002353^{-1}\> mod\> 3290887588 = 1169309581,$ $r = c'^M \>mod\> n = 2421846566699018322^{1169309581}\> mod \>3291002353 = 2648362593$ which is not $12$. Am I missing something? – Kranga Sep 29 at 16:52
• @Kranga My calculations give $c=5368334944199256653$, $c'=4487862507998304930$ and $(c′)^M\mod n=7.$ Also here $c'=r^n\mod n^2$. – Alexey Ustinov Sep 30 at 1:50