mbedtls icon indicating copy to clipboard operation
mbedtls copied to clipboard

Use mpi_core_exp_mod in bignum

Open yanesca opened this issue 1 year ago • 0 comments

Description

Use mpi_core_exp_mod() in bignum.

The two algorithms are not equivalent. The original bignum exponentiation was a sliding window algorithm. The one in mpi_core_exp_mod() uses a fixed window approach. This change is intentional. We don't want to maintain two algorithms and decided to keep the fixed window algorithm.

The change of algorithms impacts performance. To keep the performance comparable to previous versions, the window size had to be increased.

The choice of the parameter was based on measurements on my development machine (Intel i5). This is 2nd-best and 2nd-worst of 5 runs, for three key sizes, in operations per second (so, higher is better). (As in https://github.com/Mbed-TLS/mbedtls/issues/6790.)

w 6 5 4 3 2 1 dev
2048 392-398 421-426 426-433 426-432 398-401 286-317 441-456
3072 148-149 152-158 145-152 150-153 133-136 108-108 143-156
4096 71-72 72-73 69-73 61-70 63-64 49-49 72-72

Fixes #6600 .

PR checklist

Please tick as appropriate and edit the reasons (e.g.: "backport: not needed because this is a new feature")

  • [ ] changelog provided
  • [ ] backport not required
  • [ ] tests already present

yanesca avatar Feb 14 '24 15:02 yanesca