2

I'm new to security and crpyto, I know that Public/Private keys are generated in a different way depending on the used algorithm,
But let's take RSA as an instance (Using prime numbers),
Does the algorithm generate keys randomly or in a structured way?

I mean if I asked for a public/private key, would the algorithm:
- Generate random prime numbers and then generate from them the Public/Private key? OR
- It has for example a database that contains all of the keys that it has generated before, and then compares new keys to them to avoid collision?

OR how can it ensure that that generated public/private key has been never generated before?

Yousef Gamal
  • 123
  • 5

1 Answers1

3

The way random prime generation works is by generating a huge, random odd number of a specific size (e.g. 2048 bits). It is then checked for primality. If it is not prime, it is incremented by two and checked again. This repeats until it is found to be prime. I describe this more in another answer.

There is nothing specific that prevents two private keys from being the same, but the probability of that is so astronomically low as to be irrelevant. There's no reason to explicitly try to avoid collisions. Note that this assumes the system has a good source of random numbers. Bugged random number generators or embedded systems with a poor source of randomness may generate RSA moduli who share a prime factor, leading to trivial cryptanalysis by checking for the greatest common denominator between two moduli and then dividing them by the result to obtain both prime factors.

See also What are the odds of an RSA private key collision?

Glorfindel
  • 2,235
  • 6
  • 18
  • 30
forest
  • 64,616
  • 20
  • 206
  • 257
  • But why there's no way implemented to prevent two private keys from being the same? I know it's very low probability of this to happen BUT still there's a chance for it to happen. – Yousef Gamal Nov 10 '18 at 06:21
  • @YousefGamal The chance is lower than the chance that your encryption key happens to be all zeros, just by chance. It's low enough that you could safely bet the life of everyone on Earth that it will never happen due to chance and you would still be safe. – forest Nov 10 '18 at 06:26
  • @YousefGamal And such a test would be so easy. All you'd need to do is download *all* public keys of *all* current and expired certificates from *all* current and expired CAs and see if they work as public key for your suggested private key ... – Hagen von Eitzen Nov 10 '18 at 10:21