|
|
基于FPGA的SM9数字签名算法的快速实现
|
Abstract:
SM9算法是由我国推出的基于双线性对的标识密码算法，其中使用的R-ate双线性对在计算效率上优于Weil对和Tate对，但在实际应用中仍有不足。针对上述问题，为了提升SM9中双线性对的计算效率，提出了一种在FPGA平台上使用滑动窗口改进R-ate对运算的方法。该方法以蒙哥马利模乘为基础改进扩域模逆运算并通过滑动窗口算法优化R-ate双线性对运算中的Miller循环部分。同时根据蒙哥马利模乘特性减少椭圆曲线上点运算计算量提升签名算法运算效率。仿真结果表明，采用该方法可以将SM9中R-ate对的运算效率提升约18.46%，对SM9签名算法效率提升约为13.55%。
SM9 algorithm is an identity-based cryptographic algorithm based on bilinear pairing introduced by our country, in which the R-ate pairing used is better than Weil pairing and Tate pairing in terms of computational efficiency, but it still has deficiencies in practical applications. To improve the computational efficiency of the bilinear pairing in SM9, a method was proposed to improve the R-ate pairing operation by using a sliding window on the FPGA platform. The method was based on the Montgomery modular multiplication to enhance the modular inverse operation in the twelfth extension field and optimize the Miller loop in the R-ate pairing operation through the sliding window algorithm. At the same time, the computational efficiency of the signature algorithm was improved by reducing the number of point operations on elliptic curves according to the Montgomery modular multiplication property. Simulation results showed that this method could improve the computational efficiency of R-ate pairing in SM9 by approximately 18.46%, and the efficiency of the SM9 signature algorithm by approximately 13.55%.
| [1] | Shamir, A. (2000) Identity-Based Cryptosystems and Signature Schemes. In: Blakley, G.R. and Chaum, D., Eds., Advances in Cryptology, Springer, 47-53. https://doi.org/10.1007/3-540-39568-7_5 |
| [2] | Boneh, D., Lynn, B. and Shacham, H. (2001) Short Signatures from the Weil Pairing. In: Boyd, C., Ed., Advances in Cryptology—ASIACRYPT 2001, Springer, 514-532. https://doi.org/10.1007/3-540-45682-1_30 |
| [3] | Chen, X., Zhang, F. and Kim, K. (2006) New ID-Based Group Signature from Pairings. Journal of Electronics (China), 23, 892-900. https://doi.org/10.1007/s11767-005-0065-2 |
| [4] | Zhang, F. and Kim, K. (2002) ID-Based Blind Signature and Ring Signature from Pairings. In: Zheng, Y.L., Ed., Advances in Cryptology—ASIACRYPT 2002, Springer, 533-547. https://doi.org/10.1007/3-540-36178-2_33 |
| [5] | Lin, C.Y. and Wu, T.C. (2004) An Identity-Based Ring Signature Scheme from Bilinear Pairings. 18th International Conference on Advanced Information Networking and Applications, Fukuoka, 29-31 March 2004, 182-185. https://doi.org/10.1109/aina.2004.1283782 |
| [6] | Boneh, D., Gentry, C., Lynn, B. and Shacham, H. (2003) Aggregate and Verifiably Encrypted Signatures from Bilinear Maps. In: Biham, E., Ed., Advances in Cryptology—EUROCRYPT 2003, Springer, 416-432. https://doi.org/10.1007/3-540-39200-9_26 |
| [7] | Joux, A. (2000) A One Round Protocol for Tripartite Diffie-Hellman. In: Bosma, W., Ed., Algorithmic Number Theory, Springer, 385-393. https://doi.org/10.1007/10722028_23 |
| [8] | Chen, L., Cheng, Z. and Smart, N.P. (2007) Identity-Based Key Agreement Protocols from Pairings. International Journal of Information Security, 6, 213-241. https://doi.org/10.1007/s10207-006-0011-9 |
| [9] | Lee, E., Lee, H. and Park, C. (2009) Efficient and Generalized Pairing Computation on Abelian Varieties. IEEE Transactions on Information Theory, 55, 1793-1803. https://doi.org/10.1109/tit.2009.2013048 |
| [10] | Menezes, A., Vanstone, S. and Okamoto, T. (1991) Reducing Elliptic Curve Logarithms to Logarithms in a Finite Field. Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, New Orleans, 5-8 May 1991, 80-89. https://doi.org/10.1145/103418.103434 |
| [11] | Frey, G., Muller, M. and Ruck, H. (1999) The Tate Pairing and the Discrete Logarithm Applied to Elliptic Curve Cryptosystems. IEEE Transactions on Information Theory, 45, 1717-1719. https://doi.org/10.1109/18.771254 |
| [12] | Kim, T., Kim, S. and Cheon, J.H. (2013) On the Final Exponentiation in Tate Pairing Computations. IEEE Transactions on Information Theory, 59, 4033-4041. https://doi.org/10.1109/tit.2013.2240763 |
| [13] | Scott, M., Benger, N., Charlemagne, M., Dominguez Perez, L.J. and Kachisa, E.J. (2009) On the Final Exponentiation for Calculating Pairings on Ordinary Elliptic Curves. In: Shacham, H. and Waters, B., Eds., Pairing-Based Cryptography—Pairing 2009, Springer, 78-88. https://doi.org/10.1007/978-3-642-03298-1_6 |
| [14] | Cheng, Z.H. and Nistazakis, M. (2005) Implementing Pairing-Based Cryptosystems. Proceedings of 3rd International Workshop in Wireless Security Technologies (IWWST 2005), London, 4-5 April 2005. |
| [15] | Barreto, P.S.L.M., Kim, H.Y., Lynn, B. and Scott, M. (2002) Efficient Algorithms for Pairing-Based Cryptosystems. In: Yung, M., Ed., Advances in Cryptology—CRYPTO 2002, Springer, 354-369. https://doi.org/10.1007/3-540-45708-9_23 |
| [16] | Ezzouak, S., El Amrani, M. and Azizi, A. (2014) Optimizing the Computing of Pairing with Miller’s Algorithm. International Journal of Security and Its Applications, 8, 171-182. https://doi.org/10.14257/ijsia.2014.8.4.16 |
| [17] | Stange, K.E. (2007) The Tate Pairing via Elliptic Nets. In: Takagi, T., et al., Eds., Pairing-Based Cryptography—Pairing 2007, Springer, 329-348. https://doi.org/10.1007/978-3-540-73489-5_19 |
| [18] | Miller, V.S. (2004) The Weil Pairing, and Its Efficient Calculation. Journal of Cryptology, 17, 235-261. https://doi.org/10.1007/s00145-004-0315-8 |
| [19] | Zhao, C., Zhang, F. and Huang, J. (2008) Efficient Tate Pairing Computation Using Double-Base Chains. Science in China Series F: Information Sciences, 51, 1096-1105. https://doi.org/10.1007/s11432-008-0070-9 |
| [20] | 密码行业标准化技术委员会. SM9标识密码算法 第1部分: 总则: GM/T 0044.1-2016 [S]. 北京: 中国标准出版社, 2016. |
| [21] | 甘植旺, 廖方圆. 国密SM9中R-ate双线性对快速计算[J]. 计算机工程, 2019, 45(6): 171-174. |
| [22] | 付柱. R-ate双线性对密码算法的高效实现[D]: [硕士学位论文]. 天津: 天津大学, 2018. |
| [23] | 胡芯忆, 何德彪, 彭聪, 等. 一种SM9算法R-ate对的快速实现方法[J]. 密码学报, 2022, 9(5): 936-948. |
| [24] | 李江峰. SM9算法的研究与FPGA实现[D]: [硕士学位论文]. 西安: 西安电子科技大学, 2021. |
| [25] | Dong, X., Gao, M., Ma, X., Xiao, C. and Zhang, L. (2024) An Implementation of R-ate Pairing Based on FPGA. 2024 3rd International Conference on Big Data, Information and Computer Network (BDICN), Sanya, 12-14 January 2024, 167-173. https://doi.org/10.1109/bdicn62775.2024.00041 |
