SCIS 2022
2022 Symposium on
Cryptography and Information Security
Osaka, Japan & Online, Jan. 18 – 21, 2022
The Institute of Electronics,
Information and Communication Engineers

Copyright ©2022 The Institute of Electronics,
Information and Communication Engineers

Efficient Modular Inversion Resisting Side Channel Attack
Yaoan Jin ∗Atsuko Miyaji†

Keywords: constant time modular inversion (CTMI), constant time GCD, side channel attack(SCA).

Abstract

1

With the development of side channel attack (SCA),
theoretically proved secure cryptosystems, digital signatures, protocols, etc. are no longer secure on internet of things (IoT) devices and PCs. Specifically,targeting the SCA weakness of binary euclidean algorithm (BEA) and binary extended euclidean algorithm (BEEA), which are used to compute greatest
common divisor (GCD) and modular inversion (MI) respectively, simple power analysis (SPA), cache-timing
attack (CTA), machine learning-based profiling attack(ML-PA) were conducted on RSA key generation andECDSA with high success rate. As for countermeasures, one can hide the secret input values by appropriate masking procedure. Otherwise, the constanttime modular inversion (CTMI) algorithm based on
Fermat’s little theorem (FLT) maybe a good choice.
However it can not compute GCD and is not efficientfor general inputs. [WB14] and [BY19] proposed CTMI
algorithms respectively, which are not based on FLT.
Their algorithms can work on more computation tasks
including modular inversion but also lost efficiency. Small
number of iterations and simple computations during
one iteration are good characteristics of a CTMI algorithm. We propose a new CTMI algorithm, whichcombines the basic idea of BEEA and the fact, ∀A, B ∈Z, GCD(A, B) = GCD(B, A − B) = GCD(A, A −B), satisfies these characteristics. Our CTMI algorithms resisting SCA can compute the same computation tasks as [BY19]. Compared with [BY19] andFLT, Our CTMI algorithms computes both GCD andMI much efficiently by experiments.

[WB14] proposed a CTMI algorithm by improving
Kaliski’s algorithm to a constant-time version. The
basic idea is that computing the contents of all branches
then selecting the correct values from them according
to the defined signal variables during each iteration.
Because the total bit length of the inputs (a numbera and a prime p) reduces at least one every iterationin the CTMI algorithm. [WB14] fixed the number ofiterations as 2 · bitlen(p).
[BY19] also proposed a CTMI algorithm. The computations during one iteration are more simple than
[WB14], but its number of iterations defined by ⌊(49d+57)/17⌋(d ≥ 46), where d = max(bitlen(a), bitlen(p)),
is much more.

2Related work

Our work

Our setting of the constant number of iterations isthe same as [WB14]. The main computations in ourCTMI algorithm are base on:
 GCD(a, b) = GCD(a, b−a2 ), odd(a), odd(b)GCD(a, b) = GCD( 2b , b − a), odd(a), even(b).
GCD(a, b) = GCD( a2 , b − a), even(a), odd(b).
(1)
where a, b ∈ Z and a ≤ b. Note that there are branches
in our algorithm, but the computations in each branch
are the same without dummy computations. It is easy
to remove branches from our algorithm by tricks. Ouralgorithm can also compute Montgomery inversion. We
analyze SCA security and efficiency of our work froma theoretical and experimental point of view.

∗Graduate School of Engineering, Osaka University, 2-1 Yamadaoka, Suita, Osaka, Japan. jin@cy2sec.comm.eng.osakau.ac.jp† Graduate School of Engineering, Osaka University, 2-1 Yamadaoka, Suita, Osaka, Japan and Japan Advanced Institute of Science and Technology, 1-1 Asahidai, Nomi, Ishikawa,Japan. miyaji@comm.eng.osaka-u.ac.jp

References[1] [BY19] Bernstein, Daniel J., and Bo-Yin Yang.,“Fast constant-time gcd computation and modularinversion.” IACR Transactions on Cryptographic
Hardware and Embedded Systems, (2019): 340-398.
[2] [WB14] Bos, Joppe W, “Constant time modularinversion.” Journal of Cryptographic Engineering(2014): 275-281.
1