Cryptanalysis of Unbalanced RSA with Small CRT-Exponent

摘要

We present lattice-based attacks on RSA with prime factors p and q of unbalanced size. In our scenario, the factor q is smaller than N~β and the decryption exponent d is small modulo p - 1. We introduce two approaches that both use a modular bivariate polynomial equation with a small root. Extracting this root is in both methods equivalent to the factorization of the modulus N = pq. Applying a method of Coppersmith, one can construct from a bivariate modular equation a bivariate polynomial f(x,y) over Z that has the same small root. In our first method, we prove that one can extract the desired root of f(x,y) in polynomial time. This method works up to β < (3-5~(1/2))/2 ≈ 0.382. Our second method uses a heuristic to find the root. This method improves upon the first one by allowing larger values of d modulo p - 1 provided that β ≤ 0.23.