How to derive a private/public keypair from a random seed?

Question

For RSA, my understanding is that large primes are found randomly to build a private/public keypair. If a static seed can be used in that random search process, it should be possible to derive the same public/private keypair reliably.

For a repeatable discovery of foundational large-primes, the search for random primes might begin with an initial random large number. Then a sequential evaluation of large numbers to detect if they are prime.

This could be used to virtually create a TLS-PSK kind of system but using the more widely deployed TLS algorithms (PSK isn't widely deployed). Therefore, TLS is leveraged and induced to work like a PSK-based system, by using the random seed to find the large primes. That is, the seed value is virtually the PSK "symmetric key". Both parties derive the same private/public keypair from the large primes from the shared seed.

Are there major security flaws with this approach? Are there existing schemes that accomplish such a random seed process?

Advantages achieved:

• Simple central distribution (PKI) - a central control server distributes "seeds" in the same manner as "symmetric passwords" that could conceivably be changed every 15 minutes.
• Tooling - TLS protection with common libraries (eg. C# .Net Framework) - with a "symmetric password" like framework. (DTLS isn't common)

Compared to central keypair generation and distribution:

• Processing is decentralised and more scalable if the central control server only needs to generate a cryptographically-random seed. (The search for the primes happens N times, where N is the amount of nodes using the shared seed).
• Fewer bytes to communicate. If the seed value is fewer bytes than communicating a public/private keypair.

I have a conceptual new secure communication system in mind that would use these advantages.

Answer 1

How to derive a private/public keyset from a random seed?

In principle: seed a Cryptographically Strong Pseudo Random Number Generator with the random seed, and use it to generate the RSA key pair "normally". For the later, we could use FIPS 186-4 B.3.2.

Are there major security flaws with this approach?

Yes, the obvious one: any entity knowing the seed can compute the private key. We need to trust every such entity beyond the designated holder of the private key to only use the seed to compute the public key.

As an aside, deterministic RSA key pair generation may need extra work to be protected from side-channel attacks (timing, power analysis).

There's also a functional issue: RSA key generation is rather slow, and implementations often have no firm stated upper bound on their execution time.

Answer 2

Technical How

For RSA see https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Key_generation

• The distinct prime numbers are required to calculate n as well as for other steps in the process. Therefore separate seeds for p and q would be needed, because they should not be adjacent primes, but both random. Therefore it is infeasible to derive with "a random seed" securely, so the following assumes there are two seeds.
• The primality test for RSA is given https://en.wikipedia.org/wiki/Primality_test. The Fermat primality test "is often used for the key generation phase" of RSA. Iteration through a sequence of integers appears to be feasible.

More pieces of information:

• In the following link you can see it seeds with a random 512 bit odd number. see How are primes generated for RSA?
• A typical size for n is 2048 bits - that is, the key strength for RSA matches n. An n of 1048 bits needs a p of 1024 bits and a q of 1024 bits.
• For the size of a standard RSA keypair "Since the public and private key of a given pair share the same modulus, they also have, by definition, the same "length". see https://security.stackexchange.com/questions/90169/rsa-public-key-and-private-key-lengths
• Therefore, the public key is 2048 bits, and the private key is 2048 bits, and the combined size of a public-private keypair is 4096 bits when p+q bits is 2048. So therefore, two seeds for the primes would be 2048, and at least half the size of the final public-private keypair.
• A standard RSA private key file includes much more than just the "private key", it also includes all of the variables that are used during the process of creating the keypair. This includes p and q, and n (and more). Which would make the two seed values at least 1/3 of the size of the final RSA key file. see https://security.stackexchange.com/questions/90169/rsa-public-key-and-private-key-lengths

---

Practical how

Both of the above are theory, in practice, each key generation libraries might work differently.

If you have control over the key generation algorithm (design or choice of algorithm), then you can certainly iterate through a sequence of integers starting from a seed until a prime value is found. You can also employ a naive sieve to skip over integers such as even integers, and integers ending in 5 or 10. More elaborate sieves also exist.

---

Security

Given that the exchange of the two seeds would occur in a secure manner (as would occur with TLS-PSK), there is practically no difference between transmitting a new key pair or the two seed values to derive a key pair.

---

Useful for scaling

Apart from distributing the processing effort, the seed integers would use half the amount of bytes to transmit and store.

If you are storing this information centrally for 1M devices and cycling keys every 10 minutes, then it's more scalable to work with two-seed-integers than centrally deriving and storing the key pairs.