可預防旁通道攻擊之指數運算演算法

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：39

、訪客IP：3.142.35.75

姓名

陳健寧(Chien-Ning Chen) 查詢紙本館藏

畢業系所

資訊工程學系

論文名稱

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

相關論文

★ 多種數位代理簽章之設計	★ 小額電子支付系統之研究
★ 實體密碼攻擊法之研究	★ 商業性金鑰恢復與金鑰託管機制之研究
★ AES資料加密標準之實體密碼分析研究	★ 電子競標系統之研究
★ 針對堆疊滿溢攻擊之動態程式區段保護機制	★ 通用型數域篩選因數分解法之參數探討
★ 於8051單晶片上實作可防禦DPA攻擊之AES加密器	★ 以非確定式軟體與遮罩分割對策防禦能量攻擊之研究
★ 遮罩保護機制防禦差分能量攻擊之研究	★ AES資料加密標準之能量密碼分析研究
★ 小額電子付費系統之設計與密碼分析	★ 公平電子現金系統之研究
★ RSA公開金鑰系統之實體密碼分析研究	★ 保護行動代理人所收集資料之研究

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

在實做密碼系統時，為了達到較高的安全性，常常利用智慧卡或類似的獨立封閉設備，儲存金鑰及處理重要的運算。然而智慧卡或類似的設備，仍然會受到旁通道分析的威脅。旁通道分析針對執行密碼系統的硬體，分析其所洩露的旁通道資訊，例如所消耗電流或運算所需時間等。攻擊者雖然無法直接讀取儲存在智慧卡內的金鑰，但可分析旁通道資訊，得到智慧卡內部運算的相關資訊，間接取得其所儲存的金鑰。近代公開金鑰密碼系統中的指數運算也同樣受到旁通道分析的威脅。現有的指數運算演算法的發展，多半著重於效率及所使用的空間，並基於原有的演算法修改為對旁通道分析的防禦法。
在論文中，利用二元最大公因數演算法計算指數的最大公因數的過程，發展出一新型式的多指數運算演算法。與基於共同平方法所發展的多指數運算演算法相比，所提出的演算法在速度及所需的空間上，都有相當的優勢，且由於其本身的特性，亦適合做為對旁通道分析的防禦法。此外，所提出的多指數運算演算法無需使用乘法反元素運算，不受乘法反元素的限制，可套用於多數的公開金鑰密碼系統。其亦有良好的擴展性，對於不同長度的指數，或是不同項數的多指數運算，都有不錯的效率。
除了多指數運算演算法以外，論文中亦從指數編碼的角度分析指數運算演算法。在此部分，首先提出了一般化的非相鄰格式(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.

關鍵字(中)

★ 指數運算
★ 密碼學
★ 旁通道分析
★ 實體密碼分析
★ 二元最大公因數演算法
★ 指數編碼

關鍵字(英)

★ cryptography
★ side-channel analysis
★ exponentiation
★ exponent recoding
★ binary GCD algorithm
★ physical cryptanalysis

論文目次

1 Introduction . . . 1
1.1 Motivation of the Research . . . 1
1.2 Organization of the Dissertation . . . 2
1.3 Our Contributions . . . 3
I Preliminary and Review . . . 5
2 Exponentiation Algorithm . . . 7
2.1 Single-Exponentiation Algorithm . . . 7
2.1.1 Elliptic curve point scalar multiplication . . . 8
2.2 Exponent Recoding . . . 9
2.2.1 Window method . . . 10
2.2.2 Signed-digit recoding . . . 11
2.3 Multi-Exponentiation Algorithm . . . 13
3 Side-Channel Analysis . . . 15
3.1 Simple Power Analysis . . . 15
3.2 Differential Power Analysis . . . 17
3.3 DPA Countermeasure . . . 19
3.3.1 Randomized exponentiation algorithm . . . 20
3.4 Collision-Based Power Analysis . . . 22
3.4.1 Efficient countermeasure against Yen's small order collision-based power analysis . . . 23
3.5 Timing Attack . . . 24
II Multi-Exponentiation Algorithm . . . 27
4 Binary GCD Multi-Exponentiation Algorithm . . . 29
4.1 GCD Algorithm and GCD Multi-Exponentiation Algorithm . . . 29
4.1.1 Binary GCD algorithm . . . 30
4.1.2 Euclidean double-exponentiation algorithm . . . 31
4.2 Proposed Binary GCD Multi-Exponentiation Algorithm . . . 33
4.2.1 Improvement to binary GCD double-exponentiation algorithm . . . 34
4.2.2 Analogy between conventional single-exponentiation algorithm and proposed algorithm . . . 35
4.2.3 Triple or higher dimensional multi-exponentiation . . . 36
4.3 Estimation of Complexity of Proposed Algorithm . . . 37
4.4 Performance Comparison . . . 40
4.5 Countermeasure Against Side-Channel Analysis . . . 43
4.5.1 Security against simple power analysis . . . 43
4.5.2 Security against differential power analysis and timing attack . . . 43
4.6 Summary of Binary GCD Multi-Exponentiation Algorithm . . . 44
5 High-Dimensional Multi-Exponentiation . . . 47
5.1 Existing High-Dimensional Multi-Exponentiation Algorithm . . . 47
5.1.1 Lim-Lee algorithm . . . 48
5.1.2 BGMW method . . . 49
5.2 Complexity of High-Dimensional Binary GCD Multi-Exponentiation . . . 51
5.3 Performance Comparison of High-Dimensional Multi-Exponentiation . . . 53
5.4 Application in Batch Verification of Signatures . . . 54
5.5 Simulation Result of High-Dimensional Multi-Exponentiation . . . 55
III Exponent Recoding Algorithm . . . 59
6 NAF Recoding with Randomized Digit Set {0, 1, r} . . . 61
6.1 Proposed {0, 1, r}-NAF Recoding . . . 61
6.1.1 Ha-Moon recoding improved by {0, 1, r}-NAF . . . 62
6.2 DPA and Distribution of Intermediate Results of Randomized Recoding . . . 63
6.3 Summary of {0, 1, r}-NAF Recoding . . . 65
7 Inherent Weakness of Left-to-Right NAF and Sliding Window Technique . . . 67
7.1 On the Computational Sequence of Scalar Multiplication with Left-to-Right NAF and Sliding Window Technique . . . 67
7.2 Weakness of Left-to-Right NAF Recoding . . . 69
7.2.1 Review of Muir and Stinson's left-to-right NAF algorithm . . . 69
7.2.2 Reconstruction of state transition . . . 71
7.2.3 Expected number of candidates of a scalar . . . 73
7.3 Weakness of Left-to-Right Sliding Window Method . . . 75
7.3.1 Left-to-right 2-bit sliding window method and property of recoded scalar . . . 75
7.3.2 Estimation of average number of candidates . . . 78
7.4 Summary of Weakness about Left-to-Right Recoding . . . 79
IV Concluding Remarks . . . 81
8 Summary and Future Works . . . 83
8.1 Summary of Contributions . . . 83
8.2 Future Research Directions . . . 84
Bibliography . . . 87

參考文獻

[1] Ronald L. Rivest, Adi Shamir, and Leonard M. Adleman. A method for obtaining digital signatures and public-key cryptosystem. Communications of ACM, 21(2):120-126, 1978.
[2] Taher ElGamal. A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Trans. on Information Theory, 31(4):469-472, July 1985.
[3] Victor S. Miller. Use of elliptic curves in cryptography. In Hugh C. Williams, editor, Advances in Cryptology - CRYPTO '85, volume 218 of Lecture Notes in Computer Science, pages 417-426. Springer, 1986.
[4] Neal Koblitz. Elliptic curve cryptosystems. Mathematics of Computation, 48(177):203-209, Jan. 1987.
[5] Jurjen Bos and Matthijs Coster. Addition chain heuristics. In Gilles Brassard, editor, Advances in Cryptology - Crypto '89, volume 435 of Lecture Notes in Computer Science, pages 400-407. Springer, 1990.
[6] George W. Reitwiesner. Binary arithmetic. Advances in Computers, 1:231-308, 1960.
[7] Jerome A. Solinas. Efficient arithmetic on Koblitz curves. Design, Codes and Cryptography, 19(2-3):195-249, March 2000.
[8] Hugo Krawczyk and Tal Rabin. Chameleon signatures. In Network and Distributed System Security Symposium, NDSS 2000. The Internet Society, 2000.
[9] E. G. Straus. Addition chains of vectors. The American Mathematical Monthly, 71:806-808, 1964.
[10] Jorge Olivos. On vectorial addition chains. Journal of Algorithms, 2(1):13-21, 1981.
[11] Sung-Ming Yen, Chi-Sung Laih, and Arjen K. Lenstra. Multi-exponentiation. IEE Proceedings: Computers and Digital Techniques, 141(6):325-326, 1994.
[12] Bodo Moller. Algorithms for multi-exponentiation. In Serge Vaudenay and Amr M. Youssef, editors, Selected Areas in Cryptography (SAC 2001), volume 2259 of Lecture Notes in Computer Science, pages 165-180. Springer, 2001.
[13] Jerome A. Solinas. Low-weight binary representations for pairs of integers, 2001. Available at http://www.cacr.math.uwaterloo.ca/techreports/2001/corr2001-41.ps.
[14] John Proos. Joint sparse forms and generating zero columns when combing, 2003. Available at http://www.cacr.math.uwaterloo.ca/techreports/2003/corr2003-23.ps.
[15] Paul C. Kocher. Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems. In Neal Koblitz, editor, Advances in Cryptology - CRYPTO '96, volume 1109 of Lecture Notes in Computer Science, pages 104-113. Springer, 1996.
[16] Paul C. Kocher, Joshua Jaffe, and Benjamin Jun. Introduction to differential power analysis and related attacks, 1998. Available at http://www.cryptography.com/public/pdf/DPATechInfo.pdf.
[17] Paul C. Kocher, Joshua Jaffe, and Benjamin Jun. Differential power analysis. In Michael Wiener, editor, Advances in Cryptology - CRYPTO '99, volume 1666 of Lecture Notes in Computer Science, pages 388-397. Springer, 1999.
[18] Dakshi Agrawal, Bruce Archambeault, Josyula R. Rao, and Pankaj Rohatgi. The EM side-channel(s). In Burton S. Kaliski Jr., Cetin K. Koc, and Christof Paar, editors, Cryptographic Hardware and Embedded Systems - CHES 2002, volume 2523 of Lecture Notes in Computer Science, pages 29-45. Springer, 2003.
[19] U.S. DEPARTMENT OF COMMERCE/National Institute of Standards and Technology. Data encryption standard (DES). Federal Information Processing Standards Publication 46-3, Reaffirmed 1999 October 25. Available at http://csrc.nist.gov/publications/fips/fips46-3/fips46-3.pdf.
[20] Elisabeth Oswald. Enhancing simple power-analysis attacks on elliptic curve cryptosystems. In Burton S. Kaliski Jr., Cetin K. Koc, and Christof Paar, editors, Cryptographic Hardware and Embedded Systems - CHES 2002, volume 2523 of Lecture Notes in Computer Science, pages 82-97. Springer, 2003.
[21] Katsuyuki Okeya and Kouichi Sakurai. On insecurity of the side channel attack countermeasure using addition-subtraction chains under distinguishability between addition and doubling. In Lynn Batten and Jennifer Seberry, editors, Information Security and Privacy (ACISP 2002), volume 2384 of Lecture Notes in Computer Science, pages 420-435. Springer, 2002.
[22] Katsuyuki Okeya and Kouichi Sakurai. A multiple power analysis breaks the advanced version of the randomized addition-subtraction chains countermeasure against side channel attacks. In Information Theory Workshop, 2003. Proceedings., pages 175-178. IEEE, 2003.
[23] Katsuyuki Okeya and Dong-Guk Han. Side channel attack on Ha-Moon's countermeasure of randomized signed scalar multiplication. In Thomas Johansson and Subhamoy Maitra, editors, Progress in Cryptology - INDOCRYPT 2003, volume 2904 of Lecture Notes in Computer Science, pages 334-348. Springer, 2003.
[24] Chris Karlof and DavidWagner. Hidden Markov model cryptanalysis. In Colin D. Walter, Cetin K. Koc, and Christof Paar, editors, Cryptographic Hardware and Embedded Systems - CHES 2003, volume 2779 of Lecture Notes in Computer Science, pages 17-34. Springer, 2003.
[25] Colin D. Walter. Issues of security with the Oswald-Aigner exponentiation algorithm. In Tatsuaki Okamoto, editor, Topics in Cryptology - CT-RSA 2004, volume 2964 of Lecture Notes in Computer Science, pages 208-221. Springer, 2004.
[26] Jean-Sebastien Coron. Resistance against differential power analysis for elliptic curve cryptosystems. In Cetin K. Koc and Christof Paar, editors, Cryptographic Hardware and Embedded Systems (CHES '99), volume 1717 of Lecture Notes in Computer Science, pages 292-302. Springer, 1999.
[27] Marc Joye and Sung-Ming Yen. The Montgomery powering ladder. In Burton S. Kaliski Jr., Cetin K. Koc, and Christof Paar, editors, Cryptographic Hardware and Embedded Systems - CHES 2002, volume 2523 of Lecture Notes in Computer Science, pages 291-302. Springer, 2003.
[28] Peter L. Montgomery. Speeding the pollard and elliptic curve methods for factorization. Mathematics of Computation, 48(177):243-264, Jan. 1987.
[29] Sung-Ming Yen, Seungjoo Kim, Seongan Lim, and Sangjae Moon. A countermeasure against one physical cryptanalysis may benefit another attack. In Kwangjo Kim, editor, Information Security and Cryptology - ICISC 2001, volume 2288 of Lecture Notes in Computer Science, pages 414-427. Springer, 2002.
[30] Benoit Chevallier-Mames, Mathieu Ciet, and Marc Joye. Low-cost solutions for preventing simple side-channel analysis: Side-channel atomicity. IEEE Transaction on Computers, 53(6):760-768, 2004. Also available at Cryptology ePrint Archive, Report 2003/237.
[31] Thomas S. Messerges, Ezzy A. Dabbish, and Robert H. Sloan. Investigations of power analysis attacks on smartcards. In USENIX Workshop on Smartcard Technology, 1999.
[32] Jean-Sebastien Coron, Paul Kocher, and David Naccache. Statistics and secret leakage. In Yair Frankel, editor, Financial Cryptography (FC 2000), volume 1962 of Lecture Notes in Computer Science, pages 157-173. Springer, 2001.
[33] Christophe Clavier, Jean-Sebastien Coron, and Nora Dabbous. Differential power analysis in the presence of hardware countermeasures. In Cetin K. Koc and Christof Paar, editors, Cryptographic Hardware and Embedded Systems - CHES 2000, volume 1965 of Lecture Notes in Computer Science, pages 252-263. Springer, 2000.
[34] Mehdi-Laurent Akkar, Regis Bevan, Paul Dischamp, and Didier Moyart. Power analysis, what is now possible ... . In Tatsuaki Okamoto, editor, Advances in Cryptology - ASIACRYPT 2000, volume 1976 of Lecture Notes in Computer Science, pages 489-502. Springer, 2000.
[35] Rita Mayer-Sommer. Smartly analyzing the simplicity and the power of simple power analysis on smartcards. In Cetin K. Koc and Christof Paar, editors, Cryptographic Hardware and Embedded Systems - CHES 2000, volume 1965 of Lecture Notes in Computer Science, pages 78-92. Springer, 2000.
[36] Eric Brier, Christophe Clavier, and Francis Olivier. Correlation power analysis with a leakage model. In Marc Joye and Jean-Jacques Quisquater, editors, Cryptographic Hardware and Embedded Systems - CHES 2004, volume 3156 of Lecture Notes in Computer Science, pages 16-29. Springer, 2004.
[37] Louis Goubin. A refined power-analysis attack on elliptic curve cryptosystems. In Yvo G. Desmedt, editor, Public Key Cryptography - PKC 2003, volume 2567 of Lecture Notes in Computer Science, pages 199-211. Springer, 2003.
[38] Toru Akishita and Tsuyoshi Takagi. Zero-value point attacks on elliptic curve cryptosystem. In Colin Boyd and Wenbo Mao, editors, Information Security (ISC 2003), volume 2851 of Lecture Notes in Computer Science, pages 218-233. Springer, 2003.
[39] Whitfield Diffie and Martin E. Hellman. New directions in cryptography. IEEE Transactions on Information Theory, 22(6):644-654, Nov. 1976.
[40] David Chaum. Blind signatures for untraceable payments. In David Chaum, Ronald L. Rivest, and Alan T. Sherman, editors, Advances in Cryptology: Proceedings of CRYPTO '82, pages 199-203. Plemum, New York, 1983.
[41] Pierre-Alain Fouque and Frederic Valette. The doubling attack - why upwards is better than downwards. In Colin D. Walter, Cetin K. Koc, and Christof Paar, editors, Cryptographic Hardware and Embedded Systems - CHES 2003, volume 2779 of Lecture Notes in Computer Science, pages 269-280. Springer, 2003.
[42] Elisabeth Oswald and Manfred Aigner. Randomized addition-subtraction chains as a countermeasure against power attacks. In Cetin K. Koc, David Naccache, and Christof Paar, editors, Cryptographic Hardware and Embedded Systems - CHES 2001, volume 2162 of Lecture Notes in Computer Science, pages 39-50. Springer, 2001.
[43] Francois Morain and Jorge Olivos. Speeding up the computations on an elliptic curve using addition-subtraction chains. Theoretical Informatics and Applications, 24:531-544, 1990.
[44] Jae Cheol Ha and Sang Jae Moon. Randomized signed-scalar multiplication of ECC to resist power attacks. In Burton S. Kaliski Jr., Cetin K. Koc, and Christof Paar, editors, Cryptographic Hardware and Embedded Systems - CHES 2002, volume 2523 of Lecture Notes in Computer Science, pages 551-563. Springer, 2003.
[45] Sung-Ming Yen, Chien-Ning Chen, SangJae Moon, and JaeCheol Ha. Improvement on Ha-Moon randomized exponentiation algorithm. In Choonsik Park and Seongtaek Chee, editors, Information Security and Cryptology - ICISC 2004, volume 3506 of Lecture Notes in Computer Science, pages 154-167. Springer, 2005.
[46] Pierre-Alain Fouque, Frederic Muller, Guillaume Poupard, and Frederic Valette. Defeating countermeasures based on randomized BSD representations. In Marc Joye and Jean-Jacques Quisquater, editors, Cryptographic Hardware and Embedded Systems - CHES 2004, volume 3156 of Lecture Notes in Computer Science, pages 312-327. Springer, 2004.
[47] Sang Gyoo Sim, Dong Jin Park, and Pil Joong Lee. New power analysis on the Ha-Moon algorithm and the MIST algorithm. In Javier Lopez, Sihan Qing, and Eiji Okamoto, editors, Information and Communications Security (ICICS 2004), volume 3269 of Lecture Notes in Computer Science, pages 291-304. Springer, 2004.
[48] Jong Hoon Shin, Dong Jin Park, and Pil Joong Lee. Dpa attack on the improved Ha-Moon algorithm. In Jooseok Song, Taekyoung Kwon, and Moti Yung, editors, Information Security Applications (WISA 2005), volume 3786 of Lecture Notes in Computer Science, pages 283-291. Springer, 2006.
[49] Sung-Ming Yen, Wei-Chih Lien, SangJae Moon, and JaeCheol Ha. Power analysis by exploiting chosen message and internal collisions - vulnerability of checking mechanism for RSA-decryption. In Ed Dawson and Serge Vaudenay, editors, Progress in Cryptology - Mycrypt 2005, volume 3715 of Lecture Notes in Computer Science, pages 183-195. Springer, 2005.
[50] Jean-Francois Dhem, Francois Koeune, Philippe-Alexandre Leroux, Patrick Mestre, Jean-Jacques Quisquater, and Jean-Louis Willems. A practical implementation of the timing attack. In Jean-Jacques Quisquater and Bruce Schneier, editors, Smart Card Research and Applications (CARDIS '98), volume 1820 of Lecture Notes in Computer Science, pages 167-182. Springer, 2000.
[51] Peter Montgomery. Modular multiplication without trial division. Mathematics of Computation, 44(170):519-521, 1985.
[52] Werner Schindler. A timing attack against RSA with the Chinese remainder theorem. In Cetin K. Koc and Christof Paar, editors, Cryptographic Hardware and Embedded Systems - CHES 2000, volume 1965 of Lecture Notes in Computer Science, pages 109-124. Springer, 2000.
[53] David Brumley and Dan Boneh. Remote timing attacks are practical. In 12th USENIX Security Symposium, pages 1-14, 2003.
[54] The OpenSSL Project. OpenSSL: The open source toolkit for SSL/TLS. The official website: http://www.openssl.org/.
[55] Donald E. Knuth. The art of computer programming, volume 2. Addison-Wesley, third edition, 1997.
[56] Richard P. Brent. Analysis of the binary Euclidean algorithm. ACM SIGSAM Bulletin, 10(2):6-7, 1976.
[57] Josef Stein. Computational problems associated with Racah algebra. Journal of Computational Physics, 1:397-405, 1967.
[58] Francois Bergeron, Jean Berstel, Srecko Brlek, and Christine Duboc. Addition chains using continued fractions. Journal of Algorithms, 10:403-412, 1989.
[59] Peter de Rooij. Efficient exponentiation using precomputation and vector addition chains. In Alfredo De Santis, editor, Advances in Cryptology - EUROCRYPT '94, volume 950 of Lecture Notes in Computer Science, pages 389-399. Springer, 1995.
[60] Bodo Moller. Improved techniques for fast exponentiation. In Pil Joong Lee and Chae Hoon Lim, editors, Information Security and Cryptology - ICISC 2002, volume 2587 of Lecture Notes in Computer Science, pages 298-312. Springer, 2003.
[61] Christophe Clavier and Marc Joye. Universal exponentiation algorithm a first step towards provable SPA-resistance. In Cetin K. Koc, David Naccache, and Christof Paar, editors, Cryptographic Hardware and Embedded Systems - CHES 2001, volume 2162 of Lecture Notes in Computer Science, pages 300-308. Springer, 2001.
[62] Frederic Muller and Frederic Valette. High-order attacks against the exponent splitting protection. In Moti Yung, Yevgeniy Dodis, Aggelos Kiayias, and Tal Malkin, editors, Public Key Cryptography - PKC 2006, volume 3958 of Lecture Notes in Computer Science, pages 315-329. Springer, 2006.
[63] Mihir Bellare, Juan A. Garay, and Tal Rabin. Fast batch verification of modular exponentiation and digital signatures. In Kaisa Nyberg, editor, Advances in Cryptology - EUROCRYPT '98, volume 1403 of Lecture Notes in Computer Science, pages 236-250. Springer, 1998.
[64] Dan Boneh, Craig Gentry, Ben Lynn, and Hovav Shacham. Aggregate and verifiably encrypted signatures from bilinear maps. In Eli Biham, editor, Advances in Cryptology - EUROCRPYT 2003, volume 2656 of Lecture Notes in Computer Science, pages 416-432. Springer, 2003.
[65] Chae Hoon Lim and Pil Joong Lee. More flexible exponentiation with pre-computation. In Yvo G. Desmedt, editor, Advances in Cryptology - CRYPTO '94, volume 839 of Lecture Notes in Computer Science, pages 95-107. Springer, 1994.
[66] Chae Hoon Lim. Efficient multi-exponentiation and application to batch verification of digital signatures, 2000. Available at http://dasan.sejong.ac.kr/~chlim/pub/multi exp.ps.
[67] Ernest F. Brickell, Daniel M. Gordon, Kevin S. McCurley, and David Bruce Wilson. Fast exponentiation with precomputation. In Rainer A. Rueppel, editor, Advances in Cryptology - EUROCRYPT '92, volume 658 of Lecture Notes in Computer Science, pages 200-207. Springer, 1993.
[68] Marc Joye and Sung-Ming Yen. Optimal left-to-right binary signed-digit recoding. IEEE Trans. on Computers, 49(7):740-748, 2000.
[69] James A. Muir and Douglas R. Stinson. New minimal weight representations for left-to-right window methods. In Alfred Menezes, editor, Topics in Cryptology - CT-RSA 2005, volume 3376 of Lecture Notes in Computer Science, pages 366-383. Springer, 2005.
[70] Dong-Guk Han, , Tetsuya Izu, , and Tsuyoshi Takagi. Some explicit formulae of NAF and its left-to-right analogue. Cryptology ePrint Archive, 2005. Available at http://eprint.iacr.org/2005/384.
[71] Andrew D. Booth. A signed binary multiplication technique. Quarterly Journal of Mechanics and Applied Mathematics, 4(2):236-240, 1951.

指導教授

顏嵩銘(Sung-Ming Yen)

審核日期

2010-7-27

推文