Small Secret Key Attack on a Takagi's Variant of RSA

Kouichi ITOH  Noboru KUNIHIRO  Kaoru KUROSAWA  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E92-A    No.1    pp.33-41
Publication Date: 2009/01/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E92.A.33
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)
Category: Public Key Cryptography
lattice,  LLL,  trivariate polynomial,  RSA,  

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

For a variant of RSA with modulus N=prq and ed ≡ 1 (mod(p-1)(q-1)), we show that d is to be recovered if d < N(2-)/(r+1). (Note that φ(N) (p-1)(q-1).) Boneh-Durfee's result for the standard RSA is obtained as a special case for r=1. Technically, we develop a method for finding a small root of a trivariate polynomial equation f(x, y,z)=x(y-1)(z-1)+1 ≡ 0 (mod e) under the condition that yrz=N. Our result cannot be obtained from the generic method of Jochemsz-May.