一种基于维数缩减的单变元 Coppersmith 算法

RSA 是最为经典的公钥密码体制之一, 在实际使用中, RSA 系统有明文被截获的可能. 针对部分 RSA 明文信息泄露的情况, Coppersmith 算法被广泛应用于 RSA 分析中, 其主要思想是利用 LLL 算法求解一个单变元模方程, 如果成功求解方程, 那么全部明文将会被恢复. 本文主要从三个方面对基于小根问题的单变元 Coppersmith 算法进行了改进. 首先根据 Nguyen 等人的工作, 我们可以获得随机格的 LLL 约减基首向量模长的较为精确的估计. 本文利用上述估计获得了一个平均意义上的可能成功求解方程所需的较低维数, 并以此维数为起点, 逐次增加 e 维进行约化, 直...

Full description

Saved in:
Bibliographic Details
Published in:Journal of Cryptologic Research 2023-01, Vol.10 (5), p.897
Main Authors: Chun-Zhi, ZHAO, Jin-Zheng, CAO, Qing-Feng, CHENG, 赵春智, 曹金政, 程庆丰
Format: Article
Language:Chinese
Subjects:
Algorithms
Computer systems
Cryptography
Reduction
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:RSA 是最为经典的公钥密码体制之一, 在实际使用中, RSA 系统有明文被截获的可能. 针对部分 RSA 明文信息泄露的情况, Coppersmith 算法被广泛应用于 RSA 分析中, 其主要思想是利用 LLL 算法求解一个单变元模方程, 如果成功求解方程, 那么全部明文将会被恢复. 本文主要从三个方面对基于小根问题的单变元 Coppersmith 算法进行了改进. 首先根据 Nguyen 等人的工作, 我们可以获得随机格的 LLL 约减基首向量模长的较为精确的估计. 本文利用上述估计获得了一个平均意义上的可能成功求解方程所需的较低维数, 并以此维数为起点, 逐次增加 e 维进行约化, 直至成功求解方程. 其次, 考虑到 Coppersmith 格严格意义上不是随机格, 如果将 Nguyen 等人工作直接应用到 Coppersmith 格上, 结果可能会有误差. 因此, 本文通过引入概率统计的方法获得了 LLL 算法在 Coppersmith 格上约化效果的新估计, 优化了起始维数. 最后, 本文采取了利用已知的未知明文比特位数对原来的未知量进行变量代换的技巧, 降低了算法的求解复杂度. 实验表明, 本文提出的I-Coppersmith 算法能较大幅度地提高小根问题的求解效率, 算法的运行时间减少约 50%.
ISSN:2097-4116
DOI:10.13868/j.cnki.jcr.000640