[ingenter]

RSA is not broken per se. (AFAIK) If you have a 4096-bit key, nobody is able to factor a 4096-number yet.

However, using a bad random prime generator might lead to birthday attack when someone is using the same prime as you. Having two keys that share a prime, it is possible to factor both.

Also, one of the "primes" used is 231, which is extremely stupid, its factors 3711, so there are two keys that are using the same non-prime number as one of "prime" factors for the key. And one of its factors is motherfucking second prime.

I suspect it's a backdoor or a blatant error in RSA key generator or prime checker.

[contravariant]

Wouldn't RSA just fail if you used a non-prime factor? You shouldn't be able to decrypt any messages if you calculate the totient incorrectly, and for a public key pq, if either p or q isn't prime then (p-1)(q-1) won't be the totient.

[strags]

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.

[contravariant]

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.

[eximius]

http://en.m.wikipedia.org/wiki/Carmichael_number

[contravariant]

I suppose that would work, although with a factor of 3 more than 1/3 of all inputs are not relatively prime so in those cases it would fail anyway.