In the RSA problem, picking a message $x \in \mathbb{Z}_N \setminus \mathbb{Z}_N^*$ implies factorizing $N$. Since factorization with respect to the standard RSA generator is hard assuming the RSA problem is hard, it is likely that selecting $x \in \mathbb{Z}_N \setminus \mathbb{Z}_N^*$ is hard. Thus, one may ask the question:

Given $x$ uniformly distributed over $\mathbb{Z}_N$ what is the probability that $x \notin \mathbb{Z}_N^*?$

with the hope that it is negligible. So I write:

$P[x \notin \mathbb{Z}_N^*] = 1 - \frac{\phi(N)}{N} = \frac{1}{p}+\frac{1}{q} - \frac{1}{pq}$

However, how does one prove this is negligible?

  • $\begingroup$ Hint: $p$ and $q$ both are large, including much larger than $4^k$ for $k$-bit security. Note: since you hypothesized that $N=p\,q$ with primes $p$ and $q$ such that $\phi(N)=(p-1)(q-1)$, you must have $p\ne q$; and then it is no longer necessary to restrict to $\Bbb Z_N^*$ for RSA; see Does RSA work for any message $m$. $\endgroup$
    – fgrieu
    Feb 1 '19 at 16:32
  • 1
    $\begingroup$ "one tries to avoid to pick a message $x \in \mathbb Z_N$" Whatever you meant to say here, it's probably wrong. $\endgroup$
    – fkraiem
    Feb 1 '19 at 16:45
  • $\begingroup$ @fkraiem Probably $x\in \mathbb{Z}_N\setminus \mathbb{Z}_N^*$. Though, yes you do not try to avoid it, you just need that it doesn't happen except with negligible probability. $\endgroup$
    – Maeher
    Feb 1 '19 at 16:56
  • $\begingroup$ @Maeher Well, clearly if you can produce such an $x$, you can factor $N$, so it should go without saying that it is infeasible. ;) $\endgroup$
    – fkraiem
    Feb 1 '19 at 17:02
  • $\begingroup$ Basically, "one tries to avoid" makes it sound like "you could do it if you wanted to, but it's better not to", while in fact you just can't. $\endgroup$
    – fkraiem
    Feb 1 '19 at 17:09

With fgrieu's idea:

If we consider the generator working on a security parameter of $n$ bits (meaning resistance to $\mathcal O(2^n)$ computational effort), then each of the prime $p$ and $q$ must be at least (about) $n$-bit, otherwise trial division would factor the public modulus. Then, $N=p\,q$ with $p$ and $q$ distinct primes at least $2^n$ implies $P[x \notin \mathbb{Z}_N^*]=1-\frac{(p-1)(q-1)}{p\,q}<\frac1p+\frac1q<\frac2{2^n}$, that is $\mathcal O(2^{-n})$ which is negligible.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.