Presentation 2007-11-21
Small Secret Key Attack on Takagi's Variant of RSA (Part1)
Noboru KUNIHIRO, Koichi ITOH, Kaoru KUROSAWA,
PDF Download Page PDF download Page Link
Abstract(in Japanese) (See Japanese page)
Abstract(in English) For a variant of RSA with modulus N = p^rq and ed≡1 mod(p-1)(q-1), we show that a secret exponent d can be recovered in polynomial time if d < N^<(7-2√<7>/3(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. Our algorithm is based on Coppersmith's approach and is heuristic. Technically, we develop a method of a finding small root of a trivariate modular equation f(x,y,z)=x(y-1)(z-1)+1=0(mod e) under the condition such that y^rz = N. Our result cannot be obtained from the generic method of Jochemsz-May. We also performed some numerical experiments. In any examples, resultant was not vanished and the secret key was recovered.
Keyword(in Japanese) (See Japanese page)
Keyword(in English) lattice / LLL / trivariate polynomial / RSA
Paper # ISEC2007-90,OIS2007-62
Date of Issue

Conference Information
Committee ISEC
Conference Date 2007/11/14(1days)
Place (in Japanese) (See Japanese page)
Place (in English)
Topics (in Japanese) (See Japanese page)
Topics (in English)
Chair
Vice Chair
Secretary
Assistant

Paper Information
Registration To Information Security (ISEC)
Language ENG
Title (in Japanese) (See Japanese page)
Sub Title (in Japanese) (See Japanese page)
Title (in English) Small Secret Key Attack on Takagi's Variant of RSA (Part1)
Sub Title (in English)
Keyword(1) lattice
Keyword(2) LLL
Keyword(3) trivariate polynomial
Keyword(4) RSA
1st Author's Name Noboru KUNIHIRO
1st Author's Affiliation The University of Electro-Communications()
2nd Author's Name Koichi ITOH
2nd Author's Affiliation Fujitsu Labs
3rd Author's Name Kaoru KUROSAWA
3rd Author's Affiliation Ibaraki University
Date 2007-11-21
Paper # ISEC2007-90,OIS2007-62
Volume (vol) vol.107
Number (no) 345
Page pp.pp.-
#Pages 8
Date of Issue