A Hybrid Attack on Small Private Exponent RSA via Continued Fractions and Lattices

In this study, we propose a hybrid cryptanalytic technique targeting the RSA cryptosystem when instantiated with small private exponents. By integrating the continued fraction approach with Coppersmith’s lattice-based technique, we formulate a novel vulnerability framework. Utilizing an innovative relationship extracted from continued fraction convergents, we deduce an improved upper bound for the secret key: d<N1−α/3−γ/2. In this context, α:=logNe and γ:=logN|p+q−S|, where S serves as a known approximation of the prime sum p+q. As an extension of our preliminary conference proceedings, this paper supplies comprehensive proofs for all theoretical propositions, performs a comprehensive parameter sensitivity evaluation, and provides bounds for partial prime exposure scenarios. Empirical evaluations confirm the theoretical mechanics of our framework, demonstrating that it offers improved bounds in specific partial leakage scenarios compared to traditional lattice-only baselines.