Paper 2022/1241

Continued Fractions Applied to a Family of RSA-like Cryptosystems

George Teseleanu, IMAR
Paul Cotan, IMAR
Abstract

Let $N=pq$ be the product of two balanced prime numbers $p$ and $q$. Murru and Saettone presented in 2017 an interesting RSA-like cryptosystem that uses the key equation $ed - k (p^2+p+1)(q^2+q+1) = 1$, instead of the classical RSA key equation $ed - k (p-1)(q-1) = 1$. The authors claimed that their scheme is immune to Wiener's continued fraction attack. Unfortunately, Nitaj \emph{et. al.} developed exactly such an attack. In this paper, we introduce a family of RSA-like encryption schemes that uses the key equation $ed - k [(p^n-1)(q^n-1)]/[(p-1)(q-1)] = 1$, where $n>1$ is an integer. Then, we show that regardless of the choice of $n$, there exists an attack based on continued fractions that recovers the secret exponent.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. ISPEC 2022
Keywords
continued fractions Murru-Saettone cryptosystem small private key attack
Contact author(s)
george teseleanu @ yahoo com
paulcotan @ gmail com
History
2022-09-19: approved
2022-09-19: received
See all versions
Short URL
https://ia.cr/2022/1241
License
Creative Commons Attribution-NonCommercial-ShareAlike
CC BY-NC-SA

BibTeX

@misc{cryptoeprint:2022/1241,
      author = {George Teseleanu and Paul Cotan},
      title = {Continued Fractions Applied to a Family of RSA-like Cryptosystems},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1241},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/1241}},
      url = {https://eprint.iacr.org/2022/1241}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.