The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Cryptosystèmes théoriquement sécurisés, les signatures numériques peuvent ne pas être sécurisées après avoir été mises en œuvre sur des appareils Internet des objets (IoT) et des PC en raison d'attaques par canal secondaire (SCA). Étant donné que la génération de clés RSA et ECDSA nécessitent des calculs GCD ou des inversions modulaires, qui sont souvent calculés à l'aide de l'algorithme euclidien binaire (BEA) ou de l'algorithme euclidien étendu binaire (BEEA), les faiblesses SCA de BEA et BEEA deviennent une préoccupation majeure. Les algorithmes GCD à temps constant (CT-GCD) et d'inversion modulaire à temps constant (CTMI) sont des contre-mesures efficaces dans de telles situations. L'inversion modulaire basée sur le petit théorème de Fermat (FLT) peut fonctionner en temps constant, mais elle n'est pas efficace pour les entrées générales. Deux algorithmes CTMI, nommés BOS et BY dans cet article, ont été proposés respectivement par Bos, Bernstein et Yang. Leurs algorithmes sont tous basés sur le concept du BEA. Cependant, une itération de BOS nécessite des calculs compliqués et BY nécessite plus d'itérations. Un petit nombre d'itérations et des calculs simples au cours d'une itération sont de bonnes caractéristiques d'un algorithme à temps constant. Sur la base de ce point de vue, cette étude propose de nouveaux algorithmes CT-GCD et CTMI à itérations courtes sur Fp empruntant un concept simple à BEA. Nos algorithmes sont évalués d’un point de vue théorique. Par rapport à BOS, BY et à la version améliorée de BY, il a été démontré expérimentalement que nos algorithmes à itérations courtes sont plus rapides.
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.
Copier
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 Fp 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
Copier
@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 Fp 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},}
Copier
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 Fp 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 -