一般来说，哈希函数是可用于将任意长度的数据映射到定长数据的任何函数。由于任意长度的二进制字符串通常是表示数据的一种方式，我们可以将哈希函数理解为以下映射:
$$H: \{0,1\}^* \to \{0,1\}^k$$
其中 $\{0,1\}^*$ 表示任意但有限长度的所有二进制字符串的集合，$\{0,1\}^k$ 表示看到长度恰好为 $k$ 位的二进制字符串的集合。
$H$ 的像(images) ，即哈希函数 $H$ 的返回值，被称为 哈希值(hash value)、摘要(digests) 或简称为 哈希(hashes)
符号 8
在下文中，我们称元素 $b \in \{0, 1\}$ 为 1 bit 。如果 $s \in \{0,1\}^*$ 是二进制字符串，我们称 $|s| = k$ 是其长度，即 $s$ 的位数。我们使用 $<>$ 表示空字符串，使用 $s=<b_1,b_2,\ldots,b_k>$ 表示 k 位长的二进制字符串。
如果给定两个二进制字符串 $s=<b_1,b_2,\ldots,b_k>$ 和 $s'=<b'_1,b'_2,\ldots,b'_l>$ ，我们使用 $s||s'$ 表示字符串 拼接(concatenation)，即 $s||s'=<b_1,b_2,\ldots,b_k,b'_1,b'_2,\ldots,b'_l>$
如果 $H$ 是一个哈希函数，将任意长度的二进制字符串 $s \in \{0, 1\}^*$映射到长度为 $k$ 的二进制字符串，我们记 $H(s)_j$ 是像 $H(s)$ 的第 $j$ 位。
示例 45
最基本的哈希函数 $H_k:\{0,1\}^*\to \{0,1\}^k$ 是通过简单的截断或填充实现哈希。设存在二进制字符串 $s$ ，如果 $|s| > k$，那么我们直接阶段大于 $|s|$ 的字段; 如果 $|s| < k$，那么我们通过填充 $0$ 以实现长度。为了使该哈希函数具有确定性，我们定义截断和填充都应该发生在左侧。
比如，如果参数 $k = 3$，使用此哈希函数处理 $s_1=<0,0,0,0,1,0,1,0,1,1,1,0>$ 和 $s_2=1$ ，那么哈希后的结果位 $H_3(s_1)=<1,1,0>$ 和 $H_3(s_2)=<0,0,1>$
哈希函数的一个理想属性是 均匀性(uniformity)，这意味着哈希函数应尽可能将输入值均匀的映射到输出空间。使用数学术语表示，任意来自 $\{0, 1\}^k$ 长度为 $k$ 的字符串都应该以大致相同的概率生成输出结果。
特别令人感兴趣的是密码学哈希函数，该函数是一个单向函数。这实质上意味着给定来自 $\{0,1\}^k$ 的字符串 $y$ ，不可能找到一个字符串 $x \in \{0, 1\}^*$ 使得 $H(x)=y$ 成立。该属性通常被称为 抗原象形(preimage-resistanc)
此外，如果给定一个字符串 $x_1 \in \{0,1\}^*$ 那么找到另一个字符串 $x_2 \in \{0,1\}^*$ 使其满足 $H(x_1)=H(x_2)$ 是不可能的。
另外，要找到两个字符串 $x_1, x_2 \in \{0,1\}^*$ 使其满足 $H(x_1)=H_(x_2)$ 是不可行的，称为 抗碰撞性(collision resistance)。需要注意的是，碰撞总是存在的，因为函数 $H: \{0,1\}^* \to \{0,1\}^k$ 的输入是无限多的，不可避免的产生碰撞。事实上，对于任何产生长度为 $k$ 的哈希函数，找到给定摘要的原象总是需要 $2^k$ 的暴力搜索。计算这些值实际上是不可能的，也不太可能偶然产生具有相同哈希值。
密码学哈希函数的第三个属性是输入的微小变化(如更改单个位)应该生成看起来完全不同的哈希值。这被称为 扩散(diffusion) 或雪崩效应。
由于密码学哈希函数将输入的微小变化映射位输出值的较大变化，因此通过将输出与预期输出进行比较，我们较为容易发现哈希函数实现的错误。因此，密码学哈希函数的定义通常包含一些常见输出和预期输出的哈希值的测试向量。由于空字符串 $<>$ 是唯一长度为 0 的字符串，因此常见的测试向量都包含空字符串的哈希值。
示例 46
考虑 示例 45 中的 k 截断哈希函数。由于空字符串的长度为 0 ，因此空字符串的哈希是长度为 $k$ 且仅包含 0 的字符串:
$$H_k(<>)= <0,0,\ldots, 0,0>$$
从 $H_k$ 的定义可以明显看出，这个简单的哈希函数不符合密码学哈希函数的定义。特别的是，每个哈希值都是自己的原象，因为对于长度为 $k$ 的字符串， $H_k(y)=y$。因此我们很容易找到原象，所以抗原象性的性质不成立。
此外，很容易构造碰撞，因为所有长度 $|s| > k$ 且右侧 k 位相同的字符串均对应相同的哈希值。这意味着该哈希函数不是抗碰撞的。
最后，该哈希函数没有太多的扩散，因为如果不改变最右边 k 位的数据根本不会改变哈希值。
使用纸笔计算密码学安全级别的哈希函数是可能的，但是很乏味。幸运的是， Sage 提供了 hashlib 库。该库提供了一系列的函数帮助用户使用 Python 编写可靠和稳定的包含哈希函数的代码。以下示例展示了如何在 Sage 中使用 hashlib
示例 47
一个用于被认为可以生产密码学安全的哈希函数是 SHA256 哈希函数。正如上文讨论的概念，该函数可以将任意长度的二进制字符串映射为长度为 256 位的二进制字符串:
$$ \text{SHA256}: \{0, 1\}^* \to \{0, 1\}^{256}$$
为了评估 SHA256 哈希函数的正确实现，对于空字符串的哈希结果如下:
$$ \text{SHA256}(<>) = e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855 $$
为了具有更好的人类可读性，通常的做法是使用 16 进制而不是 2 进制形式展示哈希结果。我们可以使用 Sage 计算哈希结果，并将其自由地在二进制、十六进制和十进制之间转化。为此，我们导入 hashlib 的 SHA256 实现:
sage: import hashlib
sage: test = 'e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855'
sage: empty_string = ""
sage: binary_string = empty_string.encode()
sage: hasher = hashlib.sha256(binary_string)
sage: result = hasher.hexdigest()
sage: type(result)
<class 'str'>
sage: d = ZZ('0x' + result)
sage: d.str(16) == test
True
sage: d.str(16)
'e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855'
sage: d.str(2)
'1110001110110000110001000100001010011000111111000001110000010100100110101111101111110100110010001001100101101111101110010010010000100111101011100100000111100100011001001001101110010011010011001010010010010101100110010001101101111000010100101011100001010101'
sage: d.str(10)
'102987336249554097029535212322581322789799900648198034993379397001115665086549'