← All research spotlights

Research spotlight · Unit 2

Daniel J. Bernstein

University of Illinois Chicago

Research field
Cryptography, algorithms for secure and fast computation

Daniel J. Bernstein designs cryptographic systems and the algorithms that run them safely on real computers, where the time a computation takes can betray a secret. With Bo-Yin Yang he developed a variant of Euclid's algorithm whose sequence of operations does not depend on its input, so that a secret key cannot be read off the timing of a gcd or modular inversion, and showed that it is also faster than the earlier safe methods. The algorithm now computes the modular inverses in the library that signs Bitcoin transactions. The unit presents it right after the extended Euclidean algorithm, whose data-dependent quotients it was designed to avoid.

In the masterclass

Section 4, after the extended Euclidean algorithm and its Bézout coefficients, shows how Bernstein and Yang made the algorithm run in constant time.

The research is presented in Unit 2: Divisibility and the Euclidean Algorithm, in a research spotlight box that explains the result at the level of the unit and links it to what you have just learned.

The paper

Bernstein, D. J., Yang, B.-Y. (2019). Fast constant-time gcd computation and modular inversion. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2019(3), 340‑398. https://doi.org/10.46586/tches.v2019.i3.340-398

The scientists named here are not contributors to the NT Masterclass, are not affiliated with it, and have not endorsed it. The program presents and explains their published research, with references to the original papers.