The search functionality is under construction.

The search functionality is under construction.

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

Yaoan JIN

Osaka University

Atsuko MIYAJI

Osaka University

The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.

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 -