Re: [Cfrg] Query: Very best practice for RSA key generation

[Phillip Hallam-Baker <[e-mail]>]

Thanks for the info. I will take a look on the next iteration. This is what
I sent out on Friday:

http://mathmesh.com/Documents/draft-hallambaker-mesh-udf.html

One comment on this approach is that rather than using the traditional
nextprime(x) function, it would be more satisfactory to take the next
output from the KDF. This is easy to do:

try KDF (PRK, "p0", l)
try KDF (PRK, "p1", l)
try KDF (PRK, "p2", l)
etc.

Where try is a function that extracts the necessary number of bits, sets
the first and last to 1 and tests for primality. This ensures that there is
an exactly equal probability of choosing every prime in the space rather
than a bias towards primes that are preceded by an empty gap of non primes.

Not that we know of a reason such a gap might be an issue, but it seems
proper to avoid it since we can.

I also plan to add DSA to the draft since it has been requested. The
mechanism for generating the first prime will be the same. The mechanism
for the second prime will be as constrained by the specification.


On Mon, Oct 21, 2019 at 11:25 AM Scott Fluhrer (sfluhrer) <
[e-mail]> wrote:

> Actually, NIST SP 800-56B already defines a number of ways to map a seed
> into an RSA key.  While they’re not perfect (they are overly complex, and
> of course, there are a number of methods and parameters in those methods
> that we’d need to agree upon), however (IMHO) it’d make more sense to start
> from there rather than inventing a new method…
>
>
>
> *From:* Cfrg <[e-mail]> *On Behalf Of * Phillip Hallam-Baker
> *Sent:* Thursday, October 17, 2019 4:26 PM
> *To:* [e-mail]; [e-mail]
> *Subject:* [Cfrg] Query: Very best practice for RSA key generation
>
>
>
> [CC'd to CFRG as this is a crypto question, MATHMESH as the target group,
> OpenPGP as a group that recently asked for the same capability. Also to the
> cryptography list for additional eyes. Looking to add this to the UDF draft
> tomorrow]
>
>
>
> 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.
>
>
>
> The use case here is that the user wants to be able to be very very sure
> the key was correctly generated and that they can recover it. So lets say I
> want to configure OpenPGP with the same keypair on three different machines
> without the full Mesh PKI.
>
>
>
>
>
> The basic idea is that a user has a key which expressed in Base32 looks
> like this:
>
>
>
> ZAAA-UJUY-H7TF-SFLK-CWAW-TKC4-O5HQ
>
>
>
> The first three bytes are
>
> C8     Type code for key generation with 16 bit key type]
>
> 00,00 RSA 2048 bit key pair
>
>
>
> The remaining characters are to provide randomness for the key
> generation function. A minimum of 112 bits (work factor of RSA 2048) are
> required. So 112+24 = 136 bits
>
>
>
> 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.
>
>
>
> I don't plan to do DH. For ECDH, I suggest the NIST and CFRG curves only.
>
>
>
>
>
> OK so some interesting variations. Lets say I don't trust the
> random number generator on any one machine. So lets use Shamir Secret
> sharing on three different machines for a 140 bit output:
>
>
>
> f(1) = SAYE-UHOY-TVZO-LPGT-ZAGE-7JUW-6MTJ-I
> f(2) = SAYX-4HWP-3753-L4P3-N4S6-C2G4-QVPA-A
> f(3) = SAZD-HQNJ-KSDK-HAY7-BIFO-34Y2-NH7O-C
>
>
>
> We can now combine the shares on the target machine to (re)generate the
> keypair. We can also give ourselves a couple of additional shares as well:
>
>
>
> f(4) = SAZW-WBTE-7MJ2-44B6-TC5X-KRKQ-UEEW-U
> f(5) = SA2C-H3IC-2ORN-NOK2-DM3X-OX37-FJ6W-Q
>
>
>
>
>