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

41–50 of 82 posts

Re: RSA-260 Factorized

#41

Post by stouset »

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…

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

Re: RSA-260 Factorized

#42

Post by mswphd »

stouset wrote: post #41
aaronmdjones wrote: post #38

Earlier quoted context omitted.

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…

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

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)

Re: RSA-260 Factorized

#43

Post by pseudohadamard »

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…

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.

Re: RSA-260 Factorized

#44

Post by pseudohadamard »

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…

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.

Re: RSA-260 Factorized

#45

Post by [deleted] »

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…

[deleted]

Re: RSA-260 Factorized

#46

Post by pseudohadamard »

adastra22 wrote: post #29
layer8 wrote: post #12

Earlier quoted context omitted.

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

RSA-1024 absolutely is not.

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

Re: RSA-260 Factorized

#48

Post by charcircuit »

bawolff wrote: post #34
internet2000 wrote: post #22

Earlier quoted context omitted.

[flagged]

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

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

Re: RSA-260 Factorized

#49

Post by adastra22 »

pseudohadamard wrote: post #46
adastra22 wrote: post #29

Earlier quoted context omitted.

RSA-1024 absolutely is not.

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

Re: RSA-260 Factorized

#50

Post by hnaccount_rng »

charcircuit wrote: post #48
bawolff wrote: post #34

Earlier quoted context omitted.

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

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…

Post reply on HN