[Cryptography] Very best practice for RSA key generation

Phillip Hallam-Baker phill at hallambaker.com
Sun Oct 20 18:51:09 EDT 2019


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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://www.metzdowd.com/pipermail/cryptography/attachments/20191020/c00d10a3/attachment.htm>


More information about the cryptography mailing list