RSA-260 Factorized

Posted by samyok 5 days ago

Comments

Comment by nk_kolja 5 days ago

Impressive. I wonder the methodology. Algorithmic improvements? More probably just an implementational optimisation. Last RSA record was due to special q sieving methods if I recall well, some 3k core hours. I hope there’s a theoretical improvement behind the result.

Comment by nk_kolja 4 days ago

So RSA 260 is about 2-3 times harder than RSA 250, which was solved in 2700 core hours in 2020, so it’s probably no algorithmic improvements, just a tweak here and there plus faster hardware.

Comment by alexfoo 4 days ago

2700 core years

Comment by nk_kolja 3 days ago

Of course years. Typo.

Comment by mswphd 4 days ago

faster hardware could also mean gpu/asic/etc.

Comment by ni5arga 3 days ago

I'm assuming it is still GNFS but GPU backed.

For reference, check this out:

> cuda-sieve is an experimental, standalone CUDA implementation of the lattice-sieving relation-collection pipeline used by the Number Field Sieve. It builds factor bases, sieves both sides of a special-q lattice, performs trial division and GPU cofactorisation, and emits relations for msieve.

https://github.com/kyleaskine/cuda-sieve

Comment by learningstud 3 days ago

The general public is gradually catching up with NSA it seems...

Comment by 4 days ago

Comment by aaron695 4 days ago

[dead]

Comment by madars 5 days ago

"4397328654844826923795068102505872571721883526553349659561256924505973939597593482272505698004801207988043088656411102133523080581 divides RSA-260"

Background: https://en.wikipedia.org/wiki/RSA_Factoring_Challenge

Comment by samyok 5 days ago

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

Comment by rho4 3 days ago

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?

Comment by rcxdude 3 days ago

The ordering is stupid because some of them are named by the number of bits and some of them are named by the number of decimal digits. They are in order of size and this is the largest one so far, despite the confusing names.

Comment by ajross 4 days ago

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 version: it was absolutely enough, factorization is seemingly settled math at this point, no new techniques have been discovered.

At the end of the day RSA was just fine and no one really needed to bother with ECC and all of its confusing tutorials.

And the ~23 year old 1024 bit key holding my GnuPG box closed is still just fine, cryptographically. (Though the chances of getting hit with a keylogger or other side channel attack over that period are nontrivially high and I suppose I really should rotate it or something).

Comment by stouset 4 days ago

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 arithmetic rather than needing bignums) and far better suited for embedded devices. Migration has been an enormous win even if you think the security of RSA is fine.

Comment by red_admiral 3 days ago

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.

Comment by consp 3 days ago

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

Depends on what your goal is and if you like more footguns.

Comment by pseudohadamard 3 days ago

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.

Comment by red_admiral 3 days ago

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

Comment by pseudohadamard 3 days ago

EdDSA is also quite a mess, see e.g. https://hdevalence.ca/blog/2020-10-04-its-25519am/. Almost no two implementations that aren't the same code base can agree on what is and isn't a valid signature. ECDSA isn't nearly as bad, there's only two forms of the same signature possible and implementations seem to generate either of the two at random (this makes for a great subliminal channel to leak the private key if you don't have the source code). With RSA PKCS #1 (but not PSS) there's one and only one form for a signature.

So oddly enough the supposedly really bad insecure terrible etc PKCS #1 RSA is the only one where the signature is totally unambiguous.

Comment by 3 days ago

Comment by mattashii 4 days ago

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.

Comment by aaronmdjones 3 days ago

RSA operations are performed modulo n, where n is the product of 2 primes. A 2048-bit RSA key is an n that is 2048 bits long (with the most significant bit set by definition).

There are no consumer CPUs that have 2048-bit-wide registers; even AVX10 tops out at 512 bits. Thus, mathematical operations on RSA keys are performed using arbitrary precision integer libraries like OpenSSL's own BN (BigNum) library, or GMP (the GNU Multiple Precision Arithmetic Library) as used by GNUTLS, in software.

For example, adding 1 to an arbitrary precision integer is not a CPU add or increment instruction, nor is multiplying 2 integers (or an integer and a constant factor) a CPU multiplication instruction.

Comment by stouset 3 days ago

256-bit ECC on the other hand is frequently performed by 4-wide 64-bit operations with a little extra accounting.

Comment by mswphd 3 days ago

and the more recent (post-quantum) lattice-based stuff can get away with ~16 bit arithmetic (it's vectors of ~512-1024 dimension, but the operations are SIMD-friendly)

Comment by monster_truck 3 days ago

Can get all the way down to 4 with a little CRT/RNS if you're trying to go even faster

Comment by raverbashing 3 days ago

Honestly BigInts are not a big deal, they're pretty mature at this day and age (and I mean, 20 yrs ago)

Comment by Dylan16807 3 days ago

> AFAIK you can do all RSA maths with registers just double as wide as the key, no variable width anything required there.

Yeah, you don't need variable width, you just need a kind of register that basically doesn't exist.

Comment by mswphd 4 days ago

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 main concern for RSA is not GNFS, but something stronger. SOTA RSA attacks (such as GNFS) use "index calculus". You can also use index calculus to attack finite field diffie hellman. In the 2010's, there was remarkable progress in index calculus attacks against finite field DH in the small characteristic case. For example, the current record for binary characteristic finite field DH is ~30k bits (and this is by an academic --- a nation state could definitely do more).

It is not known that similar progress is possible in other cases (such as for RSA). But it's very much possible that factoring is much easier than expected. Simultaneously I wouldn't personally bet money on it, and if that breakthrough happened, there were sufficient warning signs that I would feel justified in saying "told you so" to people trusting RSA.

Comment by upofadown 3 days ago

It's not just because the GPG user is small fry that 1024 bit RSA is low risk for them. It is mostly because there is only one of them. A nation state attacker would have to spend billions of dollars and years of lost opportunity to use their resource more effectively to get the messages/files of a single person. There are much cheaper and faster ways to accomplish the same thing.

If, say, Gmail was using some static 1024 bit RSA based scheme things would be different. Then an attacker would get the messages of billions of users.

Comment by ajross 4 days ago

> 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 that factoring is much easier than expected

And this is sort of toothless? I mean, that's true for ECC too. It's true for all cryptography. It's true for all software. For all engineering. For all math. We'll never know what we don't know. New discoveries tomorrow may upend everything any given property ("safety" is just one) we think our existing machines hold.

But they probably won't. And the moments where that happens are extremely rare. And to be blunt RSA already got hit with that particular lightning bolt.

Comment by pseudohadamard 3 days ago

There's also the question of why anyone would bother. You can factor RSA-1024 today in about a year with a national-lab-level supercomputer. Which 1k-bit RSA key would you shut down a national lab for a year for to factor? Heck, which key would you shut it down for a week for to factor? There's no single key out there of any interest when you can just spear-phish your intended target, or get RCE on their unpatched router, or get the cleaners to plug in a USB key and let it do its thing while they're vaccuuming, or whatever.

Comment by tptacek 4 days ago

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.

Comment by ajross 3 days ago

Everyone wants to argue crypto when my point was precisely the opposite (to wit: "Two decades after the factoring freakout, RSA is fine, go figure"), but whatever. I'll retract that when they break it. But the pace has been slowing down, not speeding up. Getting from RSA-250 to -260 was six years. That's not going to get us there before I kick it, at least.

If you want to pin me down on something slightly more formal: DRAM density scaling kinda stopped a few years back, systems aren't getting any bigger (much to Sam Altman's public dismay), and there is a superlinear matrix size requirement in factorization techniques that AFAIK no one knows how to fix. We can get the cycles to do it, but not the space.

Probably. Maybe not! But even so, it will remain cheaper to steal my secrets with the proverbial $5 wrench. RSA? It was fine.

Comment by Dylan16807 3 days ago

The last few jumps between 2x0 were 3 years, 2 years, 1 year, 1 year, and 6 years.

I don't think you can extrapolate that into "slowing down". It wouldn't even be surprising if the next five jumps averaged 2 years each and RSA-1024 was cracked in a decade.

I'm sure RAM is an issue but I don't expect it to be a hard wall.

Comment by adgjlsfhk1 3 days ago

honestly I wouldn't be shocked if 2048 bit rsa gets factored in our lifetime. GNFS doesn't have the feel of an optimal algorithm. dropping to L(1/4) would bring 1500 bits into reach, and it seems plausible still that factoring is polynomial.

Comment by mswphd 3 days ago

any cryptography can break at any time. Sometimes "sudden" breaks happen. You can't defend against these, so there (perversely) isn't that much of a point worrying about them, besides using schemes many people have thought about for a while.

Another way cryptography breaks is via iterative improvements. For example, in the last few months there are two big cryptanalytic stories

1. The novel scheme (though not standardized) HAWK had its security reduced by ~1/2 by AI. It is no longer compelling in any way. This was in a sense "predictable" though. There was a series of papers showing that HAWK-like schemes were vulnerable to an attack of this type. Then, AI was able to bridge the gap and apply these attacks directly to HAWK.

2. The ISO-standardized scheme McCliece (from ~45 years ago) has had some alarming security reductions, and may be effectively broken (it's still a little early to tell, many cryptanalytic papers require heuristics that must be justified, etc). Again, this was in a sense "predictable". Starting ~3 years ago it was discovered that McCliece had some yet-unexploited structure, and since then there have been more and more papers exploiting this further, until recently more dramatic attacks have occurred.

In both cases, there is a clear "story" you can (post-hoc) tell about the attacks. You can't always predict precisely where the attacks will end up (for the McCliece attack, it appears more effective than I would have predicted at least). But you can often tell when things are gradually weakening, before a full collapse.

RSA has a cousin (binary characteristic finite field DH) that had this gradual weakening into total collapse happen in the 2010s. It is possible this cousin was a problem child, and GNFS will remain the best attack against RSA until quantum computers fully break it. I can't predict the future. But I can say that ECC has had no such problematic cousins.

This is to say that we are blessed that we have extremely strong cryptography available. Why you would choose to use the weakest defensible option is beyond me, and not something anyone serious about security would ever recommend doing. There is no upside, and only downsides.

Comment by ajross 3 days ago

> Why you would choose to use the weakest defensible option

I still remain confused why people are interpreting this from what I wrote. I'm not "choosing" to use RSA nor advocating for its use. I'm pointing out anecdotally that I have a GnuPG keychain still live with a 1024 bit key from the last millenium (or close to that, honestly I don't know for sure) that everyone was *sure*, 20 years ago, was broken and insecure. And... it wasn't. It's fine.

The xkcd point seems profound to me: the crypto nerds were entirely wrong about their focus and sense of urgency here. Today, it's much cheaper to steal my key with simple violence. It will remain so when I'm on my death bed. Probably when my heirs are too. And I find that interesting. What else are we nerds getting wrong?

Comment by adastra22 3 days ago

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.

Comment by upofadown 3 days ago

This article (mine) is about this:

2048 Bit RSA and the Year 2030 https://articles.59.ca/doku.php?id=em:20482030

I guess it could be updated to include this latest factoring result. Said result would not change the conclusion of the article.

Comment by layer8 4 days ago

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

Comment by adastra22 3 days ago

RSA-1024 absolutely is not.

Comment by pseudohadamard 3 days ago

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

Comment by adastra22 3 days ago

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 factoring hardware that would be multiple orders of magnitude more efficient.

It is quite likely that there are at least two actors (US and China) that can break RSA-1024, and they are no doubt working through a priority list of all accessible servers with such weak keys. If your firewall is not broken & now back-doored, it is only because you're not important enough to have gotten to yet.

RSA-2048 (or better, RSA-3072) is usually a drop-in replacement. ECC would be even better. There is no reason not to.

Comment by hnaccount_rng 3 days ago

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

Comment by adastra22 3 days ago

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.

Comment by pseudohadamard 3 days ago

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

If you're running something with code from a large US corporation, or outsourced to contractors, or made in China, or with a web interface, or [3 more pages of stuff] and your main worry is the size of your RSA keys, then I've got a Fortigate security appliance to sell you.

Comment by hnaccount_rng 1 day ago

I would have formulated it less dismissively than my sibling but yes. There are ~no scenarios, where the Cloud act is not the more straightforward solution. Even factoring RSA-1024 will take non-zero compute time. And that can be spend more productively

Comment by 4 days ago

Comment by mikestorrent 4 days ago

You can just send the gnupg box and keys to me, I will hold them securely for you so you don't have to worry about it

Comment by pugfugly 4 days ago

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

Comment by catlifeonmars 3 days ago

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.

Comment by adastra22 3 days ago

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.

Comment by arcticbull 3 days ago

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

Comment by smallerize 3 days ago

Yes, but since R&D and funding are in a feedback loop now (promising results -> more money -> better results etc), it might only take a couple more years to get there. https://arstechnica.com/science/2026/06/amazon-quera-promise...

Comment by adastra22 3 days ago

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.

Comment by Dylan16807 3 days ago

It's really really easy to eliminate noise in a digital system of transistors. For analog systems with subtle values, I would say we still can't arbitrarily scale that up with transistors. And quantum is like analog but far worse.

Comment by heavenlyblue 3 days ago

transistors are local unit, qubits are not

Comment by adastra22 3 days ago

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.

Comment by fsh 3 days ago

Photonic quantum interfaces typically operate at glacial speeds and with terrible fidelities. There is a lot more missing than good qubits.

Comment by tgv 3 days ago

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

Comment by adastra22 3 days ago

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.

Comment by fsh 3 days ago

Electrical engineers in the 1940s already had "infinitely stable" memory in the form of delay lines and Williams tubes. Quantum error correction is incomparably more difficult than using digital bits.

Comment by shaaaade 3 days ago

Why is it that every time I read about quantum computers, fusion, and high energy density batteries, the word "just" seems extremely load-bearing, but results are like just, nowhere to be seen

Comment by catlifeonmars 3 days ago

What does indefinitely stable mean?

Comment by Davidzheng 3 days ago

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

Comment by jgalt212 3 days ago

depending on your definition of "super fast" all forms of crypto could fall.

Comment by dclavijo 5 days ago

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

Comment by internet2000 4 days ago

[flagged]

Comment by adastra22 3 days ago

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.

Comment by tyre 3 days ago

I heard it was a lucky guess

Comment by bawolff 3 days ago

Seems unlikely given claude would not really be effective for this type of problem.

Comment by charcircuit 3 days ago

Why not? Claude has already shown it can automate mathematics and it can automate programming and running programs (including renting the servers).

Comment by hnaccount_rng 3 days ago

Because there is nothing not already automated here. RSA will either be cracked because some assumption about prime numbers doesn’t hold or because we throw more and more brute force on it.

And if it were the former it wouldn’t be the “next” in line that would be cracked…

Comment by charcircuit 3 days ago

You don't have to have RSA be broken in order to get a competitive advantage over other people searching. You just need Claud to find software optimization that got overlooked or something from number theory to come up with better candidates to guess.

Comment by bawolff 3 days ago

True, but if that happened, i think that would be the headline, not RSA-260 was factorized.