# $m ∈ Z_n \backslash Z^*_n$, RSA works but not secure

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.

-
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}}$.