Paper 2023/1299

A New RSA Variant Based on Elliptic Curves

Maher Boudabra, Department of Computing and Mathematics, King Fahd University of Petroleum and Minerals, Saudi Arabia
Abderrahmane Nitaj, Normandie Univ, UNICAEN, CNRS, LMNO, 14000 Caen, France

We propose a new scheme based on ephemeral elliptic curves over the ring $\mathbb{Z}/n\mathbb{Z}$ where $n=pq$ is an RSA modulus with $p=u_p^2+v_p^2$, $q=u_q^2+v_q^2$, $u_p\equiv u_q\equiv 3\pmod 4$. The new scheme is a variant of both the RSA and the KMOV cryptosystems. The scheme can be used for both signature and encryption. We study the security of the new scheme and show that is immune against factorization attacks, discrete logarithm problem attacks, sum of two squares attacks, sum of four squares attacks, isomorphism attacks, and homomorphism attacks. Moreover, we show that the private exponents can be much smaller than the ordinary exponents for RSA and KMOV, which makes the decryption phase in the new scheme more efficient.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. Minor revision. MDPI Cryptography 2023
DOI cryptography7030037
Public key CryptographyRSAKMOVElliptic curvesContinued fractionsCoppersmith's method.
Contact author(s)
maher boudabra @ kfupm edu sa
abderrahmane nitaj @ unicaen fr
2023-09-02: approved
2023-08-31: received
See all versions
Short URL
No rights reserved


      author = {Maher Boudabra and Abderrahmane Nitaj},
      title = {A New RSA Variant Based on Elliptic Curves},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1299},
      year = {2023},
      doi = { cryptography7030037},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.