3 ms·
I have a stupid question that will reveal how I know nothing about cryptography. I understand that large primes are somehow important for some types of cryptog
by Consultant32452 11y ago
I have a stupid question that will reveal how I know nothing about cryptography. I understand that large primes are somehow important for some types of cryptography. How are there not just databases of large primes that make breaking the types of cryptography that rely on large primes trivial?
- xyzzyz 11y agoThere are _a lot_ of large primes. If you randomly choose a 1024 bit prime, it's _extremely unlikely_ anybody seen or used that prime before you.
- laughinghan 11y agoThere are too many. Not just more than could fit in every database on Earth. More than could fit on every database if every star in the sky had an Earth, each with as many databases as there are on Earth. This is nothing specific to cryptography or prime numbers. Fun fact: if you shuffle a deck of cards correctly, it's almost certain that no one in history has ever had a deck in the exact same order. https://www.math.hmc.edu/funfacts/ffiles/10002.4-6.shtml https://www.math.hmc.edu/funfacts/ffiles/10002.4-6.shtml
- Consultant32452 11y agoI understand that there's a huge number of primes, but surely the primes being used to generate keys or whatever process they're involved in are "known" primes, right? It's not as if when I try to encrypt something my machine is going to search for a new prime number that hopefully won't get guessed.
- yoha 11y agoLong prime numbers are used for RSA keys. You only generate RSA keys when creating a new identity (webserver certificate, client certificate, SSH key, etc). Then, you do search for "a new prime number that hopefully won't get guessed". It can take from a few seconds to several minutes, depending on the hardware and the desired key length. The usual approach is to take a random odd number of desired length and then have a probabilistic primality test (much faster than what would be needed for a formal proof). Several attacks rely on bad entropy or bad pseudo random number generators (PRNG) to guess what prime was selected.