1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 1. Regular TLS authenticates each other with an asymmetric public-key algorithm. TLS-PSK however don't need that, as they authenticates each other with "pre-shared key", so I don't get the point why you'd use the random seed to derive keyset (mis-spelling for keypair?) and what you use those for. 2. public key cannot be directly generated from a seed, it has to involve some calculation with the private key, otherwise, the relationship between the private and the public key cannot be established. $\endgroup$ – DannyNiu Jun 22 at 4:57
  • $\begingroup$ I second DannyNiu's interrogation: what would this (feasible thing) achieve? Any party knowing the secret used to derive the private/public key pair would know the private key (or at least would be able to compute it). $\endgroup$ – fgrieu Jun 22 at 7:57
  • $\begingroup$ I have added an advantages section for the benefit of those who require context beyond the question I am asking. @DannyNiu 1) TLS-PSK is not widely adopted; I'll rename to "keypair" if that's more accurate; 2) "public key cannot be ...." - I am referring to deriving large primes from a seed in a search for large primes, that are subsequently used to generate both private/public keys. $\endgroup$ – Todd Jun 22 at 8:25
  • $\begingroup$ @fgrieu "Any party knowing the secret used to derive the private/public key pair..." - this is the same as TLS-PSK, but this scheme allows common TLS deployments to be leveraged and given PSK-like capabilities. $\endgroup$ – Todd Jun 22 at 8:25
  • $\begingroup$ How would you distribute such a seed? By using a secure transport layer? How would you trust the public key. Add a ephemeral self signed root certificate to the trust store? Otherwise, for key pair generation, you just seed a CSPRNG and then create the public / private key pair. But there are a lot of dangers doing so, e.g. change of the CSPRNG or algorithm may break your scheme. $\endgroup$ – Maarten Bodewes Jun 22 at 8:43
1
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ "any entity knowing the seed can compute the private key" - the same is true of a symmetric key. My OP is about accomplishing this kind of a feature with the existing TLS infrastructure. $\endgroup$ – Todd Jun 22 at 11:18
  • 1
    $\begingroup$ @Todd: if it solve your problem, and everyone is fully aware that the system has the (bearable) performance penalty of asymmetric without its usual security properties, fine. In particular, supposed holders of private keys repudiating the use made of the private key are in a better position than if they had chosen the private key in a way such that they are responsible for its confidentiality. It you want more details on the CSPRNG, and generation procedure, I can add some. $\endgroup$ – fgrieu Jun 22 at 12:52
0
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ You've given an RSA specific overview on RSA key pair generation. You will find likewise Q/A here about RSA key pair generation from a password (which is the same thing, other than requiring an additional strengthening step using a PBKDF). First of all, EC key pair generation is probably less problematic. Second, I don't think this makes the scheme any more practical considering the issues I brought out in the comments below the question. $\endgroup$ – Maarten Bodewes Jun 22 at 11:49
  • $\begingroup$ @MaartenBodewes Thanks for your concern. However, according to my updated answer (I was still working on it), when working at scale, managing the seed-pairs is twice as storage/transmission efficient, and processing can be distributed, and there are no foreseeable security issues given the constraints of the OP question. $\endgroup$ – Todd Jun 22 at 12:04
  • $\begingroup$ Well, I'm glad you satisfied yourself with your answer anyway. $\endgroup$ – Maarten Bodewes Jun 22 at 12:10
  • $\begingroup$ TODO: EC keypair generation process would be interesting for insight. Is the difference between seed and final keypair size smaller? Is the processing difference smaller? How about for post-QC algorithms like lattice-based? $\endgroup$ – Todd Jun 22 at 12:10
  • $\begingroup$ @MaartenBodewes I was hoping this information was on the tip of an expert's brain, I spent over an hour researching it myself, and it might be good trivia for someone else one day. $\endgroup$ – Todd Jun 22 at 12:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.