New Method for Factoring RSA Moduli with Implicit Hint
Ryuichi Sakai, Masao Kasahara · IEICE Technical Report; IEICE Tech. Rep. · 2014
This paper presents a new method for factoring two RSA moduli N1 = p1q1 and N2 = p2q2 with an implicit hint, p1 � p2 (mod 2 t ). We show that the new method can factor N1 and N2 with much smaller hint compared with the conventional methods. I. INTRODUCTION In 2009, May and Ritzenhofen proposed an efficient method for factoring two RSA moduli N1 = p1q1 and N2 = p2q2 with an implicit hint, p1 � p2 (mod 2 t ) and showed the bound of the method that enables to succeed to factor the numbers(1). Their bound is t > 2(� + 1) where � is the bit length of q1 and q2. This bound was improved to t > 2� by Kurosawa and Ueda in 2013 and they confirmed their bound by the several experimental results(2). In this paper, we propose a new method for factoring two RSA moduli with the same implicit hint. With our proposed method, we can improve the bound to t � 2� l where l is larger than 10.