Skip to main content
replaced http://crypto.stackexchange.com/ with https://crypto.stackexchange.com/
Source Link

The method mentioned in the answeranswer by MaartenMaarten will allow you to reduce the private key size for any public key algorithm by regenerating the key from a random seed, each time you need it.

The drawback is the performance. Each time you need to use the key you need to spend as much CPU time for regenerating the key as you used for generating it the first time. However by analyzing how the CPU time is spent during RSA key generation, it is possible to improve performance.

In order to find a suitable prime the RSA key generation tries many different numbers - most of which have to be discarded because they are not primes. And each candidate requires CPU time to decide whether it is prime.

Once the first candidate has been generated using a specific seed and found not to be prime, you can continue generating another candidate using the next random numbers from the PRNG. A better approach however is to simply discard the seed which did not produce a suitable prime immediately. Instead continue trying new seeds until a suitable prime has been found.

This procedure can be repeated until two seeds have been found, which each produce a suitable prime as the very first candidate. Now storing those two seeds will be sufficient to work as secret key.

The advantage is that when using the private key there is no need to run the primality test because the seeds are already known to produce primes as the first candidate. This will not be much slower to use than an ordinary RSA secret key.

The method mentioned in the answer by Maarten will allow you to reduce the private key size for any public key algorithm by regenerating the key from a random seed, each time you need it.

The drawback is the performance. Each time you need to use the key you need to spend as much CPU time for regenerating the key as you used for generating it the first time. However by analyzing how the CPU time is spent during RSA key generation, it is possible to improve performance.

In order to find a suitable prime the RSA key generation tries many different numbers - most of which have to be discarded because they are not primes. And each candidate requires CPU time to decide whether it is prime.

Once the first candidate has been generated using a specific seed and found not to be prime, you can continue generating another candidate using the next random numbers from the PRNG. A better approach however is to simply discard the seed which did not produce a suitable prime immediately. Instead continue trying new seeds until a suitable prime has been found.

This procedure can be repeated until two seeds have been found, which each produce a suitable prime as the very first candidate. Now storing those two seeds will be sufficient to work as secret key.

The advantage is that when using the private key there is no need to run the primality test because the seeds are already known to produce primes as the first candidate. This will not be much slower to use than an ordinary RSA secret key.

The method mentioned in the answer by Maarten will allow you to reduce the private key size for any public key algorithm by regenerating the key from a random seed, each time you need it.

The drawback is the performance. Each time you need to use the key you need to spend as much CPU time for regenerating the key as you used for generating it the first time. However by analyzing how the CPU time is spent during RSA key generation, it is possible to improve performance.

In order to find a suitable prime the RSA key generation tries many different numbers - most of which have to be discarded because they are not primes. And each candidate requires CPU time to decide whether it is prime.

Once the first candidate has been generated using a specific seed and found not to be prime, you can continue generating another candidate using the next random numbers from the PRNG. A better approach however is to simply discard the seed which did not produce a suitable prime immediately. Instead continue trying new seeds until a suitable prime has been found.

This procedure can be repeated until two seeds have been found, which each produce a suitable prime as the very first candidate. Now storing those two seeds will be sufficient to work as secret key.

The advantage is that when using the private key there is no need to run the primality test because the seeds are already known to produce primes as the first candidate. This will not be much slower to use than an ordinary RSA secret key.

Source Link
kasperd
  • 1.4k
  • 1
  • 10
  • 23

The method mentioned in the answer by Maarten will allow you to reduce the private key size for any public key algorithm by regenerating the key from a random seed, each time you need it.

The drawback is the performance. Each time you need to use the key you need to spend as much CPU time for regenerating the key as you used for generating it the first time. However by analyzing how the CPU time is spent during RSA key generation, it is possible to improve performance.

In order to find a suitable prime the RSA key generation tries many different numbers - most of which have to be discarded because they are not primes. And each candidate requires CPU time to decide whether it is prime.

Once the first candidate has been generated using a specific seed and found not to be prime, you can continue generating another candidate using the next random numbers from the PRNG. A better approach however is to simply discard the seed which did not produce a suitable prime immediately. Instead continue trying new seeds until a suitable prime has been found.

This procedure can be repeated until two seeds have been found, which each produce a suitable prime as the very first candidate. Now storing those two seeds will be sufficient to work as secret key.

The advantage is that when using the private key there is no need to run the primality test because the seeds are already known to produce primes as the first candidate. This will not be much slower to use than an ordinary RSA secret key.