Analysis of multiplication algorithms in Galuis fields for the cryptographic protection of information

: pp. 338 - 349
Lviv Polytechnic National University, Ukraine

The mathematical basis for processing a digital signature is elliptic curves. The processing of the points of an elliptic curve is based on the operations performed in the Galois fields GF(pm). Fields with a simple foundation are not well-studied and very interesting for research. In this paper, a comparison of the complexity of algorithms for the realization of the multiplication operation in Galois fields GF(pm) with different bases is carried out. Conducts a comparison of the 3 most common  multiplication algorithms. Found that fields with a base greater than 2 will have greater complexity of the algorithm.

  1. Zholubak I. M., Kostyk A. T., Glukhov V. S. (2015). Peculiarities of processing the elements of triple Galois fields on the modern element base, Bulletin of the Lviv Polytechnic National University “Computer systems and networks”, Is. 830, 27–33.
  2. Zholubak I. M., Glukhov V. S. (2016). Determination of the extended Galois field GF(dm) with the least hardware complexity of the multiplier, Bulletin of the Lviv Polytechnic National University “Information Systems and Networks”, Is. 835, 50–58.
  3. Zholubak I. M., Glukhov V. S. (2017). Hardware costs of Galois field multipliers GF(dm) with a large basis, Bulletin of the Lviv Polytechnic National University “Computer Sciences and Information Technologies”
  4. Hlukhov V., Zholubak I., Kostyk A., Rahma M. (2017). Galois Fields Elements Processing Units for Cryptographic Data Protection in Cyber-Physical Systems. Advances in Cyber-Physical Systems, Vol. 2, No. 2, Lviv Polytechnic National University, 44–53.
  5. Glukhov V. S., Elias R. M. (2015). Reducing the structural complexity of multi-section multipliers of elements of Galois fields, Electrical and computer systems, No. 19 (95), 222–226.
  6. Cherkaskyi M. V., Tkachuk T. I. (2012). Complexity characteristics of multiplication devices, Radioelectronic and computer systems, No. 5, 142, 147 p.
  7. Hlukhov V., Hlukhova A. Galois field elements multipliers structural complexity evaluation, Proceedings of the 6th International Conference ACSN–2013. Lviv, Ukraine, 2013, 18–19.
  8. Glukhov V. S., Trish G. M. Estimation of the structural complexity of multi-section multipliers of elements of Galois fields, Bulletin of the Lviv Polytechnic National University “Computer systems and networks”, 2014, Vol. 806, 27–33.
  9. Rahma M., Zholubak I. and Hlukhov V. (2018). Devices for multiplicative inverse calculation in the binary Galois fields, 2018 IEEE 9th International Conference on Dependable Systems, Services and Technologies (DESSERT), Kyiv, 261–264. DOI: 10.1109/DESSERT.2018.8409141.
  10. Shalagin S. and Zakharov V. (2021). Implementing the Markov Probability Functions Based on a Set of Polynomials over Galois Field, 2021 International Conference on Information Technology and Nanotechnology (ITNT), Samara, Russian Federation, 1–3. DOI: 10.1109/ITNT52450.2021.9649171.
  11. Li Y. (2020). A tile assembly model to calculate point-multiplication on conic curves over finite field GF(2n), 2020 IEEE Intl Conf on Parallel & Distributed Processing with Applications, Big Data & Cloud Computing, Sustainable Computing & Communications, Social Computing & Networking (ISPA/BDCloud/SocialCom/SustainCom), Exeter, United Kingdom, 41–48. DOI: 10.1109/ISPA-BDCloud- SocialCom-SustainCom51426.2020.00032.
  12. Wu K. and Wei G. (2019). Optimized Design of ECC Point Multiplication Algorithm Over GF(2m), 2019 International Conference on Electronic Engineering and Informatics (EEI), Nanjing, China, 420–425. DOI: 10.1109/EEI48997.2019.00097.
  13. Ibrahim A. (2019). “Efficient Parallel and Serial Systolic Structures for Multiplication and Squaring Over GF( 2m )”, in Canadian Journal of Electrical and Computer Engineering, Vol. 42, No. 2, 114–120, Spring 2019. DOI: 10.1109/CJECE.2019.2900087.
  14. El-Razouk H. (2022). “Input-Latency Free Versatile Bit-Serial GF(2m) Polynomial Basis Multiplication”, in IEEE Transactions on Very Large Scale Integration (VLSI) Systems, Vol. 30, No. 5, 589–602, May 2022. DOI: 10.1109/TVLSI.2022.3155611.
  15. Zhang C., Chen C. and Wu H. (2021). “Area-Efficient Finite Field Multiplication in GF(2n) Using Single- Electron Transistors”, 2021 IEEE Asia Pacific Conference on Circuit and Systems (APCCAS), Penang, Malaysia, 25– 28. DOI: 10.1109/APCCAS51387.2021.9687675.