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:
- 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.