臺灣博碩士論文加值系統

相較於另一主流的公開金鑰密碼技術RSA，橢圓曲線密碼利用其數學特性能以更短的金鑰長度達到相同的安全強度等級。本論文提出了基於多項式基底且滿足Galois fields (GF (2^163)) 的高效能橢圓曲線運算電路，採用NIST建議的K-163曲線實現。我們使用Lopez-Dahab 投影座標系以避免冗長的模倒數運算，再配合使用Double-and-Add演算法實現橢圓曲線的點乘法運算。核心運算單元分別以Modular Addition、Modular Squaring、Digit-Serial Multiplication、Itoh-Tsujii 倒數演算法作為整個橢圓曲線電路之運算核心。在硬體實現上，我們採用階層式架構設計，利用台灣半導體研究中心(TSRI) 所提供之TSMC 0.18μm 製程技術搭配Synopsys Design Compiler合成所需電路，電路面積約為42.619K (gate count)，最高操作頻率可達到100MHz，點乘法平均運算時間為0.709ms。

Comparing with another mainstream Public-key Cryptography (PKC) technology RSA, Elliptic Curve Cryptography (ECC) technology uses its mathematical characteristics to achieve shorter key length with the same security strength level. This thesis proposes a high-performance elliptic curve encryption circuit based on Polynomial Basis and satisfying Galois fields GF (2^163), which is implemented using the K-163 curve recommended by NIST. We use the Lopez-Dahab projective coordinate system to avoid tedious modular inversion and use the Double-and-Add algorithm to implement the point multiplication of the elliptic curve. The modular addition, modular squaring, modular digit-serial multiplication, and Itoh-Tsujii inversion are the key computing cores. In hardware implementation, we adopt hierarchical structure design and use the TSMC 0.18μm process technology provided by the Taiwan Semiconductor Research Institute (TSRI) and Synopsys Design Compiler to synthesize our design. The chip area is about 42.619K (gate count) and the highest operating frequency can reach 100MHz. The average operation time of Point Multiplication is 0.709ms.

誌謝 ii
摘要 iii
ABSTRACT iv
目錄 vi
圖目錄 ix
表目錄 xii
第一章 序論 1
1.1 介紹與動機 1
1.2 研究目標與成果 1
1.3 章節簡介 2
第二章 密碼學與相關數學背景介紹 4
2.1 密碼學發展 4
2.2 密碼系統與安全性 6
2.2.1 密碼系統功能 6
2.2.2 密碼系統安全 7
2.2.3 密碼攻擊 8
2.2.4 對稱金鑰密碼系統(Symmetric-Key Cryptosystem) 11
2.2.5 公開金鑰密碼系統(Public-Key Cryptosystem) 13
2.3 橢圓曲線密碼系統(Elliptic Curve Cryptosystem) 15
2.3.1 數論基礎 17
2.3.1.1 有限場(Finite Field) 17
2.3.1.2 群(Group) 18
2.3.1.3 定義於二元域 19
2.3.1.4 同餘與模數運算 21
2.3.1.5 多項式(Polynomial Basis)與一般式(Normal Basis)基底 22
2.3.2 有限場的選擇 24
2.3.2.1 有限場GF(p) 24
2.3.2.2 有限場GF(2m) 24
2.3.3 橢圓曲線與其參數的選擇 28
2.3.3.1 韋爾斯特拉斯(Weierstrass Equation, Generic Curve) 30
2.3.3.2 愛德華曲線(Edwards Curve) 30
2.3.3.3 蒙哥馬利曲線(Montgomery Curve) 31
2.3.3.4 黑森曲線(Hessian Curve) 31
2.3.4 基於橢圓曲線的運算 32
2.3.4.1 無窮遠點 O 32
2.3.4.2 有關Point Addition 相異點之加法運算 32
2.3.4.3 有關Point Doubling 相同點之加法運算 33
2.3.4.4 有關Point Multiplication 點乘法運算 34
2.3.5 坐標系的選擇 37
2.3.5.1 仿射坐標系(Affine Coordinate System) 37
2.3.5.2 投影坐標系(Projective Coordinate System) 38
2.3.6 有限場的運算與不可約分多項式介紹 41
2.3.6.1 基於GF(2m)的加法運算(Modular Addition) 41
2.3.6.2 不可約分多項式(Irreducible Polynomial) 42
2.3.6.3 基於GF(2m)的乘法運算(Modular Multiplication) 46
2.3.6.4 基於GF(2m)的平方運算(Modular Squaring) 48
2.3.6.5 基於GF(2m)的倒數運算(Modular Inversion) 49
第三章 演算法介紹 53
3.1 基於GF(2m)之Modular Multiplication演算法 54
3.1.1 以2-bit作為一個digit (d = 2) 55
3.1.2 以4-bit作為一個digit (d = 4) 56
3.2 基於GF(2m)之Modular Squaring演算法 58
3.3 基於GF(2m)之Modular Inverse演算法 61
3.4 有關Point Multiplication演算法 66
第四章 硬體設計與實現 68
4.1 橢圓曲線點乘法運算之硬體設計 68
4.2 階層式模組之實現 69
4.3 基於多項式基底之二元運算加法器硬體實現 71
4.4 基於多項式基底之 Digit-Serial 模乘法器之實現 72
4.5 基於多項式基底之模平方器之硬體實現 74
4.6 有關 Itoh-Tsujii Inverse Algorithm 之硬體實現 75
4.7 有關 Scalar Multiplication 之硬體實現 78
第五章 實驗結果 86
5.1 電路設計與驗證流程 86
5.2 加密與解密過程的PM運算驗證 87
5.2.1 RTL Function-Level Simulation Result 89
5.2.2 Gate-Level Simulation Result 91
5.3 模擬數據比較 93
第六章 結論與未來展望 97
6.1 結論 97
6.2 未來展望 97
參考文獻 99
附錄/Appendix 107

[1]R. L. Rivest, A. Shamir, and L. Adleman, “A Method for Obtaining Digital Signatures and Public-Key Cryptosystems,” Communications of ACM, vol. 21, no. 2, pp. 120-126, February 1978.
[2]N. Koblitz, “Elliptic Curve Cryptosystems,” Mathematics of Computation, vol. 48, no. 177, pp. 203-209, January 1987.
[3]V. S. Miller, “Use of Elliptic Curves in Cryptography,” Advances in Cryptology — CRYPTO ’85 Proceedings. Lecture Notes in Computer Science, vol. 218, pp. 417-426, 1986.
[4]W. Diffie and M. Hellman, “New Directions in Cryptography,” in IEEE Transactions on Information Theory, vol. 22, no. 6, pp. 644-654, November 1976.
[5]Certicom cooperation, The Next Generation of Cryptography, https://www.certicom.com/content/certicom/en/code-and-cipher/article/502-public-key-sizes-for-aes.html
[6]M. S. Hossain, Y. Kong, E. Saeedi and N. C. Vayalil, “High-Performance Elliptic Curve Cryptography Processor over NIST Prime Fields,” IET Computers & Digital Techniques, vol. 11, no. 1, pp. 33-42, 2017.
[7]H. Ting and C. Huang, “Design of Low-Cost Elliptic Curve Cryptographic Engines for Ubiquitous Security,” 2014 International Symposium on VLSI Design, Automation and Test, Hsinchu, pp.1-4, April 2014.
[8]H. Zhao, L. Wang and G. Bai, “An Elliptic Curve Cryptography Coprocessor Over GF(2m) on a Low-Cost Embedded System,” 2007 International Workshop on Electron Devices and Semiconductor Technology (EDST), Tsinghua University, pp. 190-193, June 2007.
[9]T. Itoh, S. Tsujii, “A Fast Algorithm for Computing Multiplicative Inverses in GF(2m) Using Normal Bases,” Information and Computation, vol. 78, no. 3, pp. 171–177, September 1988.
[10]鄧安文，2014，密碼學，全華圖書股份有限公司。
[11]National Institute of Standards and Technology (NIST), “Data Encryption Standard (DES),” Federal Information Processing Standards Publication 46 (FIPS-46), January 1977.
[12]National Institute of Standards and Technology (NIST), “Advanced Encryption Standard (AES),” Federal Information Processing Standards Publication 197 (FIPS-197), November 2001.
[13]T. Elgamal, “A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms,” IEEE Transactions on Information Theory, vol. 31, no. 4, pp. 469-472, July 1985.
[14]C. Paar and J. Pelzl, Understanding cryptography: A Textbook for Students and Practitioners, Springer Science & Business Media, pp.156~157 2009.
[15]Institute of Electrical and Electronics Engineers (IEEE), “IEEE Standard Specifications for Public-Key Cryptography,” IEEE 1363-2000, January 2000.
[16]National Institute of Standards and Technology (NIST), “Digital Signature Standard (DSS),” Federal Information Processing Standards Publication 186-2 (FIPS-186-2), January 2000.
[17]Standards for Efficient Cryptography Group (SECG), “SEC 1: Elliptic Curve Cryptography,” Standards for Efficient Cryptography 1 (SEC 1), May 2009.
[18]Standards for Efficient Cryptography Group (SECG), “SEC 2: Recommended Elliptic Curve Domain Parameters,” Standards for Efficient Cryptography 2 (SEC 2), January 2010.
[19]National Institute of Standards and Technology (NIST), “Digital Signature Standard (DSS),” Federal Information Processing Standards Publication 186-5 (FIPS-186-5), October 2019.
[20]American National Standards Institute (ANSI), “Public Key Cryptography for the Financial Services Industry - The Elliptic Curve Digital Signature Algorithm (ECDSA),” ANSI X9.62, November 2005.
[21]American National Standards Institute (ANSI), “Public Key Cryptography for the Financial Services Industry - Key Agreement and Key Transport Using Elliptic Curve,” ANSI X9.63–2011 (R2017), February 2017.
[22]Institute of Electrical and Electronics Engineers (IEEE), “IEEE Standard Specifications for Public-Key Cryptography,” IEEE 1363.3-2013, November 2013.
[23]B. Kaliski, “RSA Factoring Challenge,” Encyclopedia of Cryptography and Security. Springer, Boston, MA. https://doi.org/10.1007/978-1-4419-5906-5_433
[24]T. Kleinjung et al, “Factorization of a 768-Bit RSA Modulus,” Advances in Cryptology – CRYPTO 2010. Lecture Notes in Computer Science (LNCS), vol. 6223, pp. 333-350, 2010.
[25]Certicom corporation, “Certicom ECC Challenge,” November 1997. https://www.certicom.com/content/certicom/en/the-certicom-ecc-challenge.html
[26]D. V. Bailey, L. Batina, D. J. Bernstein, P. Birkner, J. W. Bos, H. Chen, C. Cheng, G. van Damme, G. de Meulenaer, L. J. D. Perez,J. Fan, T. G ̈uneysu, F. Gurkaynak, T. Kleinjung, T. Lange, N. Mentens, R. Niederhagen, C. Paar, F. Regazzoni, P. Schwabe, L. Uhsadel, A. VanHerrewege, and B. Yang, “Breaking ECC2K-130,” 2009. https://eprint.iacr.org/2009/541.pdf
[27]R. K. Kodali, “Elliptic Curve Based Digital Envelope in WSN,” 2013 International Conference on Advanced Electronic Systems (ICAES), Pilani, pp. 292-296, September 2013.
[28]M. Imran and M. Rashid, “Architectural Review of Polynomial Bases Finite Field Multipliers Over GF(2m),” 2017 International Conference on Communication, Computing and Digital Systems (C-CODE), Islamabad, pp. 331-336, March 2017.
[29]J. Fan, D. V. Bailey, L. Batina, T. Güneysu, C. Paar and I. Verbauwhede, “Breaking Elliptic Curve Cryptosystems Using Reconfigurable Hardware,” 2010 International Conference on Field Programmable Logic and Applications, Milano, pp. 133-138, August 2010.
[30]I. H. Hazmi, F. Zhou, F. Gebali and T. F. Al-Somani, “Review of Elliptic Curve Processor Architectures,” 2015 IEEE Pacific Rim Conference on Communications, Computers and Signal Processing (PACRIM), Victoria, BC, pp. 192-200, August 2015.
[31]C. F. Uribe, “A Reconfigurable and Interoperable Hardware Architecture for Elliptic Curve Cryptography,” Ph.D. Thesis, Instituto Nacional de Astrofísica, Óptica y Electrónica, December 2008.
[32]D. Hankerson et al, Guide to Elliptic Curve Cryptography. New York: Springer-Verlag, 2004, chapter 3, pp. 76-87.
[33]F. Ding, Y. Long and P. Wu, “Study on Secret Sharing for SM2 Digital Signature and Its Application,” 2018 14th International Conference on Computational Intelligence and Security (CIS), Hangzhou, pp. 205-209, November 2018.
[34]W. Li, J. Liu and G. Bai, “High-speed Implementation of SM2 Based on Fast Modulus Inverse Algorithm,” 2018 China Semiconductor Technology International Conference (CSTIC), Shanghai, pp. 1-3, March 2018.
[35]H. M. Edwards, “A Normal Form for Elliptic Curves,” Bulletin of the American Mathematical Society, vol. 44, no. 3, pp. 393-422, July 2007.
[36]P. L. Montgomery, “Speeding the Pollard and Elliptic Curve Methods of Factorization”, Mathematics of Computation, vol. 48, no. 177, pp. 243-264, January 1987.
[37]N. P. Smart, “The Hessian Form of an Elliptic Curve,” Cryptographic Hardware and Embedded Systems — CHES 2001, Lecture Notes in Computer Science, vol. 2162, pp. 118-125, 2001.
[38]M. Joye, S. M. Yen, “The Montgomery Powering Ladder,” Cryptographic Hardware and Embedded Systems - CHES 2002, Lecture Notes in Computer Science, vol. 2523, pp. 291-302, 2002.
[39]Z. U. A. Khan and M. Benaissa, “High-Speed and Low-Latency ECC Processor Implementation Over GF(2m) on FPGA,” IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 25, no. 1, pp. 165-176, January 2017.
[40]J. López, R. Dahab, “Fast Multiplication on Elliptic Curves Over GF(2m) without Precomputation,” Cryptographic Hardware and Embedded Systems, Lecture Notes in Computer Science, vol. 1717, pp. 316-327, 1999.
[41]D. Hankerson et al, Guide to Elliptic Curve Cryptography. New York: Springer-Verlag, 2004, chapter 3, pp. 86-95.
[42]Wang, Troung, Shao, Deutsch, Omura and Reed, “VLSI Architectures for Computing Multiplications and Inverses in GF(2m),” IEEE Transactions on Computers, vol. C-34, no. 8, pp. 709-717, August 1985.
[43]D. Hankerson et al, Guide to Elliptic Curve Cryptography. New York: Springer-Verlag, 2004, chapter 2, pp. 40-42.
[44]B. S. Kaliski, “The Montgomery Inverse and Its Applications,” IEEE Transactions on Computers, vol. 44, no. 8, pp. 1064-1065, August 1995.
[45]P. L. Montgomery, “Modular Multiplication without Trial Division”, Mathematics of Computation, vol. 44, no. 170, pp. 519-521, April 1985.
[46]A. Karatsuba and Yu. Ofman. “Multiplication of Many-Digital Numbers by Automatic Computers,” USSR Academy of Sciences, vol.145, no. 2, pp. 293-294, September 1962.
[47]D. Narh Amanor, C. Paar, J. Pelzl, V. Bunimov and M. Schimmler, “Efficient Hardware Architectures for Modular Multiplication on FPGAs,” International Conference on Field Programmable Logic and Applications, Tampere, pp. 539-542, August 2005.
[48]Z. Liu, D. Liu, X. Zou, H. Lin, J. Cheng, “Design of an Elliptic Curve Cryptography Processor for RFID Tag Chips,” Sensors, vol. 14, no. 10, pp. 17883-17904, September 2014.
[49]K. Javeed, X. Wang and M. Scott, “Serial and Parallel Interleaved Modular Multipliers on FPGA Platform,” 2015 25th International Conference on Field Programmable Logic and Applications (FPL), London, pp. 1-4, September 2015.
[50]F. Rodriguez-Henriquez, N. Cruz-Cortes and N. A. Saqib, “A Fast Implementation of Multiplicative Inversion Over GF(2m),” International Conference on Information Technology: Coding and Computing (ITCC'05) - Volume II, Las Vegas, NV, pp. 574-579, April 2005.
[51]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, November 2008.
[52]J. Hong and W. Wu, “The Design of High-Performance Elliptic Curve Cryptographic,” 2009 52nd IEEE International Midwest Symposium on Circuits and Systems, Cancun, pp. 527-530, August 2009.
[53]張正賢（2009）。以投影座標實現高效能架構之橢圓曲線晶片。國立高雄大學電機工程學系碩士班碩士論文，高雄市。
[54]Y. Dan and H. He, “Tradeoff Design of Low-Cost and Low-Energy Elliptic Curve Crypto-Processor for Wireless Sensor Networks,” 2012 8th International Conference on Wireless Communications, Networking and Mobile Computing, Shanghai, pp. 1-5, September 2012.
[55]J. Heyszl and F. Stumpf, “Efficient One-Pass Entity Authentication Based on ECC for Constrained Devices,” 2010 IEEE International Symposium on Hardware-Oriented Security and Trust (HOST), Anaheim, CA, pp. 88-93, June 2010.
[56]J. Lee, S. Chung, H. Chang and C. Lee, “Efficient Power-Analysis-Resistant Dual-Field Elliptic Curve Cryptographic Processor Using Heterogeneous Dual-Processing-Element Architecture,” IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 22, no. 1, pp. 49-61, January 2014.
[57]X. Tan, M. Dong, C. Wu, K. Ota, J. Wang and D. W. Engels, “An Energy-Efficient ECC Processor of UHF RFID Tag for Banknote Anti-Counterfeiting,” IEEE Access, vol. 5, pp. 3044-3054, 2017.
[58]N. Desai, C. Juvekar, S. Chandak and A. P. Chandrakasan, “An Actively Detuned Wireless Power Receiver with Public Key Cryptographic Authentication and Dynamic Power Allocation,” IEEE Journal of Solid-State Circuits, vol. 53, no. 1, pp. 236-246, January 2018.