基于多离散对数问题的公钥密码的分析

doi:10.3969/j.issn.0372-2112.2018.01.030

电子学报 ›› 2018, Vol. 46 ›› Issue (1): 218-222.DOI: 10.3969/j.issn.0372-2112.2018.01.030

基于多离散对数问题的公钥密码的分析

苏盛辉^1,2,3, 孙国栋²

1. 南京航空航天大学计算机学院, 江苏南京 211106;
2. 北京工业大学计算机学院, 北京 100124;
3. 南京理工大学公共安全科技创新中心, 江苏南京 210094

收稿日期:2014-12-19 修回日期:2017-01-22 出版日期:2018-01-25
- 作者简介:
- 苏盛辉,博士,教授,博导,研究方向为计算复杂性理论、身份认证学、密码学和网络信息安全.REESSE1+非对称体制、JUNA单向散列函数与轻量级数字签名体制、JUOAN非对称密码体制首席发明人,MPP/ASPP/TLP三个新计算难题、渐近粒度归约方法AGR、身份认证学(Idology)主要提出者.E-mail:reesse@126.com;孙国栋,博士生,研究方向为非对称密码体制、非对称身份认证体制和网络信息安全.
- 基金资助:
- 国家863高技术研究发展计划 (No.2009AA01Z441）

Analysis of a Public-Key Cryptograph Based on Multi-Discrete Logarithm Problems

SU Sheng-hui^1,2,3, SUN Guo-dong²

1. College of Computers, Nanjing University of Aeronautics & Astronautics, Nanjing, Jiangsu 211106, China;
2. College of Computers, Beijing University of Technology, Beijing 100124, China;
3. Public Security Innovation Center, Nanjing University of Science & Technology, Nanjing, Jiangsu 210094, China

Received:2014-12-19 Revised:2017-01-22 Online:2018-01-25 Published:2018-01-25

摘要/Abstract

摘要： 本文对一个特定群生成元系中元素的阶数的选取做了讨论，对多离散对数问题和基于它的公钥加密方案做了分析.指出在原文所述情况下，多离散对数问题可转化为离散对数问题，从而，该问题存在亚指数时间解，并导致相关私钥在大多数情况下是亚指数时间不安全的.本文进一步指出，在几乎任何情况下，密文还原问题都可转化为离散对数问题，从而，它也存在亚指数时间解.所以，要把离散对数问题和ElGamal公钥密码改造成抗Shor量子算法攻击的，还需做更深入的、持久的探索.

关键词: 多离散对数问题, 公钥密码, 安全性, 量子算法, 亚指数时间解

Abstract: The paper discusses the selection of orders of elements in one generator set for a specified group,and analyzes multi-discrete logarithm problems (MDLP) and a public key encryption scheme based on the MDLP.The paper points out that under the circumstances described by the original paper,the MDLP may be transformed into a discrete logarithm problem,which manifests that there exists a sub-exponential time solution for the MDLP,and causes a related private key insecure in sub-exponential time in most cases.Further,in almost any case,a ciphertext inversion problem may be transformed into a discrete logorithm problem,which illustrates that there also exists a sub-exponential time solution to the ciphertext.Therefore,to convert a discrete logarithm and the ElGamal cryptosystem into those which are resistant to the Shor quantum alg.orithm attack,the people still need to make deeper and longer explorations.

Key words: multi-discrete logarithm problem, public key cryptograph, security, quantum algorithm, sub-exponential time solution

中图分类号:

TN918

苏盛辉, 孙国栋. 基于多离散对数问题的公钥密码的分析[J]. 电子学报, 2018, 46(1): 218-222.

SU Sheng-hui, SUN Guo-dong. Analysis of a Public-Key Cryptograph Based on Multi-Discrete Logarithm Problems[J]. Acta Electronica Sinica, 2018, 46(1): 218-222.

参考文献

[1] Shor P W.Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer[J].SIAM J.on Computing,1997,26(5):1484-1509.
[2] Grover L K.Quantum mechanics helps in searching for a needle in a Haystack[J].Physical Review Letters,1997,79(2):325-328.
[3] Rivest R L,Shamir A,Adleman L M.A method for obtaining digital signatures and public-key cryptosystems[J].Communications of the ACM,1978,21(2):120-126.
[4] ElGamal T.A public-key cryptosystem and a signature scheme based on discrete logarithms[J].IEEE Transactions on Information Theory,1985,31(4):469-472.
[5] 张文芳,王小敏,郭伟,等.基于椭圆曲线密码体制的高效虚拟企业跨域认证方案[J].电子学报,2014,42(6):1095-1102. ZHANG Wen-fang,WANG Xiao-min,GUO Wei,et al.An efficient inter-enterprise authentication scheme for VE based on the elliptic curve cryptosystem[J].Acta Electronica Sinica,2014,42(6):1095-1102.(in Chinese)
[6] 古春生,景征骏,于志敏,等.基于遍历矩阵的公钥加密方案的安全性分析[J].电子学报,2014,42(10):2081-2085. GU Chun-sheng,JING Zheng-jun,YU Zhi-min,et al.Security on public key encryption scheme based on ergodic matrice[J].Acta Electronica Sinica,2014,42(10):2081-2085.(in Chinese)
[7] Su S,Lü S.A public key cryptosystem based on three new provable problems[J].Theoretical Computer Science,2012,426-427:91-117.
[8] Su S,Lü S,Fan X.Asymptotic granularity reduction and its application[J].Theoretical Computer Science,2011,412(39):5374-5386.
[9] Su S,Lü S.REESSE1+ Reward Proof by Experiment A New Approach to Proof of P!=NP[DB/OL].Cornell University Library(http://arxiv.org/pdf/0908.0482/),2009-08-04(revised 2014-08-25).
[10] 付向群,鲍皖苏,史建红,等.基于多离散对数问题的公钥密码[J].电子与信息学报,2014,36(6):1423-1427. Fu Xiang-qun,Bao Wan-su,Shi Jian-hong,et al.Public-key cryptograph based on the multi-discrete logarithm problem[J].Journal of Electronics & Information Technology,2014,36(6):1423-1427.(in Chinese)
[11] Menezes A,Oorschot van P C,Vanstone S.Handbook of Applied Cryptography[M].London,UK:CRC Press,1996.
[12] Hungerford W T.Algebra[M].New York:Springer-Verlag,1998.
[13] Snaith P V.Groups,Rings and Galois Theory[M].Singapore:World Scientific Publishing,1998.

[1]	赵耿, 马英杰, 陈磊, 董有恒, 侯艳丽. 基于扰动时空混沌系统的动态S盒设计[J]. 电子学报, 2022, 50(8): 2037-2042.
[2]	胡文文, 周日贵. 基于d维单个量子态的半量子密钥分发方案[J]. 电子学报, 2022, 50(5): 1025-1032.
[3]	郑秋华, 胡程楠, 崔婷婷, 申延召, 曾英佩, 吴铤. 一种基于概率分析的DHR模型安全性分析方法[J]. 电子学报, 2021, 49(8): 1586-1598.
[4]	支婷, 刘颖, 周华春, 张宏科. 智慧标识网络服务机理研究进展及安全性分析[J]. 电子学报, 2021, 49(8): 1653-1664.
[5]	欧庆于, 罗芳, 吴晓平, 杨鹏. 基于电压毛刺故障扰动的分组密码安全性度量方法研究[J]. 电子学报, 2021, 49(3): 417-423.
[6]	汪榆淋, 窦家维. k-min问题安全多方计算方案及应用[J]. 电子学报, 2021, 49(11): 2256-2260.
[7]	魏铎, 高海英. 一种支持算术张成程序的密文策略属性加密方案[J]. 电子学报, 2020, 48(10): 1993-2002.
[8]	宋云. 基于GHZ态局域测量的量子秘密共享[J]. 电子学报, 2019, 47(7): 1443-1448.
[9]	杨曦, 罗平, 贾古丽. 基于社会学信任理论的软件可信性概念模型[J]. 电子学报, 2019, 47(11): 2344-2353.
[10]	李俊志, 关杰. 非线性反馈移存器型序列密码的完全性通用算法[J]. 电子学报, 2018, 46(9): 2075-2080.
[11]	李子臣, 张卷美, 杨亚涛, 张峰娟. 基于NTRU的全同态加密方案[J]. 电子学报, 2018, 46(4): 938-944.
[12]	吴涛, 景晓军. 一种强不可伪造无证书签名方案的密码学分析与改进[J]. 电子学报, 2018, 46(3): 602-606.
[13]	房丙午, 黄志球, 王勇, 李勇. 状态不可观测的信息物理融合系统运行时验证[J]. 电子学报, 2018, 46(12): 2824-2831.
[14]	房丙午, 黄志球, 王勇, 李勇. 基于混合贝叶斯网络的混合系统安全性分析方法[J]. 电子学报, 2017, 45(12): 2896-2902.
[15]	王鹏, 黄焱, 袁亚男, 都政, 安俊秀. 多尺度量子谐振子算法的收敛特性[J]. 电子学报, 2016, 44(8): 1988-1993.

基于多离散对数问题的公钥密码的分析

Analysis of a Public-Key Cryptograph Based on Multi-Discrete Logarithm Problems

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics