Is $r_2$ a uniformly at random value in $Z_n$, where $r_2=r_1 . m$

44 Views Asked by At

Let $m$ be an arbitrary value in $Z_n$, where n is RSA modulo (n=p.q, where p and q are large primes). Then have: $r_2=r_1 . m$, where $r_1$ is a value chosen uniformly at random : $r_1\in Z^*_n$.

**Question : Is $r_2$ a uniformly at random value in $Z_n$?

Remark: Given n, it is hard to factorize n into p and q.

1

There are 1 best solutions below

1
On

Stripped of the unnecessary notions regarding probability, the question is asking whether the map $A_m: \mathbb Z_n^* \to \mathbb Z_n^*$ specified as $$A_m(r) \equiv m\cdot r \bmod ~ n, \quad m \in \mathbb Z_n^*$$ is a one-to-one map. If $m$ has a multiplicative inverse $m^{-1}$ in $\mathbb Z_n$, then $A_m(r)$ is a one-to-one map, and the the inverse map is $A_{m^{-1}}(r)$. If $m$ does not have a multiplicative inverse, then $A_m(r)$ is a many-to-one map and the inverse does not exist. For the special case when $n = pq$ is the product of two primes $p$ and $q$, the multiples of $p$ and $q$ do not have multiplicative inverses. This holds even when the primes are large or "safe" as the OP demands they must be.