A Continued Fraction-Hyperbola based Attack on RSA cryptosystem

Abstract

In this paper we present new arithmetical and algebraic results following the work of Babindamana and al. on hyperbolas and describe in the new results an approach to attacking a RSA-type modulus based on continued fractions, independent and not bounded by the size of the private key $d$ nor the public exponent $e$ compared to Wiener's attack. When successful, this attack is bounded by $\mathcal{O}\left(b\log {\alpha }_{j4}\log ({\alpha }_{i3}+{\alpha }_{j3})\right)$ with $b=10^y$, ${\alpha }_{i3}+{\alpha }_{j3}$ a non trivial factor of $n$ and ${\alpha }_{j4}$ such that $(n+1)/(n-1)={\alpha }_{i4}/{\alpha }_{j4}$. The primary goal of this attack is to find a point $X_{\alpha }=\left(-{\alpha }_3,{\alpha }_3+1\right)\in {\mathbb{Z}}_{\star }^2$ that satisfies $⟨X_{{\alpha }_3},P_3⟩=0$ from a convergent of $\frac{{\alpha }_{i4}}{{\alpha }_{j4}}+\delta$, with $P_3\in {\mathcal{B}}_n(x,y{)}_{{\mid }_{x\ge 4n}}$. We finally present some experimental examples. We believe these results constitute a new direction in RSA Cryptanalysis using continued fractions independently of parameters $e$ and $d$.