Hashing with polynomials
DOI:
https://doi.org/10.26577/JMMCS.2020.v107.i3.08Keywords:
irreducible polynomial, Hash function, finite field, redundant cyclic code, collisionAbstract
Hash functions are easy-to-compute compression functions that take a variable-length input and convert it to a fixed-length output. Hash functions are used as compact representations, or digital fingerprints, of data and to provide message integrity. In modern cryptography, various hash functions are widely used. The main problem with using hash functions is that the existence of irreversible functions that exclude the possibility of collisions has not been proven. In addition, there are no universal hashing methods, and they should be selected depending on their area of application. A special role is played by complexity-theoretical problems, namely, algebraic number theory. One of these problems is the search for irreducible polynomials of a given degree over a finite field, which can be used to search for message hash codes.
The relevance of the study of irreducible polynomials over simple and extended Galois fields is due to their diverse application in various fields of science and technology. Irreducible polynomials have found their application in various fields of mathematics, information technology and information security. Using the properties of irreducible polynomials allows you to maximize the effective computer implementation of arithmetic in finite fields, which is of particular importance for cryptography and coding theory. Finding irreducible polynomials is difficult to compute, especially over large fields. The procedure for finding irreducible polynomials requires efficient algorithms and large computational resources, as in the case of finding prime numbers, which is the main problem for constructing effective hashing algorithms based on them.
This article describes a method for constructing hash functions based on calculating the remainder of a division by irreducible polynomials. In addition, the problem of searching for irreducible polynomials is considered. Computer modeling of hash functions using irreducible polynomials over finite fields has been performed. The results of using various irreducible polynomials and their analysis are presented. The results of the article can be used in cryptographic applications and coding theory.
References
[2] Sedgewick R., Algorithms in C++ , Parts 1-4: Fundamentals, Data Structure, Sorting, Searching - 3rd ed. (1988): 752.
[3] Khomich E.A., "Neprivodimyye mnogochleny nad konechnymi polyami i svyaz’ s kriptografiyey [Irreducible polynomials over finite fields and connection with cryptography]" , Academic Publicistics, Vol.3 (2017): 19-22.
[4] Whitfield Diffiee and Martin E. Hellman, "New directions in cryptography" , IEEE Trans. on Information Theory Vol. IT-22, no. 6.(1976):644-654.
[5] Landau S., "Find Me a Hash" , Notices Amer. Math. Soc., vol.53 (2006): 330-332.
[6] Shpilrain V., "Hashing with Polynomials" , Information Security and Cryptology – ICISC 2006 LNCS 4296 (2006): 22-28.
Springer, 2006. DOI: https://doi.org/10.1007/11927587_4
[7] Menezes A., P. van Oorschot and S Vanstone, "Handbook of Applied Cryptography" , CRC Press (1997).
[8] Avezova YA.E., "Sovremennyye podkhody k postroyeniyu khesh-funktsiy na primere finalistov konkursa SHA-3 [Modern approaches to the construction of hash functions using the example of the finalists of the SHA-3 contest]" , Voprosy kiberbezopasnosti, no. 3(11) (2015): 60-67.
[9] Shai Halevi and Hugo Krawczyk, "Strengthening Digital Signatures via Randomized Hashing" , Advances in Cryptology-CRYPTO 2006, LNCS 4117 (2006): 41-59. Springer, 2006. DOI: https://doi.org/10.1007/11818175_3
[10] Henry S. and Warren, Jr., Hacker’s Delight , - 3rd ed., Addison Wesley (2013): 816.
[11] Lidl R. and Niderrayter H., Finite Fields , Cambridge: Cambridge University Press (2000): 768.
[12] Turusbekova U.K. and Azieva G.T., "Investigation of irreducible normal polynomials special type over а field of characteristic 2" , Vestnik KazNPU im. Abaya, seriya "Fiziko-matematicheskiye nauki" no 3(67) (2019): 122-127.
[13] Crandall R. E. and Pomerance C. B., Prime Numbers: A Computational Perspective , New York: Springer-Verlag (2005): 597.
[14] Gorbenko I.D. and Shtan’ko I.A., "Funktsii kheshirovaniya. Ponyatiya, trebovaniya, klassifikatsiya, svoystva i primeneniye [Hash Functions Concepts, requirements, classification, properties and application]" , Radioelektronika i informatika, no. 1 (1998): 64-69.
[15] Sankhanil Dey, Amlan Chakrabarti and Ranjan Ghosh, "4-bit crypto S-boxes: Generation with irreducible polynomials over Galois field GF(24) and cryptanalysis" , International Journal of Tomography and Simulation, vol. 32, no. 3 (2019): 46-60.
