3

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?

Improve this question

1 Answer 1

Reset to default
4

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?

Improve this answer
5
  • 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
    Commented Nov 10, 2018 at 6: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
    Commented Nov 10, 2018 at 6: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
    Commented Nov 10, 2018 at 10:21
  • 2
    @YousefGamal it is crucial, especially when ensuring security or robustness or correctness of software, to get emotionally comfortable that there is always a chance - certainty is an illusion. Even if you had some way to check for private key uniqueness, there is a chance that a stray high-energy photon from space hits a transistor in your CPU just as it was finishing a uniqueness check, causing a false to become a true and oh look you have duplicate keys anyway. Or due to human error a hacker can cause duplicate keys. And so on. So just get random collision odds below those odds.
    – mtraceur
    Commented Feb 7, 2023 at 1:32
  • 2
    @mtraceur Interestingly, the algorithm most commonly used for generating prime numbers (Miller-Rabin) is probabilistic, but the chance that it will incorrectly choose a composite number is actually lower than the chance that a deterministic algorithm like ECPP will make a mistake simply due to hardware failure. With the numbers used in cryptography, probabilities can be so low that even the low chance of a particular bit flipping can be higher.
    – forest
    Commented Feb 7, 2023 at 2:10

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .