Comment by stouset
6 hours 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.
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.
1 reply →
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.