Extended partial key exposure attacks on RSA: Improvement up to full size decryption exponents
Extended partial key exposure attacks on RSA: Improvement up to full size decryption exponents
复制标题
DOI：
10.1016/j.tcs.2020.07.004
复制
发表时间：
2020-07
期刊：
影响因子：
--
通讯作者：
Kaichi Suzuki;Atsushi Takayasu;N. Kunihiro
中科院分区：
文献类型：
--
作者：
Kaichi Suzuki;Atsushi Takayasu;N. Kunihiro
使用基于格的 Coppersmith 方法对 RSA 的部分密钥暴露攻击进行了深入研究。 Ernst 等人（Eurocrypt'05）通过考虑三种攻击场景来研究该问题；（1）已知秘密指数 d 的最高有效位（MSB），（2）已知 d 的最低有效位（LSB），（3）已知 d 的 MSB 和 LSB。所提出的攻击很有价值，因为它们是处理全尺寸指数 e 的第一个结果。 Takayasu 和 Kunihiro（SAC'14，理论计算机科学'19）通过利用线性化技术，提出了当 d 足够小时（即，（1）的 d< N 0.5625 和（2）的 d< N 0.368）时对（1）和（2）的改进攻击。在本文中，我们扩展了 Takayasu-Kunihiro 的攻击并改进了 Ernst 等人针对 (3) 的攻击。特别是，我们的攻击包含 Takayasu-Kunihiro 对 (1) 和 (2) 的攻击，作为特殊情况，当给定的 LSB 和 MSB 的数量分别为零时。此外，与 Takayasu-Kunihiro 的攻击相反，我们对 Ernst 等人的攻击的改进并不限于小秘密指数，例如 d< N 0.5625。事实上，我们能够将 Ernst 等人的攻击改进到几乎达到全尺寸解密指数，即，即使 d 接近 N。从技术上讲，扩展并不简单。我们首先修改 Takayasu-Kunihiro 的格基矩阵（2），以便它兼容嵌入给定的 MSB。这种修改对于将 MSB 和 LSB 同时嵌入到矩阵中至关重要。
Partial key exposure attacks on RSA have been intensively studied by using lattice-based Coppersmith's methods. Ernst et al.(Eurocrypt'05) studied the problem by considering three attack scenarios;(1) the most significant bits (MSBs) of a secret exponent d known,(2) the least significant bits (LSBs) of d known,(3) both the MSBs and the LSBs of d known. The proposed attacks were valuable since they were the first results to handle full size exponents e. Takayasu and Kunihiro (SAC'14, Theoretical Computer Science'19) proposed improved attacks for (1) and (2) when d is sufficiently small, ie, d< N 0.5625 for (1) and d< N 0.368 for (2), by utilizing a linearization technique. In this paper, we extend Takayasu-Kunihiro's attacks and improve Ernst et al.'s attack for (3). In particular, our attack contains Takayasu-Kunihiro's attacks for (1) and (2) as special cases when the amount of given LSBs and MSBs are zero, respectively. Furthermore, as opposed to Takayasu-Kunihiro's attacks, our improvement against Ernst et al.'s attack is not limited to small secret exponents such as d< N 0.5625. Indeed, we are able to improve Ernst et al.'s attack almost up to full size decryption exponents, ie, even when d is close to N. Technically, the extension is not straightforward. We first modify Takayasu-Kunihiro's lattice basis matrix for (2), so that it is compatible to embed the given MSBs. The modification is crucial for embedding both the MSBs and the LSBs simultaneously to the matrix.