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

If you happen happen to have a message $m ∈ Z_n \backslash Z^*_n$, RSA works but not secure. How likely is it going to happen? $|n|=1024$ bits $|p| = 512$ bits $|q| = 512$ bits.

share|improve this question
Since this is homework: How many elements are in $Z_n$? There are $n=p\cdot q$ right? How many elements are there in $Z_n^*$? There are $\varphi(n)=(p-1)(q-1)$ right? Consequently, the bad event is hitting one of the $n-\varphi(n)$ elements. Is it likely to hit one of those? – DrLecter Mar 26 '14 at 15:49
@user12708: DrLecter was giving you a hint rather than asking you a question. – figlesquidge Mar 26 '14 at 16:06
Yes to all of the assumptions. So, since there n is 1024 bits, φ(n) = φ(p)φ(q), φ(p) = 2^512(1-1/2), φ(q) = 2^512(1-1/2), φ(n) = 2^512(1-1/2)*2^512(1-1/2) = (1/4)2^1024? ... I guess my main problem was, how do I hit the bad condition? – user12708 Mar 26 '14 at 16:09
You still have the wrong value for $\phi(p)$. $\phi(p)$ is defined to be the number of values between 1 and $p-1$ which is relatively prime to $p$. If $p$ is prime, how many of the values between 1 and $p-1$ are relatively prime to $p$? – poncho Mar 26 '14 at 16:14
Ok, now I am more confused...P is 512 bits, so it's range is 0 to 2^512? right? From there ϕ(p) is ϕ(2^512)? – user12708 Mar 26 '14 at 16:22

We know that $|\mathbb{Z}_n| = p\cdot q$ and that $|\mathbb{Z}_n^*| = (p-1)(q-1)$.

So $|\mathbb{Z}_n \backslash \mathbb{Z}^*_n| = (pq) - (p-1)(q-1) = pq - pq + p + q - 1 = p + q -1$. That number is approximately $2^{513}$ given your example prime sizes.

So, out of approximately $2^{1024}$ choices for messages $m$, quite a few are bad. That said, finding one of those is equivalent to factoring. The fastest known method for finding one of these bad messages is to first factor the modulus. Then you can trivially find one.

With just random guessing, each message is equally likely, so has a probability of $\frac{1}{2^{1024}}$, so the probability of finding one of these bad messages is $\frac{2^{513}}{2^{1024}} = \frac{1}{2^{511}}$.

share|improve this answer

Your Answer


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

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