Paillier: guessing the message when knowing the cipher and the random number I cannot get my head around this.

In Paillier, the ciphertext is calculated using

$c = g^m.r^n\ mod\ n^2$

where $(n,g)$ forms the public key and $r$ is a random number $0&lt;r&lt;n$.

Assuming an attacker knows $c$, $r$, $n$. and $g$, what would it take  - in average - to find $m$ ?
You don't need to guess, you can find $m$ for sure.

If you know $c,r,n,g$, then you can eliminate $r^n$ from the ciphertext and get $c'=g^m \bmod n^2$.

In $Z_{n^2}^*$, we have $(n+1)^x = 1+nx \bmod n^2$ ($x\in Z_n$). Therefore:


If $g=n+1$ is used, then $c'=g^m \bmod n^2 =1+mn$, then you can find $m=(c'-1)/n$.
If $g\ne n+1$, since the order of $g$ must be a multiple of $n$, we have $g= (1+n)^a=1+an \bmod n^2$ for some $a$, then we can find $a=(g-1)/n$. Then $c'=g^m \bmod n^2 =1+amn$, and we can compute $m=(c'-1)/an$.


Added based on Bruno's comment: the general forumula (for all $g$) is $m=(c'-1)/(g-1)$.