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
mn
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 stringssome 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 lengthssome short, some long.
A simplified version of MASH
We shall experiment with a simplified version of the MASH hash function:
 Start with two prime numbers p and q,
and their product N.
 Turn the data to be hashed into a single integer n.
 Express n as ``digits'' in base N:
2 3 q
n = a + a N + a N + a N + ... + a N
0 1 2 3 q
 Start with H being the largest prime less than N.
 For i from 0 to q
2
H < (H + a_i) +H (mod N)
 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:

a:=wholeRagits(n::RadixExpansion(N))::List ZMOD N
 Now create the hash:
 H:=prevPrime(N)
 for i in 1..#a repeat H:=(H+a.i)^2+H
 Note that since the elements of the list a are already
defined as being modulo N, we don't have to use a mod
function in this last step.
 Create the hashes of a few other strings and files. What happens if you
try to hash a really long text file?
 Experiment with hashing using some other (large) primes.