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

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

[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