eth Root Attack on Dual Modulus RSA

Bety Hayat Susanti, Tsamara Khadijah Silim, Nadia Paramita Retno Adiati, Mareta Wahyu Ardyani

Abstract


The Rivest–Shamir–Adleman (RSA) algorithm relies on the presumed difficulty of integer factorization, making it vulnerable to certain attacks, particularly in the quantum era. One proposed variant, dual modulus RSA, is claimed to enhance resilience against specific cryptanalytic techniques. This study evaluates its security by applying an e^th-root attack using an advanced fraction method. The results demonstrate that the plaintext can be recovered without the private key, confirming that dual modulus RSA, like standard RSA, remains susceptible under particular conditions. Although dual modulus RSA incurs higher computational cost, the attack remains effective. These findings suggest that structural changes alone do not guarantee improved security and emphasize the need for rigorous cryptanalysis of RSA variants against established mathematical attacks.

Keywords


Dual Modulus RSA; eth Root Attack; Public Key Cryptanalysis

Full Text:

PDF

References


[M. A. Islam, M. A. Islam, N. Islam, and B. Shabnam, “A modified and secured RSA public key cryptosystem based on ‘n’ prime numbers,” J. Comput. Commun., vol. 6, no. 3, pp. 78–90, 2018. https://doi.org/10.4236/jcc.2018.63006.

A. Nitaj, M. R. Bin, K. Ariffin, N. Nur, H. Adenan, and N. A. Abu, “Classical attacks on a variant of the RSA cryptosystem,” Cryptology ePrint Archive, Paper 2021/1160, 2021. https://doi.org/10.1007/978-3-030-88238-9_8.

M. Cherkaoui-Semmouni, A. Nitaj, W. Susilo, and J. Tonien, “Cryptanalysis of RSA variants with primes sharing most significant bits,” in Proc. ISC’21, Lecture Notes in Computer Science, vol. 12912, 2021, pp. 42–53. https://doi.org/10.1007/978-3-030-91356-4_3.

H. M. Sun, M. E. Wu, W. C. Ting, and M. J. Hinek, “Dual RSA and its security analysis,” IEEE Trans. Inf. Theory, vol. 53, no. 8, pp. 2922–2933, Aug. 2007. https://doi.org/10.1109/TIT.2007.901248.

B. Hutagaol, M. A. Budiman, and H. Mawengkang, “Hybrid cryptosystems MRC-4 algorithm and RSA dual modulus to secure data,” in Proc. 2023 Int. Conf. Comput. Sci. Inf. Technol. (ICOSNIKOM), Medan, Indonesia, 2023, pp. 1–6.

A. Nitaj and M. Boudabra, “Improved cryptanalysis of the multi-power RSA cryptosystem variant,” in Progress in Cryptology – AFRICACRYPT 2023, vol. 14024, Cham, Switzerland: Springer, 2023, pp. 153–170.

L. Peng, L. Hu, Y. Lu, and M. Zhao, “Cryptanalysis of dual RSA,” Des. Codes Cryptogr., vol. 83, pp. 1–21, 2017.

K. R. Raghunandan, R. R. Dsouza, N. Rakshith, S. Shetty, and G. Aithal, “Analysis of an enhanced dual RSA algorithm using Pell’s equation to hide public key exponent and a fake modulus to avoid factorization attack,” in Adv. Artif. Intell. Data Eng. (AIDE), vol. 1343, Singapore: Springer, 2021, pp. 731–746.

B. Swami, R. Singh, and S. Choudhary, “Dual modulus RSA based on Jordan-totient function,” Procedia Technol., vol. 24, pp. 1581–1586, 2016. https://doi.org/10.1016/j.protcy.2016.05.143.

G. A. Zimbele and S. A. Demilew, “Hidden real modulus RSA cryptosystem,” Int. J. Comput., vol. 22, no. 2, pp. 238–247, 2023. https://doi.org/10.47839/ijc.22.2.3094.

Y.-S. Sien, C. W.-C. Chiou, and W.-C. Sun, “A factorization attack algorithm on RSA cryptosystem using fast searching algorithm,” J. Appl. Math. Comput., vol. 6, no. 4, pp. 390–404, 2022. https://doi.org/10.26855/jamc.2022.12.001.

Y. Y. Song, Cryptanalysis Attacks on RSA. Berlin, Germany: Springer, 2008.

M. Stamp and R. M. Low, Applied Cryptanalysis: Breaking Ciphers in the Real World. Hoboken, NJ, USA: Wiley, 2007.

M. Hinek, Cryptanalysis of RSA and Its Variants. Boca Raton, FL, USA: CRC Press, 2009.

I. H. Masri and B. H. Susanti, “Cryptanalysis on polynomial congruence-based public key with Chinese Remainder Theorem,” in Proc. 2023 IEEE Int. Conf. Cryptogr., Informatics, Cybersecurity (ICoCICs), 2023, pp. 159–164.

I. K. Y. Sucipta, B. H. Susanti, and S. S. Carita, “Cryptanalysis of the RSA cryptosystem based on n prime numbers,” in 2024 7th Int. Conf. Inf. Commun. Technol. (ICOIACT), Ishikawa, Japan, 2024, pp. 270–275. https://doi.org/10.1109/ICOIACT64819.2024.10912893.

D. A. Ferdianto, B. H. Susanti, and S. Rosdiana, “Common modulus attack on the elliptic curve-based RSA algorithm variant,” in 2024 7th Int. Conf. Inf. Commun. Technol. (ICOIACT), Ishikawa, Japan, 2024, pp. 101–106. https://doi.org/10.1109/ICOIACT64819.2024.10913331.

P. Q. Nguyen, “Public-key cryptanalysis,” in Recent Trends in Cryptography, Contemp. Math., vol. 477, pp. 67–119, 2009.

D. Zhang, H. Wang, S. Li, and B. Wang, “Progress in the prime factorization of large numbers,” J. Supercomput., vol. 80, pp. 11382–11400, 2024. https://doi.org/10.1007/s11227-023-05876-y.

A. C. Ramachandran, P. Ramachandran, and L. Velusamy, “Computing the eᵗʰ root of a number using a variant of the RSA algorithm (for even e’s),” U.S. Patent US8595349B2, Nov. 26, 2013.

Y. Wang, H. Zhang, and H. Wang, “Quantum algorithm for attacking RSA based on the eᵗʰ root,” J. Sichuan Univ. (Eng. Sci. Ed.), vol. 50, pp. 72–77, 2018.

A. J. Menezes, P. C. van Oorschot, and S. A. Vanstone, Handbook of Applied Cryptography, 1st ed. Boca Raton, FL, USA: CRC Press, 1996.

W. Stallings, Cryptography and Network Security: Principles and Practice, 8th ed. Upper Saddle River, NJ, USA: Pearson Education, 2023.

D. R. Stinson and M. Paterson, Cryptography: Theory and Practice, 4th ed. Boca Raton, FL, USA: Chapman & Hall/CRC, 2017. https://doi.org/10.1201/9781315282497.

A. Nitaj, Y. Kadri, M. T. Ahmed, and A. El Maazouz, “Security issues of novel RSA variant,” IEEE Access, vol. 10, pp. 13020–13032, 2022.




DOI: http://dx.doi.org/10.30829/zero.v9i1.24486

Refbacks

  • There are currently no refbacks.


Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

Publisher :
Department of Mathematics
Faculty of Science and Technology
Universitas Islam Negeri Sumatera Utara Medan
📱 WhatsApp:085270009767 (Admin Official)
SINTA 2 Google Scholar CrossRef Garuda DOAJ