Sign up ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

If you happen happen to have a message m ∈ Zn \ 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
Also, you have the wrong value for $\phi(p)$. $\;$ – Ricky Demer Mar 26 '14 at 16:08
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

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.