Хеширование на основе многочленов
DOI:
https://doi.org/10.26577/JMMCS.2020.v107.i3.08Ключевые слова:
неприводимый многочлен, Хеш-функция, конечное поле, избыточный циклический код, столкновениеАннотация
В современной криптографии широко используются различные хеш-функции. Хеш-функции - это простые для вычисления функции сжатия, которые принимают входные данные переменной длины и преобразуют их в выходные данные фиксированной длины.
Они используются в качестве компактных представлений или цифровых отпечатков пальцев для обеспечения целостности сообщения. Основная проблема использования хеш-функций заключается в том, что существование необратимых функций, исключающих возможность столкновений, не доказано. Кроме того, не существует универсальных методов хеширования, и их следует выбирать в зависимости от области их применения. Особую роль играют теоретико-сложностные проблемы, а именно алгебраическая теория чисел. Одной из таких проблем является поиск неприводимых многочленов заданной степени над конечным полем, которые можно использовать для поиска хеш-кодов сообщений.
Актуальность исследования неприводимых полиномов над простыми и расширенными полями Галуа обусловлена их разнообразным применением в различных областях науки и техники. Неприводимые многочлены нашли свое применение в различных областях математики, информационной техники и защите информации. Использование свойств неприводимых многочленов позволяет максимизировать эффективную компьютерную реализацию арифметики в конечных полях, что имеет особое значение для криптографии и теории кодирования. Поиск неприводимых многочленов является сложной для вычисления задачей, особенно над полями большой размерности. Процедура нахождения неприводимых многочленов требует эффективных алгоритмов и больших вычислительных ресурсов, как в случае нахождения простых чисел, что является основной проблемой для построения эффективных алгоритмов хеширования на их основе.
В представленной статье описан метод построения хеш-функций, основанный на вычислении остатка от деления на неприводимый многочлен. Кроме того, рассмотрена проблема поиска неприводимых многочленов. Выполнено компьютерное моделирование хеш-функций с использованием неприводимых многочленов над конечными полями. Представлены результаты использования различных неприводимых многочленов и их анализ. Результаты статьи могут быть использованы в криптографических приложениях и теории кодирования.
Библиографические ссылки
[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.
