Multi-scalar Multiplication Algorithm for Elliptic Curve Based on MBNS and Sliding Window

doi:10.3969/j.issn.1006-2475.2019.01.003

Abstract

Abstract: Scalar multiplication heavily determines the overall implementation efficiency of Elliptic Curve Cryptography(ECC), some elliptic curve cryptosystems of public keys require multi-scalar multiplication. Multi-base number system is very suitable for efficient computation of scalar multiplications of elliptic curves because of shorter representation length and less Hamming weight. In order to improve the efficiency of ECC, this paper proposes an efficient multi-scalar multiplication based on the existing scalar multiplication algorithm in binary fields and prime fields. This new algorithm is a combination of sliding window method and multi-base scalar multiplication algorithm. The experimental results show that the new algorithm costs less compared with Shamir’s trick and interleaving with NAF’s method. The new approach can effectively improve the efficiency of scalar multiplication algorithm, so that the scalar multiplication is more efficient. Compared to other algorithms, the new approach is improved about 7.9%~20.6%.

Key words: Elliptic Curve Cryptography(ECC), multi-scalar multiplication, point halving, MBNS, sliding window algorithm

CLC Number:

TP309

LI Yan-mei1, YIN Xin-chun1,2,SHAO Meng-li2. Multi-scalar Multiplication Algorithm for Elliptic Curve Based on MBNS and Sliding Window[J]. Computer and Modernization, doi: 10.3969/j.issn.1006-2475.2019.01.003.

References

［1］ MILLER V S. Uses of elliptic curve in cryptography［C］// Proceedings of the CRYPTO85. 1986:417-426.
［2］ KOBLITZ N. Elliptic curve cryptosystems［J］. Mathematics of Computation, 1987,48(177):203-209.
［3］ DIMITROV V, IMBERT L, MISHRA P K. Efficient and secure elliptic curve point multiplication using double base chains［C］// Proceedings of the 11th International Conference on the Theory and Application of Cryptology and Information Security. 2005,3788:59-78.
［4］ MISHRA P K, DIMITROV V. Efficient quintuple formulas for elliptic curves and efficient scalar multiplication using multibase number representation［C］// International Conference on Information Security. 2007,4779:390-406.
［5］罗琴灵,蒋朝惠. 一种高效的多基标量乘扩展算法［J］. 计算机技术与发展, 2015,25(5):95-98.
［6］刘铎,戴一奇. 计算椭圆曲线上多标量乘的快速算法［J］. 计算机学报, 2008,31(7):1131-1137.
［7］邬可可,黄国伟,孔令晶. 一种灵活的椭圆曲线密码并行化方法［J］. 计算机与现代化, 2018(2):71-75.
［8］邬可可,高月芳,闫立军. 一种抵御差分侧信道分析的椭圆曲线同构方法［J］. 计算机与现代化, 2017(10):105-110.
［9］李艳梅,殷新春. 一种基于多基表示的标量乘扩展算法［J］. 小型微型计算机系统, 2017,38(12):2699-2702.
［10］赖忠喜,张占军,陶东娅. 椭圆曲线中直接计算7P的方法及其应用［J］. 计算机应用, 2013,33(7):1870-1874.
［11］PUROHIT G N, RAWAT A S. Fast scalar multiplication in ECC using the multi-base number system［J］. International Journal of Computer Science Issues, 2011,8(1):131-137.
［12］殷新春,赵荣,侯洪祥,等. 基于折半运算的快速双基数标量乘算法［J］. 计算机应用, 2009,29(5):1285-1288.
［13］邓维勇. 椭圆曲线密码体制中标量乘法研究［D］. 昆明:昆明理工大学, 2012.
［14］赖忠喜,林君焕,张占军. 素数域GF(P)上椭圆曲线快速标量乘算法的研究［J］. 计算机工程与应用, 2015,51(4):100-104.
［15］IEEE. IEEE Standard Computer Dictionary A Compilation of IEEE Standard Computer Glossaries［M］. IEEE, 1990.
［16］CHEN T S, HUANG K H, CHUNG Y F. Digital multi-signature scheme based on the elliptic curve cryptosystem［J］. Journal of Computer Science and Technology, 2004,19(4):570-573.
［12］SOLINAS J A. Low-weight Binary Representation for Pairs of Integers［R］. Centre for Applied Cryptographic Research, University of Waterloo, Combinatorics and Optimization Research Report CORR 2001-41, 2001.
［18］HANKERSON D, MENEZES A J, VANSTONE S A. Guide to Elliptic Curve Cryptography［M］. Springer-Verlag, 2003.
［19］殷新春,张海灵,杨婷. 基于多基数系统的优化多标量乘快速算法［J］. 通信学报, 2010,31(S1):122-126.
［20］PUROHIT G N, RAWAT A S, KUMAR M. Elliptic curve point multiplication using MBNR and point halving［J］. International Journal of Advanced Networking and Applications, 2012,3(5):1329-1337.
［21］DOCHE C, IMBERT L. Extended double-base number system with applications to elliptic curve cryptography［C］// International Conference on Cryptology in India. 2006(4329):335-348.
［22］KNUDSEN E W. Elliptic scalar multiplication using point halving［C］// Proceedings of the 11th International Conference on the Theory and Application of Cryptology and Information Security. 1999,1716:134-149.

[1]	CAI Si-mu, WANG Li-bin. A Universally-composable Secure Non-interactive Commitment Scheme [J]. Computer and Modernization, 2024, 0(01): 6-12.
[2]	HAN Dong-song, SHA Le-tian, ZHAO Chuang-ye. Worm and Agent-based Attack Modeling for Industrial Control Systems [J]. Computer and Modernization, 2023, 0(10): 107-114.
[3]	YE Li-ming, CHEN Wei-wen. A Cascaded Insulator Defect Detection Model Combining Semantic Segmentation and Object Detection [J]. Computer and Modernization, 2023, 0(06): 82-88.
[4]	LIU Jun, YUAN Lin, FENG Zhi-shang, ZHANG Biao, LIU Chao. Efficient Healing Key Management Scheme for UAV Group [J]. Computer and Modernization, 2023, 0(06): 103-109.
[5]	ZHA Kai-jin, WANG Zhi-bo, HE Yue-shun, XU Hong-zhen. Survey on Blockchain Security Protection [J]. Computer and Modernization, 2023, 0(06): 110-117.
[6]	DENG Yin-juan, DU Hong-zhen, DOU Xiao-xia. Registered Users Public Key Searchable Encryption Scheme with Secure-channel Free [J]. Computer and Modernization, 2020, 0(09): 43-48.
[7]	DENG Ming-wei, OU Wei, YANG Jie. Safety Analysis of Three Classic Blockchain Consensus Mechanisms [J]. Computer and Modernization, 2020, 0(06): 34-.
[8]	ZHANG Xi, WANG Jian. A Public Integrity Auditing Scheme Based on Blind Signature for Shared Data in Cloud [J]. Computer and Modernization, 2020, 0(04): 60-.
[9]	WU Ke-he， CHEN Hong-xiang， LI Wei. Research on Beidou Secure Transport Protocol Based on SM9 Identity Password [J]. Computer and Modernization, 2020, 0(02): 41-.
[10]	ZHANG Yi, WANG Bo. Image Encryption Based on Fractional Rossler Chaotic Sequence [J]. Computer and Modernization, 2019, 0(12): 119-.
[11]	WEN Ting-ting, LI Hong-zhe. Elastic Load Balancing Algorithm for Cloud Computing Service [J]. Computer and Modernization, 2019, 0(10): 28-.
[12]	LI He-ting, FENG Ren-jun, CHEN Hai-yan, JING Dong-sheng. Intrusion Detection Based on Heterogeneous Convolutional Neural Network [J]. Computer and Modernization, 2019, 0(10): 117-.
[13]	ZHANG Su-ning, WANG Yue-juan, WU Shui-ming, JING Dong-sheng. Network Intrusion Data Clustering Algorithm Based on Krylov Subspace [J]. Computer and Modernization, 2019, 0(10): 121-.
[14]	SHANG Jing-wei1,2, JIANG Rong1,2, HU Xiao-han1,2, SHI Ming-yue1,2. Medical Big Data and Privacy Leakage [J]. Computer and Modernization, 2019, 0(07): 111-.
[15]	ZHANG Peng, ZHOU Liang. Trust-based Dynamic Multi-level Access Control Model [J]. Computer and Modernization, 2019, 0(07): 116-.