检索结果-内蒙古大学图书馆

An optimal bound for factoring unbalanced RSA moduli by solving generalized implicit factorization problem

JOURNAL OF SUPERCOMPUTING 2025年第1期81卷 1-24页

作者： Zhang, Ran Bi, Jingguo Li, Lixiang Peng, Haipeng Beijing Univ Posts & Telecommun Sch Cyberspace Secur Beijing 100876 Peoples R China Beijing Univ Posts & Telecommun Informat Secur Ctr State Key Lab Networking & Switching Technol Beijing 100876 Peoples R China State Key Lab Cryptol POB 5159 Beijing 100878 Peoples R China

The integer factorization problem, concerning the product of two primes N = pq, has been a focal point for researchers since its rise to prominence with the RSA algorithm, a renowned public key scheme. It is well known that the integer factorization problem can be solved by the Number Field Sieve (NFS) algorithm in sub-exponential time, this challenge may also find resolution in polynomial time under certain conditions for the primes. In this paper, we revisit the problem of factoring RSA moduli with the implicit hint, where the implicit hint is the shared bits of primes. As for k RSA moduli, we present a novel implicit factorization approach applicable when the unknown multiples ap of the prime factors p share a certain number of most significant bits (MSBs) or least significant bits (LSBs). By drawing inspiration from addressing the Approximate Common Divisor problem (ACDP), we transform this problem into solving the small roots of k-1 trivariate polynomials. To compute these small roots, we employ Coppersmith's method to construct a lattice basis for the modular polynomials. We modify the lattice basis by introducing new variables, achieving an optimal bound in the MSB and LSB cases. Our attack breaks the RSA system and improves upon all previous attacks on such variants when the amount of the shared bits is sufficiently large. Concluding our paper, we meticulously validate the theoretical analysis results, with experimental data confirming the full practical feasibility of our attack on such an RSA variant system.

关键词： RSA system generalized implicit factorization problem Coppersmith's method LLL algorithm

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：