# Miyaji Laboratory

Elliptic Curve Cryptosystems (ECC) has gained increasing popularity in public key cryptography since was first proposed independently by Miller and Koblitz in mid of 1980's. In comparison with other established systems such as RSA, ECC has become especially attractive for applications due to its shorter key size requirement, which are translated to less power and storage requirements, and reduced computing times. For example, 160-bits of ECC and 1024-bits of RSA offer the same level of security. These advantages make ECC beneficial for use in smart cards and embedded systems where storage, power, and computing resources are at a premium.In public key cryptography each user or the device taking part in the communication generally have a pair of keys, a public key and a private key, and a set of operations associated with the keys to do the cryptographic operations. The operations of ECC is defined over the elliptic curve $y^2 = x^3 + Ax + B$, where $4A^3 + 27b^2 \neq 0$. All points $(x, y)$ which satisfies the above equation plus a point at infinity lies on the elliptic curve. The private key is a random number $k$ and the public key is a point in the curve $Q$, where $Q$ is obtained by multiplying the private key with the generator point $P$ in the curve.The security of ECC depends on the Elliptic Curve Discrete Logarithm Problem (ECDLP). Let $P$ and $Q$ be two points on an elliptic curve such that $kP = Q$, where $k$ is a scalar. Given $P$ and $Q$, it is computationally infeasible to obtain $k$, if $k$ is sufficiently large. $k$ is the discrete logarithm of $Q$ to the base $P$. Therefore, the most dominant computation part of ECC is the scalar multiplication $kP$, i.e. multiplication of a scalar $k$ with any point $P$ on the curve. The speed of scalar multiplication plays an important role in the efficiency of ECC. The running time of scalar multiplication is computed based on two levels of complexity, elliptic curve point operations and finite filed operations. Performing fast point operations on an elliptic curve is crucial for efficient scalar multiplication. Computation time of point operation depends on the coordinate system adapted. Point operations in affine coordinate involves inversion, which is particularly a very costly operation over prime fields. To avoid inversion for prime filed, various coordinate systems have been proposed such as Projective coordinate, Jacobian coordinate, modified Jacobian coordinate, and Chudnovsky Jacobian coordinate. Using these coordinates, we can remove inversions from the point operations at the cost of increase in the other simpler filed operations. Computation cost of point operations are different for various coordinates. Some coordinate systems such as modified Jacobian coordinate have faster doubling than the other coordinate systems and some coordinate systems such as Chudnovsky Jacobian coordinate have faster addition. One possible way for an efficient scalar multiplication is to use the mixed coordinate systems for the computation of point operations. The common method for scalar multiplication is performed by iterative point additions and point doubling on an elliptic curve according to bits $k_i$ of binary representation $k$, which is called binary method. Various methods have been proposed for the efficient computation of $kP$ by reducing point operations (addition, doubling). One method can be made by taking different binary representations of the multiplier $k$ such as non-adjacent form (NAF), window non-adjacent forms such as (wNAF) and Frac-wNAF. Unfortunately that the aforementioned methods are vulnerable to side-channel attacks, which measure observable parameters such as timings or power consumptions during cryptographic operations to deduce the whole or partial secret information of a cryptosystem. Side-channel attacks were extended to elliptic curve cryptosystems. The particular target of side-channel attacks for elliptic curve cryptosystems is the scalar $k$ in scalar multiplication, which is a secret positive integer. Various methods to improve the security against power analysis attacks have been proposed, such as Montgomery ladder and the Joye's double-and-add algorithm. When extra memory is allowed, the window method (wNAF, Frac-wNAF) can dramatically speed up the main computation of point multiplication with the pre-computation space. In this case, a table of points is built and stored in advance (pre-computation stage) for later use during the execution of the scalar multiplication itself (evaluation stage). Although these window-based methods effectively reduce the number of non zero terms in most representations, a potential drawback is the cost of computing such a table, which grows with the window size. Thus, it is an important research effort to minimize the cost of the pre-computation stage to reduce the total cost of scalar multiplication. Further, although improved elliptic curve shapes with faster explicit formulae are currently the focus of intense research, there is still a lack of analysis of pre-computation schemes that are efficient for these settings. In this direction, Patrick Longa and Catherine Gebotys proposes a efficient pre-computation schemes based on conjugate'' addition (CA), which requires much fewer additional field operations by computing the addition and subtraction of two distinct points together. Later Sasahara, Miyaji and Yokogawa developed the pre-computation schemes using doubling-and-tripling formula (DT), which computes the doubling and tripling of point parallel. In this thesis, we improved the pre-computation schemes based on the following idea: compute all the precomputed points by only CA and DT, without independent point addition. We refer to this strategy as making perfect'' conjugate pair. It will turn out that this strategy will allow using the efficient point operations such as CA and DT as possible as we can, thus computing precomputed tables very efficiently. Further, our pre-computation schemes compute the intermediate points in Chudnovsky Jacobian coordinate which has faster addition. As representing points in Chudnovsky Jacobian coordinate will require more memory cost, we propose a new mode of addition formulae which keep the data of one input point. With the proposed addition formulae, the extra memory requirement due to Chudnovsky Jacobian coordinate representation will be reduced. This thesis compares and analyses the performance of the proposed schemes with the previous efficient methods by representing precomputed tables in Jacobian coordinates. The analysis shows that the proposed schemes offer the lowest computation costs for pre-computation tables for scalar multiplication. Then we proposed several ternary method for scalar multiplication, representing the scalar $k$ in ternary expansion $(k'_{n'-1},\ldots ,k'_1,k'_0)_3$, where $k'_i\in \left\lbrace 0,1,2 \right\rbrace$, $k'_{n'-1}\neq 0$. As the length of ternary expansion is much shorter than binary one, we can improve time efficiency by the ternary methods. And we use the addition formulae in mixed coordinates to further reduce the computation time. Our propose ternary signed-digit method and extended ternary signed-digit method offer the lowest computation time with one extra register.