[Cryptography] Very best practice for RSA key generation

Christian Huitema huitema at huitema.net
Sun Oct 20 02:58:46 EDT 2019

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?

-- Christian Huitema

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://www.metzdowd.com/pipermail/cryptography/attachments/20191019/e3b77c75/attachment.htm>

More information about the cryptography mailing list