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

Kouichi ITOH  Noboru KUNIHIRO  Kaoru KUROSAWA 

Publication
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
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)
Category: Public Key Cryptography
Keyword: 
lattice,  LLL,  trivariate polynomial,  RSA, 

Full Text: PDF(293KB)

Summary: 
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.