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

[mok-kong shen]

[Addendum] While in my OP the possibility of exploiting a certain kind of
backdoors was used to support my urgent plea of having a publically 
certified
open-source software for RSA key generation, the realization of such
certifications would understandably anyway require much time and 
certainly not
be easy in practice.

In order however to render the issue in any case sensitive in the minds 
of all
those who really care for their own IT security, I like to stress the 
fact that
there are much more sophisticated schemes of embedding backdoors into
non-open-source RSA key generation software that lie clearly beyond the 
feasible
realm of studies of the kind done by A. K. Lenstra et al. In other 
words, the
security risks that are looming could in fact be extremely hideous and thus
outside of the consciousness of the victims at all.

One nice backdoor scheme of the said genre is due to maartin, who gave 
in an
Internet discussion many years ago a sketch of his idea, albeit 
unfortunately
in such short wordings that it was apparently not closely examined by the
readers at that time and henceforth entirely ignored. I recently remembered
maartin's idea and tried it out in an implementation sketched in the 
following:

Suppose one generates RSA keys with modulus n = p*q > 2**mb for mb=2000.
Generate a pseudo-random comparatively small, say 256-bit, value head to 
be the
leading part of n. Use head as a parameter to uniquely generate a prime 
p of
mb//2 bits. Different ways of designing such a unique mapping are obviously
conceivable. In my implementation head is used to seed a PRNG to generate a
pseudo-random mb//2-bit value ptemp and one finds the next prime p after 
ptemp
with Miller-Rabin. Let ltail = mb + 2 - 256. Generate a pseudo-random 
value tail
of ltail bits. Concatenate head and tail to be ntemp. With qtemp = 
ntemp//p find
the next prime q after qtemp with Miller-Rabin. Compute n = p*q. If n < 
2**mb,
which is of fairly low probability in practice, repeat the above procedure.
This way, the n generated will have its leading 256 bits identical to head.
Thus a person knowing this backdoor can simply get the value of head from n
and with it recover p in the way mentioned above and obtain then q and e and
d, i.e. everything of the original RSA key generation.

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.

M. K. Shen