<div dir="ltr"><div dir="ltr"><div class="gmail_default" style="font-size:small"><br></div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Sun, Oct 20, 2019 at 2:58 AM Christian Huitema <<a href="mailto:huitema@huitema.net">huitema@huitema.net</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
  
    
  
  <div>
    <p><br>
    </p>
    <div>On 10/18/2019 7:20 PM, Jonathan
      Thornburg wrote:<br>
    </div>
    <blockquote type="cite">
      <pre>On Thu, Oct 17, 2019 at 04:23:31PM -0400, Phillip Hallam-Baker wrote:
</pre>
      <blockquote type="cite" style="color:rgb(0,0,0)">
        <pre>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.

</pre>
      </blockquote>
      <pre>[[...]]
</pre>
      <blockquote type="cite" style="color:rgb(0,0,0)">
        <pre>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.
</pre>
      </blockquote>
      <pre>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.</pre>
    </blockquote>
    <p><br>
    </p>
    <p>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:<br>
    </p>
    <p>p0 = KDF ("ZAAA-UJUY-H7TF-SFLK-CWAW-TKC4-O5HQ".FromBase32(),
      "P")  <br>
      p = next_prime (p0)</p>
    <p>Suppose that instead of just stating "next_prime (p0)", the
      algorithm tried a series of pseudo random numbers seeded with P0,
      for example:</p>
    <p>p(i+1) = KDF(p(i),"P")</p>
    <p>and stops at the first p(n) that appears to be prime. Would that
      work?</p></div></blockquote><div><span class="gmail_default" style="font-size:small">Easy enough to implement and eliminates the issue. </span> </div></div></div>