Treffer: An Improved Attack on the RSA Variant Based on Cubic Pell Equation.

In this paper, we present a novel method to solve trivariate polynomial modular equations of the form x (y 2 + A y + B) + z ≡ 0   (mod   e). Our approach integrates Coppersmith's method with lattice basis reduction to efficiently solve the former equation. Several variants of RSA are based on the cubic Pell equation x 3 + f y 3 + f 2 z 3 − 3 f x y z ≡ 1   (mod   N) , where f is a cubic nonresidue modulus N = p q . In these variants, the public exponent e and the private exponent d satisfy e d ≡ 1   (mod   ψ (N)) with ψ (N) = p 2 + p + 1 q 2 + q + 1 . Moreover, d can be written in the form d ≡ v 0 z 0   (mod   ψ (N)) with any z 0 satisfying gcd (z 0 , ψ (N)) = 1 . In this paper, we apply our method to attack the variants when d ≡ v 0 z 0   (mod   ψ (N)) and when | z 0 | and | v 0 | are suitably small. We also show that our method significantly improves the bounds of the private exponents d of the previous attacks on the variants, particularly in the scenario of small private exponents and in the scenarios where partial information about the primes is available. [ABSTRACT FROM AUTHOR]