7
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – SEJPM Feb 6 at 12:38
  • 3
    $\begingroup$ @SEJPM is this The Million-Key Question - Investigating the Origins of RSA Public Keys $\endgroup$ – kelalaka Feb 6 at 13:15
  • 2
    $\begingroup$ 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. $\endgroup$ – fgrieu Feb 6 at 14:39
  • 2
    $\begingroup$ "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). $\endgroup$ – puzzlepalace Feb 6 at 20:52
  • 3
    $\begingroup$ @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. $\endgroup$ – fgrieu Feb 7 at 9:57
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.