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

RSA-260 Factorized

twitter.com

Post reply on HN
Print view View original

21–30 of 82 posts

Re: RSA-260 Factorized

#21

Post by mattashii »

stouset wrote: post #14
ajross wrote: post #7

It's sort of fun to remember the genuine worry in the community around RSA and the (really, really shocking at the time!) progress in factorization leading up to GNFS techniques. Like, it really looked like everything was going to fall apart. We all rushed to 1024 bit keys, and then to 2048 bit after what felt like a few months. And... maybe even that wouldn't be enough? And actual history ended up being the boring v…

RSA might be fine mathematically but as a production cryptosystem it’s an unmitigated disaster by modern standards. Compared to elliptic curves, it is comically easy to build an RSA implementation which is catastrophically broken. Both the number of and subtlety of footguns in RSA are extreme. Even ignoring that, ECC is far more efficient (in part thanks to smaller key sizes and being able to be done with fixed-width…

Assuming a given fixed key size, where does RSA need non-fixed-width arithmatic? AFAIK you can do all RSA maths with registers just double as wide as the key, no variable width anything required there. And I don't think that this is much different from ECC maths, apart from ECC's keys just being way less wide for an approximately equivalent security level.

Re: RSA-260 Factorized

#23

Post by tptacek »

ajross wrote: post #19
mswphd wrote: post #15

Earlier quoted context omitted.

the researchers from the RSA-250 record have publicly claimed that factoring 1024-bit RSA keys is within reach of nation states. Your 1024 bit key is only "fine" because you are a small fry, not because cryptographers think it cannot be attacked. This would be true if you used a (non-standard) RSA-768 parameterization as well, which is easier than what we are talking about on this post. It's also worth mentioning the…

> Your 1024 bit key is only "fine" because you are a small fry, not because cryptographers think it cannot be attacked. This is falling for an xkcd 538 fallacy, btw. Nation states obviously have vast higher capability to subvert individual data than brute forcing its crypto. I stand by what I said: 1024-bit RSA keys are "fine" and will remain so. RSA-309 will not fall within our lifetime. > it's very much possible th…

That's a weirdly confident prediction. Why do you think 309 isn't going to fall in our lifetimes?

"SHA2 will never be broken in our lifetimes" is something I've heard JP Aumasson say many times, but that's based on the fact that there's no line of sight anywhere to techniques that could break it. But you can't say that about 1024 bit RSA.

Re: RSA-260 Factorized

#24

Post by catlifeonmars »

pugfugly wrote: post #20
ajross wrote: post #7

It's sort of fun to remember the genuine worry in the community around RSA and the (really, really shocking at the time!) progress in factorization leading up to GNFS techniques. Like, it really looked like everything was going to fall apart. We all rushed to 1024 bit keys, and then to 2048 bit after what felt like a few months. And... maybe even that wouldn't be enough? And actual history ended up being the boring v…

Peter Shor would like to have a word with you...

Shor's algorithm needs technology we still don’t have. Get back to me when we can have more than a handful of qubits reliably compute things.

Re: RSA-260 Factorized

#25

Post by Davidzheng »

ajross wrote: post #7

It's sort of fun to remember the genuine worry in the community around RSA and the (really, really shocking at the time!) progress in factorization leading up to GNFS techniques. Like, it really looked like everything was going to fall apart. We all rushed to 1024 bit keys, and then to 2048 bit after what felt like a few months. And... maybe even that wouldn't be enough? And actual history ended up being the boring v…

but complexity is not known right? like tomorrow someone could come up with a super fast algorithm?

Re: RSA-260 Factorized

#26

Post by adastra22 »

internet2000 wrote: post #22
dclavijo wrote: post #3

What was the methodology,software, hardware, cpu cores, time taken?

[flagged]

It wasn’t. The person that posted the factorization has nothing to do with Anthropic, and has for many years held the leaderboard on GPU-hours applied to factorization and prime search problems. He’s not yet on record as to how this one was done (probably waiting for publication), but there is no reason at all to assume any LLM was involved.

Re: RSA-260 Factorized

#27

Post by adastra22 »

catlifeonmars wrote: post #24
pugfugly wrote: post #20

Earlier quoted context omitted.

Peter Shor would like to have a word with you...

Shor's algorithm needs technology we still don’t have. Get back to me when we can have more than a handful of qubits reliably compute things.

We only need the ability to make make 1 qubit with indefinite reliable / fully error corrected state. Quantum interconnects would allow for these to be connected into arbitrarily large quantum computers.

Re: RSA-260 Factorized

#28

Post by adastra22 »

ajross wrote: post #7

It's sort of fun to remember the genuine worry in the community around RSA and the (really, really shocking at the time!) progress in factorization leading up to GNFS techniques. Like, it really looked like everything was going to fall apart. We all rushed to 1024 bit keys, and then to 2048 bit after what felt like a few months. And... maybe even that wouldn't be enough? And actual history ended up being the boring v…

RSA-260 has a 862 bit key. In terms of work, a 1024 bit key is only about 50-100x more work to break than the factorization posted in TFA.

Re: RSA-260 Factorized

#29

Post by adastra22 »

layer8 wrote: post #12
ajross wrote: post #7

It's sort of fun to remember the genuine worry in the community around RSA and the (really, really shocking at the time!) progress in factorization leading up to GNFS techniques. Like, it really looked like everything was going to fall apart. We all rushed to 1024 bit keys, and then to 2048 bit after what felt like a few months. And... maybe even that wouldn't be enough? And actual history ended up being the boring v…

ECC does have the benefit of smaller keys, but yes, RSA seems fine security-wise for the foreseeable future.

RSA-1024 absolutely is not.
Post reply on HN