In the RSA problem one tries to avoid to pick a message $x \in \mathbb{Z}_N$. 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 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 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 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 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 at 17:09

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.