Attacks on Multi-Prime RSA with Small Prime Difference-猫眼课题宝

DOI：

10.1007/978-3-642-39059-3_4

发表时间：

2013-07

期刊：

影响因子：

通讯作者：

中科院分区：

其他

文献类型：

作者：

Hui Zhang;T. Takagi

考虑了模数n =p1p2…pr（r≥3）的多素数RSA （MPRSA）攻击。人们认为，对MPRSA的小私有指数攻击不如对RSA的有效（参见Hinek等人在SAC 2003上的工作），这意味着人们可以在MPRSA中使用比原始RSA更小的私有指数。然而，我们的攻击表明，当素数差Δ （Δ =pr−p1=Nγ, 0 <γ< 1/r，假设sep1<p2<⋯<pr）很小时，显著超出Hinek界的私有指数可能是不安全的。通过探索φ(N)与其上界之间的关系，我们提出的小私指数攻击可以充分利用小素数差带来的好处。结果表明，当δ为私有指数与baseN的指数，即d=Nδ时，MPRSA是不安全的。这个结果是最著名的小私有指数攻击的完美扩展。我们还提出了一种针对MPRSA的类费马因子攻击，它可以直接因子化模n时。这些结果超过了Bahig等人（ICICS 2012）的结果，并且在实践中被实验证明是有效的。

We consider some attacks on multi-prime RSA (MPRSA) with a modulusN=p1p2…pr(r≥ 3). It is believed that the small private exponent attack on the MPRSA is less effective than that on RSA (see Hinek et al.’s work at SAC 2003), which means that one can use a smaller private exponent in the MPRSA than that in the original RSA. However, our attacks show that private exponents which are significantly beyond Hinek’s bound may be insecure when the prime difference Δ (Δ =pr−p1=Nγ, 0 <γ< 1/r, supposep1<p2< ⋯ <pr) is small. By exploring the relation betweenφ(N) and its upper bound, our proposed small private exponent attack can make full use of the benefit brought by small prime difference. It is shown that the MPRSA is insecure when, whereδis the exponential of the private exponentdwith baseN, i.e.,d=Nδ. This result is a perfect extension of the best known small private exponent attack. We also present a Fermat-like factoring attack on the MPRSA which can directly factor the modulusNwhen. These results surpass those of Bahig et al. (ICICS 2012) and the attacks are experimentally proved effective in practice.

Attacks on Multi-Prime RSA with Small Prime Difference

文献摘要

相似文献