An Improved Attack on the RSA Variant Based on Cubic Pell Equation

Abstract

In this paper, we present a novel method to solve trivariate polynomial modular equations of the form x(y2+Ay+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 x3+fy3+f2z3−3fxyz≡1 (mod N), where f is a cubic nonresidue modulus N=pq. In these variants, the public exponent e and the private exponent d satisfy ed≡1 (mod ψ(N)) with ψ(N)=p2+p+1q2+q+1. Moreover, d can be written in the form d≡v0z0 (mod ψ(N)) with any z0 satisfying gcd(z0,ψ(N))=1. In this paper, we apply our method to attack the variants when d≡v0z0 (mod ψ(N)) and when |z0| and |v0| 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.

Keywords

• Coppersmith’s method
• lattice basis reduction
• RSA variants
• factorization