Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Breakthrough a step toward revealing hidden structure of prime numbers

science.org

Post reply on HN
Print view View original

111–120 of 161 posts

Re: Breakthrough a step toward revealing hidden structure of prime numbers

#111

Post by AnotherGoodName »

zitterbewegung wrote: post #88
EMIRELADERO wrote: post #2

This got me thinking. Imagine this discovery led to a larger breakthrough on prime numbers that allowed easy factorization of large integers and effectively rendered public key cryptography such as RSA ineffective overnight, by allowing anyone with a consumer-grade CPU to crack any production-size key. Does the industry have DR plans for this scenario? Can the big players quickly switch to a different, unbroken encry…

Many people in the industry does not think that RSA is crackable due to the assumptions that the Riemann Hypothesis and also the distribution of prime numbers is such a hard problem with a long time of being unsolvable. A possible mitigation for things like websites would be either ECC or even using the quantum resistant encryption systems (the industry would more likely avoid this due to the systems being very proto…

RSA was once 128bits and today has to be 2048bits minimum to be secure because it was essentially broken multiple times. There used to be 128bit rsa encrypting hardware that now doesn’t work at all to protect data due to previous mathematical breakthroughs.

The congruence of squares equivalence to factorization demonstrated we need at least 500 bits and then the special number field seive that built on this push it to 1024. The general number field seive pushed it again to 2048.

Sure it’s not a log(n) break but it’s been broken. If you look at the complexity analysis of the special vs general number field seive the portion of the exponent going from 1/2 to 1/3 should give you thought. Can it be moved to 1/4? Could it be moved indefinitely to 1/x? The general number field seive is relatively recent. If someone comes up with a similar breakthrough again (and this has happened many times over with rsa) your 2048bit keys won’t be secure just as your 128bit rsa keys from the past are no longer secure.

Re: Breakthrough a step toward revealing hidden structure of prime numbers

#112

Post by [deleted] »

dakiol wrote: post #110
EMIRELADERO wrote: post #2

This got me thinking. Imagine this discovery led to a larger breakthrough on prime numbers that allowed easy factorization of large integers and effectively rendered public key cryptography such as RSA ineffective overnight, by allowing anyone with a consumer-grade CPU to crack any production-size key. Does the industry have DR plans for this scenario? Can the big players quickly switch to a different, unbroken encry…

Isn’t this the same as zero-day vulnerabilities? Typically only a bunch of people out there know how to take advantage of such holes, and eventually they get fixed. I guess if public key cryptography gets broken, only a bunch of people would know how to take advantage of it, and eventually it would get fixed.

[deleted]

Re: Breakthrough a step toward revealing hidden structure of prime numbers

#113

Post by sameoldtune »

zxcb1 wrote: post #78
keepamovin wrote: post #25

People always think the structure of primes is complex, but it's not really, it's just a recursive structure of the magnitude gaps not landed on by multiples of previous gaps. It doesn't make it easier to "predict" without tracking all prior gaps, but it's not essentially a complex structure. Kind of funny that like such a simple structure is so elusive. Sorta like how the 3n + 1 sequence gives rise to such complexit…

Why isn't this considered a solved problem? https://en.wikipedia.org/wiki/Information_theory https://en.wikipedia.org/wiki/Computational_irreducibility https://en.wikipedia.org/wiki/Aperiodic_tiling

I don’t understand how your links relate to primality.

Re: Breakthrough a step toward revealing hidden structure of prime numbers

#114

Post by sameoldtune »

testaccount135 wrote: post #28

"they pulled some unorthodox moves to finally break Ingham’s bound" Why is taking methods from other fields an unorthodox move? I come from an engineering background an there it is the common case. The usage of harmonic analysis is a staple in many fields (audio, waves, electrical analysis, statistics) and of course the algorithms are pure math under the hood. If I want to find a reaccuring structure in an underlying…

It’s kind of silly. Just a reporter reporting. You could say that every discovery in mathematics involves some “unorthodox” move, since the orthodoxy is all that is known so far.

Re: Breakthrough a step toward revealing hidden structure of prime numbers

#115

Post by admax88qqq »

raverbashing wrote: post #74
scrapheap wrote: post #29

Earlier quoted context omitted.

If someone found a way to easily factorize large integers easily on consumer grade hardware then it would be very painful as RSA is one of the big public key algorithms. Before you start worrying about it though consider that RSA has held up for 47 years of active cryptanalysis so far - during which time many alternative algorithms have been suggested as being superior, only to be broken a short time later. Also the…

Actually RSA has several "gotchas", so it is not that it has held up but people have managed to work around those gotchas into a working encryption system (Basically your data is not encrypted with RSA, you encrypt a secondary key, send it with RSA but the main encryption is AES see https://en.wikipedia.org/wiki/Transport_Layer_Security#Key_e... )

A lot of the RSA gotchas are due to trying to take implementation shortcuts either for convenience or speed.

If you don’t choose your primes truly randomly for example.

Using a secondary key and using RSA for the key share is not about avoiding RSA gotchas it’s just about performance.

Re: Breakthrough a step toward revealing hidden structure of prime numbers

#116

Post by AnotherGoodName »

scrapheap wrote: post #29
EMIRELADERO wrote: post #2

This got me thinking. Imagine this discovery led to a larger breakthrough on prime numbers that allowed easy factorization of large integers and effectively rendered public key cryptography such as RSA ineffective overnight, by allowing anyone with a consumer-grade CPU to crack any production-size key. Does the industry have DR plans for this scenario? Can the big players quickly switch to a different, unbroken encry…

If someone found a way to easily factorize large integers easily on consumer grade hardware then it would be very painful as RSA is one of the big public key algorithms. Before you start worrying about it though consider that RSA has held up for 47 years of active cryptanalysis so far - during which time many alternative algorithms have been suggested as being superior, only to be broken a short time later. Also the…

RSA has effectively been broken many times. We literally had 128bit RSA encryption hardware at one point. There were even export controls on keys beyond a certain length (512bits) that today are trivial to break with the general number field seive. You look at the history of RSA and it’s not pretty. Dixons method had us all scrambling to use 512bit keys (pushing the export restrictions), special number field seive had us rushing to get to 1024bit. The general number field seive more recently pushed us to 2048bits. Who can tell what’s next here. In fact look at the complexity of the special vs general number field seives and you’ll see the statements are almost the same, just some constants reduced. That’s worrying because there’s no reason to think the current constants are a minimum here. We may well find out 2048bits is not enough.

Heck just read a paper in state of the art dedicated RSA encryption hardware from the 80s. All now completely broken. They are very impressed with some of the 512bit hardware!

https://people.csail.mit.edu/rivest/pubs/pubs/Riv84.pdf

Re: Breakthrough a step toward revealing hidden structure of prime numbers

#117

Post by [deleted] »

EMIRELADERO wrote: post #2

This got me thinking. Imagine this discovery led to a larger breakthrough on prime numbers that allowed easy factorization of large integers and effectively rendered public key cryptography such as RSA ineffective overnight, by allowing anyone with a consumer-grade CPU to crack any production-size key. Does the industry have DR plans for this scenario? Can the big players quickly switch to a different, unbroken encry…

[deleted]

Re: Breakthrough a step toward revealing hidden structure of prime numbers

#118

Post by heyoni »

Retr0id wrote: post #105
heyoni wrote: post #101

Earlier quoted context omitted.

Wouldn’t it likely originate from academia? If so you can bet that the work will be published just like this one.

It's hard to know where things are today, but historically, public academia has often been behind the true cutting edge of cryptanalysis. For example, take a look at the history of Differential Cryptanalysis https://en.wikipedia.org/wiki/Differential_cryptanalysis > The discovery of differential cryptanalysis is generally attributed to Eli Biham and Adi Shamir in the late 1980s, who published a number of attacks agai…

That is both impressive and disappointing. I'm so used to seeing large corporations publishing AI models and other techniques (like Ghidra) that I assumed a finding like that would be disseminated to the public. But you're right, something that could be used to decrypt modern ciphers could very well be kept secret for as long as possible.

Re: Breakthrough a step toward revealing hidden structure of prime numbers

#119

Post by AnotherGoodName »

EMIRELADERO wrote: post #2

This got me thinking. Imagine this discovery led to a larger breakthrough on prime numbers that allowed easy factorization of large integers and effectively rendered public key cryptography such as RSA ineffective overnight, by allowing anyone with a consumer-grade CPU to crack any production-size key. Does the industry have DR plans for this scenario? Can the big players quickly switch to a different, unbroken encry…

That happened many many times over with rsa!

The us government used to restrict export of long rsa keys. At one point much of the world was using 128bit rsa keys but Dixon method had everyone scrambling to use 512bit keys. Then the special number field drive had us all scrambling to use 1024bit keys and the general number field seive again had us scrambling to get to 2048bit keys.l and that really wasn’t that long ago relatively speaking.

Check out rsa encryption hardware from the 80s. They are really proud of some of the hardware that can do 512bits! (Useless today)

https://people.csail.mit.edu/rivest/pubs/pubs/Riv84.pdf

The special and general number field seize complexity statements are a few constants in difference. Look at those constants. Do they seem to be some root limit to you? Is it really that unlikely that there’s not a way to reduce those further making even 2048bit keys useless?

You don’t need to ask “what would happen if RSA broke” because those of us who have been through this many times now can straight up tell you. You’ll be scrambling to once more bump up the key size and you’ll be auditing all the potential data leaked.

Re: Breakthrough a step toward revealing hidden structure of prime numbers

#120

Post by tzs »

scrapheap wrote: post #29
EMIRELADERO wrote: post #2

This got me thinking. Imagine this discovery led to a larger breakthrough on prime numbers that allowed easy factorization of large integers and effectively rendered public key cryptography such as RSA ineffective overnight, by allowing anyone with a consumer-grade CPU to crack any production-size key. Does the industry have DR plans for this scenario? Can the big players quickly switch to a different, unbroken encry…

If someone found a way to easily factorize large integers easily on consumer grade hardware then it would be very painful as RSA is one of the big public key algorithms. Before you start worrying about it though consider that RSA has held up for 47 years of active cryptanalysis so far - during which time many alternative algorithms have been suggested as being superior, only to be broken a short time later. Also the…

> Before you start worrying about it though consider that RSA has held up for 47 years of active cryptanalysis so far

True, but is there much overlap between the set of people who actively do cryptanalyses on RSA and the set of people who actively research integer factoring?

As far as I know the skills needed to make progress on integer factoring are not really needed for anything in cryptography other than that specific problem and include a bunch of other skills that have nothing whatsoever to do with cryptography and take a long time to master. It's also been an open and important problem long enough that if it is solved it is likely to be by someone who is a world class expert in it, similar to how Fermat's Last Theorem was finally solved.

Similarly the skills needed for anything in cryptanalysis other than trying to break RSA by factoring are useless for working on integer factoring. The result is that very few, if any, people have the time and ability to become both cryptanalysts and world class integer factoring researchers.

Thus I'd expect nearly all of the 47 years of active RSA cryptanalysis has been on finding and fixing the numerous mistakes that can be made when implementing RSA that allow it to be broken without factoring.

I'd guess it is also similar with the P = NP problem. A solution to that has implications for cryptography but I doubt many cryptanalysts are working on the P = NP problem. Also maybe same for the Riemann hypothesis (I'm not sure if that one has implications for cryptography).

Post reply on HN