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

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

通信学报 ›› 2015, Vol. 36 ›› Issue (8): 61-67.doi: 10.11959/j.issn.1000-436x.2015128

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

黄华伟¹,彭长文²,瞿云云¹,李春华³

¹ 贵州师范大学数学与计算机科学学院,贵州贵阳 550001
² 贵州师范学院数学与计算机科学学院,贵州贵阳 550018
³ 华东交通大学理学院，江西南昌 330013

出版日期:2015-08-25 发布日期:2015-08-25
基金资助:
国家自然科学基金资助项目;国家自然科学基金资助项目;贵州省科学技术基金资助项目;贵州省科学技术基金资助项目;贵州师范大学博士基金资助项目

Security of the cryptosystems based on ergodic matrices

Hua-wei HUANG¹,Chang-wen PENG²,Yun-yun QU¹,Chun-hua LI³

¹ School of Mathematics and Computer Science,Guizhou Normal University,Guiyang 550001,China
² School of Mathematics and Computer Sciences,Guizhou Normal College,Guiyang 550018,China
³ School of Science,East China Jiaotong University,Nanchang 330013,China

Online:2015-08-25 Published:2015-08-25
Supported by:
The National Natural Science Foundation of China;The National Natural Science Foundation of China;The Doctorial Foundation of Guizhou Normal University

摘要/Abstract

摘要：

分析了基于有限域遍历矩阵的公钥密码体制的安全性。根据公钥，采取逆矩阵消去方法得到伪造私钥的线性方程组。从而证明了计算性TEME问题是多项式时间可解的，利用伪造私钥即可破解PZZ1密码体制的密文。在一些情况下，SEME 问题在多项式时间内可归约为离散对数问题，若密钥参数选取不当，PZZ2 密码体制是基于离散对数问题的，并不基于NP困难问题。

关键词: 遍历矩阵, 公钥密码, 计算复杂度, 有限域, 算法

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

黄华伟,彭长文,瞿云云,李春华. 遍历矩阵密码体制的安全性[J]. 通信学报, 2015, 36(8): 61-67.

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.

参考文献 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.

[1]	杜小妮, 王香玉, 梁丽芳, 李锴彬. 轻量级分组密码Piccolo的量子密码分析[J]. 通信学报, 2023, 44(6): 175-182.
[2]	鲁蔚锋, 李宁, 徐佳, 徐力杰, 徐建. 多接入边缘计算中相关性任务的联合调度算法[J]. 通信学报, 2023, 44(4): 87-98.
[3]	杨光, 吴朝阳, 聂敏, 闫晓红, 江帆. 基于CWGAN-SLM的多小波OFDM系统峰均比抑制算法研究[J]. 通信学报, 2023, 44(4): 99-110.
[4]	罗智勇, 张玉, 王青, 宋伟伟. 基于贝叶斯攻击图的SDN入侵意图识别算法的研究[J]. 通信学报, 2023, 44(4): 216-225.
[5]	黄华伟. 基于矩阵作用问题的公钥密码体制抗量子攻击安全性分析[J]. 通信学报, 2023, 44(3): 220-226.
[6]	张淑芬, 董燕灵, 徐精诚, 王豪石. 基于目标扰动的AdaBoost算法[J]. 通信学报, 2023, 44(2): 198-209.
[7]	王晓云, 张小舟, 马良, 王亚娟, 楼梦婷, 姜涛, 金婧, 王启星, 刘光毅. 6G通信感知一体化网络的感知算法研究与优化[J]. 通信学报, 2023, 44(2): 219-230.
[8]	刘帅, 关杰, 胡斌, 马宿东. 基于MILP的轻量级密码算法ACE的差分分析[J]. 通信学报, 2023, 44(1): 39-48.
[9]	哈冠雄, 贾巧雯, 陈杭, 贾春福. 无第三方服务器的基于数据流行度的加密去重方案[J]. 通信学报, 2022, 43(8): 17-29.
[10]	谢良波, 李宇洋, 王勇, 周牧, 聂伟. 基于自适应蝙蝠算法的室内RFID定位算法[J]. 通信学报, 2022, 43(8): 90-99.
[11]	曾嵘, 杭潇. 车联网环境下可重构智能反射面辅助无线信道估计算法[J]. 通信学报, 2022, 43(8): 142-150.
[12]	李曼曼, 陈少真. 改进的减轮Kiasu-BC算法的中间相遇攻击[J]. 通信学报, 2022, 43(7): 41-48.
[13]	王子园, 杜瑞忠. 边缘环境下基于无证书公钥密码的数据完整性审计方案[J]. 通信学报, 2022, 43(7): 62-72.
[14]	曾浩, 母王强, 杨顺平. 高机动目标跟踪ATPM-IMM算法[J]. 通信学报, 2022, 43(7): 93-101.
[15]	朱思峰, 蔡江昊, 柴争义, 孙恩林. 车联网云边协同计算场景下的多目标优化卸载决策[J]. 通信学报, 2022, 43(6): 223-234.

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

Security of the cryptosystems based on ergodic matrices

在线阅读

PDF下载

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献 14

相关文章 15

Metrics

推荐阅读 0