<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
</head>
<body>
<p><br>
</p>
<div class="moz-cite-prefix">On 10/18/2019 7:20 PM, Jonathan
Thornburg wrote:<br>
</div>
<blockquote type="cite"
cite="mid:20191019022050.GB80263@iron.bkis-orchard.net">
<pre class="moz-quote-pre" wrap="">On Thu, Oct 17, 2019 at 04:23:31PM -0400, Phillip Hallam-Baker wrote:
</pre>
<blockquote type="cite" style="color: #000000;">
<pre class="moz-quote-pre" wrap="">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 class="moz-quote-pre" wrap="">[[...]]
</pre>
<blockquote type="cite" style="color: #000000;">
<pre class="moz-quote-pre" wrap="">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 class="moz-quote-pre" wrap="">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>
<p>-- Christian Huitema<br>
</p>
</body>
</html>