Miyaji Laboratory

Today, internet of things (IoT) devices have penetrated into thousands of households. While enjoying the convenience of IoT devices, our interests are also compromised by the security vulnerabilities of IoT devices. The security of IoT devices should be taken seriously. In particular, the development of side channel attacks (SCAs) targeting IoT devices in recent years makes the security of IoT devices more and more important. Therefore, IoT devices with limited computational resources require compact cryptosystems resisting SCAs. Elliptic curve cryptosystems (ECCs) are typical public key cryptosystems (PKCs) that can ensure equivalent security with considerably shorter keys than Rivest-Shamir-Adleman (RSA). Therefore, compact ECCs are recommended for IoT devices. In ECCs, elliptic curve scalar multiplications (ECSMs) are dominant computations. Therefore, enhancing the security and
efficiency of ECSMs is important. In ECSMs, modular inversions are required when affine elliptic curve addition formulae are used. Modular inversions are also critical computations in elliptic curve digital signature algorithms (ECDSAs). Therefore, we also focus on secure and
compact modular inversions. An ECSM consists of a scalar multiplication algorithm and elliptic curve addition formulae.
Elliptic curve addition formulae based on affine coordinates are memory-saving and can be efficient according to the ratio of modular inversion cost to modular multiplication cost but weak against SCAs. Elliptic curve complete addition (CA) formulae based on projective coordinates
can achieve secure ECSMs resisting SCAs but are not compact. We focus on secure and efficient ECSMs taking advantage of the compact affine elliptic curve addition formulae. Greatest common divisor (GCD) computations or modular inversions are used in RSA key
generation, affine elliptic curve addition formulae, and ECDSAs. Therefore, we need focus on them for secure and efficient ECCs. GCD computations and modular inversions are often computed using the binary Euclidean algorithm (BEA) and binary extended Euclidean algorithm
(BEEA), respectively. Therefore, 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. A modular inversion by 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, were proposed by Bos, Bernstein and Yang, respectively. Their algorithms are all based on the concept of BEA. However, one iteration of BOS has compli
cated computations, and BY requires many iterations. A small number of iterations and simple computations during one iteration are good characteristics of a constant-time algorithm.

In the first part of this thesis, three notions of a secure ECSM, named generality of k, secure generality, and executable coordinates, are proposed. Then, the original affine elliptic curve addition formulae are extended to eliminate some exceptional points. We improve Joye's
regular 2-ary RL algorithm and propose new RL ECSMs, which can scan the input scalars from right to left (RL) using (extended) affine coordinates. For the security, we prove that our RL ECSMs satisfy secure generality and (extended) affine coordinates are executable coordinates
for them. In the second part of this thesis, new LR ECSMs scanning the input scalars from left to
right (LR) are proposed, which are more memory-saving. Our LR ECSM with a memory of 12 field elements uses the least amount of memory. The secure generality of our LR ECSMs and that (extended) affine coordinates are executable coordinates for them are also proved.
The efficiency of both LR and RL ECSMs is enhanced by optimizing the number of inversions. Compared with prior works, the efficiency of our LR (RL) ECSMs is analyzed from theoretical and experimental perspectives.
In the third part of this thesis, new short-iteration CT-GCD and CTMI algorithms over Fp, named SICT-GCD and SICT-MI, respectively, are proposed borrowing a simple concept from BEA. SICT-GCD and SICT-MI are evaluated from a theoretical perspective. Compared
with modular inversions by FLT, BOS, BY, and the improved version of BY, SICT-GCD and SICT-MI are experimentally demonstrated to be faster.