Improved RC4 algorithm based on elliptic curve

doi:10.11772/j.issn.1001-9081.2018122459

Journal of Computer Applications ›› 2019, Vol. 39 ›› Issue (8): 2339-2345.DOI: 10.11772/j.issn.1001-9081.2018122459

• Cyber security • Previous Articles Next Articles

Improved RC4 algorithm based on elliptic curve

CHEN Hong, LIU Yumeng, XIAO Chenglong, GUO Pengfei, XIAO Zhenjiu

School of Software, Liaoning Technical University, Huludao Liaoning 125105, China

Received:2018-12-12 Revised:2019-04-06 Online:2019-08-10 Published:2019-04-17
Supported by:
This work is partially supported by the National Natural Science Foundation of China (61404069), the Science and Technology Research Project of Liaoning Provincial Department of Education (LJ2017QL032).

基于椭圆曲线的改进RC4算法

陈虹, 刘雨朦, 肖成龙, 郭鹏飞, 肖振久

辽宁工程技术大学软件学院, 辽宁葫芦岛 125105

通讯作者: 刘雨朦
作者简介:陈虹(1967-),女,辽宁阜新人,副教授,硕士,CCF会员,主要研究方向:网络安全、信息安全;刘雨朦(1994-),女,辽宁沈阳人,硕士研究生,主要研究方向:网络安全、信息安全;肖成龙(1984-),男,湖南株洲人,副教授,博士,主要研究方向:软硬件协同设计、高层次综合、可扩展处理器;郭鹏飞(1981-),男,辽宁朝阳人,副教授,博士,主要研究方向:图像处理、算法优化;肖振久(1968-),男,内蒙宁城人,副教授,硕士,主要研究方向:信息安全。
基金资助:
国家自然科学基金资助项目（61404069）；辽宁省教育厅科学技术研究项目（LJ2017QL032）。

Abstract

Abstract: For the problem that the Rivest Cipher 4 (RC4) algorithm has invariant weak key, the randomness of the key stream sequence is not high and the initial state of the algorithm can be cracked, an improved RC4 algorithm based on elliptic curve was proposed. In the algorithm, the initial key was generated by using elliptic curve, Hash function and pseudo-random number generator, and a nonlinear transformation was performed under the action of the S-box and the pointer to finally generate a key stream sequence with high randomness. The randomness test carried out by National Institute of Standards and Technology (NIST) shows that the frequency test, run test and Maurer are 0.13893, 0.13081, and 0.232050 respectively higher than those of the original RC4 algorithm, which can effectively prevent the generation of invariant weak keys and resist the "sentence" attack. The initial key is a uniformly distributed random number without deviation, which can effectively resist the distinguishing attack. The elliptic curve and Hash function have one-way irreversibility, the pseudo-random number generator has high password strength, the initial key guess is difficult to assign and is not easy to crack, which can resist the state guessing attack. Theoretical and experimental results show that the improved RC4 algorithm is more random and safe than the original RC4 algorithm.

Key words: Rivest Cipher 4 (RC4) algorithm, key stream sequence, elliptic curve, Hash function, randomness

摘要： 针对流密码（RC4）算法存在不变性弱密钥、密钥流序列随机性不高和算法初始状态可以被破解等问题，提出一种基于椭圆曲线的RC4改进算法。该算法利用椭圆曲线、哈希函数和伪随机数产生器生成初始密钥，在S盒和指针的作用下进行非线性变换最终生成具有高随机性的密钥流序列。美国国家标准与技术研究院（NIST）随机性测试结果表明，改进算法的频率检验、游程检验和Maurer指标比原RC4算法分别高出0.13893，0.13081和0.232050，能有效防止不变性弱密钥的产生，抵抗"受戒礼"攻击；初始密钥是一个分布均匀的随机数，不存在偏差，能够有效抵御区分攻击；椭圆曲线、哈希函数具有单向不可逆性，伪随机数产生器具有高密码强度，初始密钥猜测赋值困难，不易破解，能够抵抗状态猜测攻击。理论和实验结果表明改进RC4算法的随机性和安全性高于原RC4算法。

关键词: 流密码(RC4)算法, 密钥流序列, 椭圆曲线, 哈希函数, 随机性

CLC Number:

CHEN Hong, LIU Yumeng, XIAO Chenglong, GUO Pengfei, XIAO Zhenjiu. Improved RC4 algorithm based on elliptic curve[J]. Journal of Computer Applications, 2019, 39(8): 2339-2345.

陈虹, 刘雨朦, 肖成龙, 郭鹏飞, 肖振久. 基于椭圆曲线的改进RC4算法[J]. 计算机应用, 2019, 39(8): 2339-2345.

References

[1] FINNEY H. An RC4 cycle that can't happen[J]. Post. in Sci. Crypt.,1994:246.
[2] KNUDSEN L R, MEIER W, PRENEEL B, et al. Analysis methods for (alleged) RC4[C]//Proceedings of the 1998 International Conference on the Theory and Application of Cryptology and Information Security, LNCS 1514. Berlin:Springer, 1998:327-341.
[3] FLUHRER S R, McGREW D A. Statistical analysis of the alleged RC4 keystream generator[C]//Proceedings of the 2000 International Workshop on Fast Software Encryption, LNCS 1978. Berlin:Springer, 2000:19-30.
[4] PAUL S, PRENEEL B. A new weakness in the RC4 key stream generator and an approach to improve the security of the cipher[C]//Proceedings of the 2004 International Workshop on Fast Software Encryption, LNCS 3017. Berlin:Springer, 2004:245-259.
[5] MIYAJI A, SUKEGAWA M. New analysis based on correlations of RC4 PRGA with nonzero-bit differences[J]. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 2010, E93-A(6):1066-1077.
[6] 常亚琴.对流密码RC4的区分攻击[J].计算机工程,2011,37(3):119-120,123. (CHANG Y Q. Distinguishing attack on stream cipher RC4[J]. Computer Engineering, 2011, 37(3):119-120, 123.)
[7] HOCH J J, SHAMIR A. Fault analysis of stream ciphers[C]//Proceedings of the 2004 International Workshop on Cryptographic Hardware and Embedded Systems, LNCS 3156. Berlin:Springer, 2004:240-253.
[8] FLUHRER S, MANTIN I, SHAMIR A. Weakness in the key scheduling algorithm of RC4[C]//Proceedings of the 2001 International Workshop on Selected Areas in Cryptography, LNCS 2259. Berlin:Springer, 2001:1-24.
[9] MANTIN I. Analysis of the stream cipher RC4[D/OL]. Weizmann Institute of Science, 2001[2018-10-23]. http://www.wisdom.weizmann.ac.il/itsik/RC4/Papers/Mantin1.zip.
[10] AKGVN M, KAVAK P, DEMIRCI H. New results on the key scheduling algorithm of RC4[C]//Proceedings of the 2008 International Conference on Cryptology in India, LNCS 5365. Berlin:Springer, 2008:40-52.
[11] MANTIN I. Bar-Minzva attack:breaking SSL with 13-year old RC4 weakness[N]. Blackhat, 2015-03-22.
[12] 苑超,徐蜜雪,斯雪明.对不同种子密钥长度的RC4算法的明文恢复攻击[J].计算机应用,2018,38(2):370-373. (YUAN C, XU M X, SI X M. Plaintext recovery attack on RC4 with different length of seed key[J]. Journal of Computer Applications, 2018, 38(2):370-373.)
[13] 胡亮,迟令,袁巍,等.RC4算法的密码分析与改进[J].吉林大学学报(理学版),2012,50(3):511-516. (HU L, CHI L, YUAN W, et al. Cryptanalysis and improvements of RC4 algorithm[J]. Journal of Jilin University (Science Edition), 2012, 50(3):511-516.)
[14] 陈立,邓成良,肖慧娟.基于RC4的混沌改进算法及其性能分析[J].科学技术与工程,2010,10(26):6449-6452,6458. (CHEN L, DENG C L, XIAO H J. An algorithm improved by chaos based on RC4 and its performance analysis[J]. Science Technology and Engineering, 2010, 10(26):6449-6452, 6458.)
[15] ZOLTAK B. VMPC oneway function and stream cipher[C]//Proceedings of the 2004 International Workshop on Fast Software Encryption, LNCS 3017. Berlin:Springer, 2004:210-225.
[16] TSUNOO Y, SAITO T, KUBO H, et al. The most efficient distinguishing attack on VMPC and RC4A[J]. Estream Project, 2005:1-12.
[17] 侯整风,孟毛广,朱晓玲,等. RC4流密码算法的分析与改进[J].计算机工程与应用,2015,51(24):97-101. (HOU Z F, MENG M G, ZHU X L, et al. Analysis and improvement of RC4 stream cipher algorithm[J]. Computer Engineering and Applications, 2015, 51(24):97-101.)
[18] 孟毛广.RC4流密码算法的研究与改进[D].合肥:合肥工业大学,2014:9-12. (MENG M G. Research and improvement of RC4 stream cipher algorithm[D]. Hefei:Hefei University of Technology, 2014:9-12.)
[19] 田松,李宝,王鲲鹏.椭圆曲线离散对数问题的研究进展[J].密码学报,2015,2(2):177-188. (TIAN S, LI B, WANG K P. On the progress of elliptic curve discrete logarithm problem[J]. Journal of Cryptologic Research, 2015, 2(2):177-188.)
[20] 张小红,郭焰辉.基于椭圆曲线密码的RFID系统安全认证协议研究[J].信息网络安全,2018,18(10):51-61. (ZHANG X H, GUO Y H. Research on RFID system security authentication protocol based on elliptic curve cryptography[J]. Netinfo Security, 2018, 18(10):51-61.)
[21] 巫光福,曾宪文,刘娟,等.基于纠错码的Hash函数的设计与分析[J].信息网络安全,2018,18(1):67-72. (WU G F, ZENG X W, LIU J, et al. Design and analysis of hash function based on error correcting code[J]. Netinfo Security, 2018, 18(1):67-72.)
[22] BARKER E, BARKER W, BURR W, et al. Recommendation for Key Management-Part 1:General, SP 800-57[R]. Gaithersburg, MD:National Institute of Standards & Technology, 2007:1-142.
[23] 翟高寿,刘晨,向勇.基于内核函数监控的Linux系统防护方法的研究与实现[J].信息网络安全,2018,18(3):26-38. (ZHAI G S, LIU C, XIANG Y. Study and implementation of systematic protection by monitoring abnormal invocation of Linux kernel functions[J]. Netinfo Security, 2018, 18(3):26-38.)
[24] KIM S, UMENO K, HASEGAWA A. Corrections of the NIST statistical test suite for randomness[EB/OL].[2018-10-10]. http://www.docin.com/p-1036631337.html.

Improved RC4 algorithm based on elliptic curve

基于椭圆曲线的改进RC4算法

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

[1]	SHI Zhicai, WANG Yihan, ZHANG Xiaomei, CHEN Shanshan, CHEN Jiwei. Provable radio frequency identification authentication protocol with scalability [J]. Journal of Computer Applications, 2019, 39(3): 774-778.
[2]	LIU Xindong, XU Shuishuai, CHEN Jianhua. Authentication scheme for smart grid communication based on elliptic curve cryptography [J]. Journal of Computer Applications, 2019, 39(3): 779-783.
[3]	QIN Pingle, LI Qi, ZENG Jianchao, ZHANG Na, SONG Yulong. Image retrieval algorithm for pulmonary nodules based on multi-scale dense network [J]. Journal of Computer Applications, 2019, 39(2): 392-397.
[4]	LI Jianxun, MA Meiling, GUO Jianhua, YAN Jun. False trend time series detection based on randomness analysis [J]. Journal of Computer Applications, 2019, 39(10): 2955-2959.
[5]	XU Hailin, LU Yang. Efficient bilinear-pairing-free certificate-based encryption scheme with keyword search [J]. Journal of Computer Applications, 2018, 38(2): 379-385.
[6]	YANG Xingchun, XU Chunxiang, LI Chaorong. ECC-based RFID authentication protocol enabling tag ownership transfer [J]. Journal of Computer Applications, 2017, 37(8): 2275-2280.
[7]	LI Yun, CHEN Pangsen, SUN Shanlin. Security analysis and implementation for wireless local area network access protocol via near field communication authentication [J]. Journal of Computer Applications, 2016, 36(5): 1236-1245.
[8]	XU Hailin, CHEN Ying, LU Yang. Efficient certificate-based proxy re-encryption scheme without bilinear pairings [J]. Journal of Computer Applications, 2016, 36(5): 1250-1256.
[9]	TAO Yuan, ZHOU Xi, MA Yupeng, ZHAO Fan. Mobile mutual authentication protocol based on Hash function [J]. Journal of Computer Applications, 2016, 36(3): 657-660.
[10]	XU Shengwei, CHEN Cheng, WANG Rongrong. Improved differential fault attack on scalar multiplication algorithm in elliptic curve cryptosystem [J]. Journal of Computer Applications, 2016, 36(12): 3328-3332.
[11]	HAN Guoliang, SHENG Maojia, BAO Congxiao, LI Xing. Stateless communication mechanism between an IPv4 network and the IPv6 Internet [J]. Journal of Computer Applications, 2015, 35(8): 2113-2117.
[12]	ZHANG Xidong, TONG Weiming, WANG Tiecheng, JIN Xianji. Cipher texts generation method in elliptic curve cryptography based on plaintext length [J]. Journal of Computer Applications, 2015, 35(10): 2863-2866.
[13]	YE Xiang XU Zhan HU Xiang LIU Dan. Low-cost mutual authenticate and encrypt scheme for active RIFD system [J]. Journal of Computer Applications, 2014, 34(2): 456-460.
[14]	FENG Jie LAN Caihui XIE Borong. ID-based proxy re-signature scheme with strong unforgeability [J]. Journal of Computer Applications, 2014, 34(11): 3291-3294.
[15]	WANG Yi DU Weizhang. Security analysis and improvement of certificateless signature scheme without bilinear pairing [J]. Journal of Computer Applications, 2013, 33(08): 2250-2252.