Small Secret CRT-Exponent Attacks on Takagi's RSA

Naoyuki SHINOHARA  Tetsuya IZU  Noboru KUNIHIRO  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E94-A   No.1   pp.19-27
Publication Date: 2011/01/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E94.A.19
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)
Category: Public Key Cryptography
Keyword: 
CRT-exponent,  lattice,  LLL,  Takagi's RSA,  

Full Text: PDF(485.9KB)>>
Buy this Article




Summary: 
CRT-RSA is a variant of RSA, which uses integers dp = d mod (p-1) and dq = d mod (q-1) (CRT-exponents), where d, p, q are the secret keys of RSA. May proposed a method to obtain the secret key in polynomial time if a CRT-exponent is small, moreover Bleichenbacher and May improved this method. On the other hand, Takagi's RSA is a variant of CRT-RSA, whose public key N is of the form prq for a given positive integer r. In this paper, we extend the May's method and the Bleichenbacher-May's method to Takagi's RSA, and we show that we obtain p in polynomial time if by the extended May's method, and if by the extended Bleichenbacher-May's method, when dq is arbitrary small. If r=1, these upper bounds conform to May's and Bleichenbacher-May's results respectively. Moreover, we also show that the upper bound of pr increase with an increase in r. Since these attacks are heuristic algorithms, we provide several experiments which show that we can obtain the secret key in practice.