# Distinguishing generators of RSA primes and moduli

We are trying to distinguish two RSA prime generators:

1. Prime generator 1

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

• draw uniformly at random an integer $$p$$ with $$2^{1023.5}
• 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.

• There was a paper that was dedicated to identifying which library generated a given RSA key. It should cover these two strategies. However I'm unable to find it right now. – SEJPM Feb 6 '19 at 12:38
• – kelalaka Feb 6 '19 at 13:15
• The question's bias is briefly discussed in the above paper, on top of page 19. Primes preceded by larger “gaps” will be selected with slightly higher probability; however, this bias is not observable from the distribution of the primes. But the conclusion in the second part of that sentence is wrong. – fgrieu Feb 6 '19 at 14:39
• "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." I think this claim merits justification, it's not self-evident at face value (to me at least). – puzzlepalace Feb 6 '19 at 20:52
• @puzzlepalace: note $p_i$ the $i^\text{th}$ prime. In generator 2, $p_i$ is generated when the one draw at the first generation step led to $p$ such that $p_{i-1}<p\le p_i$. Therefore, a $p_i$ in the interval $(2^{1023.5},2^{1024})$ (except the lowest such $p_i$) is picked with probability proportional to $p_i-p_{i-1}$, a non-constant quantity, computable from the output of the generator. Contrast with generator 1, which picks every prime in said interval with the same probability. – fgrieu Feb 7 '19 at 9:57