基于SM2签名的批验签高效实现方案

doi:10.3969/j.issn.1671-1122.2022.05.001

摘要/Abstract

摘要：

数字货币交易需要验证多个签名,使用批验签可以缩短计算时间、降低计算负载。文章提出一种高效的SM2批验签方案,利用半标量乘法计算第一签名值对应的椭圆曲线上的点乘运算结果,使用同余多项式和结式验证批量签名的正确性。文章所提方案对点乘算法、半标量点乘算法、多参数求逆算法和结式计算进行优化设计,并在恩智浦安全智能卡控制器N7121上进行实验。实验结果表明,在系统频率为96 MHz、CPU频率和密码协处理器频率分别为48 MHz和96 MHz、密码协处理器可访问内存空间为4 kB的情况下,文章所提方案同时验签7个SM2签名的模乘数小于13000次,运行时间为128.17 ms,与逐一验证单个签名的方案相比,文章所提方案的计算速度可提升2.1倍。

关键词: 数字签名, SM2, 批验签, 数字货币

Abstract:

Multiple signatures need to be verified in digital currency transactions, and batch verification can shorten the calculation time and reduce calculation load. This paper proposed an efficient SM2 batch verification scheme, which used semi-scalar multiplication to calculate the result of point multiplication on the elliptic curve corresponding to the first signature value, and used congruence polynomials and the resultant to verify the correctness of batch signatures. This scheme optimized the design of the point multiplication algorithm, the seminumeric point multiplication algorithm, the multi-parameter inversion algorithm and the resultant calculation, and was implemented on the NXP secure smart card controller N7121 platform. Experimental results show that when the system clock frequency is 96 MHz, the CPU clock frequency and the cryptoclock coprocessor frequency are 48 MHz and 96 MHz respectively, and the memory space that the crypto coprocessor can access is 4 kB, modular multiplications of 7 SM2 signatures at once is less than 13000. The running time is 128.17 ms. Compared with verifying individual signatures one by one, the calculation speed of the proposed scheme can be increased by 2.1 time.

Key words: digital signature, SM2, batch verification, digital currency

中图分类号:

TP309

李莉, 白鹭, 涂航, 张标. 基于SM2签名的批验签高效实现方案[J]. 信息网络安全, 2022, 22(5): 1-10.

LI Li, BAI Lu, TU Hang, ZHANG Biao. Eff icient Implementation Scheme of Batch Verif ication Based on SM2 Signatures[J]. Netinfo Security, 2022, 22(5): 1-10.

图/表 8

表1

表2

表3

表4

表5

图1

表6

表7

参考文献 18

[1]	WANG Hao, SONG Xiangfu, KE Junming, et al. Blockchain and Privacy Preserving Mechanisms in Cryptocurrency[J]. Netinfo Security, 2017, 17(7): 32-39.
	王皓, 宋祥福, 柯俊明, 等. 数字货币中的区块链及其隐私保护机制[J]. 信息网络安全, 2017, 17(7): 32-39.
[2]	WARRAN S, FAN Ziyang, BLAKE M. CBDC Technology Considerations[EB/OL]. (2021-11-09)[2021-12-27]. https://cn.weforum.org/reports/digital-currency-governance-consortium-white-paper-series/cbdc-tech-considerations#report-nav.
[3]	GM/T 32918. 2-2016 Information Security Technology-Public Key Cryptographic Algorithms SM2 Based on Elliptic Curves-Part 2: Digital Signature Algorithm[S]. Beijing: Chinese Encryption Administration, 2016.
	GM/T 32918. 2-2016 信息安全技术SM2椭圆曲线公钥密码算法第2部分:数字签名算法[S]. 北京: 国家密码局, 2016.
[4]	KOBLITZ N. Elliptic Curve Cryptosystems[J]. Mathematics of Computation, 1987, 48(177): 203-209. doi: 10.1090/S0025-5718-1987-0866109-5 URL
[5]	YAO Qian, LI Huifeng, WEN Xinxiang, et al. Digital Currency System: China, ZL201610179399.3[P]. 2017-10-03.
	姚前, 李会锋, 温信祥, 等. 数字货币系统:中国, ZL201610179399.3[P]. 2017-10-03.
[6]	FIAT A. Batch RSA[C]// Springer. Conference on the Theory and Application of Cryptology. Heidelberg: Springer, 1989: 175-185.
[7]	HARN L. Batch Verifying Multiple RSA Digital Signatures[J]. Electronics Letters, 1998, 34(12): 1219-1220. doi: 10.1049/el:19980833 URL
[8]	KARATI S, DAS A, ROYCHOWDHURY D, et al. Batch Verification of ECDSA Signatures[C]// Springer. International Conference on Cryptology in Africa. Heidelberg: Springer, 2012: 1-18.
[9]	KARATI S, DAS A. Faster Batch Verification of Standard ECDSA Signatures Using Summation Polynomials[C]// Springer. International Conference on Applied Cryptography and Network Security. Heidelberg: Springer, 2014: 438-456.
[10]	KITTUR A S, PAIS A R. A New Batch Verification Scheme for ECDSA* Signatures[J]. Sādhanā, 2019, 44(7): 1-12. doi: 10.1007/s12046-018-0983-y URL
[11]	BERNSTEIN D J, DOUMEN J, LANGE T, et al. Faster Batch Forgery Identification[C]// Springer. International Conference on Cryptology in India. Heidelberg: Springer, 2012: 454-473.
[12]	LIDL R, NIEDERREITER H. Introduction to Finite Fields and their Applications[M]. Cambridge: Cambridge University Press, 1994.
[13]	YANG Yi, HE Debiao, WANG Huaqun, et al. An Efficient Blockchain-Based Batch Verification Scheme for Vehicular Ad Hoc Networks[EB/OL]. (2019-12-27)[2021-11-20]. https://onlinelibrary.wiley.com/doi/abs/10.1002/ett.3857.
[14]	APOSTOL T M. Resultants of Cyclotomic Polynomials[J]. Proceedings of the American Mathematical Society, 1970, 24(3): 457-462. doi: 10.1090/S0002-9939-1970-0251010-X URL
[15]	SEMAEV I A. Summation Polynomials and the Discrete Logarithm Problem on Elliptic Curves[EB/OL]. (2004-02-05)[2021-12-06]. https://www.iacr.org/cryptodb/data/paper.php?pubkey=12007.
[16]	KARATI S, DAS A, CHOWDHURY D R. Using Randomizers for Batch Verification of ECDSA Signatures[EB/OL]. (2012-10-13)[2021-11-19]. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.300.7276.
[17]	BRAUER A. On Addition Chains[J]. Bulletin of American Mathematical Society, 1939, 45(10): 736-739. doi: 10.1090/S0002-9904-1939-07068-7 URL
[18]	KUDITHI T, SAKTHIVEL R. High-Performance ECC Processor Architecture Design for IoT Security Applications[J]. The Journal of Supercomputing, 2019, 75(1): 447-474. doi: 10.1007/s11227-018-02740-2 URL

符号	含义
a	SM2椭圆曲线参数
b	SM2椭圆曲线参数
G	SM2椭圆曲线的基点
n	基点G的阶
d_A	S_A的SM2私钥
P_A	S_A的SM2公钥
M	待签名的消息
ID_A	S_A的可辨识标识
ENTL_A	ID_A的位长
x_G	基点G的横坐标
y_G	基点G的纵坐标
x_A	公钥P_A的横坐标
y_A	公钥P_A的纵坐标
H₂₅₆	消息摘要长度为256位的哈希函数
H_v	消息摘要长度为v的哈希函数

点倍运算	运算量	点加运算	运算量
2A→A	1I+3M+8MA	A+A→A	1I+2M+6MA
2J→J	10M+13MA	J+J→J	14M+5MA
—	—	J+A→J	11M+7MA

t	v	l	计算量	存储空间/B
2	6	3	15M+1I	120
3	14	4	39M+1I	416
4	30	5	87M+1I	928
5	13	4	36M+1I	384
6	21	5	60M+1I	640
7	29	5	84M+1I	896
8	45	6	132M+1I	1408
9	61	6	180M+1I	1920

t	方案一	模乘	方案二	模乘
2	P₂	12M	—	—
3	P₄	71M	A₂,J₂,Res₄	25M
4	P₈	285M	A₄,J₂,Res₆	105M
5	P₁₆	1035M	A₄,J₄,Res₈	154M
6	—	—	A₈,J₄,Res₁₂	520M
7	—	—	A₈,J₈,Res₁₆	650M
8	—	—	A₁₆,J₈,Res₂₄	2547M
9	—	—	A₁₆,J₁₆,Res₃₂	2480M

t	加速点乘		半标量点乘		多参数求逆		判断批验签结果		总计算量	speedup_t
t	计算量	占比	计算量	占比	计算量	占比	计算量	占比	总计算量	speedup_t
2	5063M	0.792	1030M	0.161	285M	0.045	12M	0.002	6390M	1.548
3	5344M	0.740	1545M	0.214	309M	0.043	25M	0.003	7223M	2.055
4	5657M	0.692	2060M	0.252	357M	0.044	105M	0.013	8179M	2.419
5	7576M	0.714	2575M	0.243	306M	0.029	154M	0.015	10611M	2.331
6	7752M	0.663	3090M	0.264	330M	0.028	520M	0.044	11692M	2.539
7	8138M	0.638	3605M	0.283	354M	0.028	650M	0.051	12747M	2.717
8	8141M	0.525	4120M	0.265	402M	0.026	2547M	0.164	15210M	2.550
9	8764M	0.537	4635M	0.284	450M	0.028	2480M	0.152	16329M	2.727