Continued Fractions Applied to a Family of RSA-like Cryptosystems

George Teseleanu; Paul Cotan

Paper 2022/1241

Continued Fractions Applied to a Family of RSA-like Cryptosystems

George Teseleanu

, IMAR

Paul Cotan

, IMAR

Abstract

Let $N = p q$ 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 $e d - k (p^{2} + p + 1) (q^{2} + q + 1) = 1$ , instead of the classical RSA key equation $e d - 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 $e d - 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 , 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: 2023-07-03: last of 2 revisions; 2022-09-19: received; See all versions
Short URL: https://ia.cr/2022/1241
License: 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},
      url = {https://eprint.iacr.org/2022/1241}
}