Subject: [Mathmesh] Query: Very best practice for RSA key generation

From: Phillip Hallam-Baker <[email-masked]>
Date: Thu, 17 Oct 2019 16:25:56 -0400

[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

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Mon, 21 Oct 2019 15:24:54 +0000

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 <[email-masked]> On Behalf Of Phillip Hallam-Baker
Sent: Thursday, October 17, 2019 4:26 PM
To: [email-masked]; [email-masked]
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:

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

p = next_prime (p0)
q = next_prime (q0)

So that is the RSA part.

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:

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:

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Mon, 21 Oct 2019 14:32:25 -0400

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) <
[email-masked]> 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 <[email-masked]> *On Behalf Of * Phillip Hallam-Baker
> *Sent:* Thursday, October 17, 2019 4:26 PM
> *To:* [email-masked]; [email-masked]
> *Subject:* [Cfrg] Query: Very best practice for RSA key generation
>
>
>
> 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:
>
>
>