(54.236.58.220) 您好!臺灣時間:2021/03/05 00:36
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:陳耀琳
研究生(外文):Chen, Yao-Lin
論文名稱:抵抗能量攻擊法的雙域橢圓曲線密碼運算單元之設計與實現
論文名稱(外文):Design and Implementation of a Dual-Field Elliptic Curve Cryptographic Processor with Power Analysis Countermeasures
指導教授:李鎮宜
指導教授(外文):Lee, Chen-Yi
學位類別:碩士
校院名稱:國立交通大學
系所名稱:電子研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2010
畢業學年度:98
語文別:英文
論文頁數:72
中文關鍵詞:橢圓曲線密碼有限域運算模數除法運算能量攻擊法
外文關鍵詞:Elliptic curve cryptographyFinite field operationsModular division operationPower analysis attack
相關次數:
  • 被引用被引用:0
  • 點閱點閱:212
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:17
  • 收藏至我的研究室書目清單書目收藏:0
在這篇論文中,我們提出了一個可支援雙域有限域運算以及可支援任意橢圓曲線運算的雙域橢圓曲線密碼運算單元。透過我們提出的通用演算法,這個運算單元的執行週期數大幅的降低。藉由我們提出的面積共用方法以及梯子選擇法,我們160位元以及256位元的雙域橢圓曲線密碼運算單元的面積在聯電90奈米製程下只須0.29mm2和0.45mm2。此外,運算單元的操作面積也可以透過我們提出的指數判定器以及資料路徑分離法可大幅的提升。我們也提出一個可以對抗能量攻擊法的雙域橢圓曲線密碼運算單元。透過我們提出的通用亂數演算法,我們面積的損失僅僅8.4%。
In this thesis, we propose a high-performance dual-field elliptic curve cryptographic processor (DECP) architecture that can support all finite field operations and elliptic curve (EC) functions with arbitrary field and curve. Based on our proposed fast unified division algorithm, the operation cycles can be significantly reduced. Compared with previous works using high radix multiplication in projective coordinate, our 160-bit and 256-bit DECPs can achieve competitive performance in terms of execution cycles with only 0.29mm2 and 0.45mm2 silicon area in UMC 90nm CMOS technology by exploiting hardware sharing and ladder selection techniques. In addition, the operating frequency in prime field and binary field can be increased due to the proposed data-path separation and degree checker. To resist power analysis attack, we propose a DECP with power analysis countermeasures architecture based on the proposed unified random algorithms with only 8.4% area overhead.
1 Introduction 1
1.1 Elliptic Curve Cryptography . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Power Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2 Preliminary of Elliptic Curve Cryptography Cryptosystem 4
2.1 Point Addition and Doubling over Finite Fields . . . . . . . . . . . . . . . 5
2.2 Analysis of Point Addition and Doubling in Different Coordinates . . . . . 6
2.3 Elliptic Curve Point Scalar Multiplication Methods . . . . . . . . . . . . . 7
2.4 Galois Field Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.4.1 Unified Multiplication Algorithms . . . . . . . . . . . . . . . . . . . 9
2.4.2 Unified Inversion and Division Algorithms . . . . . . . . . . . . . . 11
2.5 Elliptic Curve Cryptographic Applications . . . . . . . . . . . . . . . . . . 18
2.5.1 Elliptic Curve Data En/Decryption . . . . . . . . . . . . . . . . . . 18
2.5.2 Elliptic Curve Based Protocols . . . . . . . . . . . . . . . . . . . . . 18
2.6 Power Analysis Attacks and Countermeasures . . . . . . . . . . . . . . . . 19
2.6.1 Simple Power Analysis . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.6.2 Differential Power Analysis . . . . . . . . . . . . . . . . . . . . . . . 20
3 Proposed Unified Algorithms 23
3.1 Unified Division Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.2 Unified Multiplication Algorithm . . . . . . . . . . . . . . . . . . . . . . . 30
3.3 Unified Random Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.3.1 Unified Random Division Algorithm . . . . . . . . . . . . . . . . . 31
3.3.2 Unified Random Multiplication Algorithm . . . . . . . . . . . . . . 33
4 Proposed Architectures 35
4.1 Galois Field Arithmetic Unit . . . . . . . . . . . . . . . . . . . . . . . . . . 35
4.1.1 Data-path Separation . . . . . . . . . . . . . . . . . . . . . . . . . . 36
4.1.2 Hardware Sharing . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.1.3 Degree Checker . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
4.1.4 Ladder Selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
4.2 Dual-Field Elliptic Curve Cryptography Processor . . . . . . . . . . . . . . 40
4.3 Dual-Field Elliptic Curve Cryptography Processor with Power Analysis
Countermeasures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
5 Implementation Results 47
5.1 Galois Field Arithmetic Unit . . . . . . . . . . . . . . . . . . . . . . . . . . 47
5.2 Dual-Field Elliptic Curve Cryptography Processor . . . . . . . . . . . . . . 48
5.3 Dual-Field Elliptic Curve Cryptography Processor with Power Analysis
Countermeasures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
6 Conclusion and Discussion 57
A Appendix 58
A.1 Duality of Multiplication and Division . . . . . . . . . . . . . . . . . . . . 58
A.2 Power Analysis Attack on The Dual-Field Elliptic Curve Cryptographic
Processors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
A.3 Unified Division Algorithm Based on Takagi’s Algorithm . . . . . . . . . . 59
A.4 Word-based Unified Multiplication/Division Architecture . . . . . . . . . . 61
A.5 ECC Processor for RFID systems . . . . . . . . . . . . . . . . . . . . . . . 63
[1] Standard Specifications for Public-Key Cryptography: Additional Techniques, IEEE Std. 1363A, 2000.
[2] D. Hankerson, A. Menezes, and S. Vanstone, Guide to Elliptic Curve Cryptography. Springer, 2004.
[3] I. F. Blake, G. Seroussi, and N. P. Smart, Elliptic Curves in Cryptography. Cambridge University Press, 1999.
[4] ——, Advances in Elliptic Curve Cryptography. Cambridge University Press, 2005.
[5] H. Cohen and G. Frey, Handbook of Elliptic and Hyperelliptic Curve Cryptography. Chapman and Hall/CRC, 2006.
[6] W. Trappe and L. C. Washington, Introduction to Cryptography with Coding Theory, 2nd ed. Pearson Education International, 2006.
[7] R. L. Rivest, A. Shamir, and L. Adleman, “A method for obtaining digital signatures and public-key cryptosystems,” Commun. ACM, vol. 21, no. 2, pp. 120–126, 1978.
[8] H. Yan and Z. J. Shi, “Studying software implementations of elliptic curve cryptography,” in 3rd International Conference on Information Technology: New Generations (ITNG), Las Vegas, Nevada, USA, 2006.
[9] G. Chen, G. Bai, and H. Chen, “A high-performance elliptic curve cryptographic processor for general curves over GF(p) based on a systolic arithmetic unit,” IEEE Trans. Circuits Syst. II, Exp. Briefs, vol. 54, no. 5, pp. 412–416, May 2007.
[10] C. J. McIvor, M. McLoone, and J. V. McCanny, “Hardware elliptic curve cryptographic processor over GF(p),” IEEE Trans. Circuits Syst. I, Regular, vol. 53, no. 9, pp. 1946–1957, Sept. 2006.
[11] P. Longa and A. Miri, “Fast and flexible elliptic curve point arithmetic over prime fields,” IEEE Transactions on Computers, vol. 57, no. 3, pp. 289–302, Mar. 2008.
[12] J. Goodman and A. P. Chandrakasan, “An energy-efficient reconfigurable public-key cryptography processor,” IEEE J. Solid-State Circuits, vol. 36, no. 11, pp. 1808–1820, Nov. 2001.
[13] J.-H. Chen, M.-D. Shieh, and W.-C. Lin, “A high-performance unified-field reconfigurable cryptographic processor,” IEEE Transactions on Computers, pp. 1–14, Nov. 2009.
[14] Y. K. Lee, K. Sakiyama, L. Batina, and I. Verbauwhede, “Elliptic-curve-based security processor for RFID,” IEEE Transactions on Computers, vol. 57, no. 11, pp. 1514–1527, Nov. 2008.
[15] K. Sakiyama, L. Batina, B. Preneel, and I. Verbauwhede, “Multicore curve-based cryptoprocessor with reconfigurable modular arithmetic logic units over GF(2n),” IEEE Transactions on Computers, vol. 56, no. 9, pp. 1269–1282, Sept. 2007.
[16] K. Jarvinen and J. Skytta, “On parallelization of high-speed processors for elliptic curve cryptography,” IEEE Trans. Very Large Scale Integr. (VLSI) Syst., vol. 16, no. 9, pp. 1162–1175, Sept. 2008.
[17] B. Ansari and M. A. Hasan, “High-performance architecture of elliptic curve scalar multiplication,” IEEE Transactions on Computers, vol. 57, no. 11, pp. 1443–1453, Nov. 2008.
[18] S. Okada, N. Torii, K. Itoh, and M. Takenaka, “Implementation of elliptic curve cryptographic coprocessor over GF(2m) on an FPGA,” in Proc. Cryptographic Hardware and Embedded Systems (CHES’00), Worcester, MA, USA, Aug. 2000.
[19] Y. Eslami, A. Sheikholeslami, P. G. Gulak, S. Masui, and K. Mukaida, “An areaefficient universal cryptography processor for smart cards,” IEEE Trans. Very Large Scale Integr. (VLSI) Syst., vol. 14, no. 1, pp. 43–56, Jan. 2006.
[20] M. Purnprajna, C. Puttmann, and M. Porrmann, “Power aware reconfigurable multiprocessor for elliptic curve cryptography,” in Design, Automation and Test in Europe Conference and Exhibition, ICM, Munich, Germany, Mar. 2008, pp. 1462–1467.
[21] S. Peter, P. Langend¨orfer, and K. Piotrowski, “Flexible hardware reduction for elliptic curve cryptography in GF(2m),” in Design, Automation and Test in Europe Conference and Exhibition, Nice Acropolis, France, Apr. 2007, pp. 1–6.
[22] S. Kumar and C. Paar, “Are standards compliant elliptic curve cryptosystems feasible on RFID?” in Workshop Record of the ECRYPT Workshop RFID Security, 2006.
[23] A. Satoh and K. Takano, “A scalable dual-field elliptic curve cryptographic processor,” IEEE Trans. Comput., vol. 52, no. 4, pp. 449–460, 2003.
[24] J.-Y. Lai and C.-T. Huang, “Elixir: High-throughput cost-effective dual field processors and the design framework for elliptic curve cryptography,” IEEE Trans. Very Large Scale Integr. (VLSI) Syst., vol. 16, no. 11, pp. 1567–1580, Nov. 2008.
[25] ——, “A highly efficient cipher processor for dual-field elliptic curve cryptography,” IEEE Trans. Circuits Syst. II, Exp. Briefs, vol. 56, no. 5, pp. 394–398, May 2009.
[26] E.W.Weisstein, “Fermat’s little theorem,” in MathWorld–A Wolfram Web Resource, http://mathworld.wolfram.com/FermatsLittleTheorem.html.
[27] B. S. K. Jr., “The Montgomery inverse and its applications,” IEEE Transactions on Computers, vol. 44, no. 8, pp. 1064–1065, Aug. 1995.
[28] E. Sava¸s and C¸ . K. Ko¸c, “The Montgomery modular inverse - revisited,” IEEE Trans. Circuits Syst. II, Exp. Briefs, vol. 49, no. 7, pp. 763–766, July 2000.
[29] R. Deng and Y. Zhou, “Improvement to Montgomery modular inverse algorithm,” IEEE Trans. Circuits Syst. II, Exp. Briefs, vol. 55, no. 9, pp. 1207–1210, Sept. 2006.
[30] A. A.-A. Gutub, A. F. Tenca, and C¸ . K. Ko¸c, “Scalable and unified hardware to compute Montgomery inverse in GF(p) and GF(2n),” in CHES’02, Redwood Shores, CA, USA, 2003.
[31] Y.-J. Liu, “An implementation of universal dual-field scalar multiplication on elliptic curve cryptosystems,” Master’s thesis, National Chiao Tung University, 2007.
[32] C.-Y. Tseng, “Design and implementation of an SPA-resistance dual-field elliptic curve arithmetic unit,” Master’s thesis, National Chiao Tung University, 2008.
[33] J.-W. Lee, Y.-L. Chen, C.-Y. Tseng, H.-C. Chang, and C.-Y. Lee, “A 521-bit dualfield elliptic curve cryptographic processor with power analysis resistance,” in European Solid-State Circuits Conference (ESSCIRC), Seville, Spain, Sept. 2010 (to appear).
[34] E. Sava¸s, “A carry-free architecture for Montgomery inversion,” IEEE Transactions on Computers, vol. 54, no. 12, pp. 1508–1519, Dec. 2005.
[35] M. E. Kaihara and N. Takagi, “A hardware algorithm for modular multiplication/division,” IEEE Transactions on Computers, vol. 54, no. 1, pp. 12–21, January, 2005.
[36] G. Chen and H. Chen, “A new systolic architecture for modular division,” IEEE Transactions on Computers, vol. 56, no. 2, pp. 282–286, Feb. 2007.
[37] G. M. d. Dormale, P. Bulens, and J.-J. Quisquater, “Efficient modular division implementation,” in FPL 2004, LNCS 3203, Leuven, Belgium, 2004, pp. 231–240.
[38] N. Takagi, “A VLSI algorithm for modular division based on the binary GCD algorithm,” IEICE Trans. Fundamentals, vol. E81-A, no. 5, pp. 724–728, May 1998.
[39] S. Mangard, E. Oswald, and T. Popp, Power analysis Attacks-Revealing the Secrets of Smart Cards. Springer, 2006.
[40] A. Miyamoto, N. Homma, T. Aoki, and A. Satoh, “SPA aganist an FPGA-based RSA implementation with a high-radix Montgomery multiplier,” in IEEE Int. Symp. Circuit Sust. (ISCAS), New Orleans, USA, May 2007, pp. 1847–1850.
[41] ——, “Chosen-message SPA attacks against FPGA-based RSA hardware implementation,” in Int. Conf. on Field Programmable Logic and Applications (FPL), Heidelberg, Germany, Sept. 2008.
[42] P. C. Kocher, “Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems,” in Proceedings of the 16th Annual International Cryptology Conference on Advances in Cryptology, 1996, pp. 104–113.
[43] P. C. Kocher, R. Lee, and G. McGraw, “Security as a new dimension in embedded system design,” in Proceedings of the 41th Annual Conference on Design Automation, 2004, pp. 753–760.
[44] P. C. Kocher, J. Jaffe, and B. Jun, “Differential power analysis,” in Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology, 1999, pp. 388–397.
[45] R. Muresan and S. Gregori, “Protection circuit against differential power analysis attacks for smart cards,” IEEE Transactions on Computers, vol. 57, no. 11, pp. 1540–1549, Nov. 2008.
[46] E. Brier and M. Joye, “Weiersta elliptic curves and side-channel attack,” in PKC’02, vol. 2274, Paris, France, 2002, pp. 335–345.
[47] J. L´opez and R. Dahab, “Fast multiplication on elliptic curve over GF(2n) without precomputation,” in CHES’99, vol. 1717, Worcester, MA, USA, 1999, pp. 316–327.
[48] P. Fouque and F. Valette, “The doubling attack-why upwards is better than downwards,” in CHES’03, vol. 2779, Cologne, Germany, 2003, pp. 269–280.
[49] K. Itoh, T. Izu, and M. Takenaka, “Address-bit differential power analysis of cryptographic schemes OK-ECDH and OK-ECDSA,” in CHES’02, Redwood Shores, CA, USA, 2003, pp. 399–412.
[50] L. Goubin, “A refined power-analysis attack on elliptic curve cryptosystems,” in PKC 2003, ser. Lecture Notes in Computer Science, vol. 2567, Miami, Florida, USA, 2003, pp. 199–210.
[51] T. Akishita and T. Takagi, “Zero-value point attacks on elliptic curve cryptosystem,” in ISC 2003, ser. Lecture Notes in Computer Science, vol. 2851, Bristol, UK, 2003, pp. 199–210.
[52] J. L´opez and R. Dahab, “Improved algorithms for elliptic curve arithmetic in GF(2m),” in Sel. Areas Cryptography: 5th Annu. Int. Workshop(SAC), vol. 1556, Santa Fe, New Mexico, Aug. 1998, pp. 201–212.
[53] H. Cohen, A. Miyaji, and T. Ono, “Efficient elliptic curve exponentiation using mixed coordinates,” in in Proc. Adv. Cryptolog. (Asiacrypt’98).
[54] P. L. Montgomery, “Modular multiplication without trial division,” Mathematics of Computation, vol. 44, no. 170, pp. 519–521, April 1985.
[55] G. Chen, G. Bai, and H. Chen, “A dual-field elliptic curve cryptographic processor based on a systolic arithmetic unit,” in IEEE Int. Symp. Circuit Sust. (ISCAS), Seattle, Washington, USA, May 2008, pp. 3298–3301.
[56] A. F. Tenca and C¸ . K. Ko¸c, “A scalable architecture for modular multiplication based on Montgomery’s algorithm,” IEEE Transactions on Computers, vol. 52, no. 9, pp. 1215–1221, Sept. 2003.
[57] D. E. Knuth, The Art of Computer Programming, 3rd ed. Addison-Wesley, 1998, vol. 2, ch. Seminumerical Algorithms.
[58] G. V. S. Raju and R. Akbani, “Elliptic curve cryptosystem and its applications,” in IEEE International Conference on Systems, Man and Cybernetics, vol. 2, Crystal City Hyatt Regency Washington, D. C., USA, Nov. 2003, pp. 1540–1543.
[59] FIPS 186—Digital signature standard, National Institute of Standards and Technology (NIST) Std., June 2009.
[60] J.-S. Coron, “Resistance against differential power analysis for elliptic curve cryptography,” in CHES’99, ser. Lecture Notes in Computer Science, C¸ . K. Ko¸c and C. Paar, Eds., vol. 1717, Worcester, MA, USA, 1999, pp. 292–302.
[61] T. Addabbo, M. Alioto, A. Fort, S. Rocchi, and V. Vignoli, “Long period pseudo random bit generators derived from a discretized chaotic map,” in IEEE International Symposium on Circuits and Systems (ISCAS), vol. 2, Kobe, Japan, May 2005, pp. 892–895.
[62] A. Rukhin, J. Soto, J. Nechvatal, M. Smid, E. Barker, S. Leigh, M. Levenson, D. B. M. Vangel, A. Heckert, J. Dray, and S. Vo, A statistical test suite for random and pseudorandom number generators for cryptographic applications, NIST Special Publication 800-22 Std., Aug. 2008.
[63] F. Zhou, C. Chen, D. Jin, C. Huang, and H. Ming, “Evaluating and optimizing power consumption of anti-collision protocols for application in RFID systems,” in AUTO-ID Labs, white paper, 2008.
[64] Information Technology-Radio Frequency Identification for Item Management-Part 3: Parameters for Air Interface Communications at 13.56 MHz, ISO/IEC Std. 18000-3:2004, 2004.

連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關論文
 
系統版面圖檔 系統版面圖檔