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

作者简介:

通讯作者:

中图分类号:

TP309

基金项目:

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


On the Progress of Lattice-based Cryptanalysis of RSA and its Variant Algorithms
Author:
Affiliation:

Fund Project:

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

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

    Abstract:

    The lattice-based cryptanalysis method using the algorithms solving hard lattice problems is used to analyze the security of public key cryptosystems, and has become one of the powerful mathematical tools to study the security of RSA and its variant algorithms. The key of this method is the construction of lattice basis. In 2006, Jochemsz and May proposed a general lattice basis construction strategy. However, the general strategy does not make full use of the algebraic structure of RSA algorithms. In recent years, the lattice-based cryptanalysis of RSA mostly focuse on the algebraic structure of specific algorithms, and use special lattice construction techniques to achieve better results. In this paper, we first introduce the lattice-based cryptanalysis method and the general lattice basis construction strategy, and abstract several common lattice construction techniques from previous works. Secondly, we give a survey of main progress on lattice-based cryptanalysis of standard RSA, which covers the following concerns: factoring with known bits, small secret exponent attacks and partial key exposure attacks. Then, we summarize the special algebraic structures of several commonly used RSA variant algorithms and their applicable lattice construction techniques. Finally, we classify and summarize the lattice-based cryptanalysis works of RSA, and prospect the future of the lattice-based cryptanalysis of RSA and the further work.

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

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

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • 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号