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

• 学术论文 • 上一篇    下一篇

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

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

  1. 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-hui1,2,3, SUN Guo-dong2   

  1. 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

摘要: 本文对一个特定群生成元系中元素的阶数的选取做了讨论,对多离散对数问题和基于它的公钥加密方案做了分析.指出在原文所述情况下,多离散对数问题可转化为离散对数问题,从而,该问题存在亚指数时间解,并导致相关私钥在大多数情况下是亚指数时间不安全的.本文进一步指出,在几乎任何情况下,密文还原问题都可转化为离散对数问题,从而,它也存在亚指数时间解.所以,要把离散对数问题和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

中图分类号: