Paper 2017/437
Slothful reduction
Abstract
In the implementation of many public key schemes, there is a need to implement modular arithmetic. Typically this consists of addition, subtraction, multiplication and (occasionally) division with respect to a prime modulus. To resist certain side-channel attacks it helps if implementations are ``constant time''. As the calculations proceed there is potentially a need to reduce the result of an operation to its remainder modulo the prime modulus. However often this reduction can be delayed, a process known as ``lazy reduction''. The idea is that results do not have to be fully reduced at each step, that full reduction takes place only occasionally, hence providing a performance benefit. Here we extend the idea to determine the circumstances under which reduction can be delayed to the very end of a particular public key operation.
Note: Added RFC7748 analysis
Metadata
- Available format(s)
-
PDF
- Category
- Implementation
- Publication info
- Preprint.
- Contact author(s)
- mike scott @ miracl com
- History
- 2024-05-19: last of 9 revisions
- 2017-05-22: received
- See all versions
- Short URL
- https://ia.cr/2017/437
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2017/437,
author = {Michael Scott},
title = {Slothful reduction},
howpublished = {Cryptology {ePrint} Archive, Paper 2017/437},
year = {2017},
url = {https://eprint.iacr.org/2017/437}
}
