Generalized Framework to Attack RSA with Special Exposed Bits of the Private Key

Shixiong WANG  Longjiang QU  Chao LI  Shaojing FU  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E100-A   No.10   pp.2113-2122
Publication Date: 2017/10/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E100.A.2113
Type of Manuscript: PAPER
Category: Cryptography and Information Security
RSA,  partial key exposure attack,  lattice,  LLL algorithm,  Coppersmith's method,  unravelled linearization,  

Full Text: PDF(1MB)
>>Buy this Article

In this paper, we study partial key exposure attacks on RSA where the number of unexposed blocks of the private key is greater than or equal to one. This situation, called generalized framework of partial key exposure attack, was first shown by Sarkar [22] in 2011. Under a certain condition for the values of exposed bits, we present a new attack which needs fewer exposed bits and thus improves the result in [22]. Our work is a generalization of [28], and the approach is based on Coppersmith's method and the technique of unravelled linearization.