International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Fast constant-time gcd computation and modular inversion

Authors:
Daniel J. Bernstein , Department of Computer Science, University of Illinois at Chicago, Chicago, IL 60607–7045, USA; Horst Görtz Institute for IT Security, Ruhr University Bochum
Bo-Yin Yang , Institute of Information Science and Research Center of Information Technology and Innovation, Academia Sinica, 128 Section 2 Academia Road, Taipei 115-29
Download:
DOI: 10.13154/tches.v2019.i3.340-398
URL: https://tches.iacr.org/index.php/TCHES/article/view/8298
Search ePrint
Search Google
Presentation: Slides
Abstract: This paper introduces streamlined constant-time variants of Euclid’s algorithm, both for polynomial inputs and for integer inputs. As concrete applications, this paper saves time in (1) modular inversion for Curve25519, which was previously believed to be handled much more efficiently by Fermat’s method, and (2) key generation for the ntruhrss701 and sntrup4591761 lattice-based cryptosystems.
Video from TCHES 2019
BibTeX
@article{tches-2019-29328,
  title={Fast constant-time gcd computation and modular inversion},
  journal={IACR Transactions on Cryptographic Hardware and Embedded Systems},
  publisher={Ruhr-Universität Bochum},
  volume={2019, Issue 3},
  pages={340-398},
  url={https://tches.iacr.org/index.php/TCHES/article/view/8298},
  doi={10.13154/tches.v2019.i3.340-398},
  author={Daniel J. Bernstein and Bo-Yin Yang},
  year=2019
}