4 ms·

RSA encryption keys uses the product of two large primes, where each prime is many digits long. So many new primes are "discovered" every day.

schoen 9y ago
Interestingly, those primes' primality is normally proven statistically rather than deductively. This is not really a practical issue for people using RSA, but could be a philosophical issue for someone interested in the question of how many different numbers' primality has been proven by humanity.
- OscarCunningham 9y ago
  In fact if someone worked out how to crack RSA when it turned out that one of those numbers weren't prime then they would have invented a fast primality check. Which would be really cool in itself, and allow RSA to be fixed.
- xamuel 9y ago
  When philosophers study mankind's knowledge, it's more typical to study the things mankind would ideally know at the end of all time assuming mankind could continue forever. (Formally: the knowledge predicate is usually assumed to satisfy modus ponens: if mankind knows "A implies B" and mankind knows "A", then mankind knows "B") Under this abstraction, if mankind knows the axioms of logic and Peano arithmetic, then mankind [ideally eventually] knows the primality of all primes. Contrast: Which Turing machines will mankind [ideally eventually] know are never-halting? This is a much harder question and the answer is probably not "all never-halting Turing machines"
  - schoen 9y ago
    It's a little funny that mankind gets to use a full-fledged infinite-tape Turing machine in order to compute arbitrarily large computations, since no such machine would fit in our universe. https://en.wikipedia.org/wiki/Limits_of_computation https://en.wikipedia.org/wiki/Limits_of_computation https://en.wikipedia.org/wiki/Transcomputational_problem https://en.wikipedia.org/wiki/Transcomputational_problem
    - deleted 9y ago
      [deleted]
    - fooker 9y ago
      The description of a Turing machine that can do arbitrarily large computations can be finite. See: Kolmogorov complexity.
      - schoen 9y ago
        Sure, but it feels a little funny in one way to say that people "know" all of its output, although I'd agree that for other purposes being able to write a program to generate something is a relatively good description of what it means to understand it.
  - JackFr 9y ago
    > then mankind [ideally eventually] knows the primality of all primes We already know the primality of all primes. They're prime. All numbers though . . .
    - deleted 9y ago
      [deleted]
- deckar01 9y ago
  RSA implementations do use probabilistic primality tests when generating primes. OpenSSL [0] uses the Miller-Rabin primality test for RSA, which can be wrong, but they use enough iterations to make it very unlikely. [0]: https://wiki.openssl.org/index.php/Manual:BN_generate_prime(3)#DESCRIPTION https://wiki.openssl.org/index.php/Manual:BN_generate_prime(...
- sowbug 9y ago
  Not that I worry about this much, but if the fast prime generation methods we use are imperfect, then how bad is it when someone's PGP key or TLS certificate is based on nonprimes? Do black-hats ever strike gold and find out that someone's key is easily factorable? Or is there an additional property of common primality tests that their errors tend to be insignificant? (e.g., yes, this number isn't really prime, but its factors are very likely to be so large that they are also impractical to find, rather than, say, divisible by 7.)
  - Someone 9y ago
    Yes, but not because of the use of non-primes, AFAIK. There also are ‘bad choices’ for the primes that one should avoid. See https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Faulty_key_generation https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Faulty_key_..., https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Importance_of_strong_random_number_generation https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Importance_... Also, for those that are concerned about doing statistical primality tests, there are fast deterministic tests (https://en.wikipedia.org/wiki/Primality_test#Fast_deterministic_tests https://en.wikipedia.org/wiki/Primality_test#Fast_determinis...). Read https://en.wikipedia.org/wiki/AKS_primality_test https://en.wikipedia.org/wiki/AKS_primality_test for pointers to the algorithms to use in practice.
  - schoen 9y ago
    I think there was some research about this that did find some flawed implementations leading to semiprime p or q, but basically you can choose the probability that a probable prime is actually composite to be low enough that the expected number of weak keys ever generated for this reason is still less than one. (I haven't personally understood the probabilistic primality tests well enough to understand how they guarantee that the probability of error contributed by each round of the test is completely independent of every other round.)
- adrianN 9y ago
  I don't know to what confidence ssh-keygen and the like test their candidates, but it's not hard to make the probability for composite smaller than the probability that the computer doing a proper primality test is hit by an asteroid while doing the computation.

schoen 9y ago

Interestingly, those primes' primality is normally proven statistically rather than deductively. This is not really a practical issue for people using RSA, but could be a philosophical issue for someone interested in the question of how many different numbers' primality has been proven by humanity.

OscarCunningham 9y ago
In fact if someone worked out how to crack RSA when it turned out that one of those numbers weren't prime then they would have invented a fast primality check. Which would be really cool in itself, and allow RSA to be fixed.
xamuel 9y ago
When philosophers study mankind's knowledge, it's more typical to study the things mankind would ideally know at the end of all time assuming mankind could continue forever. (Formally: the knowledge predicate is usually assumed to satisfy modus ponens: if mankind knows "A implies B" and mankind knows "A", then mankind knows "B") Under this abstraction, if mankind knows the axioms of logic and Peano arithmetic, then mankind [ideally eventually] knows the primality of all primes. Contrast: Which Turing machines will mankind [ideally eventually] know are never-halting? This is a much harder question and the answer is probably not "all never-halting Turing machines"
- schoen 9y ago
  It's a little funny that mankind gets to use a full-fledged infinite-tape Turing machine in order to compute arbitrarily large computations, since no such machine would fit in our universe. https://en.wikipedia.org/wiki/Limits_of_computation https://en.wikipedia.org/wiki/Limits_of_computation https://en.wikipedia.org/wiki/Transcomputational_problem https://en.wikipedia.org/wiki/Transcomputational_problem
  - deleted 9y ago
    [deleted]
  - fooker 9y ago
    The description of a Turing machine that can do arbitrarily large computations can be finite. See: Kolmogorov complexity.
    - schoen 9y ago
      Sure, but it feels a little funny in one way to say that people "know" all of its output, although I'd agree that for other purposes being able to write a program to generate something is a relatively good description of what it means to understand it.
- JackFr 9y ago
  > then mankind [ideally eventually] knows the primality of all primes We already know the primality of all primes. They're prime. All numbers though . . .
  - deleted 9y ago
    [deleted]
deckar01 9y ago
RSA implementations do use probabilistic primality tests when generating primes. OpenSSL [0] uses the Miller-Rabin primality test for RSA, which can be wrong, but they use enough iterations to make it very unlikely. [0]: https://wiki.openssl.org/index.php/Manual:BN_generate_prime(3)#DESCRIPTION https://wiki.openssl.org/index.php/Manual:BN_generate_prime(...
sowbug 9y ago
Not that I worry about this much, but if the fast prime generation methods we use are imperfect, then how bad is it when someone's PGP key or TLS certificate is based on nonprimes? Do black-hats ever strike gold and find out that someone's key is easily factorable? Or is there an additional property of common primality tests that their errors tend to be insignificant? (e.g., yes, this number isn't really prime, but its factors are very likely to be so large that they are also impractical to find, rather than, say, divisible by 7.)
- Someone 9y ago
  Yes, but not because of the use of non-primes, AFAIK. There also are ‘bad choices’ for the primes that one should avoid. See https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Faulty_key_generation https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Faulty_key_..., https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Importance_of_strong_random_number_generation https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Importance_... Also, for those that are concerned about doing statistical primality tests, there are fast deterministic tests (https://en.wikipedia.org/wiki/Primality_test#Fast_deterministic_tests https://en.wikipedia.org/wiki/Primality_test#Fast_determinis...). Read https://en.wikipedia.org/wiki/AKS_primality_test https://en.wikipedia.org/wiki/AKS_primality_test for pointers to the algorithms to use in practice.
- schoen 9y ago
  I think there was some research about this that did find some flawed implementations leading to semiprime p or q, but basically you can choose the probability that a probable prime is actually composite to be low enough that the expected number of weak keys ever generated for this reason is still less than one. (I haven't personally understood the probabilistic primality tests well enough to understand how they guarantee that the probability of error contributed by each round of the test is completely independent of every other round.)
adrianN 9y ago
I don't know to what confidence ssh-keygen and the like test their candidates, but it's not hard to make the probability for composite smaller than the probability that the computer doing a proper primality test is hit by an asteroid while doing the computation.