[deleted]
Breakthrough a step toward revealing hidden structure of prime numbers
141–150 of 161 posts
Re: Breakthrough a step toward revealing hidden structure of prime numbers
#142[deleted]
Re: Breakthrough a step toward revealing hidden structure of prime numbers
#143Earlier quoted context omitted.
does the move to elliptic crypto suggest that the people in the know expect prime factorisation to be broken soon?
Since no one mentioned, a major reason to prefer elliptic curves is that you can get equivalent security for much smaller key sizes.
I had to implement key generation on an embedded device @ 180MHz. RSA2048 would take upwards of five minutes if you didn't get lucky finding primes early on. Stronger ECC would be done within a second.
Re: Breakthrough a step toward revealing hidden structure of prime numbers
#144Earlier 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…
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 ha…
That is not when an encryption algorithm is usually considered to be broken, it just means that a certain key length is not sufficient anymore. You can break 20 bit RSA with pen and paper, but as long as a linear change in the key length causes an exponential increase in the decryption time, the algorithm is not broken. At this moment, the record for the factorization of a specific RSA key is one of 829 bits, which suggests (by extrapolation) that within a few decades 1024 bits may not be safe if your adversary has the resources. No (reasonable) key length can be expected to be safe forever, even without any mathematical breakthroughs
Re: Breakthrough a step toward revealing hidden structure of prime numbers
#145This 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…
Since Setec Astronomy closed operation, we've been okay.
Re: Breakthrough a step toward revealing hidden structure of prime numbers
#146Earlier quoted context omitted.
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 ag…
RSA failures with bit-depth were a matter of degree; a prime number factorization break-through would be a matter of kind.
It’s not log(n) but still a break since we were literally using lower bit strength than was trivially factorable thanks to mathematical advances and to the point of thinking RSA 2048 is safe, well we once thought that about 128bit RSA. If the above pans out like the general number field seive did we may yet need to move the goal posts further. And we really really shouldn’t be surprised if it happens since it’s happened so many times already.
Re: Breakthrough a step toward revealing hidden structure of prime numbers
#147Earlier quoted context omitted.
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 ha…
That is not when an encryption algorithm is usually considered to be broken, it just means that a certain key length is not sufficient anymore. You can break 20 bit RSA with pen and paper, but as long as a linear change in the key length causes an exponential increase in the decryption time, the algorithm is not broken. At this moment, the record for the factorization of a specific RSA key is one of 829 bits, which s…
I’d say it’s a break if the encryption you once used (512bit and below RSA) is now trivially decrypted thanks to mathematical advances.
RSA 2048 hasn’t been broken but 512bit RSA definitely had been by any definition.
I feel “RSA is fine because much longer key lengths still work” is hiding what happened here. Yes we can still get into the infeasible realm with RSA and really long keys but the algorithm has definitely let us down multiple times thanks to mathematical improvements in factorization that just keep coming.
Re: Breakthrough a step toward revealing hidden structure of prime numbers
#148Earlier quoted context omitted.
Yes, it’s difficult to predict where such an understanding might lead. If it reframes and redefines all of number theory, then we might call it one component of the foundational theory of number theory. Analogously, if someone proves that P = NP, then that will be great, but the significance of lambda calculus and Turing completeness will remain. If the proof is constructive and practical, we’ll just have to repriori…
> if someone proves that P = NP > we’ll just have to reprioritize and update the list of algorithms we teach to undergrads, issue performance-enhancement updates to some software libraries, and patch any security vulnerabilities. Wow, your optimism sure is something. What are you patching and with what? How do you “patch any security vulnerabilities” when said vulnerability is “all of our security research, except on…
Gosh it was early in the morning and somehow I was thinking in terms of factoring prime numbers when I added the security point. But consider cryptography as an application of number theory and compatibility theory.
Interestingly, if there are cryptography alternatives that can still be relied upon if factoring primes is easy, but the same does not hold if P = NP in a practical sense, then that’s further support for the primary point that learning more about prime numbers would not reset the foundation of number theory.
Re: Breakthrough a step toward revealing hidden structure of prime numbers
#149This 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 ag…
> At one point much of the world was using 128bit rsa keys
When?
I was writing crypto libraries in the early 90s to support RSA, DSA and ElGamal at my company (this predates the times when good open source crypto libraries were broadly available).
Even back then 128 bit RSA keys were not used. The smallest the library supported was 512 and the smallest we ever used in production was 768 bits.
That's how far back my own memory goes. But here's a paper from Arjen Lenstra from 2001 which has a table showing computationally equivalent key sizes back to 1982.
https://infoscience.epfl.ch/server/api/core/bitstreams/c323a...
In 1982, security comparable (at the time!) to DES would have been 417 bit RSA keys.
So even in 1982, using 128 bit RSA keys made no sense!
> You’ll be scrambling to once more bump up the key size and you’ll be auditing all the potential data leaked.
If you've had to do this for RSA keys (more than once, even!) I respectfully suggest you need to be a lot more conservative picking key lengths. There has never been a sudden breakthrough in factorization that has rendered conservatively chosen RSA key lengths obsolete overnight.
Re: Breakthrough a step toward revealing hidden structure of prime numbers
#150Earlier quoted context omitted.
RSA failures with bit-depth were a matter of degree; a prime number factorization break-through would be a matter of kind.
It’s not log(n) but still a break since we were literally using lower bit strength than was trivially factorable thanks to mathematical advances and to the point of thinking RSA 2048 is safe, well we once thought that about 128bit RSA. If the above pans out like the general number field seive did we may yet need to move the goal posts further. And we really really shouldn’t be surprised if it happens since it’s happe…
I believe this was one of the reasons for the broad adoption of elliptic curve based cryptography. The mechanism is not based on prime numbers, so smaller keys were adequate, and it was hoped that they might avoid future degradation due to prime factorization research. Of course they could still be vulnerable to their own attacks, but it still requires an attacker to expend more resources.