<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>