可預防旁通道攻擊之指數運算演算法 ; Exponentiation Algorithm with Immunity Against Side-Channel Attack

NCUIR > College of Electrical Engineering & Computer Science > Graduate Institute of Computer Science and Information Engineering > Electronic Thesis & Dissertation > Item 987654321/44713

Please use this identifier to cite or link to this item: http://ir.lib.ncu.edu.tw/handle/987654321/44713

Title:	可預防旁通道攻擊之指數運算演算法;Exponentiation Algorithm with Immunity Against Side-Channel Attack
Authors:	陳健寧;Chien-Ning Chen
Contributors:	資訊工程研究所
Keywords:	指數運算;密碼學;旁通道分析;實體密碼分析;二元最大公因數演算法;指數編碼;cryptography;side-channel analysis;exponentiation;exponent recoding;binary GCD algorithm;physical cryptanalysis
Date:	2010-07-27
Issue Date:	2010-12-09 13:53:29 (UTC+8)
Publisher:	國立中央大學
Abstract:	在實做密碼系統時，為了達到較高的安全性，常常利用智慧卡或類似的獨立封閉設備，儲存金鑰及處理重要的運算。然而智慧卡或類似的設備，仍然會受到旁通道分析的威脅。旁通道分析針對執行密碼系統的硬體，分析其所洩露的旁通道資訊，例如所消耗電流或運算所需時間等。攻擊者雖然無法直接讀取儲存在智慧卡內的金鑰，但可分析旁通道資訊，得到智慧卡內部運算的相關資訊，間接取得其所儲存的金鑰。近代公開金鑰密碼系統中的指數運算也同樣受到旁通道分析的威脅。現有的指數運算演算法的發展，多半著重於效率及所使用的空間，並基於原有的演算法修改為對旁通道分析的防禦法。在論文中，利用二元最大公因數演算法計算指數的最大公因數的過程，發展出一新型式的多指數運算演算法。與基於共同平方法所發展的多指數運算演算法相比，所提出的演算法在速度及所需的空間上，都有相當的優勢，且由於其本身的特性，亦適合做為對旁通道分析的防禦法。此外，所提出的多指數運算演算法無需使用乘法反元素運算，不受乘法反元素的限制，可套用於多數的公開金鑰密碼系統。其亦有良好的擴展性，對於不同長度的指數，或是不同項數的多指數運算，都有不錯的效率。除了多指數運算演算法以外，論文中亦從指數編碼的角度分析指數運算演算法。在此部分，首先提出了一般化的非相鄰格式(NAF)編碼，從右到左將指數編碼為由字元 {0,1,r} 所組成的數字。因每次編碼前都隨機地產生字元r，所提出的編碼法可加強如Ha-Moon這類基於非相鄰格式所發展出來的隨機編碼演算法，對於差分能量分析的防禦能力。而論文的最後一部份，分析了左到右的非相鄰格式編碼及左到右的滑動視窗法。與右到左的編碼法相比，左到右的編碼法對於簡單能量分析的防禦力較差。實做指數運算演算法時，應避免使用左到右的指數邊碼法。Smart card and other stand-alone cryptographic devices provide a secure environment to store the secret key and manipulate sensitive information. However, those devices may suffer from the threat of side-channel analysis which exploits power consumption, execution time, or other side-channel leakages of those devices. Exponentiation computation is a basic operation in many modern public-key cryptosystems and also suffers from the threat of side-channel analysis. An attacker can retrieve the secret exponent by analyzing the leaked side-channel information. Since smart card usually has very limited memory capacity and computation capability, both space requirement and the immunity against side-channel analysis should be taken into consideration when designing fast exponentiation algorithms. In this dissertation, we propose a series of multi-exponentiation algorithms which are developed based on the computational sequence of the binary GCD algorithm. Comparing with existing multi-exponentiation algorithms, the proposed algorithms have the advantage of space efficient, good performance, and being inversion free. They have the merit of developing countermeasures against side-channel analysis and are very suitable for implementation on smart card or other resource-limited devices. The proposed algorithms also have the advantage of good scalability, i.e., they achieve good performance in various bit lengths of exponents and various dimensions of multi-exponentiation. We also develop and analyze exponentiation algorithms from the view point of exponent recoding. A generalization of the NAF recoding and the sliding window method is proposed. The proposed algorithm, a right-to-left ${0,1,r}$-NAF recoding, can cooperate with the Ha-Moon algorithm to achieve better immunity against differential power analysis. A detailed analysis of the left-to-right NAF recoding and the left-to-right sliding window method is also proposed. In contrast that the hidden Markov module cryptanalysis exploits multiple computational sequences and adapts to analyze randomized recoding algorithms, our analysis skill focuses on how much information can be retrieved by exploiting only one computational sequence and adapts to deterministic recoding algorithms. The proposed analysis clearly shows that the left-to-right exponent recoding is less secure than the right-to-left recoding.
Appears in Collections:	[Graduate Institute of Computer Science and Information Engineering] Electronic Thesis & Dissertation

Files in This Item:

File	Description	Size	Format
index.html		0Kb	HTML	923	View/Open

社群 sharing

Loading...