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.
replyRSA 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).
replyThere 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.
replyand 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)
replyI'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.
replydeleted
reply