dc.description.abstract | For decade, elliptic curve cryptosystems (ECCs) have received a lot of attention due to having the ability to provide an equivalent security level with a smaller key size in comparison with other public key cryptosystems such as RSA. Hence, in terms of memory storage, it is attractive to apply ECCs to resource-constrained devices like smart cards. While an ECC is operated in such low speed devices, efficient computations are urgently required, and security issues should be reconsidered especially for some attacks based on special-purpose hardware.
This thesis primarily revolves around the topics related to scalar multiplication, the most essential computation of ECCs. The arithmetic of ECCs, recoding techniques, performance analysis, performance enhancement, side-channel attacks and countermeasures are extensively discussed in this thesis. These related topics are divided into three main subjects in which we will investigate the matters in detail and then propose novel methods for enhancement.
First, recoding techniques applied to scalar multiplication in ECCs are discussed. In order to investigate behaves of recoding systems, a probability analysis is usually employed for analysis, but its analysis results often have bias in error estimation. Hence we propose a precise analysis to replace the traditional one.
In the second subject, how to improve the performance of scalar multiplication in ECCs will be discussed. We propose a fast scalar multiplication method by utilizing the merged point operations, and a trick called EOSR for manipulating operation sequence. Compared with the work presented by Han et al., the proposed method yields 31.836% improvement. Additionally, an efficient SPA countermeasure based on the merged operations is proposed, and it is significantly better than Coron’’s double-and-add-always algorithm by at least 45.553% in performance.
In the third subject, we explore data collision-based power attacks. Kim et al. proposed a doubling attack against the Yen-Lu-Tseng downward algorithm, but their attack on average required 2^{0.35n} operations to test key candidates. Thus, we provide an enhanced doubling attack which can efficiently and directly reveal all the secret key bits. Moreover, an experiment on an 8051 compatible microcontroller is conducted to show that the data collision assumption which our proposed doubling attack is based on can be realized. Our study indicates that almost all the left-to-right algorithms are vulnerable to the proposed attack. Therefore, an upward variant of the Yen-Lu-Tseng algorithm against doubling attacks is proposed.
| en_US |