/usr/share/doc/axiom-doc/hypertex/cryptoclass9.xhtml is in axiom-hypertex-data 20120501-8.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 | <?xml version="1.0" encoding="UTF-8"?>
<html xmlns="http://www.w3.org/1999/xhtml"
xmlns:xlink="http://www.w3.org/1999/xlink"
xmlns:m="http://www.w3.org/1998/Math/MathML">
<head>
<meta http-equiv="Content-Type" content="text/html" charset="us-ascii"/>
<title>Axiom Documentation</title>
<style>
html {
background-color: #ECEA81;
}
body {
margin: 0px;
padding: 0px;
}
div.command {
color:red;
}
div.center {
color:blue;
}
div.reset {
visibility:hidden;
}
div.mathml {
color:blue;
}
input.subbut {
background-color:#ECEA81;
border: 0;
color:green;
font-family: "Courier New", Courier, monospace;
}
input.noresult {
background-color:#ECEA81;
border: 0;
color:black;
font-family: "Courier New", Courier, monospace;
}
span.cmd {
color:green;
font-family: "Courier New", Courier, monospace;
}
pre {
font-family: "Courier New", Courier, monospace;
}
</style>
</head>
<body>
<div align="center"><img align="middle" src="doctitle.png"/></div>
<hr/>
<center>
<h2>RCM3720 Cryptography, Network and Computer Security</h2>
<h3>Laboratory Class 9: Hash Functions</h3>
</center>
<hr/>
<br/><br/>
<b>A simple hash</b>
<br/><br/>
Given two prime numbers <tt>p</tt> and <tt>q</tt>, and their product
<tt>N</tt>, we can define a hash of a number <tt>n</tt> to be
<pre>
n
hash = g (mod N)
</pre>
This is provably collision resistant, because if we want to find two hashes
which are equal, then we need to find <tt>m</tt> and <tt>n</tt> for which
<pre>
m n
g = g (mod N)
</pre>
or that
<pre>
m-n
g = 1 (mod N)
</pre>
By Euler's theorem, we know that
<pre>
ϕ(N)
g = 1 (mod N)
</pre>
This means that finding a collision requires finding two numbers
<tt>m</tt> and <tt>n</tt> for which
<pre>
m = n (mod ϕ(N))
</pre>
Since computing ϕ(N) requires a knowledge of the factorization of
<tt>N</tt>, this will be hard if <tt>p</tt> and <tt>q</tt> are large.
<ul>
<li> Enter the following commands:
<ul>
<li> <span class="cmd">p:=nextPrime(87654321)</span></li>
<li> <span class="cmd">q:=nextPrime(98765432)</span></li>
<li> <span class="cmd">N:=p*q</span></li>
<li> <span class="cmd">g:=17</span></li>
</ul>
</li>
<li> Read in the utility file <a href="rcm3720.input">rcm3720.input</a></li>
<li> Now experiment with the following hashes:
<ul>
<li> <span class="cmd">n:=str2num("A cat")</span></li>
<li> <span class="cmd">h:=powmod(g,n,N)</span></li>
<li> <span class="cmd">n:=str2num("A bat")</span></li>
<li> <span class="cmd">h:=powmod(g,n,N)</span></li>
</ul>
</li>
<li> Even though the strings are very similar,
how similar are the hash values?
</li>
<li> Experiment with hashing some other strings---some short, some long.</li>
<li> Read in a text file (any text file, of any length) as follows:</li>
<ul>
<li>
<span class="cmd">
f:TextFile:=open("\full\path\to\file","input")
</span>
</li>
<li> <span class="cmd">str:=""</span></li>
<li>
<span class="cmd">
while not endOfFile?(f) repeat str:=concat(str,readLine(f));
</span>
</li>
</ul>
<li> Now the variable <tt>str</tt> will contain the file as one long string.
Hash this string, by converting it to a number first.
</li>
<li> Try this with a few different text files,
of different lengths---some short, some long.
</li>
</ul>
<br/><br/>
<b>A simplified version of MASH</b>
<br/><br/>
We shall experiment with a simplified version of the MASH hash function:
<ol>
<li> Start with two prime numbers <tt>p</tt> and <tt>q</tt>,
and their product <tt>N</tt>.
</li>
<li> Turn the data to be hashed into a single integer <tt>n</tt>.</li>
<li> Express <tt>n</tt> as ``digits'' in base <tt>N</tt>:</li>
<pre>
2 3 q
n = a + a N + a N + a N + ... + a N
0 1 2 3 q
</pre>
<li> Start with <tt>H</tt> being the largest prime less than <tt>N</tt>.</li>
<li> For <tt>i</tt> from 0 to <tt>q</tt></li>
<pre>
2
H <-- (H + a_i) +H (mod N)
</pre>
<li> The final value of <tt>H</tt> is the hash.</li>
</ol>
<ul>
<li> With <tt>p</tt>, <tt>q</tt> and <tt>N</tt> as before, pick a long
string (or the string from a text file) to be hashed, and turn it
into a number <tt>n</tt>.
</li>
<li> Determine the ``digits'' in base <tt>N</tt>:
<ul>
<li>
<span class="cmd">
a:=wholeRagits(n::RadixExpansion(N))::List ZMOD N
</span>
</li>
</ul>
</li>
<li> Now create the hash:
<ul>
<li> <span class="cmd">H:=prevPrime(N)</span></li>
<li> <span class="cmd">for i in 1..#a repeat H:=(H+a.i)^2+H</span></li>
</ul>
</li>
<li> Note that since the elements of the list <tt>a</tt> are already
defined as being modulo <tt>N</tt>, we don't have to use a mod
function in this last step.
</li>
<li> Create the hashes of a few other strings and files. What happens if you
try to hash a really long text file?
</li>
<li> Experiment with hashing using some other (large) primes.</li>
</ul>
</body>
</html>
|