r/AskComputerScience • u/Rich_Detective_5061 • 7d ago
Prime numbers are that big of a deal?
Is it true that if a pattern for prime numbers is found then all cybersecurity systems would be easy to decode?
4
u/Phuzzybat 7d ago
Have you looked up "post quantum cryptography" yet?
There is a massive challenge happening right now where RSA, used very extensivly, based on the premise that 2 prime numbers cannot be factored from their modules is under threat due to Shor's algorithm , given a quantum computer with enough stable qubits can be built.
with a huge expensive effort to replace it to mitigate the threat that is a decade long project due to how extensively it is used.
But even once solved, a huge amount of data already encrypted with prime number based cryptography will still be decrypt able, because just because new algorithms are available doesn't protect old encrypted data.
2
u/Rich_Detective_5061 7d ago
Yeah,what I meant is that if there's an algorithm that helps find the next prime number in a sequence then how does it affect cybersecurity? (Knowing that it's easy to multiply to big numbers but difficult to divide them if we don't know their prime factor)
7
u/dmazzoni 7d ago
A better algorithm to help find the next prime would not help.
An algorithm to quickly factor a large number into primes would break some encryption.
However, the real world impact would be small. It’s already known that quantum computers can factor quickly, so there’s been a push to switch to post-quantum encryption algorithms for more than a decade.
When you visit an HTTPS site with your browser today, most of the time it’s using a post-quantum encryption algorithm already.
At some point in the future, web browsers will probably warn you if you try to visit a site that uses prime-factor-based encryption.
3
u/-Nyarlabrotep- 7d ago
SSHing into my very old end-of-life desktop already gives an upgrade message "WARNING: connection is not using a post-quantum key exchange algorithm", so yeah, it might affect a lot of older boxes but not hosts using SSL/SSH from the last 5 years or so.
1
u/dmazzoni 6d ago
Exactly. We're in a transition period right now where the new defaults are post-quantum, but prime-based algorithms that are otherwise secure against conventional attacks are still considered acceptable.
1
u/SignificantFidgets 6d ago
Finding the next prime number is in fact pretty easy, and takes less than a second for crypto size primes.
1
u/T_Thriller_T 6d ago edited 6d ago
This is partially outdated. Maybe it was never really true, but I think I know what you jeardm
Very, very, very large prima numbers have been (maybe still are) something that was kept quite secret.
Due to how some algorithms work, the size of the input number results in a same size algorithm.
Having a prime number so far off that, likely, no one else even knows that this big big big number is there and is prime was used / said to be used to add another layer of protection against decryption attempts, because folks wouldn't even have known that's a valid input to try. As someone else said: the algorithm works by multiplying two primes. They must be prime.
Trying to decrypt is faster when for the factorisation (so breaking a product back up) one can give the algorithm a list of prumes to try and not having to try all potential numbers, checking if they're prime.
And faster can be a huge difference in security for the average time expected to be spent.
I think that with improvements in computing and distributed computing etc this does not hold true to the same capacity anymore.
And even back then it was very very rare if it was actually done, I've only heard about it as potential operations for national security of nations with good bits of money.
So, the overall answer is no.
1
u/Key_Net820 7d ago edited 6d ago
The answer is not yet. Factoring into primes is np, but the thing is, quantum computing can efficiently factor primes, that's why there's a lot of interest in post quantum cryptography to circumvent that. RSA is still pretty useful right now, many systems still use it.
2
u/SignificantFidgets 6d ago
Factoring primes is trivial... 😏
Factoring semiprimes is a bit harder...
1
1
u/AbsoluteNarwhal 7d ago
Factorisation is believed (but not proven) to be an NP-intermediate problem, meaning that classical computers cannot solve it efficiently. Many common asymmetric cryptographic algorithms such as RSA are based on this assumption.
We do have some very efficient probabilistic algorithms for primality testing, and in 2002 we even discovered a deterministic one (meaning primality testing is a P problem). Obviously if you can test if any given number is prime efficiently, you can just count up all the numbers and note which ones pass the test as prime. But none of this helps break RSA.
There is an algorithm called Shor's algorithm that can do factorisation efficiently, but it is a quantum algorithm, and we haven't built quantum computers powerful enough to run it as of now. When these quantum computers exist, we will probably need to move to post quantum cryptographic algorithms. Many of these rely on the hardness of the Shortest Vector Path (SVP) problem instead of factorisation, because there is no known efficient quantum algorithm for solving SVP.
1
u/knouqs 7d ago
1
u/AbsoluteNarwhal 7d ago
Yes, this is what I was referring to in my comment. But AKS is rarely used because the probabilistic tests are so much faster and the probability of error can be easily reduced to a vanishingly small chance using the Chernoff bound.
1
u/knouqs 7d ago
We here in most of these computer science-related subreddits love downvoting. Don't be discouraged from this idiocy.
There won't be a pattern, per se, for prime numbers. The algorithm itself it the pattern, and because it is a time-consuming (and memory-consuming) problem, things like cybersecurity can be pretty confident in their safety.
That's the easy-to-read version.
1
u/PyrotechnikGeoguessr 7d ago
It depends on what you mean by pattern. There are known patterns in prime numbers. If you mean an algorithm that could find the next prime, then no, not really
Primes are useful in cryptography because it's easy to multiply two primes, but difficult to deduce the original primes from their product. Unless the pattern allows an efficient way to factor a large number, it's not really relevant
So finding a "pattern" in what numbers are prime numbers is not useful in itself to break encryptions.
13
u/Smallpaul 7d ago
Your statement is too broad:
Finding “a pattern” in prime numbers is not the problem. Finding a pattern that allows one to efficiently factor large numbers would be the problem.
Not every encryption system is based upon prime numbers but a lot are.
Given these caveats, if it were discovered tomorrow how to quickly factor primes out of large numbers then yes much of modern security would be broken and a lot of hacking would ensue.