[Cryptography] How to counter the security risks of shared prime factors among RSA moduli employed in practice?

[Arnold Reinhold]

On Thu, 21 Jan 2016 12:00, mok-kong shen asked:

> If any reader has a nice idea for an RSA backdoor, I should appreciate 
> it very
> much to learn it and would volunteer to attempt to do an implementation to
> prove its practicality.

I think the simplest backdoor is to constrain the random number generated to start the search for one of the one of the primes to have a small enough state space so that searching all possible primes is feasible. The simplest scheme might be to use a randomly seeded 32-bit PRNG. More sophisticated schemes might seed a larger PRNG in part with data that could partially be guessed, such as the date and hour of key generation or the user name to avoid birthday paradox collisions between different key pairs. The PRNG might also contain some secret parameters known only to the attacker. Of course this sort of attack applies to other public key systems as well.

Arnold Reinhold