Compact and Efficient Constant-Time GCD and Modular Inversion with Short-Iteration

Yaoan JIN; Atsuko MIYAJI

doi:10.1587/transinf.2022ICP0009

Compact and Efficient Constant-Time GCD and Modular Inversion with Short-Iteration

Yaoan JIN, Atsuko MIYAJI

Full Text Views

0

Cite this

Summary :

Theoretically secure cryptosystems, digital signatures may not be secure after being implemented on Internet of Things (IoT) devices and PCs because of side-channel attacks (SCA). Because RSA key generation and ECDSA require GCD computations or modular inversions, which are often computed using the binary Euclidean algorithm (BEA) or binary extended Euclidean algorithm (BEEA), the SCA weaknesses of BEA and BEEA become a serious concern. Constant-time GCD (CT-GCD) and constant-time modular inversion (CTMI) algorithms are effective countermeasures in such situations. Modular inversion based on Fermat's little theorem (FLT) can work in constant time, but it is not efficient for general inputs. Two CTMI algorithms, named BOS and BY in this paper, were proposed by Bos, Bernstein and Yang, respectively. Their algorithms are all based on the concept of BEA. However, one iteration of BOS has complicated computations, and BY requires more iterations. A small number of iterations and simple computations during one iteration are good characteristics of a constant-time algorithm. Based on this view, this study proposes new short-iteration CT-GCD and CTMI algorithms over F_p borrowing a simple concept from BEA. Our algorithms are evaluated from a theoretical perspective. Compared with BOS, BY, and the improved version of BY, our short-iteration algorithms are experimentally demonstrated to be faster.

Publication: IEICE TRANSACTIONS on Information Vol.E106-D No.9 pp.1397-1406

Publication Date: 2023/09/01

Publicized: 2023/07/13

Online ISSN: 1745-1361

DOI: 10.1587/transinf.2022ICP0009

Type of Manuscript: Special Section PAPER (Special Section on Information and Communication System Security)

Category

Authors

Yaoan JIN
Osaka University
Atsuko MIYAJI
Osaka University

Keyword

constant-time modular inversion (CTMI), constant-time greatest common divisor (CT-GCD), and side channel attacks (SCA)

Cite this

Copy

Yaoan JIN, Atsuko MIYAJI, "Compact and Efficient Constant-Time GCD and Modular Inversion with Short-Iteration" in IEICE TRANSACTIONS on Information, vol. E106-D, no. 9, pp. 1397-1406, September 2023, doi: 10.1587/transinf.2022ICP0009.
Abstract: Theoretically secure cryptosystems, digital signatures may not be secure after being implemented on Internet of Things (IoT) devices and PCs because of side-channel attacks (SCA). Because RSA key generation and ECDSA require GCD computations or modular inversions, which are often computed using the binary Euclidean algorithm (BEA) or binary extended Euclidean algorithm (BEEA), the SCA weaknesses of BEA and BEEA become a serious concern. Constant-time GCD (CT-GCD) and constant-time modular inversion (CTMI) algorithms are effective countermeasures in such situations. Modular inversion based on Fermat's little theorem (FLT) can work in constant time, but it is not efficient for general inputs. Two CTMI algorithms, named BOS and BY in this paper, were proposed by Bos, Bernstein and Yang, respectively. Their algorithms are all based on the concept of BEA. However, one iteration of BOS has complicated computations, and BY requires more iterations. A small number of iterations and simple computations during one iteration are good characteristics of a constant-time algorithm. Based on this view, this study proposes new short-iteration CT-GCD and CTMI algorithms over F_p borrowing a simple concept from BEA. Our algorithms are evaluated from a theoretical perspective. Compared with BOS, BY, and the improved version of BY, our short-iteration algorithms are experimentally demonstrated to be faster.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2022ICP0009/_p

Copy

@ARTICLE{e106-d_9_1397,
author={Yaoan JIN, Atsuko MIYAJI, },
journal={IEICE TRANSACTIONS on Information},
title={Compact and Efficient Constant-Time GCD and Modular Inversion with Short-Iteration},
year={2023},
volume={E106-D},
number={9},
pages={1397-1406},
abstract={Theoretically secure cryptosystems, digital signatures may not be secure after being implemented on Internet of Things (IoT) devices and PCs because of side-channel attacks (SCA). Because RSA key generation and ECDSA require GCD computations or modular inversions, which are often computed using the binary Euclidean algorithm (BEA) or binary extended Euclidean algorithm (BEEA), the SCA weaknesses of BEA and BEEA become a serious concern. Constant-time GCD (CT-GCD) and constant-time modular inversion (CTMI) algorithms are effective countermeasures in such situations. Modular inversion based on Fermat's little theorem (FLT) can work in constant time, but it is not efficient for general inputs. Two CTMI algorithms, named BOS and BY in this paper, were proposed by Bos, Bernstein and Yang, respectively. Their algorithms are all based on the concept of BEA. However, one iteration of BOS has complicated computations, and BY requires more iterations. A small number of iterations and simple computations during one iteration are good characteristics of a constant-time algorithm. Based on this view, this study proposes new short-iteration CT-GCD and CTMI algorithms over F_p borrowing a simple concept from BEA. Our algorithms are evaluated from a theoretical perspective. Compared with BOS, BY, and the improved version of BY, our short-iteration algorithms are experimentally demonstrated to be faster.},
keywords={},
doi={10.1587/transinf.2022ICP0009},
ISSN={1745-1361},
month={September},}

Copy

TY - JOUR
TI - Compact and Efficient Constant-Time GCD and Modular Inversion with Short-Iteration
T2 - IEICE TRANSACTIONS on Information
SP - 1397
EP - 1406
AU - Yaoan JIN
AU - Atsuko MIYAJI
PY - 2023
DO - 10.1587/transinf.2022ICP0009
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E106-D
IS - 9
JA - IEICE TRANSACTIONS on Information
Y1 - September 2023
AB - Theoretically secure cryptosystems, digital signatures may not be secure after being implemented on Internet of Things (IoT) devices and PCs because of side-channel attacks (SCA). Because RSA key generation and ECDSA require GCD computations or modular inversions, which are often computed using the binary Euclidean algorithm (BEA) or binary extended Euclidean algorithm (BEEA), the SCA weaknesses of BEA and BEEA become a serious concern. Constant-time GCD (CT-GCD) and constant-time modular inversion (CTMI) algorithms are effective countermeasures in such situations. Modular inversion based on Fermat's little theorem (FLT) can work in constant time, but it is not efficient for general inputs. Two CTMI algorithms, named BOS and BY in this paper, were proposed by Bos, Bernstein and Yang, respectively. Their algorithms are all based on the concept of BEA. However, one iteration of BOS has complicated computations, and BY requires more iterations. A small number of iterations and simple computations during one iteration are good characteristics of a constant-time algorithm. Based on this view, this study proposes new short-iteration CT-GCD and CTMI algorithms over F_p borrowing a simple concept from BEA. Our algorithms are evaluated from a theoretical perspective. Compared with BOS, BY, and the improved version of BY, our short-iteration algorithms are experimentally demonstrated to be faster.
ER -