Partial Key Exposure Attacks on CRT-RSA: General Improvement for the Exposed Least Significant Bits
Partial Key Exposure Attacks on CRT-RSA: General Improvement for the Exposed Least Significant Bits
复制标题
DOI：
10.1007/978-3-319-45871-7_3
复制
发表时间：
2016-09
期刊：
影响因子：
--
通讯作者：
Atsushi Takayasu;N. Kunihiro
中科院分区：
文献类型：
--
作者：
Atsushi Takayasu;N. Kunihiro
Blömer和May（Crypto 2003）使用Coppermith的基于格的方法来研究对CRT-RSA的部分密钥暴露攻击，即，用CRT指数的最低有效位对RSA进行攻击。该攻击适用于极小的公共指数，然而，Lu，Zhang和Lin（ACNS 2014），Takayasu和Kunihiro（ACNS 2015）提出了改进的攻击。这些攻击是为了。对于较小的（resp。更大）e，Lu等人的攻击。本文提出了一种改进的RSA攻击方法。事实上，我们的攻击完全改进了以前的攻击，因为我们的攻击需要的部分信息比以前的攻击少。我们解决了与Takayasu-Kunihiro相同的模方程，但是，我们的攻击可以找到更大的根。从技术的角度来看，虽然Takayasu-Kunihiro格遵循Jochemsz-May策略（Asiacrypt 2006），但我们仔细分析了底层多项式的代数结构，并提出了更好的格结构。
Blömer and May (Crypto 2003) used Coppersmith’s lattice based method to study partial key exposure attacks on CRT-RSA, i.e., an attack on RSA with the least significant bits of a CRT exponent. The attack works for an extremely small public exponente, however, improved attacks were proposed by Lu, Zhang, and Lin (ACNS 2014), Takayasu and Kunihiro (ACNS 2015). These attack works for. For a smaller (resp. larger)e, an attack of Lu et al. (resp. Takayasu-Kunihiro’s attack) requires less partial information to attack RSA.In this paper, we propose a further improved attack. Indeed, our attack completely improves previous attacks in the sense that our attack requires less partial information than previous attacks for all. We solve the same modular equation as Takayasu-Kunihiro, however, our attack can find larger roots. From the technical point of view, although the Takayasu-Kunihiro lattice follows the Jochemsz-May strategy (Asiacrypt 2006), we carefully analyze the algebraic structure of the underlying polynomial and propose better lattice constructions.