Subverting the key generation step in RSA public key cryptography I am interested in the ways an RSA key generation implementation can or cannot be subverted so that the subverter has an advantage, but the owner of the key, and the people who interact with the owner, are left unaware that something is going on. I assume that the owner of the key does not have the ability to detect subtle bugs in the key-generation implementation, but that the key will be used for encryption and decryption with standard implementations outside the subverter's control.


My first idea was that a subverted primality test might accept, instead of rejecting, numbers of the form P1*P2 where P1 is a fixed prime known only to the subverter, and P2 a random prime. The owner of the key would end up with a modulus of the form P1*P2*Q, which the rest of the world would not necessarily be able to distinguish from a semiprime number. However, according to this answer, the owner of the key may find themselves unable to crack their own public key, that is, to read messages intended for them. I understand the linked answer to mean that the prime decomposition of the modulus is necessary to read encrypted messages, and in effect, the owner of the key would not have this decomposition. The owner of the key would only have P1*P2 on the one hand and Q on the other hand.
Another idea would be that the prime generation implementation might be subverted in a way such that there exist a million primes P1,P2, …, P1000000 that the implementation is more likely to generate than the others (say, each has probability 1/2000000 to be generated each time). This would, in effect, amount to a private Mining your Ps and your Qs attack(*), reserved for the subverter (who would know the values of P1, …, P1000000) but, as long as the subverted implementation remained in moderate use, unlikely to be detected by anyone else (owner of the key and rest of the world).


(*) It occurs to me after having written the question that the subverter can keep its game preserve more private if the subverted implementation never pairs a prime from the list P1,P2, …, P1000000 with another prime from the list. This doesn't prevent them to be discovered one by one using the original “Mining your Ps and your Qs” attack, but at least they do not unravel all at the same time.

My question is: can 1. be made to work using, say, some sort of pseudoprime instead of a composite number to maliciously accept as prime? Is there a reason why 2. might not work in practice? 

These are two questions but they are related in that they are relevant to the same purpose
I don't think idea 1 can be made to work at all. The main point is that in order to generate a correct secret decryption key, the key generator must know the order of $\mathbb Z^*_n$, i.e., the totient of the modulus $n$.  The generator knows that $n=p \cdot q$, where it believes that $p$ and $q$ are primes, and so it believes that the totient is $(p-1)(q-1)$. But in reality, if $p$ is not prime, the actual totient must be smaller, because the totient of $p$ is strictly less than $p-1$ (and similarly for $q$). So the generator will not be working with the correct totient, and cannot compute a correct secret key. (Technically, all of this assumes that $p$ and $q$ are actually coprime, which the generator can check for itself.)

As for idea 2, it essentially has been implemented in practice, in the sense that several key-generation algorithms having that flaw were deployed and used for years without suspicion. The simplest explanation is that these were accidental rather than malicious flaws, but the same kind of flaw could be deployed maliciously as well.

UPDATE: the "problem" with subversion of type 2 is that the public can discover that many keys share a common prime, and thus learn of the subversion. Here is another kind of subversion that does not have the problem of shared primes, but does allow the subverter to factor the generated modulus. The subverter designs the generation algorithm to choose a prime that is close to the output of a PRF applied to (say) the email address and/or time of day -- some (quasi-)public information that will be associated with the key, which will be unique every time the generator is run.  So the chosen primes will likely never be the same, but the subverter can find them easily using the secret key of the PRF. The only catch is that the PRF secret key must also be hidden in the generator algorithm. A suspicious user might be able to discover the subversion by inspection or by running the algorithm in controlled ways, but not by discovering shared primes across keys (because they do not exist).