This paper proposes three new attacks. In the first attack we consider the class of the public exponents satisfying an equation e X-N Y ＋（ap^r＋ bq^r）Y = Z for suitably small positive integers a, b. Applying contin...This paper proposes three new attacks. In the first attack we consider the class of the public exponents satisfying an equation e X-N Y ＋（ap^r＋ bq^r）Y = Z for suitably small positive integers a, b. Applying continued fractions we show thatY/Xcan be recovered among the convergents of the continued fraction expansion of e/N. Moreover, we show that the number of such exponents is at least N^（2/（r＋1）-ε）where ε≥ 0 is arbitrarily small for large N. The second and third attacks works upon k RSA public keys（N_i, e_i） when there exist k relations of the form e_ix-N_iy_i ＋（ap_i^r ＋ bq_i^r ）y_i = z_i or of the form e_ix_i-N_iy ＋（ap_i^r ＋ bq_i^r ）y = z_i and the parameters x, x_i, y, y_i, z_i are suitably small in terms of the prime factors of the moduli. We apply the LLL algorithm, and show that our strategy enables us to simultaneously factor k prime power RSA moduli.展开更多
文摘This paper proposes three new attacks. In the first attack we consider the class of the public exponents satisfying an equation e X-N Y ＋（ap^r＋ bq^r）Y = Z for suitably small positive integers a, b. Applying continued fractions we show thatY/Xcan be recovered among the convergents of the continued fraction expansion of e/N. Moreover, we show that the number of such exponents is at least N^（2/（r＋1）-ε）where ε≥ 0 is arbitrarily small for large N. The second and third attacks works upon k RSA public keys（N_i, e_i） when there exist k relations of the form e_ix-N_iy_i ＋（ap_i^r ＋ bq_i^r ）y_i = z_i or of the form e_ix_i-N_iy ＋（ap_i^r ＋ bq_i^r ）y = z_i and the parameters x, x_i, y, y_i, z_i are suitably small in terms of the prime factors of the moduli. We apply the LLL algorithm, and show that our strategy enables us to simultaneously factor k prime power RSA moduli.
