Fast constant-time gcd computation and modular inversion

Daniel J.  Bernstein; Bo-Yin Yang

Paper 2019/266

Fast constant-time gcd computation and modular inversion

Daniel J. Bernstein and Bo-Yin Yang

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.

Metadata

Available format(s): PDF
Category: Implementation
Publication info: A minor revision of an IACR publication in TCHES 2019
Keywords: Euclid's algorithm greatest common divisor gcd modular reciprocal modular inversion constant-time computations branchless algorithms algorithm design NTRU Curve25519
Contact author(s): authorcontact-safegcd @ box cr yp to
History: 2019-04-13: revised; 2019-03-06: received; See all versions
Short URL: https://ia.cr/2019/266
License: CC BY

BibTeX

@misc{cryptoeprint:2019/266,
      author = {Daniel J.  Bernstein and Bo-Yin Yang},
      title = {Fast constant-time gcd computation and modular inversion},
      howpublished = {Cryptology {ePrint} Archive, Paper 2019/266},
      year = {2019},
      url = {https://eprint.iacr.org/2019/266}
}