mbedtls
mbedtls copied to clipboard
Use mpi_core_exp_mod in bignum
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