Welcome to the resource topic for 2025/380
Title:
A New Generalized Attack on RSA-like Cryptosystems
Authors: Michel SECK, Oumar Niang, Djiby Sow
Abstract:Rivest, Shamir, and Adleman published the RSA cryptosystem in 1978, which has been widely used over the last four decades. The security of RSA is based on the difficulty of factoring large integers N = pq, where p and q are prime numbers. The public exponent e and the private exponent d are related by the equation ed - k(p-1)(q-1) = 1. Recently, Cotan and Te{\c{s}}eleanu (NordSec 2023) introduced a variant of RSA, where the public exponent e and the private exponent d satisfy the equation ed - k(p^n-1)(q^n-1) = 1 for some positive integer n. In this paper, we study the general equation eu - (p^n - 1)(q^n - 1)v = w with positive integers u and v, and w\in \mathbb{Z}. We show that, given the public parameters N and e, one can recover u and v and factor the modulus N in polynomial time by combining continued fractions with Coppersmith’s algorithm which relies on lattice reduction techniques, under specific conditions on u, v, and w. Furthermore, we show that if the private exponent d in an RSA-like cryptosystem is either small or too large, then N can be factored in polynomial time. This attack applies to the standard RSA cryptosystem.
ePrint: https://eprint.iacr.org/2025/380
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .