Hacker News Reader

Comment by stouset | Hacker News Reader

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.

View on HN

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.

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

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

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.

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.

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

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)

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

Honestly BigInts are not a big deal, they're pretty mature at this day and age (and I mean, 20 yrs 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.

Reply on news.ycombinator.com