Implicit-Key Attack on the RSA Cryptosystem

摘要

In this paper, we address the security evaluation issue of the RSA cryptosystem with implicitly related private keys. We formulate the attack scenario and propose a novel implicit-key attack using the lattice-based method. When given public information (N_1, e_1), (N_2, e_2) and the amount of shared bits of the private keys d_1 and d_2, one can conduct the implicit-key attack to factor N_1, N_2 in polynomial time under a certain condition. We show that the RSA cryptosystem is more insecure when taking the implicitly related keys into consideration. The experimental results are provided to verify the validity of our proposed attack.