RSA及其变体算法的格分析方法研究进展
作者:
作者单位:

作者简介:

周永彬(1973-),男,博士,教授,博士生导师,CCF高级会员,主要研究领域为网络与信息安全理论及技术.;姜子铭(1995-),女,博士生,主要研究领域为格加密,格分析.;王天宇(1992-),男,博士生,主要研究领域为格分析,格密码.;袁思蒙(1994-),女,硕士生,主要研究领域为RSA及其变体算法的格分析.;许军(1982-),男,博士,副研究员,主要研究领域为公钥密码分析,计算数论.;王鲲鹏(1971-),男,博士,研究员,博士生导师,主要研究领域为密码理论与技术,密码协议理论与技术.;刘月君(1994-),女,博士,主要研究领域为格密码,公钥密码分析.

通讯作者:

刘月君,E-mail:liuyuejun@njust.edu.cn

中图分类号:

基金项目:

国家自然科学基金(U1936209, 61632020, 62002353, 61872442); 北京市自然科学基金(4192067); 信工所攀登计划(E0Z0251112)


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

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    格分析是一种利用格困难问题的求解算法分析公钥密码安全性的分析方法, 是研究RSA类密码算法安全性的有力数学工具之一. 格分析的关键在于构造格基, 虽然目前已有通用简洁的格基构造策略, 然而, 这种通用方法无法充分、灵活地利用RSA及其变体的代数结构. 近年来, RSA类算法的格分析工作大多在通用策略的基础上引入特殊格基构造技巧. 首先介绍了格分析方法以及通用格基构造策略, 并总结提炼了几种常用格基构造技巧; 其次, 回顾了标准RSA算法格分析的主要成果, 即模数分解攻击、小解密指数攻击以及部分私钥泄漏攻击; 然后, 总结了几种主流RSA变体算法的特殊代数结构, 及其适用的特殊格基构造技巧; 最后, 对现有RSA及其变体算法的格分析工作进行了分类总结, 并展望了格分析方法的研究与发展方向.

    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.

    参考文献
    相似文献
    引证文献
引用本文

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

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2021-12-01
  • 最后修改日期:2022-01-15
  • 录用日期:
  • 在线发布日期: 2022-05-24
  • 出版日期:
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号