For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
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
Publication Date: 2009/01/01
Online ISSN: 1745-1337
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)>>
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.