[Cryptography] Very best practice for RSA key generation

[Jonathan Thornburg]

On Thu, Oct 17, 2019 at 04:23:31PM -0400, Phillip Hallam-Baker wrote:
> A question has come up for generating key pairs from a specified random
> seed. I am just looking to add this to UDF and would like advice as to what
> the very best practices are for RSA keygen.
> 
[[...]]
> 
> To generate keys, HMAC-KDF is used > 
> p0 = KDF ("ZAAA-UJUY-H7TF-SFLK-CWAW-TKC4-O5HQ".FromBase32(), "P")
> q0 = KDF ("ZAAA-UJUY-H7TF-SFLK-CWAW-TKC4-O5HQ".FromBase32(), "Q")
> 
> p = next_prime (p0)
> q = next_prime (q0)
> 
> So that is the RSA part.

This produces a very non-uniform choice of primes (p,q): a prime which
immediately follows a long sequence of non-primes will be chosen much
more often than a similarly-sized prime which has another prime just
slightly smaller than it.

That is, for any prime k, let gap(k) = k - (the largest prime < k).
Then the quoted algorithm will choose k with probability roughly
proportional to gap(k).

For example, using small numbers for convenience, a few consecutive
primes slightly bigger than a million are

   1004797
   1004873
   1004903

Therefore any p0 in the range 1004797 <= p0 < 1004873 would yield p=1004873,
while any p0 in the range 1004873 <= p0 < 1004903 would yield p=1004903.
Since there are 106 numbers in the first range, but only 8 numbers in
the second range, p=1004873 is roughly 13 times more likely to be
chosen than p=1004903.  The same argument obviously applies to q0.

ciao,
-- 
-- "Jonathan Thornburg [remove -animal to reply]" <jthorn at astro.indiana-zebra.edu>
   Dept of Astronomy & IUCSS, Indiana University, Bloomington, Indiana, USA
   currently on the west coast of Canada
   "There was of course no way of knowing whether you were being watched
    at any given moment.  How often, or on what system, the Thought Police
    plugged in on any individual wire was guesswork.  It was even conceivable
    that they watched everybody all the time."  -- George Orwell, "1984"