Distinguishing generators of RSA primes and moduli

Question

We are trying to distinguish two RSA prime generators:

1. Prime generator 1

   • draw uniformly at random an integer $p$ with $2^{1023.5}<p<2^{1024}$, until it is prime
   • output $p$.

2. Prime generator 2

   • draw uniformly at random an integer $p$ with $2^{1023.5}<p<2^{1024}$
   • while $p$ is composite, $p\gets p+1$
   • output $p$.

We can distinguish these generators from their output: the primes generated per 2 are on average farther away from the prime immediately below than are the primes generated per 1.

What advantage do we get from the above distinguisher?

Can we make a distinguisher with sizable advantage from the distribution of $p\bmod \mathtt{e221f97c30e94e1d}_{16}$ ? That 64-bit constant is the product of the odd primes to $53$. If yes, what's the advantage?

Now we derive two generators of RSA moduli, by multiplying two consecutive outputs of each of these prime generators. Can we make a distinguisher with sizable advantage, even though we can't factor the moduli? If yes, what's the advantage?

Motivation is recognizing if RSA keys are generated using this.

Answer 1

This has been examined before, for example in Fouque and Tibouchi (2001). It's been brought up in a number of places in online forums as well, though not with any sort of resolution.

I agree with this statement from F/T: "Moreover, even for more common uses of prime number generation, like RSA key generation, it seems preferable to generate primes that are almost uniform, so as to avoid biases in the RSA moduli themselves, even if it is not immediately clear how such biases can help an adversary trying to factor the moduli."

It is very easy for people to fall into the "proof by failure of imagination" trap. Well I can't think of any way to do it, so it's good. There are a lot of areas in life where this is an efficient strategy, but cryptography should avoid this compromise where possible. Just because we can't think of a way to exploit it now, why should we leave this very large bias when we know how to do much better with almost no loss of efficiency?

It's easy to implement PRIMEINC, and while just as easy to implement, TRIVIAL without optimizations is slower. Effective optimizations of the latter require some thought, coding, and testing. Most consumers honestly do not care (edit: they should, but evidence is that quality isn't a big priority until something obviously breaks). Also I see most packages like the OP's referenced pycrypto are really simple -- finding a hundred lines of optimized random prime generation would be out of place there. This does have the advantage of readability and debugging. But we can do this both better (more uniformly) and faster if we want.

The provable prime generators don't have this same issue, but they do generate only a subset of the primes in the range. Both Shawe-Taylor and Maurer spend a large portion of their papers going over the distribution and implications.