ELECTROTECHNIC AND COMPUTER SYSTEMS, Odessa national polytechnic university

MATHEMATICAL METHODS FOR CONSTRUCTING HASH FUNCTIONS BASED ON THE THEORY OF FINITE FIELDS IN INFORMATION TECHNOLOGY SYSTEMS

Abstract:

In this paper a method for constructing hash functions based on irreducible polynomials in finite fields was considered. The problem of finding irreducible polynomials was considered. A computer simulation of hash functions was performed using irreducible polynomials. The results of using various irreducible polynomials and their analysis are given. The problem of the occurrence of collisions depending on the length of the hash, and the probability of collisions is estimated depending on the number of enumeration operations were considered.

Authors:

George Vostrov ( vostrov@gmail.com,ORCID ID: 0000-0003-3856-5392 )
Olena Ponomarenko ( ponomarenkoelena1997@gmail.com,ORCID ID: 0000-0003-1585-4706 )

Keywords

hash function, finite field, irreducible polynomial, collision, cyclic redundant code, polynomial arithmetic, “birthdays” paradox

References

Graham, R., Knuth, D. (1998), Concrete mathematics. A foundation for computer science –703 p.
Sedgewick, R. (2001), Fundamental algorithms on C++, - Kyiv: Publishing house "DiaSoft"– 688 p.
Schneier, B. (1996), Applied Cryptography, Second Edition, John Wiley & Sons, 816 p. ISBN 0-471-11709-9.
Khomich, E. A. (2017), Irreducible polynomials over finite fields and relation with cryptography. – pp.19–24.
Warren, Jr., Henry, S. (2002). Hacker's Delight (1 ed.). Addison Wesley. ISBN 978-0-201-91465-8. –512 p.
Lambek, J. (1966), Lectures on rings and modules. Waltham, Massachusetts : Blaisdell. – 283 p.
Lidl, R., Niederreiter, G.(1988), Finite fields: In 2 volumes, Transl. from English, - Moscow: Publishing house "Mir", 430 p.
Crandall, R., Pomerance, K. (2011), Prime numbers: cryptographic and computational aspects, Transl. from English / Ed. and with a preface by V. Chubarikova, - Moscow: URSS: Book House "LIBROKOM", 664 p.
Rabin, M. O., Karp, R. M. (1987). Efficient randomized pattern-matching algorithms – IBM, 1987. – № 2. – pp.. 249–260.
Goldberg, S. (1976), A Direct Attack on a Birthday Problem – Mathematical Mathematics Magazine, – pp. 130–132.