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

101–110 of 161 posts

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

#101

Post by heyoni »

devnull3 wrote: post #99
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 there is a such a breakthrough then the hackers or even spy agencies will not reveal it. They will instead silently make use of it. It will be essentially a backdoor for them.

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

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

#102

Post by raverbashing »

fharding wrote: post #79
raverbashing wrote: post #74

Earlier quoted context omitted.

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... )

Key exchange is done for speed (symmetric key crypto is way faster than public key) and forward secrecy. It’s not done because RSA is flawed per se. We use DH instead of e.g. ElGamal encryption for the same reasons.

Yeah it's not so much of a flaw of RSA, but encrypting pure text with it for example is more complicated (and has more caveats with padding, etc) than just encrypting a fixed amount of bytes

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

#103

Post by Retr0id »

devnull3 wrote: post #99
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 there is a such a breakthrough then the hackers or even spy agencies will not reveal it. They will instead silently make use of it. It will be essentially a backdoor for them.

It depends on who makes the breakthrough.

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

#104

Post by EvanAnderson »

devnull3 wrote: post #99
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 there is a such a breakthrough then the hackers or even spy agencies will not reveal it. They will instead silently make use of it. It will be essentially a backdoor for them.

SETEC ASTRONOMY

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

#105

Post by Retr0id »

heyoni wrote: post #101
devnull3 wrote: post #99

Earlier quoted context omitted.

If there is a such a breakthrough then the hackers or even spy agencies will not reveal it. They will instead silently make use of it. It will be essentially a backdoor for them.

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 against various block ciphers and hash functions, including a theoretical weakness in the Data Encryption Standard (DES). It was noted by Biham and Shamir that DES was surprisingly resistant to differential cryptanalysis, but small modifications to the algorithm would make it much more susceptible.

> In 1994, a member of the original IBM DES team, Don Coppersmith, published a paper stating that differential cryptanalysis was known to IBM as early as 1974, and that defending against differential cryptanalysis had been a design goal. According to author Steven Levy, IBM had discovered differential cryptanalysis on its own, and the NSA was apparently well aware of the technique.

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

#106

Post by hennell »

eismcc wrote: post #71
timmb wrote: post #64

Something inspiring about this: "In dedicated Friday afternoon thinking sessions, he returned to the problem again and again over the past decade, to no avail."

I recall that Richard Hamming used to also reserve Friday afternoons to deep/big thinking. Sounds wonderful.

Friend of mine worked used to block off his friday afternoons for 'weekly review'. Which was part big thinking, part end of week nap, and mostly avoiding colleagues who had tricky tasks 'needed first thing monday' they had forgotten to bring up before.

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

#107

Post by nobodyandproud »

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…

IIRC, Elliptic curve cryptography doesn’t rely on factorization, so there’s already an interim PKC solution in place.

I also recall there were many problems with the ECC based algorithms or at least the implementations—something about discrete approximations weakening security?

Far beyond my comprehension

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

#108

Post by k__ »

nobodyandproud wrote: post #107
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…

IIRC, Elliptic curve cryptography doesn’t rely on factorization, so there’s already an interim PKC solution in place. I also recall there were many problems with the ECC based algorithms or at least the implementations—something about discrete approximations weakening security? Far beyond my comprehension

There is also lattice-based cryptography.

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

#109

Post by AnotherGoodName »

nobodyandproud wrote: post #107
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…

IIRC, Elliptic curve cryptography doesn’t rely on factorization, so there’s already an interim PKC solution in place. I also recall there were many problems with the ECC based algorithms or at least the implementations—something about discrete approximations weakening security? Far beyond my comprehension

ECC is very closely related though (hidden abelian subgroup problem is the category they both fall under).

It’s actually concerning because rsa was broken. The reason we’re not using 128bit rsa keys anymore and instead using 2048bit keys is because rsa was broken by the general number field sieve. We’re now all using ecc to avoid working with very large keys but there’s no mathematical proofs that ecc is anymore difficult. In fact it’s widely believed to be the same problem underneath.

That may surprise people. ECC, the thing we rely on, is not proven except by the fact that no one has broken it yet just like rsa was until someone broke it.

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

#110

Post by dakiol »

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.

Post reply on HN