[Cryptography] Very best practice for RSA key generation

[John-Mark Gurney]

Phillip Hallam-Baker wrote this message on Sun, Oct 20, 2019 at 18:51 -0400:
> On Sun, Oct 20, 2019 at 2:58 AM Christian Huitema <huitema at huitema.net>
> wrote:
> 
> >
> > On 10/18/2019 7:20 PM, Jonathan Thornburg wrote:
> >
> > 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.
> >
> >
> > So you are saying that because the spacing between primes varies, the
> > method that Phil's proposed will introduces a bias in the selection of
> > primes. This seems directly tied to Phil's specification:
> >
> > p0 = KDF ("ZAAA-UJUY-H7TF-SFLK-CWAW-TKC4-O5HQ".FromBase32(), "P")
> > p = next_prime (p0)
> >
> > Suppose that instead of just stating "next_prime (p0)", the algorithm
> > tried a series of pseudo random numbers seeded with P0, for example:
> >
> > p(i+1) = KDF(p(i),"P")
> >
> > and stops at the first p(n) that appears to be prime. Would that work?
> >
> Easy enough to implement and eliminates the issue.

Would want to fix the last bit to 1 (or it on) so you don't run the KDF
extra times, eliminating the even numbers.

-- 
  John-Mark Gurney				Voice: +1 415 225 5579

     "All that I will do, has been done, All that I have, has not."