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

81–90 of 161 posts

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

#81

Post by scrapheap »

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

There's "gotchas" with every encryption scheme - in fact whenever TLS uses any Public Key encryption scheme it'll pair it with a Symmetric Key encryption scheme. So you could say that by your definition no Public Key encryption scheme has "held up" and they've all had to be worked round :)

There are benefits to pairing the slower Public Key schemes with a Symmetric Key encryption scheme using a session key, as you get the benefits of an Public Key encryption scheme with the performance of a Symmetric Key encryption scheme.

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

#82

Post by staunton »

exe34 wrote: post #44
staunton wrote: post #11

Earlier quoted context omitted.

It's to do with "if we ever have big/good quantum computers, prime factorization is doable" and with "let's use the new shiny things". On a related note, someone might discover some elliptic curve math tomorrow and your CPU can break all that stuff just as well...

so with my cynic hat on, maybe a bunch of people already have that and that's why we're being moved off the hard stuff.

The NSA had the option to do something like that when they (via NIST) standardized DES.

They chose to standardize a version that's secure against attacks that only they knew at the time, shorten the key length so they can still brute-force it if they really need to, and successfully kept the attack secret until researchers at a foreign university independently discovered it decades later.

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

#83

Post by ertgbnm »

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…

Pretty sure that it would require that P=NP if such an event happened. So if factorization was cracked, everything else would be too.

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

#84

Post by seanhunter »

guhbkji wrote: post #66
novaRom wrote: post #63

Earlier quoted context omitted.

A generator of "all primes" is pretty simple and deterministic. But you cannot simply generate next prime given only prime n without recomputing its non-trivial remainders. That means just a binary representation of a number n doesn't provide enough information to make quick answer what is the next prime. You have to pre-compute some 'pivots' first. Basically, more complexity, but it's still simple and trivial, not e…

> not even in NP This is incorrect. Integer factorization is NP-intermediate. Very much “in NP”. https://en.m.wikipedia.org/wiki/NP-intermediate Also, saying factorization lacks “complexity” because sieves exist misunderstands both concepts. > In order to talk about complexity classes such as P, NP, and co-NP, the problem has to be stated as a decision problem. > Decision problem (Integer factorization) — For every n…

That NPI wiki link says integer factorization may be in NP-intermediate iff NPI isn't an empty set, which is unknown at the current time. My understanding is the complexity of factorization is also currently an unsolved problem although no polynomial time algorithm is currently known.

Eg https://www.connellybarnes.com/documents/factoring.pdf

    "Finally, in computational complexity theory, it is unknown whether
    factoring is in the complexity class P. In technical terms, this means that
    there is no known algorithm for answering the question "Does integer N have
    a factor less than integer s?" in a number of steps that is ))(( nPO ,
    where n is the number of digits in N, and P(n) is a polynomial function.
    Moreover, no one has proved that such an algorithm exists, or does not
    exist."
That is supported by the second wiki link you provide, which has "Unsolved problem in computer science: Can integer factorization be solved in polynomial time on a classical computer?" in a box at the side. https://en.m.wikipedia.org/w/index.php?title=Integer_factori...

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

#85

Post by NiloCK »

I've been fascinated by this question since I learned the sieve of eratosthenes as a kid. The meta logic of it is so simple:

Primes are specifically the numbers that are left over after the structured numbers (composite) ones are removed.

Everything - [structured numbers] = [ chaos? the abyss? some meta structure? ]

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

#86

Post by amelius »

ertgbnm wrote: post #83
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…

Pretty sure that it would require that P=NP if such an event happened. So if factorization was cracked, everything else would be too.

Are you sure about that?

And even if problems can be solved in polynomial time, the constants involved can be prohibitively large.

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

#87

Post by cvoss »

ertgbnm wrote: post #83
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…

Pretty sure that it would require that P=NP if such an event happened. So if factorization was cracked, everything else would be too.

Integer factorization is an NP problem but is not known to be NP-complete. Therefore, we do not know how to solve all NP problems in P time using a hypothetical P time factorization.

P =? NP would remain open.

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

#88

Post by zitterbewegung »

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 prototypical since we have just started researching this).

Since old bitcoin wallets can’t be moved off of RSA you can transfer the coins to your wallet and there is no mitigation.

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

#89

Post by 8372049 »

K0balt wrote: post #77
milansuk wrote: post #47

Earlier quoted context omitted.

True. The only solution is to keep your data outside cloud(aka someone else's computer) no matter what encryption you use.

Also means it can’t transit the internet. So actually, only on airgapped networks.

If we're going to extremes like that, airgapped networks aren't truly safe either

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

#90

Post by red_trumpet »

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…

I don't see how proving the Riemann Hypothesis would help cracking RSA? If it helps, couldn't you just assume it is true and start cracking RSA today? If you ever hit a point where it doesn't work then BOOOM: Riemann Hypothesis disproven!
Post reply on HN