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

https://doi.org/10.19053/uptc.01211129.v33.n69.2024.17935

Published 2024-09-30

  • 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 XML

References

  1. 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
  2. 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
  3. K. Petersen, H. Flensburg, R. Feldt, M. Mattsson, S. Mujtaba, Systematic Mapping Studies in Software Engineering, 2008.
  4. B. Kitchenham, S. M. Charters, Guidelines for performing Systematic Literature Reviews in Software Engineering, 2007.
  5. D. Budgen, M. Turner, P. Brereton, B. Kitchenham, Using Mapping Studies in Software Engineering, 2008. https://www.ebse.org.uk
  6. 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.
  7. 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
  8. C. Bouillaguet, P. Zimmermann, Parallel Structured Gaussian Elimination for the Number Field Sieve, 2021.
  9. 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
  10. 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
  11. 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
  12. 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
  13. 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
  14. 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
  15. 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.
  16. 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
  17. 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
  18. 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
  19. 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
  20. 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
  21. 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
  22. 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
  23. 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
  24. 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ï
  25. 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
  26. 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.

Similar Articles

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