RCM3720 Cryptography, Network and Computer Security

Laboratory Class 9: Hash Functions




A simple hash

Given two prime numbers p and q, and their product N, we can define a hash of a number n to be
           n
   hash = g  (mod N)
This is provably collision resistant, because if we want to find two hashes which are equal, then we need to find m and n for which
    m    n
   g  = g  (mod N)
or that
    m-n
   g    = 1 (mod N)
By Euler's theorem, we know that
    ϕ(N)
   g         = 1 (mod N)
This means that finding a collision requires finding two numbers m and n for which
   m = n (mod ϕ(N))
Since computing ϕ(N) requires a knowledge of the factorization of N, this will be hard if p and q are large.

A simplified version of MASH

We shall experiment with a simplified version of the MASH hash function:
  1. Start with two prime numbers p and q, and their product N.
  2. Turn the data to be hashed into a single integer n.
  3. Express n as ``digits'' in base N:
  4.                     2      3            q
       n = a + a N + a N  + a N  + ... + a N
            0   1     2      3            q
    
  5. Start with H being the largest prime less than N.
  6. For i from 0 to q
  7.                      2
          H <-- (H + a_i)  +H (mod N)
    
  8. The final value of H is the hash.