Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

$m$ is arbitrary value in $Z_n$, where n is RSA modulo. Then we do: $r_2=r_1 . m (modn)$, where $r_1$ is a random value such that $r_1\in Z^*_n$.

** Question(1): is $r_2$ a uniformly at random value in $Z_n$?

**Question(2): Would this be secure: $r_2=r_1 . m (modn)$ (where $m\in Z_n$ and $r_1\in Z^*_n$ )?

share|improve this question
Hint: What is the condition making $f: r_1\to f(r_1)=r_2=r_1\cdot m\bmod n$ a bijection over $Z^*_n$? $\;$ And how likely is that condition assuming $m$ is defined without knowledge allowing the factorization of $n$? – fgrieu Oct 21 '14 at 10:32
@fgrieu Got a bit confused – user153465 Oct 21 '14 at 10:38
Rephrased without a question mark: $\;$ Show that if $m$ has a multiplicative inverse in $Z^*_n$, then $f: r_1\to f(r_1)=r_2=r_1\cdot m\bmod n$ is an injection from $Z^*_n$ to itself. $\;$ Show that if an $m$ chosen in $Z^*_n$ without knowledge allowing the factorization of $n$ had sizable odds of having no multiplicative inverse, it would be easy to factor $n$. $\;$ Conclude about what we can safely assume about $f$ (noticing $Z^*_n$ is a finite set); then about what that implies for $r_2$ if $r_1$ is uniformly random. – fgrieu Oct 21 '14 at 11:51
@user153465: the answer to question 1 is "no"; if $m$ is an arbitrary value, consider the case that $m=0$; obviously in that case, $r_2$ is not a uniform random value. For the answer to question 1 to be "yes", we need to put restrictions on the distribution $m$ is chosen from (specifically, that probabilities that $m$ is a multiple of $p$, $q$ and $pq$ must be $1/p$, $1/q$ and $1/pq$) – poncho Oct 21 '14 at 13:49
@user153465: indeed, to answer Question 1 by the affirmative, we need to replace arbitrary value in $Z_n$ with random in $Z_n$ (as Poncho did), or chosen in $Z^*_n$ without knowledge of the factorization of $n$ (as I did). $\;$ Question 2 as currently worded is not answerable by yes or no until both this and secure are better defined. – fgrieu Oct 21 '14 at 14:17

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.