Factoring multi-power RSA moduli with primes sharing least or most significant bits

摘要

We study the factorization of a balanced multi-power RSA moduli N = prq when the unknown primes p and q share t least or most significant bits. We show that if t ≥ 1/(1+r)/(1/2) log p, then it is possible to compute the prime decomposition of N in polynomial time in logN. This result can be used to mount attacks against several cryptographic protocols that are based on the moduli N.