Development of pipelined polynomial multiplier modulo irreducible polynomials for cryptosystems

Authors

DOI:

https://doi.org/10.15587/1729-4061.2022.251913

Keywords:

cryptography, polynomial system of residue classes, pipeline multiplier modulo, FPGA

Abstract

In this paper, we consider a schematic solution of the pipeline multiplier modulo, where multiplication begins with the analysis of the lowest order of the polynomial multiplier, which can serve as an operating unit for high-speed encryption and decryption of data by hardware implementation of cryptosystems based on a non-positional polynomial notation. The functional diagram of the pipeline and the structure of its logical blocks, as well as an example of performing the operation of multiplying polynomials modulo, are given. The correct functioning of the developed circuit was checked by modeling in the Vivado Design Suite computer-aided design for the implementation of the multiplication device on the development/evaluation kit Artix-7 based on the Spartan 6 field-programmable gate array series by Xilinx. The effectiveness of the proposed hardware pipeline multiplier in modulo is confirmed by the Verilog Testbench timing diagram implemented for the evaluation kit Artix-7 field-programmable gate array. In addition, the developed pipelined modulo multiplier takes no more than 0.02 % of the resources of the used field-programmable gate array for a given length of input data. Compared to the matrix multiplication method, a pipelined modulo multiplier can handle a large data stream without waiting for the result of the previous multiplication step. The modulo pipelined multiplier depth depends on the bit width of the input data. The developed pipeline device can be used in digital computing devices operating in a polynomial system of residue classes, as well as for high-speed data encryption in blocks of cipher processors operating on the basis of a non-positional polynomial number system.

Supporting Agency

  • This research was funded by the Committee of Science of the Ministry of Education and Science of the Republic of Kazakhstan grant OR11465439.

Author Biographies

Sakhybay Tynymbayev, Almaty University of Power Engineering and Telecommunication

PhD, Professor

Department of Information Security Systems

Margulan Ibraimov, Al-Farabi Kazakh National University

Doctor PhD, Associate Professor

Department of Solid State Physics and Nonlinear Physics

Timur Namazbayev, Al-Farabi Kazakh National University; Research Center "KazAlfaTech LTD"

Master, Senior Lecturer, Engineer

Department of Solid State Physics and Nonlinear Physics

Sergiy Gnatyuk, Yessenov University

Doctor of Technical Sciences, Professor

Department of Computer Science

References

  1. Li, L., Li, S. (2016). High-Performance Pipelined Architecture of Elliptic Curve Scalar Multiplication Over GF(2m). IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 24 (4), 1223–1232. doi: https://doi.org/10.1109/tvlsi.2015.2453360
  2. Mohaghegh, S., Yemiscioglu, G., Muhtaroglu, A. (2020). Low-Power and Area-Efficient Finite Field Multiplier Architecture Based on Irreducible All-One Polynomials. 2020 IEEE International Symposium on Circuits and Systems (ISCAS). doi: https://doi.org/10.1109/iscas45731.2020.9181179
  3. Nejatollahi, H., Gupta, S., Imani, M., Rosing, T. S., Cammarota, R., Dutt, N. (2020). CryptoPIM: In-memory Acceleration for Lattice-based Cryptographic Hardware. 2020 57th ACM/IEEE Design Automation Conference (DAC). doi: https://doi.org/10.1109/dac18072.2020.9218730
  4. Singh, J., Kumar, S. (2021). A new class of irreducible polynomials. Communications in Algebra, 49 (6), 2722–2727. doi: https://doi.org/10.1080/00927872.2021.1881789
  5. Devi, S., Mahajan, R., Bagai, D. (2021). A low complexity bit parallel polynomial basis systolic multiplier for general irreducible polynomials and trinomials. Microelectronics Journal, 115, 105163. doi: https://doi.org/10.1016/j.mejo.2021.105163
  6. Svoboda, A. Valach, M. (1955). Operatorove obvody. Stroje Na Zpracovani Informaci, 3, 247–296.
  7. Akushskiy, I. Ya., Yuditskiy, D. I. (1968). Mashinnaya arifmetika v ostatochnykh klassakh. Moscow: Sovetskoe radio, 440.
  8. Sinha Roy, S., Basso, A. (2020). High-speed Instruction-set Coprocessor for Lattice-based Key Encapsulation Mechanism: Saber in Hardware. IACR Transactions on Cryptographic Hardware and Embedded Systems, 443–466. doi: https://doi.org/10.46586/tches.v2020.i4.443-466
  9. Cenk, M., Özbudak, F. (2011). Multiplication of polynomials modulo xn. Theoretical Computer Science, 412 (29) 3451–3462. doi: https://doi.org/10.1016/j.tcs.2011.02.031
  10. Biyashev, R. G., Nyssanbayeva, S. E. (2012). Algorithm for creating a digital signature with error detection and correction. Cybernetics and Systems Analysis, 48 (4), 489–497. doi: https://doi.org/10.1007/s10559-012-9428-5
  11. Nysanbaev, R. K. (1999). Kriptograficheskiy metod na osnove polinomial'nykh bazisov. Vestnik Ministerstva nauki i vysshego obrazovaniya i Natsional'noy akademii nauk Respubliki Kazakhstan, 5, 63–65.
  12. Yenlik, B., Оlga, U., Rustem, B., Saule, N. (2020). Development of an automated system model of information protection in the cross-border exchange. Cogent Engineering, 7 (1), 1724597. doi: https://doi.org/10.1080/23311916.2020.1724597
  13. Kapalova, N., Khompysh, A., Arici, M., Algazy, K. (2020). A block encryption algorithm based on exponentiation transform. Cogent Engineering, 7 (1), 1788292. doi: https://doi.org/10.1080/23311916.2020.1788292
  14. Kalimoldayev, M., Tynymbayev, S., Magzom, M., Ibraimov, M., Khokhlov, S., Abisheva, A., Sydorenko, V. (2019). Polynomials multiplier under irreducible polynomial module for high-performance cryptographic hardware tools. CEUR Workshop Proceedings, 2393, 729–737. Available at: http://ceur-ws.org/Vol-2393/paper_363.pdf
  15. Kalimoldayev, M., Tynymbayev, S., Gnatyuk, S., Khokhlov, S. et. al. (2019). Matrix multiplier of polynomials modulo analysis starting with the lower order digits of the multiplier. NEWS of National Academy of Sciences of the Republic of Kazakhstan, 4 (436), 181–187. doi: https://doi.org/10.32014/2019.2518-170x.113
  16. Jankowski, K., Laurent, P., O’Mahony, A. (2012). Intel Polynomial Multiplication Instruction and its Usage for Elliptic Curve Cryptography. White Paper, 17. Available at: https://www.intel.com/content/dam/www/public/us/en/documents/white-papers/polynomial-multiplication-instructions-paper.pdf
  17. Xilinx. Available at: https://www.xilinx.com/products/boards-and-kits.html
  18. IEEE Standard 1364-2005. IEEE Standard for Verilog Hardware Description Language. doi: https://doi.org/10.1109/ieeestd.2006.99495
  19. Kalimoldayev M., Tynymbayev S., Ibraimov M., Magzom M., Kozhagulov Y., Namazbayev T. (2020). Pipeline multiplier of polynomials modulo with analysis of high-order bits of the multiplier. Bulletin of National Academy of Sciences of the Republic of Kazakhstan, 4 (386), 13–20. doi: https://doi.org/10.32014/2020.2518-1467.98

Downloads

Published

2022-02-25

How to Cite

Tynymbayev, S. ., Ibraimov, M., Namazbayev, T. ., & Gnatyuk, S. . (2022). Development of pipelined polynomial multiplier modulo irreducible polynomials for cryptosystems. Eastern-European Journal of Enterprise Technologies, 1(4 (115), 37–43. https://doi.org/10.15587/1729-4061.2022.251913

Issue

Section

Mathematics and Cybernetics - applied aspects