Skip to main content
Cryptography

Return to Answer

typo
Source Link
Thomas Pornin
Thomas Pornin
  • 87.8k
  • 16
  • 246
  • 314

What you suggest is valid. Here is a way to show it:

In a fully implemented signature system (things are similar for asymmetric encryption), there are three modules:

  • a key pair generator, which produces a pseudo-random key pair;
  • a signature generator, which uses the private key to produce a signature over some piece of data;
  • a signature verifier, which verifies a signature over some piece of data, using the public key.

It is acceptable that the key pair generator is a deterministic algorithm, provided that it is "cryptographically strong" and works over a "long enough" secret seed. "Long enough" means: a string of length at least $t$ bits if a security level of $2^t$ must be achieved.

What you suggest is simply storing the PRNG seed instead of storing the output of the key pair generator. You run the PRNG again each time you want to use the private key. Since the PRNG is deterministic, this yields the exact same signatures that you would have obtained if you had stored the private key, so, from the outside, this is indistinguishable from the "normal" setup. Hence the security.

The concept is applicable to any asymmetric algorithm, not just EC-based algorithms. You could do so with, e.g., RSA, using the PRNG to regenerates the primes $p$ and $q$. However, for RSA, the cost would be high (generating a private key is considerably more expensive than actually computing a signature) and the generation process is susceptible to partial leakage through timing attacks, so this would be a bit delicate. For algorithms such as DSA, Diffie-Hellman or ElGamal, or their EC variants, a private key is just a random value modulo a given $q$ (the group order), so that's fast.

The only tricky point is to show that "one SHA-256 invocation" is a suitable, cryptographically strong PRNG, when you only want 256 bits of pseudo-alea. In the random oracle model, no problem. In a practical world of standard compliance and administrative acceptance, you might onewant to use an Approved PRNG, in particular HMAC_DRBG (that's the one NIST considers to be "the strongest").

Note: it is not strictly necessary to have an unbiased selection of the private key. For (EC)DSA, there is a private key $x$, and, for each signature, a new random $k$ modulo $q$ must be generated. It is crucial that $k$ is negligibly biased; but for $x$, you can be a bit more lenient. For instance, for a curve where the subgroup order $q$ has size 256 bits or more, it suffices to generate a single 256-bit integer, and reduce it modulo $q$. Some values may have a twice higher chance of being selected than others, or, if the size of $q$ is greater than 256 bits, some values have probability zero of being selected; but this is not an issue for $x$. For $k$, this would be a very serious problem.

What you suggest is valid. Here is a way to show it:

In a fully implemented signature system (things are similar for asymmetric encryption), there are three modules:

  • a key pair generator, which produces a pseudo-random key pair;
  • a signature generator, which uses the private key to produce a signature over some piece of data;
  • a signature verifier, which verifies a signature over some piece of data, using the public key.

It is acceptable that the key pair generator is a deterministic algorithm, provided that it is "cryptographically strong" and works over a "long enough" secret seed. "Long enough" means: a string of length at least $t$ bits if a security level of $2^t$ must be achieved.

What you suggest is simply storing the PRNG seed instead of storing the output of the key pair generator. You run the PRNG again each time you want to use the private key. Since the PRNG is deterministic, this yields the exact same signatures that you would have obtained if you had stored the private key, so, from the outside, this is indistinguishable from the "normal" setup. Hence the security.

The concept is applicable to any asymmetric algorithm, not just EC-based algorithms. You could do so with, e.g., RSA, using the PRNG to regenerates the primes $p$ and $q$. However, for RSA, the cost would be high (generating a private key is considerably more expensive than actually computing a signature) and the generation process is susceptible to partial leakage through timing attacks, so this would be a bit delicate. For algorithms such as DSA, Diffie-Hellman or ElGamal, or their EC variants, a private key is just a random value modulo a given $q$ (the group order), so that's fast.

The only tricky point is to show that "one SHA-256 invocation" is a suitable, cryptographically strong PRNG, when you only want 256 bits of pseudo-alea. In the random oracle model, no problem. In a practical world of standard compliance and administrative acceptance, you might one to use an Approved PRNG, in particular HMAC_DRBG (that's the one NIST considers to be "the strongest").

Note: it is not strictly necessary to have an unbiased selection of the private key. For (EC)DSA, there is a private key $x$, and, for each signature, a new random $k$ modulo $q$ must be generated. It is crucial that $k$ is negligibly biased; but for $x$, you can be a bit more lenient. For instance, for a curve where the subgroup order $q$ has size 256 bits or more, it suffices to generate a single 256-bit integer, and reduce it modulo $q$. Some values may have a twice higher chance of being selected than others, or, if the size of $q$ is greater than 256 bits, some values have probability zero of being selected; but this is not an issue for $x$. For $k$, this would be a very serious problem.

What you suggest is valid. Here is a way to show it:

In a fully implemented signature system (things are similar for asymmetric encryption), there are three modules:

  • a key pair generator, which produces a pseudo-random key pair;
  • a signature generator, which uses the private key to produce a signature over some piece of data;
  • a signature verifier, which verifies a signature over some piece of data, using the public key.

It is acceptable that the key pair generator is a deterministic algorithm, provided that it is "cryptographically strong" and works over a "long enough" secret seed. "Long enough" means: a string of length at least $t$ bits if a security level of $2^t$ must be achieved.

What you suggest is simply storing the PRNG seed instead of storing the output of the key pair generator. You run the PRNG again each time you want to use the private key. Since the PRNG is deterministic, this yields the exact same signatures that you would have obtained if you had stored the private key, so, from the outside, this is indistinguishable from the "normal" setup. Hence the security.

The concept is applicable to any asymmetric algorithm, not just EC-based algorithms. You could do so with, e.g., RSA, using the PRNG to regenerates the primes $p$ and $q$. However, for RSA, the cost would be high (generating a private key is considerably more expensive than actually computing a signature) and the generation process is susceptible to partial leakage through timing attacks, so this would be a bit delicate. For algorithms such as DSA, Diffie-Hellman or ElGamal, or their EC variants, a private key is just a random value modulo a given $q$ (the group order), so that's fast.

The only tricky point is to show that "one SHA-256 invocation" is a suitable, cryptographically strong PRNG, when you only want 256 bits of pseudo-alea. In the random oracle model, no problem. In a practical world of standard compliance and administrative acceptance, you might want to use an Approved PRNG, in particular HMAC_DRBG (that's the one NIST considers to be "the strongest").

Note: it is not strictly necessary to have an unbiased selection of the private key. For (EC)DSA, there is a private key $x$, and, for each signature, a new random $k$ modulo $q$ must be generated. It is crucial that $k$ is negligibly biased; but for $x$, you can be a bit more lenient. For instance, for a curve where the subgroup order $q$ has size 256 bits or more, it suffices to generate a single 256-bit integer, and reduce it modulo $q$. Some values may have a twice higher chance of being selected than others, or, if the size of $q$ is greater than 256 bits, some values have probability zero of being selected; but this is not an issue for $x$. For $k$, this would be a very serious problem.

Source Link
Thomas Pornin
Thomas Pornin
  • 87.8k
  • 16
  • 246
  • 314

What you suggest is valid. Here is a way to show it:

In a fully implemented signature system (things are similar for asymmetric encryption), there are three modules:

  • a key pair generator, which produces a pseudo-random key pair;
  • a signature generator, which uses the private key to produce a signature over some piece of data;
  • a signature verifier, which verifies a signature over some piece of data, using the public key.

It is acceptable that the key pair generator is a deterministic algorithm, provided that it is "cryptographically strong" and works over a "long enough" secret seed. "Long enough" means: a string of length at least $t$ bits if a security level of $2^t$ must be achieved.

What you suggest is simply storing the PRNG seed instead of storing the output of the key pair generator. You run the PRNG again each time you want to use the private key. Since the PRNG is deterministic, this yields the exact same signatures that you would have obtained if you had stored the private key, so, from the outside, this is indistinguishable from the "normal" setup. Hence the security.

The concept is applicable to any asymmetric algorithm, not just EC-based algorithms. You could do so with, e.g., RSA, using the PRNG to regenerates the primes $p$ and $q$. However, for RSA, the cost would be high (generating a private key is considerably more expensive than actually computing a signature) and the generation process is susceptible to partial leakage through timing attacks, so this would be a bit delicate. For algorithms such as DSA, Diffie-Hellman or ElGamal, or their EC variants, a private key is just a random value modulo a given $q$ (the group order), so that's fast.

The only tricky point is to show that "one SHA-256 invocation" is a suitable, cryptographically strong PRNG, when you only want 256 bits of pseudo-alea. In the random oracle model, no problem. In a practical world of standard compliance and administrative acceptance, you might one to use an Approved PRNG, in particular HMAC_DRBG (that's the one NIST considers to be "the strongest").

Note: it is not strictly necessary to have an unbiased selection of the private key. For (EC)DSA, there is a private key $x$, and, for each signature, a new random $k$ modulo $q$ must be generated. It is crucial that $k$ is negligibly biased; but for $x$, you can be a bit more lenient. For instance, for a curve where the subgroup order $q$ has size 256 bits or more, it suffices to generate a single 256-bit integer, and reduce it modulo $q$. Some values may have a twice higher chance of being selected than others, or, if the size of $q$ is greater than 256 bits, some values have probability zero of being selected; but this is not an issue for $x$. For $k$, this would be a very serious problem.