Paper 2021/1292

A Fast Large-Integer Extended GCD Algorithm and Hardware Design for Verifiable Delay Functions and Modular Inversion

Kavya Sreedhar, Mark Horowitz, and Christopher Torng


The extended GCD (XGCD) calculation, which computes B\'ezout coefficients $b_a, b_b$ such that $b_a * a_0 + b_b * b_0 = GCD(a_0, b_0)$, is a critical operation in many cryptographic applications. In particular, large-integer XGCD is computationally dominant for two applications of increasing interest: verifiable delay functions that square binary quadratic forms within a class group and constant-time modular inversion for elliptic curve cryptography. Most prior work has focused on fast software implementations. The few works investigating hardware acceleration build on variants of Euclid's division-based algorithm, following the approach used in optimized software. We show that adopting variants of Stein's subtraction-based algorithm instead leads to significantly faster hardware. We demonstrate this fact by performing a large-integer XGCD accelerator design space exploration to quantify the tradeoffs between Euclid- and Stein-based algorithms for various application requirements. This exploration leads us to an XGCD hardware accelerator that is flexible and efficient, supports fast average and constant-time evaluation, and is easily extensible for polynomial GCD. Our 16nm ASIC design calculates 1024-bit XGCD in 294ns (8X faster than the state-of-the-art ASIC) and constant-time 255-bit XGCD for inverses in the field of integers modulo the prime $2^{255} - 19$ in 87ns (31X faster than state-of-the-art software). We believe our chip is the first high-performance ASIC for the XGCD computation that is also capable of constant-time evaluation.

Available format(s)
Publication info
Preprint. Minor revision.
Extended GCDASICVerifiable delay functionClass groupsSquaring binary quadratic formsConstant-timeModular inversionCurve25519
Contact author(s)
skavya @ stanford edu
horowitz @ ee stanford edu
ctorng @ stanford edu
2022-05-10: last of 3 revisions
2021-09-27: received
See all versions
Short URL
Creative Commons Attribution


      author = {Kavya Sreedhar and Mark Horowitz and Christopher Torng},
      title = {A Fast Large-Integer Extended GCD Algorithm and Hardware Design for Verifiable Delay Functions and Modular Inversion},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1292},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.