## 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.
• Enter the following commands:
• p:=nextPrime(87654321)
• q:=nextPrime(98765432)
• N:=p*q
• g:=17
• Read in the utility file rcm3720.input
• Now experiment with the following hashes:
• n:=str2num("A cat")
• h:=powmod(g,n,N)
• n:=str2num("A bat")
• h:=powmod(g,n,N)
• Even though the strings are very similar, how similar are the hash values?
• Experiment with hashing some other strings---some short, some long.
• Read in a text file (any text file, of any length) as follows:
• f:TextFile:=open("\full\path\to\file","input")
• str:=""
• while not endOfFile?(f) repeat str:=concat(str,readLine(f));
• Now the variable str will contain the file as one long string. Hash this string, by converting it to a number first.
• Try this with a few different text files, of different lengths---some short, some long.

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

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.
• With p, q and N as before, pick a long string (or the string from a text file) to be hashed, and turn it into a number n.
• Determine the digits'' in base N: