| 摘要: | 近十年來，橢圓曲線密碼系統逐漸受到許多重視，與其他公開金鑰密碼系統相較，如RSA公開金鑰密碼系統，橢圓曲線密碼系統可採用更短長度之金鑰而達成相同安全等級，因此更適用於計算資源有限的裝置，例如智慧卡。然而，當橢圓曲線密碼系統被實作於這類裝置時，必須考量採取有效率的計算方法，以及顧及是否會遭受到基於硬體特性設計之攻擊法。 在橢圓曲線密碼系統中，最重要的核心計算為純量乘積計算，本篇論文研究將探討純量乘積計算之相關主題，並且廣泛討論編碼技術、效率分析、效率提升、物理攻擊法與其防禦法等等。這些主題將分為三大主題深入探討，並且提出改進方法。 首先探討編碼技術應用於純量乘積計算。為了觀察編碼技術之行為，通常會採用機率分析法，而傳統機率分析法其估計結果具有錯誤偏差之現象，因此我們改良傳統分析法，並且提出精確分析法。 在第二部分探討如何在橢圓曲線密碼系統加速計算。我們將利用合併點運算以及運算操作之技巧去加速純量乘積計算，與Han等人之方法相較，所提出之計算加速方法可提升效率31.836%。此外我們也利用合併點運算去建立更有計算效率之防禦法，可用來抵禦簡單能量攻擊法，與 Coron之防禦方法相較，所提出之防禦法可提升45.553%計算效率。 在第三部分將探討資料碰撞式能量攻擊法。Kim 等人提出了兩倍攻擊法針對 Yen 等人之防禦法進行攻擊，他們所提出之攻擊法仍需要20.35n次數搜尋金鑰。因此我們提出改良之攻擊法，可以更有效率直接揭露密碼系統所使用的金鑰。並且我們在8051單晶片上實作能量量測，去驗證攻擊法所基於的資料碰撞假設可以被實現。在我們的研究指出，由左到右計算之演算法皆遭受到所提出兩倍攻擊法的威脅，因此，基於Yen等人演算法，我們提出由右到左計算之變形來抵禦兩倍攻擊法。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. |
