Progress of Lattice-based Cryptanalysis of RSA and Its Variant Algorithms
Author:
Affiliation:

Clc Number:

Fund Project:

  • Article
  • |
  • Figures
  • |
  • Metrics
  • |
  • Reference
  • |
  • Related
  • |
  • Cited by
  • |
  • Materials
  • |
  • Comments
    Abstract:

    Lattice-based cryptanalysis, an analysis method using the algorithms solving hard Lattice problems to analyze the security of public-key cryptosystems, has become one of the powerful mathematical tools for studying the security of the Rivest-Shamir-Adleman (RSA)-type cryptographic algorithms. The key point of this method is the construction of the Lattice basis. There exists a general strategy for Lattice basis construction. However, this general strategy fails to fully and flexibly utilize the algebraic structure of the RSA algorithm and its variants. In recent years, Lattice-based cryptanalysis of RSA-type algorithms mostly focuses on introducing special techniques of Lattice base construction on the basis of the general strategy. This study starts by outlining Lattice-based cryptanalysis and the general strategy for Lattice basis construction and summarizing several commonly used techniques of Lattice basis construction. Subsequently, the main achievements in Lattice-based cryptanalysis of the standard RSA algorithm are reviewed, and they involve factoring with known bits, small private exponent attacks, and partial key exposure attacks. Then, the special algebraic structures of several mainstream variants of the RSA algorithm and the techniques of Lattice basis construction applicable to these variants are summarized. Finally, the available work on Lattice-based cryptanalysis of the RSA algorithm and its variants is classified and summed up, and the prospects of the research and development of lattice-based cryptanalysis are presented.

    Reference
    Related
    Cited by
Get Citation

周永彬,姜子铭,王天宇,袁思蒙,许军,王鲲鹏,刘月君. RSA及其变体算法的格分析方法研究进展.软件学报,2023,34(9):4310-4335

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:December 01,2021
  • Revised:January 15,2022
  • Adopted:
  • Online: May 24,2022
  • Published:
You are the firstVisitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063