遍历矩阵密码体制的安全性

doi:10.11959/j.issn.1000-436x.2015128

Abstract

Abstract:

The security of the public-key cryptosystems based on ergodicmatrices over finite field was analysed.According to the public key,a system of linear equations for the forged secret key bits is obtained by inverse matrix elimination method.It is proved that the computational TEME problem is solvablein polynomial time and the ciphertext of the PZZ1 cryptosystem can be decrypted by the forged secret key.In some case the SEME problem can be reduced to discrete logarithm problem in polynomial time.If the key parameters are chosen improperly,then PZZ2 cryptosystem is based on discrete logarithm problem instead of NP hard problem.

Key words: ergodic matrix, public-key cryptography, computational complexity, finite field, algorithm

Hua-wei HUANG,Chang-wen PENG,Yun-yun QU,Chun-hua LI. Security of the cryptosystems based on ergodic matrices[J]. Journal on Communications, 2015, 36(8): 61-67.

References 14

[1]	DING J T . Multi-Variate Public Key Cryptosystems[M]. Berlin: Springer-VerlagPress, 2006.
[2]	MUKESH K S . Public key cryptography with matrices[A]. Proceedings of the IEEE Workshop on Information Assurance[C]. United States Military Academy, 2004. 146-152.
[3]	STICKEL E . A new method for exchanging secret keys[A]. Proc of the Third International Conference on Information Technology and Applications(ICITA05)[C]. 2005. 426-430.
[4]	SHPILRAIN V . Cryptanalysis of stickel’s key exchange scheme[A]. Computer Science in Russia 2008,LNCS 5010[C]. 2008. 283-288.
[5]	ZHAO Y , WANG L , ZHANG W . Information-exchange using the ergodic matrices in GF(2)[A]. Proc ACNS 2004[C]. Icisa Press, 2004. 388-397.
[6]	赵永皙，黄声烈，姜占华 , 等. GF(2k)上的遍历矩阵及其特性分析[J]. 小型微型计算机系统, 2005,26(12): 2135-2139. ZHAO Y Z , HUANG S L , JIANG Z H ,et al. Ergodic matrix over GF(2k)and its properties[J]. Mini-Micro Systems, 2005,26(12): 2135-2139.
[7]	赵永皙, 姜占华, 黄声烈 . 基于 F2 上遍历矩阵的 Shamir 三次传递协议的实现[J]. 小型微型计算机系统, 2006,27(6): 986-991. ZHAO Y Z , JIANG Z H , HUANG S L . Implementation of Shamir’s three pass protocol based on ergodic matrix over finite field[J]. MiniMicro Systems, 2006,27(6): 986-991.
[8]	赵永皙, 裴士辉, 王洪军 ,等. 利用有限域上的遍历矩阵构造动态加密器[J]. 小型微型计算机系统, 2007,28(11): 2010-2014. ZHAO Y Z , PEI S H , WANG H J ,et al. Using the ergodic matrices over finite field to construct the dynamic encryptor[J]. Mini-Micro Systems, 2007,28(11): 2010-2014.
[9]	PEI S H , ZHAO Y Z , ZHAO H W . Construct public key encryption scheme using ergodic matrices over GF(2)[A]. TAMC 2007[C]. Berlin,Springer-Verlag, 2007. 181-188.
[10]	PEI S H , ZHAO H W , ZHAO Y Z . Public key cryptography based on ergodic matrices over finite field[J]. Wuhan University Journal of Natural Sciences, 2006,11(6): 1525-1528.
[11]	裴士辉, 赵永皙, 赵宏伟 . 基于遍历矩阵的公钥加密方案[J]. 电子学报, 2010,38(8): 1908-1913. PEI S H , ZHAO Y Z , ZHAO H W . Public key encryption scheme based on the ergodic matrices[J]. Chinese Journal of Electronics, 2010,38(8): 1908-1913.
[12]	赵永皙, 赵博, 裴士辉 ,等. HFEM 公钥密码方案的设计与实现[J]. 通信学报, 2011,32(6): 24-31. ZHAO Y Z , ZHAO B , PEI S H ,et al. Design and implement on the HFEM public key scheme[J]. Journal on Communications, 2011,32(6): 24-31.
[13]	赵永皙, 赵博, 裴士辉 . 有限域上遍历矩阵的特性研究[J]. 数学学报, 2012,55(3): 457-468. ZHAO Y Z , ZHAO B , PEI S H . On the properties of the ergodic matrix over finite field[J]. ACTA Mathematica Sinica, 2012,55(3): 457-468.
[14]	LIDL R , NIEDERREITER H . Introduction to Finite Fields and Their Applications[M]. Cambridge: Cambridge University Press, 1986.

Metrics

Recommended 0

No Suggested Reading articles found!

[1]	Xiaoni DU, Xiangyu WANG, Lifang LIANG, Kaibin LI. Quantum cryptanalysis of lightweight block cipher Piccolo [J]. Journal on Communications, 2023, 44(6): 175-182.
[2]	Guang YANG, Zhaoyang WU, Min NIE, Xiaohong YAN, Fan JIANG. Research on PAPR reduction algorithm based on CWGAN-SLM for multi-wavelet OFDM system [J]. Journal on Communications, 2023, 44(4): 99-110.
[3]	Zhiyong LUO, Yu ZHANG, Qing WANG, Weiwei SONG. Study of SDN intrusion intent identification algorithm based on Bayesian attack graph [J]. Journal on Communications, 2023, 44(4): 216-225.
[4]	Huawei HUANG. Security analysis of public-key cryptosystems based on matrix action problem against quantum attack [J]. Journal on Communications, 2023, 44(3): 220-226.
[5]	Shufen ZHANG, Yanling DONG, Jingcheng XU, Haoshi WANG. AdaBoost algorithm based on target perturbation [J]. Journal on Communications, 2023, 44(2): 198-209.
[6]	Xiaoyun WANG, Xiaozhou ZHANG, Liang MA, Yajuan WANG, Mengting LOU, Tao JIANG, Jing JIN, Qixing WANG, Guangyi LIU. Research and optimization on the sensing algorithm for 6G integrated sensing and communication network [J]. Journal on Communications, 2023, 44(2): 219-230.
[7]	Shuai LIU, Jie GUAN, Bin HU, Sudong MA. Differential analysis of lightweight cipher algorithm ACE based on MILP [J]. Journal on Communications, 2023, 44(1): 39-48.
[8]	Guanxiong HA, Qiaowen JIA, Hang CHEN, Chunfu JIA. Data popularity-based encrypted deduplication scheme without third-party servers [J]. Journal on Communications, 2022, 43(8): 17-29.
[9]	Liangbo XIE, Yuyang LI, Yong WANG, Mu ZHOU, Wei NIE. Indoor RFID localization algorithm based on adaptive bat algorithm [J]. Journal on Communications, 2022, 43(8): 90-99.
[10]	Rong ZENG, Xiao HANG. Reconfigurable intelligent surface assist wireless channel estimation algorithm in Internet of vehicles environment [J]. Journal on Communications, 2022, 43(8): 142-150.
[11]	Manman LI, Shaozhen CHEN. Improved meet-in-the-middle attack on reduced-round Kiasu-BC algorithm [J]. Journal on Communications, 2022, 43(7): 41-48.
[12]	Hao ZENG, Wangqiang MU, Shunping YANG. High maneuvering target tracking ATPM-IMM algorithm [J]. Journal on Communications, 2022, 43(7): 93-101.
[13]	Damin ZHANG, Yi WANG, Chengcheng ZOU, Peiwen ZHAO, Linna ZHANG. Resource allocation strategies for improved mayfly algorithm in cognitive heterogeneous cellular network [J]. Journal on Communications, 2022, 43(6): 156-167.
[14]	Sifeng ZHU, Jianghao CAI, Zhengyi CHAI, Enlin SUN. Multi-objective optimal offloading decision for cloud-edge collaborative computing scenario in Internet of vehicles [J]. Journal on Communications, 2022, 43(6): 223-234.
[15]	Weiqiong WANG, Haojie XU, Meng CUI, Qiong XIE. Hybrid tabu search algorithm for excellent Boolean function [J]. Journal on Communications, 2022, 43(5): 133-143.

Security of the cryptosystems based on ergodic matrices

RichHTML

PDF

Knowledge

Cited

Abstract

Cite this article

share this article

References 14

Related Articles 15

Metrics

Recommended 0