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

51–60 of 82 posts

Re: RSA-260 Factorized

#51

Post by hnaccount_rng »

adastra22 wrote: post #49
pseudohadamard wrote: post #46

Earlier quoted context omitted.

Why not? What's the actual threat? Let's say I'm using RSA-1024 on my firewall today. What happens next?

RSA-1024 is approx 6 bits more security than the RSA-260 challenge, so ~64x more work to factor. That is negligible by cryptographic standards. We don't know yet how much work OP put into factoring the RSA-260 challenge. No doubt it was a lot, but probably done with general purpose GPU hardware. That will continue to get cheaper to mount in the near future, and we ought to assume that nation states have access to RSA…

You are right that there are better options and there is no excuse not to choose something better today. But that’s not what GP is arguing! It’s just that: For any given interest level there is no way that expending the resources to attack the RSA key is valuable! You are either willing to expend resources then attacking the owner is far cheaper or not then you are also not investing weeks-to-month of cluster time.

And from that perspective RSA-1024 is still perfectly adequate

Re: RSA-260 Factorized

#52

Post by tgv »

adastra22 wrote: post #27
catlifeonmars wrote: post #24

Earlier quoted context omitted.

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.

But those cannot exist, can they? Nature seems really opposed to the realisation of ideals.

Re: RSA-260 Factorized

#53

Post by heavenlyblue »

adastra22 wrote: post #39
arcticbull wrote: post #31

Earlier quoted context omitted.

So we only need to invent actual quantum computers. Got it, easy.

It's more akin to "we only need to make reliable transistors to make classical computers." With the invention of the planar transistor, going from 1 transistor to 100 or 100k was not that big of a step, comparatively.

transistors are local unit, qubits are not

Re: RSA-260 Factorized

#54

Post by rho4 »

samyok wrote: post #2

anddd it's already on wikipedia https://en.wikipedia.org/wiki/RSA_numbers#RSA-260

That list ordering drives me nuts. What's up with 1024?!

And how come much larger numbers have already been solved? Based on that information one cannot strictly assume that the current solution required improvements to the strategy or hardware, no?

Re: RSA-260 Factorized

#55

Post by red_admiral »

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…

Curve25519 exists because it's also easy to build ECC footguns - not checking if an input is a valid curve point comes to mind.

ECC is definitely more efficient though.

Then again, we're all supposed to switch to post-quantum.

Re: RSA-260 Factorized

#56

Post by red_admiral »

pseudohadamard wrote: post #43
stouset wrote: post #14

Earlier quoted context omitted.

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…

I'd say ECDSA is even worse, because almost anything you get even slightly wrong with Schnorr schemes ends up leaking the private key. With RSA OTOH you just use a decent library and something like encode-and-compare for signing and you're done. I'm much more nervous about something using ECDSA than RSA once I've had a look at the code and verified that it's at least somewhat competently written.

(EC)DSA is indeed fiddly enough that you wonder if it was an NSA operation in the first place. EdDSA on the other hand seems ok.

Re: RSA-260 Factorized

#57

Post by adastra22 »

hnaccount_rng wrote: post #51
adastra22 wrote: post #49

Earlier quoted context omitted.

RSA-1024 is approx 6 bits more security than the RSA-260 challenge, so ~64x more work to factor. That is negligible by cryptographic standards. We don't know yet how much work OP put into factoring the RSA-260 challenge. No doubt it was a lot, but probably done with general purpose GPU hardware. That will continue to get cheaper to mount in the near future, and we ought to assume that nation states have access to RSA…

You are right that there are better options and there is no excuse not to choose something better today. But that’s not what GP is arguing! It’s just that: For any given interest level there is no way that expending the resources to attack the RSA key is valuable! You are either willing to expend resources then attacking the owner is far cheaper or not then you are also not investing weeks-to-month of cluster time. A…

You don't know that. We're at the point where the NSA can assuredly break RSA-1024. We know they have sufficient processing power, and it would be silly of them not to have developed that capability.

"But they're not going to spend resources breaking my router!" No, not your router specifically. But batch GCD gives sqrt speedup over multiple keys, potentially 10's to 100's of millions of keys at once with off-the-shelf GPU clusters at NSA scale. Looking at that many keys at once tends to discover low-entropy biases common in consumer router hardware, which makes brute-forcing new keys from those devices trivial to do.

If you are actually operating a service relying on RSA-1024 security, it is almost certainly pwoned.

Re: RSA-260 Factorized

#58

Post by adastra22 »

heavenlyblue wrote: post #53
adastra22 wrote: post #39

Earlier quoted context omitted.

It's more akin to "we only need to make reliable transistors to make classical computers." With the invention of the planar transistor, going from 1 transistor to 100 or 100k was not that big of a step, comparatively.

transistors are local unit, qubits are not

Transistors connect to other transistors, directly or in switched arrangements. Qubits can be connected to other qubits likewise. E.g. a single photon emitter next to a nuclear spin qubit that can send an entangled photon through a beam splitter in a photonic switch, routing that entangled pair through fiber optic cables to other qubits where a combination of electric fields, filters, and occupied energy levels cause gate operations to be applied during absorption & re-emission. Except for the long-lived, error-corrected qubit, everything I described there is off-the-shelf commercial technology.

Re: RSA-260 Factorized

#60

Post by adastra22 »

tgv wrote: post #52
adastra22 wrote: post #27

Earlier quoted context omitted.

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.

But those cannot exist, can they? Nature seems really opposed to the realisation of ideals.

My company is making them. You just need to have a sufficiently resilient surface code, which means a single device with millions of physical qubits (the standard brute-force approach) or use a qubit architecture that is intrinsically noise-free by comparison, and only needs 15-50 physical qubits (what my company is doing, and our competitors). The industry as a whole is probably only a few years away from achieving this, in some form.

A "perfect" or "indefinitely stable" qubit sounds impossible. But so would a DRAM cell to an electrical engineer in the 40's. A DRAM cell continuously refreshes to maintain state, and as a result a single bit in RAM can have a mean time to failure measured in geologic time. Likewise a quantum error correction algorithm with a sufficiently large factor, driven continuously, will maintain qubit state indefinitely.

Post reply on HN