Improved Herrmann-May’s Attack with Merging Variables and Lower LLL Bound

Using side information to attack RSA is a practical method. In reality, it’s possible to intercept some bits of an unknown divisor p of a known composite integer N for us. Then we can utilize Coppersmith’s method to recover the whole p in polynomial time according to the work of Herrmann and May (Asiacrypt’08). In this paper, we analyze the idea of merging unknown bit blocks proposed by Herrmann and May in detail and indicate the cases where the blocks can be merged with a considerable reduction in the complexity of Herrmann-May’s attack. In fact, the complexity of this attack depends on the output quality of the LLL algorithm. For this, we purposely propose a lower upper bound of the length of LLL-reduced vectors using probabilistic statistical methods. To be specific, considering the \(\Vert v_i^*\Vert /\Vert v_{i+1}^*\Vert \) ’s as continuous random variables, we find that the middle \(\Vert v_i^*\Vert /\Vert v_{i+1}^*\Vert \) ’s after LLL-reduction are almost independently and identically distributed. Then we utilize the central limit theorem to present a lower LLL bound holding with probability close to 1. We have shown the advantages of merging variables and applying new bound by experiments. Finally, we combine these two points to propose the improved Herrmann-May’s attack.