Cryptanalysis of the RSA variant based on cubic Pell equation

Abstract

RSA (Rivest-Shamir-Adleman) cryptosystem is the most popular asymmetric key cryptographic algorithm used in computer science and information security. Recently, an RSA-like cryptosystem was proposed using a novel product that arises from a cubic field connected to the cubic Pell equation. The relevant key equation is $ed = 1 mod (p^2+p+1)(q^2+q+1)$ with $N=pq$. This RSA variant is claimed to be robust against the Wiener’s attack and hence the bit-size of the private key could be shorter, namely $d < N^{1/4}$. In this paper, we explore the further security analysis and investigate the potential small private exponent attack. We show that such RSA variant is particularly vulnerable to the lattice-based method. To be specific, we can carry out the lattice-based small private exponent attack if $d < N^{2-√2}}$, which is less secure than the standard RSA. Furthermore, we conduct numerical experiments to verify the validity of the proposed attack.

Publication
Theoretical Computer Science, Available online 5 August 2021