Optimization of high-degree extension field operations in SM9 based on base field representation

Xie Zhenjie; Liu Shengli; Zhao Fangfang; Wang Zhichao

doi:10.11959/j.issn.2096-109x.AQ25187

您当前的位置：

首页 >

文章列表页 >

Optimization of high-degree extension field operations in SM9 based on base field representation

Papers | 更新时间：2026-05-11

- Optimization of high-degree extension field operations in SM9 based on base field representation
- Chinese Journal of Network and Information Security Vol. 12, Issue 2, Pages: 83-89(2026)
- 作者机构：
  
  1.信息工程大学网络空间安全教育部重点实验室，河南郑州 450001
  2.中国人民解放军78156部队，重庆 400039
- 作者简介：
- 基金信息：
  
  The Equipment Pre Research Project(30603010601)
- DOI：10.11959/j.issn.2096-109x.AQ25187
  CLC： TP309.7
- Received：19 July 2025，
  
  Revised：2026-02-21，
  
  Published：25 April 2026
- 稿件说明：
移动端阅览
谢振杰, 刘胜利, 赵方方, 等. 基于基域表示的SM9高次扩域运算优化[J]. 网络与信息安全学报, 2026, 12(2): 83-89.

Xie Zhenjie, Liu Shengli, Zhao Fangfang, et al. Optimization of high-degree extension field operations in SM9 based on base field representation[J]. Chinese Journal of Network and Information Security, 2026, 12(2): 83-89.
谢振杰, 刘胜利, 赵方方, 等. 基于基域表示的SM9高次扩域运算优化[J]. 网络与信息安全学报, 2026, 12(2): 83-89. DOI： 10.11959/j.issn.2096-109x.AQ25187.

Xie Zhenjie, Liu Shengli, Zhao Fangfang, et al. Optimization of high-degree extension field operations in SM9 based on base field representation[J]. Chinese Journal of Network and Information Security, 2026, 12(2): 83-89. DOI： 10.11959/j.issn.2096-109x.AQ25187.

摘要

国密算法SM9是我国自主研发的基于标识的密码体制，其性能瓶颈主要存在于底层的高次扩域运算。传统的塔式扩张法在实现高次扩域上的乘法、平方、求逆和Frobenius映射等运算时，存在多层逐级计算带来的冗余开销，限制了算法整体效率的提升。针对这一问题，提出一种基于基域表示的高次扩域运算优化方法。通过理论推导，建立了高次扩域上各项运算的基域表达式，将高次扩域运算转化为基域上的大整数运算，避免了塔式扩张过程的大量中间层级开销。理论分析表明，该方法通过分配律优化、合并同类项，使模运算量减少2/3以上，其他运算同步简化。测试结果显示，采用基域表示法的各项高次扩域运算速率达到塔式扩张法的2~3倍，内存开销峰值降低13.30%~63.60%。进一步地，在SM9数字签名、密钥交换、加密等7项算法中，性能提升幅度达95.39%~158.36%。基域表示法在保持算法数学等价性与安全性的前提下，能够显著提升SM9及其衍生密码方案的执行效率与资源利用率，且该方法具有通用性，可推广至SM9以外的高次扩域运算场景。

Abstract

The domestic cryptographic algorithm SM9

which is an independently innovated identity-based cryptographic system in China

was limited by performance bottlenecks in its underlying high-degree extension field operations. In the traditional tower extension method

operations such as multiplication

squaring

inversion

and Frobenius mapping on high-degree extension fields involved redundant computational overhead due to multi-level hierarchical processing

which constrained the overall efficiency improvement of the algorithm. To address this issue

a base field representation method was proposed for optimizing high-degree extension field operations. Through theoretical derivation

base field expressions for various operations on high-degree extension fields were established

transforming these operations directly into large integer arithmetic on the base field and thereby avoiding the substantial intermediate layer overhead inherent in the tower extension process. Theoretical analysis demonstrated that

through distributive law optimization and combination of like terms

modular operations were reduced by over two-thirds

with other operations simplified accordingly. Experimental results show that the proposed base field representation achieves a speedup of 2~3 times for various high-degree extension field operations compared to the tower extension method

with peak memory consumption reduced by 13.30%~63.60%. Furthermore

performance improvements of 95.39%~158.36% were observed in seven SM9 algorithms including digital signature

key exchange

and encryption. The base field representation method significantly enhances the execution efficiency and resource utilization of SM9 and its derived cryptographic schemes while preserving mathematical equivalence and security. Moreover

this method exhibits generality and can be extended to other high-degree extension field scenarios beyond SM9.

关键词

Keywords

references

全国信息安全标准化技术委员会 . 信息安全技术 SM9标识密码算法第1部分：总则 : GB/T 38635.1—2020 [S ] . 北京 : 中国标准出版社 , 2020 .

National Information Security Standardization Technical Committee . Information security technology—Identity-based cryptographic algorithms SM9—Part 1: General : GB/T 38635.1—2020 [S ] . Beijing : Standards Press of China , 2020 .

全国信息安全标准化技术委员会 . 信息安全技术 SM9标识密码算法第2部分：算法 : GB/T 38635.2—2020 [S ] . 北京 : 中国标准出版社 , 2020 .

National Information Security Standardization Technical Committee . Information security technology—Identity-based cryptographic algorithms SM9—Part 2: Algorithms : GB/T 38635.2—2020 [S ] . Beijing : Standards Press of China , 2020 .

谢振杰 , 尹小康 , 蔡瑞杰 , 等 . 基于国密算法SM9的可追踪环签名方案 [J ] . 通信学报 , 2025 , 46 ( 3 ): 199 - 211 .

Xie Z J , Yin X K , Cai R J , et al . Traceable ring signature scheme based on domestic cryptographic algorithm SM9 [J ] . Journal on Communications , 2025 , 46 ( 3 ): 199 - 211 .

蒲浪 , 林超 , 伍玮 , 等 . 基于国密SM9的公钥认证可搜索加密方案 [J ] . 软件学报 , 2025 , 36 ( 9 ): 4271 - 4284 .

Pu L , Lin C , Wu W , et al . Public-key authenticated encryption scheme with keyword search from Chinese cryptographic SM9 [J ] . Journal of Software , 2025 , 36 ( 9 ): 4271 - 4284 .

赖建昌 , 黄欣沂 , 何德彪 , 等 . 基于商用密码SM9的高效分层标识加密 [J ] . 中国科学(信息科学) , 2023 , 53 ( 5 ): 918 - 930 .

Lai J C , Huang X Y , He D B , et al . Anefficient hierarchical identity-based encryption based on SM9 [J ] . Science in China (Information Sciences) , 2023 , 53 ( 5 ): 918 - 930 .

李聪 , 梁俊凯 , 丁煜甲 , 等 . 基于SM9的分层标识广播内积函数加密 [J ] . 中国科学(信息科学) , 2024 , 54 ( 6 ): 1400 - 1418 .

Li C , Liang J K , Ding Y J , et al . Hierarchical identity-based broadcast inner product functional encryption based on SM9 [J ] . Science in China (Information Sciences) , 2024 , 54 ( 6 ): 1400 - 1418 .

赖建昌 , 黄欣沂 , 何德彪 , 等 . 基于SM9的CCA安全广播加密方案 [J ] . 软件学报 , 2023 , 34 ( 7 ): 3354 - 3364 .

Lai J C , Huang X Y , He D B , et al . CCA secure broadcast encryption based on SM9 [J ] . Journal of Software , 2023 , 34 ( 7 ): 3354 - 3364 .

崔岩 , 黄欣沂 , 赖建昌 , 等 . 基于SM9的匿名广播加密方案 [J ] . 信息安全学报 , 2023 , 8 ( 6 ): 15 - 27 .

Cui Y , Huang X Y , Lai J C , et al . Anonymous broadcast encryption based on SM9 [J ] . Journal of Cyber Security , 2023 , 8 ( 6 ): 15 - 27 .

Liu X H , Huang X Y , Cheng Z H , et al . Fault-tolerant identity-based encryption from SM9 [J ] . Science China Information Sciences , 2024 , 67 ( 2 ): 122101 .

李继国 , 方淳 . 基于SM9的指定验证者聚合签名方案 [J ] . 网络与信息安全学报 , 2024 , 10 ( 4 ): 63 - 71 .

Li J G , Fang C . Designated verifier aggregate signature scheme based on SM9 [J ] . Chinese Journal of Network and Information Security , 2024 , 10 ( 4 ): 63 - 71 .

胡芯忆 , 何德彪 , 彭聪 , 等 . 一种SM9算法R-ate对的快速实现方法 [J ] . 密码学报 , 2022 , 9 ( 5 ): 936 - 948 .

Hu X Y , He D B , Peng C , et al . A fast implementation of R-ate pairing in SM9 algorithm [J ] . Journal of Cryptologic Reseatch , 2022 , 9 ( 5 ): 936 - 948 .

Zhen P , Hu X B , Yu Y Y , et al . Research on the optimization computation of SM9 bilinear pairings [C ] // Proceedings of the 2nd International Conference on Communication and Information Systems . New York : ACM , 2017 : 256 - 261 .

Cheng X S , Zhang Y Z , Wang Y W . Simplification and hardware parallel design of frobenius mapping algorithm based on SM9 [C ] // Proceedings of the 3rd IEEE International Conference on Circuits, Systems and Devices (ICCSD) . Piscataway : IEEE Press , 2019 : 78 - 82 .

Karabina K . Squaring in cyclotomic subgroups [J ] . Mathematics of Computation , 2013 , 82 ( 281 ): 555 - 579 .

王江涛 , 樊荣 , 黄哲 . SM9中高次幂运算的快速实现方法 [J ] . 计算机工程 , 2023 , 49 ( 9 ): 118 - 124, 136 .

Wang J T , Fan R , Huang Z . Fast implementation of high power operation in SM9 [J ] . Computer Engineering , 2023 , 49 ( 9 ): 118 - 124, 136 .

谢振杰 , 刘奕明 , 蔡瑞杰 , 等 . 国密算法SM9的性能优化方法 [J ] . 计算机科学 , 2025 , 52 ( 6 ): 390 - 396 .

Xie Z J , Liu Y M , Cai R J , et al . Performance optimization method for domestic cryptographic algorithm SM9 [J ] . Computer Science , 2025 , 52 ( 6 ): 390 - 396 .

谢振杰 , 刘奕明 , 罗友强 , 等 . 国密算法SM9的计算性能改进方法 [J ] . 信息安全研究 , 2025 , 11 ( 1 ): 5 - 11 .

Xie Z J , Liu Y M , Luo Y Q , et al . The methods to improve the computational performance of domestic cryptographic algorithm SM9 [J ] . Journal of Information Securyity Research , 2025 , 11 ( 1 ): 5 - 11 .

Wu Y , Bai G Q , Wu X J . A karatsuba algorithm based accelerator for pairing computation [C ] // Proceedings of the 2019 IEEE International Conference on Electron Devices and Solid-State Circuits (EDSSC) . Piscataway : IEEE Press , 2019 : 1 - 3 .

Xie Y J , Wang B , Zhang L J , et al . A high-performance processor for optimal ate pairing computation over Barreto-Naehrig curves [J ] . IET Circuits , Devices & Systems, 2022 , 16 ( 5 ): 427 - 436 .

Guan Z . GmSSL-Cipher toolbox supporting domestic cryptographic algorithms SM2/SM3/SM4/SM9/SSL [EB ] . 2023 .

BASDDSA . Hggm-Python implementation of domestic cryptographic algorithm SM2/SM3/SM4/SM9/ZUC [EB ] . 2025 .

Python Software Foundation . Tracemalloc-Trace memory allocations [EB ] . 2025 .

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Efficient and fully simulated oblivious transfer protocol on elliptic curve

Partial blind signature scheme based on SM9 algorithm

Constant-round fair rational secret sharing scheme

Related Author

Jiashuo SONG

Zhenzhen LI

Haiyang DING

Zichen LI

Yao LYU

Jinpeng HOU

Chong NIE

Mang SU

Related Institution

China Center for Information Industry Development

School of Computer Science and Engineering, Nanjing University of Science and Technology

School of Information Management, Beijing Information Science ＆Technology University

College of Mathematics and Statistics,Guizhou University

Institute of Cryptography ＆Data Security, Guizhou University

⁰