Skip to main navigation menu Skip to main content Skip to site footer

Vol. 33 No. 69 (2024)
July-September 2024: Open Science at the Service of Engineering

Papers

Systematic Mapping Study on Fast Factorization Using Parallel or Distributed Processing Applied to Cryptanalysis

Published 2024-09-30

Supporting Agencies
Universidad del Cauca
  • Jhon-Alejandro Melo
    • ,
  • Siler Amador-Donado
    • ,
  • César-Jesús Pardo-Calvache

Jhon-Alejandro Melo
Universidad del Cauca

Siler Amador-Donado
Universidad del Cauca

César-Jesús Pardo-Calvache
Universidad del Cauca

Abstract

Cryptography is one of the branches of research within computer security and cybersecurity, it provides security to the stored information and travels between devices. Cryptanalysis, in turn, studies the weaknesses within cryptography, thus allowing improving constants about cryptographic algorithms. Currently there are several algorithms that allow to keep information secure, one of them is RSA (Rivest, Shamir and Adleman), which is used in digital certificates implemented in some communication protocols. However, there is no algorithm capable of deciphering that type of algorithms yet; therefore, the objective of this study is to support other researchers in the area of cryptanalysis. This rapid factorization study using
parallel or distributed processing contains 6 research questions that allow us to deepen the use of this type of processing to speed up the execution times of the algorithms. The results made it possible to show that by using this type of processing, factoring time can be reduced.

Keywords

Cryptanalysis, distributed processing, factoring, parallel processing

PDF

References

      Ponemon Institute, Global Encryption Trends Study: The data is in the cloud, but who’s in control? 2022. https://www.entrust.com/es/resources/reports/global-encryption-trends-study
      E. Suescún-Monsalve, J.-C. Sampaio-do-Prado-Leite, C.-J. Pardo-Calvache, “Semi-Automatic Mapping Technique Using Snowballing to Support Massive Literature Searches in Software Engineering,” Revista Facultad de Ingeniería, vol. 31, no. 60, e14189, May 2022, https://doi.org/10.19053/01211129.v31.n60.2022.14189
      K. Petersen, H. Flensburg, R. Feldt, M. Mattsson, S. Mujtaba, Systematic Mapping Studies in Software Engineering, 2008.
      B. Kitchenham, S. M. Charters, Guidelines for performing Systematic Literature Reviews in Software Engineering, 2007.
      D. Budgen, M. Turner, P. Brereton, B. Kitchenham, Using Mapping Studies in Software Engineering, 2008. https://www.ebse.org.uk
      E. Nicolás, P. Paredes, C. E. Orozco, C. Pardo, “Análisis del estado del arte acerca de la (in)felicidad en las comunidades de desarrollo de software ágil,” RISTI - Revista Iberica de Sistemas e Tecnologias de Informacao, vol. 57, pp. 425-437, 2023.
      Z. Li and W. Gasarch, An Empirical Comparison of the Quadratic Sieve Factoring Algorithm and the Pollard Rho Factoring Algorithm, 2021. https://doi.org/10.48550/arXiv.2111.02967
      C. Bouillaguet, P. Zimmermann, Parallel Structured Gaussian Elimination for the Number Field Sieve, 2021.
      H. M. Bahig, H. M. Bahig, Y. Kotb, “Fermat factorization using a multi-core system,” International Journal of Advanced Computer Science and Applications, vol. 11, no. 4, pp. 323-330, 2020. https://doi.org/10.14569/IJACSA.2020.0110444
      J. V. Monaco, M. M. Vindiola, “Factoring Integers with a Brain-Inspired Computer,” IEEE Transactions on Circuits and Systems I: Regular Papers, vol. 65, no. 3, pp. 1051-1062, 2018. https://doi.org/10.1109/TCSI.2017.2771533
      L. T. Yang, Y. Huang, J. Feng, Q. Pan, C. Zhu, “An improved parallel block Lanczos algorithm over GF(2) for integer factorization,” Information Sciences, vol. 379, no. 2, pp. 257-273, 2017. https://doi.org/10.1016/j.ins.2016.09.052
      B. Sengupta, A. Das, “Use of SIMD-based data parallelism to speed up sieving in integerfactoring algorithms,” Appl Math Comput, vol. 293, pp. 204-217, 2017. https://doi.org/10.1016/j.amc.2016.08.019
      E. J. Vuicik, D. Šešok, S. Ramanauskaitė, “Efficiency of RSA Key Factorization by Open-Source Libraries and Distributed System Architecture,” Baltic Journal of Modern Computing, vol. 5, no. 3, pp. 269-274, 2017. https://doi.org/10.22364/bjmc.2017.5.3.02
      V. Shende, G. Sudi, M. Kulkarni, “Fast cryptanalysis of RSA encrypted data using a combination of mathematical and brute force attack in distributed computing environment,” in IEEE International Conference on Power, Control, Signals and Instrumentation Engineering (ICPCSI), 2017, pp. 2446-2449. https://doi.org/10.1109/ICPCSI.2017.8392156
      D. Breitenbacher, I. Homoliak, J. Jaros, P. Hanacek, “Impact of optimization and parallelism on factorization speed of SIQS,” in 20th World Multi-Conference on Systemics, Cybernetics and Informatics, 2016, pp. 55-62.
      H. Yu, G. Bai, “Strategy of Relations Collection in Factoring RSA Modulus,” Lecture Notes in Computer Science, vol. 9543, pp. 199-211, 2016. https://doi.org/10.1007/978-3-319-29814-6_16
      S. Daoud, I. Gad, “A parallel line sieve for the GNFS Algorithm,” International Journal of Advanced Computer Science and Applications, vol. 5, no. 7, pp. 178-185, 2014. https://doi.org/10.14569/ijacsa.2014.050727
      B. Sengupta, A. Das, “SIMD-based implementations of sieving in integer-factoring algorithms,”Lecture Notes in Computer Science, vol. 8204, pp. 40-55, 2013. https://doi.org/10.1007/978-3-642-41224-0_4
      L. T. Yang, L. Xu, S. S. Yeo, S. Hussain, “An integrated parallel GNFS algorithm for integer factorization based on Linbox Montgomery block Lanczos method over GF(2),” Computers and Mathematics with Applications, vol. 60, no. 2, pp. 338-346, 2010. https://doi.org/10.1016/j.camwa.2010.01.020
      U. Meyer-Bäse, G. Botella, E. Castillo, A. García, “Nios II hardware acceleration of the epsilon quadratic sieve algorithm,” Proceedings of SPIE - The International Society for Optical Engineering, vol. 7703, e77030M, 2010. https://doi.org/10.1117/12.849883
      R. V. Yampolskiy, “Application of bio-inspired algorithm to the problem of integer factorization,” International Journal of Bio-Inspired Computation, vol. 2, no. 2, pp. 115-123, 2010. https://doi.org/10.1504/IJBIC.2010.032127
      G. Macariu, D. Petcu, “Parallel multiple polynomial quadratic sieves on multi-core architectures,” in 9th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, pp. 59-65, 2007. https://doi.org/10.1109/SYNASC.2007.21
      L. T. Yang, L. Xu, M. Lin, “Integer factorization by a parallel GNFS algorithm for public key cryptosystems,” Lecture Notes in Computer Science, vol. 3820, pp. 683-695, 2005. https://doi.org/10.1007/11599555_65
      F. Boudot et al., “State of the Art in Integer Factoring and Breaking Public-Key Cryptography,” IEEE Security and Privacy Magazine, vol. 2022, no. 2, e314918. https://doi.org/10.1109/MSEC.2022.3141918ï
      R. Young, P. Birch, C. Chatwin, A simplification of the Shor quantum factorization algorithm employing a quantum Hadamard transform, 2018. https://doi.org/10.1117/12.2309468
      S. K. Sehgal, R. Gupta, “Quantum Cryptography and Quantum Key,” in International Conference on Industrial Electronics Research and Applications, 2021, pp. 1-5. https://doi.org/10.1109/ICIERA53202.2021.9726722

Downloads

Download data is not yet available.

Most read articles by the same author(s)

1 2 > >> 

Similar Articles

You may also start an advanced similarity search for this article.