Investigating Vulnerabilities in RSA-like Cryptosystems Through Lattice-based Attacks on Small Exponent Keys
Sou Kumagai, Shota Kanzawa, Samsul Huda, Yuta Kodera, Yasuyuki Nogami · 2024
RSA-like cryptosystems, based on the original RSA algorithm, are gaining attention as potential alternatives to traditional techniques. They offer better security, efficiency, flexibility, and compatibility in cryptography. However, recent studies have uncovered vulnerabilities in these variants, particularly to Wiener-type attacks, despite initial expectations of security comparable to RSA. In this paper, we further investigate the security vulnerabilities of a variant of this technique, namely the Murru-Saettone (MS) cryptosystem. Our investigation employs lattice-based attacks to exploit weaknesses in systems with small private keys. It demonstrates that if the private exponent is smaller than N1/4, where N is the product of two distinct balanced primes, the small exponent of the cryptosystem can be recovered.