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

61–70 of 82 posts

Re: RSA-260 Factorized

#61

Post by charcircuit »

hnaccount_rng wrote: post #50
charcircuit wrote: post #48

Earlier quoted context omitted.

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

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…

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.

Re: RSA-260 Factorized

#62

Post by rcxdude »

rho4 wrote: post #54
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?

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.

Re: RSA-260 Factorized

#63

Post by Dylan16807 »

mattashii wrote: post #21
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…

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.

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

Re: RSA-260 Factorized

#64

Post by Dylan16807 »

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.

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.

Re: RSA-260 Factorized

#65

Post by raverbashing »

aaronmdjones wrote: post #38
mattashii wrote: post #21

Earlier quoted context omitted.

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.

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 (t…

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

Re: RSA-260 Factorized

#66

Post by fsh »

adastra22 wrote: post #60
tgv wrote: post #52

Earlier quoted context omitted.

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…

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.

Re: RSA-260 Factorized

#67

Post by fsh »

adastra22 wrote: post #58
heavenlyblue wrote: post #53

Earlier quoted context omitted.

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…

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

Re: RSA-260 Factorized

#68

Post by Dylan16807 »

ajross wrote: post #32
tptacek wrote: post #23

Earlier quoted context omitted.

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.

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…

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.

Re: RSA-260 Factorized

#69

Post by upofadown »

mswphd wrote: post #15
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…

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…

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.

Re: RSA-260 Factorized

#70

Post by upofadown »

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…

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.

Post reply on HN