The invention in 1978 of the first practical asymmetric cryptosystem known as RSA was a breakthrough within the long history of secret communications. Since its inception, the RSA cryptosystem has become embedded in millions of digital applications with the objectives of ensuring confidentiality, integrity, authenticity, and disallowing repudiation. However, the generation of the RSA modulus, $N=pq$ which requires p and q to be random primes, may accidentally entail the choice of a special type of prime called a near-square prime. This structure of N may be used unknowingly en masse in real-world applications since no current cryptographic implementation prevents its generation. In this study, we show that use of this type of prime will potentially lead to total destruction of RSA. We present three cases of near-square primes used as RSA primes, set in the form of (i) $N=pq=(a^m-r_a)(b^m-r_b)$; (ii) $N=pq=(a^m+r_a)(b^m-r_b)$; and (iii) $N=pq=(a^m-r_a)(b^m+r_b)$. Although (ii) and (iii) are quite similar, p and q must be within the same size range of n-bits, which results in different conditions for both cases. We formulate attacks using three different algorithms to better understand their feasibility. We also provide an efficient countermeasure that it is recommended is adopted by current cryptographic libraries with RSA implementation.

The Rivest–Shamir–Adleman (RSA) cryptosystem remains one of the most widely used public-key mechanisms, with its security depending on the computational difficulty of factoring a large composite modulus $ N $ generated from two primes. Previous studies have shown that RSA becomes vulnerable when its prime factors follow special algebraic structures or when partial information about their least significant bits (LSBs) is exposed. Earlier work demonstrated that primes close to perfect powers allow efficient reconstruction of the modulus when several LSBs of both primes are known. In this paper, we extended this line of research by examining three additional near-square prime structures in which the primes are slightly different, either positively or negatively shifted from their base-power forms. For each structure, we obtained analytical bounds that relate the difference to the square-root proximity of the modulus, and we presented polynomial-time algorithms that recover the prime factors when only a small number of their LSBs are leaked. Numerical experiments confirmed the practicality of the proposed methods. Our results broaden the class of RSA moduli susceptible to LSB-based partial key-exposure attacks and highlight the importance of strengthened key-generation strategies to avoid such structured primes.