Eff icient Implementation Scheme of Batch Verif ication Based on SM2 Signatures

doi:10.3969/j.issn.1671-1122.2022.05.001

Abstract

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

CLC Number:

TP309

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.

Figures/Tables 8

References 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