News for hackers. Stuff that matters.
Re:4096 RSA key in the strongset factored? by strags on Sunday May 17, 2015 @02:59PM (#9561239)
I've always wondered about this.

Wikipedia says ( http://en.wikipedia.org/wiki/RSA_(cryptosystem) ): "When m is not relatively prime to n, the argument just given is invalid. This is highly improbable (only a proportion of 1/p + 1/q − 1/(pq) numbers have this property), but even in this case the desired congruence is still true. Either m ≡ 0 (mod p) or m ≡ 0 (mod q), and these cases can be treated using the previous proof.".

I'm not sure I follow 100% - perhaps someone smarter can explain.

Re:4096 RSA key in the strongset factored? by contravariant on Sunday May 17, 2015 @03:09PM (#9561283)
I think that's a different problem, although it is not entirely irrelevant since having a small prime factor like 3 implies that that the method will fail in at least 1/3 of the cases.

The other problem is that the value φ(n) will be wrong, even then there are some rare cases where the method might still work (see eximius comment about carmicheal numbers) but those are exceedingly rare.