If encryption is all about primes then why not make a list of primes to break them? That number has to be massively smaller than all numbers even if it is infinite (smaller set).
Just set an almighty computer to work on primes and keep a list.
Use that finite list, bigger than anyone else has, to break codes.
It might take a thousand years to brute force a given code but if you have a list of primes I’d think it would take minutes.
Since this does NOT seem to be how breaking encryption actually works what am I missing?
The security of RSA is related to the difficulty of factoring the product of two large prime numbers, the “factoring problem”. Breaking RSA encryption is known as the RSA problem. Whether it is as difficult as the factoring problem is an open question.[17] There are no published methods to defeat the system if a large enough key is used.
(I wrote a paper about this in college and remember literally none of it)
Primes are a lot more common than you’d think. The usual way to generate large primes is to start by generating a large random number, and then testing if it’s prime, and repeating until you get one. If you really care about efficiency, then you generate your large random number in such a way that it’s already not divisible by (say) 2, 3, or 5 (because that would eliminate most non-primes), but primes are still common enough that it’s not worth even that.
Let’s say that you’re looking for 512-bit primes. There are around 3.8E151 different primes in that range, about three numbers per thousand. The entire observable universe can’t contain enough data to store that list. And a key would consist of two of those numbers, so the list of keys would be close to the square of that number. And 512 bits is the lower end of RSA key sizes; 1024 or 2048 is what’s usually used nowadays.
For Christmas someone gave me the book below. I get a Mersenne Prime is a subset of all primes but still…it made me think we have a great big list of all primes. I would guess someone has the record for the biggest prime number ever found which means we have a list of all smaller primes.
That doesn’t follow. I can give you a really large even number, say 567498765468798754468749787646474568763146876872. That doesn’t mean that I have a list of all even numbers smaller than that.
There are plenty of primes smaller than the largest known prime. The vast majority of them have never been discovered.
Yep. A quick Google search shows there are 37,607,912,081 prime numbers that are less than 1 trillion. Which means 3.8% of numbers less than 1 trillion are prime numbers. That’s a lot of prime numbers, for a relatively small set size (1 trillion).
But take that large even number I typed out above. I guarantee you that nobody else in history ever wrote out the number 567498765468798754468749787646474568763146876870, before I wrote out the number that’s two larger than that.
The usual way of finding a large prime number for use in a cryptographic algorithm is just to pick a random number of the size you want and then test if it’s prime. If not, discard it and pick another random number and repeat. Prime numbers are so common that this will succeed in a reasonably small number of attempts. I hope it is clear that after finding a prime number using this algorithm, you don’t have a list of smaller primes and in fact you don’t gain any information about the set of smaller primes.
ETA: Just to forestall confusion, the “test if it’s prime” part is done by a primality testing algorithm such as Miller-Rabin. Testing whether a number is prime by such a method does not involve iterating through smaller numbers like a naive trail division algorithm would.
It may help to realize they aren’t directly chasing “the largest prime.” They are looking for the next Mersenne prime. A Mersenne prime is in the form 2p - 1, where p is itself a prime number.
So they are finding something in order. It’s just that the largest known Mersenne prime is also the largest known prime in general. This is because testing for Mersenne primes is much easier than searching for other primes, and has other uses like finding perfect numbers.
If n is a composite number then so is 2n − 1. Therefore, an equivalent definition of the Mersenne primes is that they are the prime numbers of the form Mp = 2p − 1 for some prime p.
I used that definition as there is no point in testing if n is not prime.
2^n - 1 can only be prime if n is itself a prime. So you could say that a Mersenne prime is any prime of the form 2^n - 1, but it’s also true that it’s 2^p - 1.
@BigT 's quote there is missing its superscripts: It should say
Regarding the original question, having a list of prime numbers wouldn’t help decrypting something encrypted with RSA or a similar algorithm based on primes. It’s kind of like asking, “if a combination lock can be opened by inputting three numbers between 1 and 100, why not just have a list of numbers between 1 and 100?” The security doesn’t rely on the (false) fact that it’s hard to find primes, it relies on the difficulty in finding the specific necessary primes in the vast set of all primes.
I was in the act of fixing that, as I didn’t notice before I clicked Reply. It seems that, while the italics and links did paste over, the superscript and subscripts did not.
There is no biggest prime or biggest Mersenne prime, unless you meant discovered so far.
It’s only a lucky coincidence that currently, Mersenne primes happen to be the record-holders, because there’s a much more computationally easy test, the Lucas-Lehmer primality test.. It’s vastly harder to find huge primes of other forms. If somebody were to happen to find a non-Mersenne prime even bigger than the current record holder (extremely unlikely, but we can dream), then it will become uncertain whether the next Mersenne prime discovered will take back the record or not.
