Journal of Cryptographic Engineering Computer Networks and Communications
Comments on “Montgomery inversion"
Abstract
The constant-time Montgomery inversion algorithms proposed by Savaş and Koç are an important contribution to the field of side-channel resistant cryptography. Building upon their innovative work, this paper explores the behavior of these algorithms under specific input conditions. Our analysis suggests that for certain inputs, the constant-time binary extended Euclidean algorithm produces an incorrect result due to a subtle interaction within a dummy branch. A similar observation is made for the constant-time algorithm based on Kaliski’s method, where the post-loop adjustment logic does not appear to cover all possible intermediate outcomes. To enhance the robustness of these valuable algorithms, we propose minor and targeted refinements. These adjustments ensure mathematical correctness across all inputs while fully preserving the elegance and security of the original constant-time design.