模指數運算以及與其同結構的純量乘法計算，為公開金鑰密碼系統中，兩種核心運算。由於智慧卡的計算能力以及記憶體空間有限，在使用智慧卡實作模指數運算演算法(或公開金鑰密碼系統)時，設計一個兼具計算與空間效能的模指數運算演算法，為現行研究方向中一個重要的探討議題。另者，鑒於智慧卡易受到基於系統實作之旁通道分析攻擊(side-channel analysis attack)，在設計模指數運算演算法的同時，考量系統實作安全亦為一個重要的安全性議題。本論文即以上述的兩個議題為研究主軸，探討兼具高效能與安全的模指數運算演算法。 在整數編碼的研究主題下，NAF二進制表示法為二元整數數系中，漢明值(Hamming weight)最小之編碼方法，基於此特性，NAF為二元整數數系中可加速純量乘法計算之最佳方法；而隨機式的NAF編碼法為現存文獻當中一個典型的旁通道分析防禦法。在本論文中，我們提出了一個稱為sNAF的NAF通式編碼法，我們的研究成果顯示sNAF與NAF具有相同的平均漢明值，該兩種編碼法皆可被運用於加速純量乘法計算，與傳統的二進位表示法相比較，最高加速效益可達約11.11%。而為了抵抗旁通道分析攻擊法，我們亦提出一個隨機式的sNAF編碼法，與隨機式的NAF編碼法以及數個現存的編碼法比較，隨機式的sNAF編碼法之安全性相對性地較為優越。 兩倍攻擊法(doubling attack)為一種選擇兩筆相關密文(或明文)的旁通道分析攻擊法。在RSA密碼系統的研究主題下，本論文提出一個基於選擇小序值(small order) 密文之新穎的兩倍攻擊法，本攻擊法只需要一筆選擇密文即可進行攻擊，亦可進一步地推廣為使用不同於原始兩倍攻擊法的兩筆相關選擇密文來進行攻擊。我們的研究成果顯示，利用中國餘數定理加速RSA運算之實作方法亦無法抵抗本攻擊法。而為了防禦本攻擊法，本論文亦提出一個針對RSA密碼系統而設計的高效能防禦法。而在ECC密碼系統的研究主題下，由於常見的ECC密碼系統具有質數序值(prime order)之特性，與小序值點(密文)不存在之特質，因此，上述之新穎的兩倍攻擊法無法推廣至ECC密碼系統中。但是，攻擊者仍可能選擇小序值之錯誤點來進行攻擊，我們的研究成果顯示，現存的防禦法依然無法有效地抵抗此類攻擊法。而為了防禦此類攻擊法，本論文亦針對ECC密碼系統提出數個實作上的安全性建議。 蒙特哥馬利餘數(Montgomery reduction)演算法與中國餘數定理為兩種加速RSA密碼運算之重要技術。在本論文中，我們提出了一個新型的DPA旁通道分析攻擊法，以攻擊結合蒙特哥馬利餘數演算法以及中國餘數定理的實作方法，並以實驗結果證實本攻擊法之可行性。而為了防禦本攻擊法，基於明文(或密文)遮罩(message-blinding)技術以及中國餘數定理，本論文提出了一個高效能防禦方法。 Modular exponentiation and its analogy, scalar multiplication, are the central computations in public-key cryptosystems. Because the memory capacity and computation power are crucial to smart cards, designing efficient exponentiation algorithms is an important issue for smart-card related applications. Since smart cards may suffer from side-channel analysis (SCA) attacks, which target the implementation of cryptosystems, the implementation security of cryptosystems using smart cards is an issue as important as designing an efficient algorithm. This dissertation investigates efficient and secure methods to implement exponentiation algorithms.
Because its property of having minimal Hamming weight among binary signed-digit representations, the binary non-adjacent form (NAF) is the optimal method to speed up scalar multiplications. Randomized NAF recoding is a typical SCA countermeasure. This dissertation newly introduces the separated non-adjacent form (sNAF) as a generalization of the conventional NAF. We show that both of sNAF and NAF have the same average Hamming weight, and can speed up exponentiation algorithms with a rate about 11.11% when compared with using the conventional binary recoded scalar. This dissertation also proposes the randomized sNAF recoding scheme to increase the security strength of scalar multiplications against SCA attacks. Compared with the randomized NAF recoding and several previous recoding schemes, the randomized sNAF recoding is a superior countermeasure from the viewpoint of security. Doubling attack is a powerful SCA attack on exponentiation algorithms by exploiting two related chosen messages. This dissertation proposes the small-order doubling attack on the RSA cryptosystem by exploiting only one single chosen message of small order. This attack can be extended to the attack using two related chosen messages, which are different from the used by the original doubling attack. We show that an efficient RSA implementation improved by Chinese remainder theorem (CRT) is also weak against the proposed attacks. To prevent RSA against the proposed doubling attacks, a low-cost countermeasure is newly developed. Basically, the small-order doubling attacks can not threaten the elliptic curve cryptosystems (ECC), whereas a cryptographic elliptic curve is usually suggested with a prime order and small-order points do not exist on this kind of curves. However, this dissertation shows that existing invalid points having small orders on other curves can be used to mount a further extended doubling attack on the target curve of prime order. Several previous SCA countermeasures for ECC are shown to be vulnerable against the proposed doubling attack. To prevent ECC against the doubling attack using invalid points, efficient countermeasures are suggested in this dissertation. Montgomery reduction algorithms are often taken to cooperate with RSA-CRT methods to achieve a high performance of RSA modular exponentiations. This dissertation proposes a new DPA attack on the RSA-CRT implementation with Montgomery reduction algorithms. An experimental result is illustrated to verify the proposed DPA attacks. In order to prevent against the proposed DPA attacks, an CRT-based message blinding technique is proposed as a low-cost countermeasure.
