Research Of Hash Function Based On Multivariable Polynomials Over A Finite Field

Hash function is an important cryptographic primitive. The hash function's security analysis is increasing with the development of hash function. At the inter-American cryptography conference, Xiaoyun Wang announced collision finding of a series of hash function including MD4, MD5, HAVAL-128 and RIPEMD etc. Analysis showed that the Merkle-Damg°ard construction for Hash algorithm is suffering from length-extension attacks, multi-collision attacks, fixed point attacks and Herding attacks and so on. All these results indicate that the custom hash function and the Merkle-Damg°ard construction don't have enough security.Because Merkle-Damg°ard construction is no longer secure, a chaining variable rotative Hash function construction is designed in this paper. In order to resist length-extension attacks, multi-collision attacks, fixed point attacks and Herding attacks that the Merkle-Damgard construction is vulnerable to suffering, big internal states, NMAC and HMAC's idea and a counter are used in the construction. Chaining variable rotative Hash function construction effectively deal with chaining variable and can improve the performance of Hash function before ensure the security, especially the Hash function based on difficult mathematical problems.According to the chaining variable rotative hash function construction, a new message digest Hash algorithm (RMD-MQ-Hash) is described. RMD-MQ-Hash base on the multivariate quadratic polynomials over a finite field and have variable hash size. The security of the RMD-MQ-Hash's compression function depends on the difficulty of solving randomly drawn multivariate equations systems over a finite field. Through analyzing the security and performance of RMD-MQ-Hash, we find that RMD-MQ-Hash has the security can be analyzed, a good avalanche effect, and has some advantages in memory requirements and running speed compared with the previous multivariate Hash function.At the end, a signature scheme based on RMD-MQ-Hash is designed and implemented, and the correctness and security of signature scheme is analyzed. The key generation algorithm, signature algorithm and verification algorithm in signature scheme are simple, and the security of signature scheme only depends on the security of RMD-MQ-Hash algorithm. The length of signature that signature scheme based on RMD-MQ-Hash generated is very small.