Miyaji Laboratory

Data confidentiality is indispensable for ensuring secure communications, and cryptographic techniques are employed as the primary means of implementation. In particular, public-key cryptography, whose security relies on the computational hardness of decryption, stands as a fundamental pillar of modern communication infrastructure. While RSA, Elliptic Curve Cryptography (ECC), and Isogeny-based cryptography are prominent examples, the modular inversion calculation required within their processes consumes significantly more time than other logical operations, thereby becoming a bottleneck in implementation. Even if a public-key cryptosystem is proven to be mathematically secure, this does not guarantee equivalent security in its actual implementation. A significant threat to real-world systems is Side-Channel-Attacks (SCA), particularly timing attacks, which attempt to recover secret keys by analyzing fluctuations in execution time. To resist such attacks, constant-time implementation where execution time remains invariant regardless of the input values is essential. However, guaranteeing constant time necessitates aligning the algorithm with the most computationally expensive input scenario. This introduces redundancy in average cases, making the establishment of efficient implementation techniques a critical challenge. In this study, we analyze the iteration counts and the cost per iteration of Bernstein-Yang's "divstep" algorithm which has garnered attention for Constant-Time Modular Inversion (CTMI) as well as the improved methods proposed by Jin-Miyaji (JM), Kuramoto-Miyaji (KM), and Pornin. Based on the insights obtained, first, we provide a more rigorous proof of the iteration counts for the JM and KM methods. Second, we propose a novel CTMI algorithm that addresses the bottlenecks of existing methods while maintaining constant-time properties. Experimental results on a 13th Gen Intel Core i7-1360P @ 2.2GHz demonstrate that the proposed algorithm reduces computation time by 93.12% compared to KM, 21.52% compared to divstep, and 9.70% compared to Pornin.