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.
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.
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.
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.
No, it seems to suggest that some version of the GPG software, under some conditions, erroneously generated a terribly weak key. It's a software (or even malware) issue rather than a mathematical issue.
The article claims that a well-known person in Linux kernel etc. communities has a 4096-bit RSA private key with two "factors", one of which is 231 (which is itself not prime).
Standard RSA involves a private key which is the product of two prime numbers, and when we talk about "4096-bit RSA", we generally mean that the private key is the product of two 2048-bit numbers. Due to randomness, they might actually be 2047- or 2049-bit or something, but having one 8-bit prime and one 4088-bit prime -- let alone one 8-bit composite number -- is generally not what we mean by 4096-bit RSA, nor what software is intended to generate. It's well-known that the strength of an RSA key is restricted to the size of its smallest prime factor. (When I TA'd a crypto class a few years ago, I gave a homework assignment to break a "512-bit" RSA key that was intentionally generated as a 50-bit prime and a 462-bit prime: the entire class was able to factor it without even thinking about hardware beyond their personal laptops.)
So the mystery is not so much how it was factored, but how the key was generated that way in the first place, and whether this was even an intentional part of this person's PGP key. Other comments here imply that this particular subkey isn't even usable, so the answer to the second part seems like "not really".
An RSA public key consists of a modulus n and an exponent e. Modulus n is a product of two large primes, p and q. If one knows p or q, one can derive the private key corresponding to the given public key.
A typical GPG public key contains one or more RSA moduli, depending on the number of sub-keys.
Under certain conditions, a public key modulus will share a common factor with an existing modulus belonging to someone else. This may happen if both keys were generated on a system with a thoroughly-broken entropy source, or if a particular GPG implementation has been back-doored.
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.