散列函数
到目前为止，我们一直集中关注能够用来提供机密性的加密算法。这些算法有一个最基本的特点，即它们都具有可逆性：知道了适当的密钥必定可以从密文重构出明文信息。然而，在很多例子中，虽然使用了密码术，但不需要从密文推论出原始“信息”。事实上，可能存在一些明确要求不可逆的情况。一个例子是计算机系统的口令保护问题。使用者被告诫应该对其口令保密，于是我们可以合理地假定，该系统也在力求确保这种机密性。一旦口令出现在系统中，特别是出现在用于验证的数据库中时，它们必须得到保护。然而这时系统通常只要求核实输入的口令是否正确，而不需要从存储值中导出口令。
此外在很多密码术的例子中，需要将长信息压缩成短比特串（比原信息的长度短许多）。当出现这样的需求时，不可避免地会发生如下情况：不止一个信息会被压缩为同一个短比特串，这自然就意味着这个过程不可逆。这种效应被称为散列函数，在不同的应用领域，它们有些会使用密钥，有些则不然。
散列函数的基本意思是，作为散列函数结果的散列值是对信息的压缩表示映射。散列值有好几种称法，包括数字指纹、信息摘要，或（毫不奇怪）就叫散列。散列的应用领域很广，包括保证数据的完整性，以及作为数字签名过程的组成部分。
一般来说，散列函数接受任意长度的输入，但只产生固定长度的输出。如果两个输入产生了同样的输出，我们就说出现了冲突。正如我们已提到的，冲突的存在是不可避免的。因此，如果我们想通过数字指纹鉴定出唯一的信息，就必须小心选取散列函数，以确保冲突即使存在也不可能被发现。这给我们的启示之一是：潜在指纹值的数量必须很大。我们用一个极小的例子来说明原因。如果我们只有8个可能的指纹值，那么任意两个信息具有同一指纹值的几率为12.5％。此外，任何包含9个或9个以上信息的集合，其中必定至少包含一个冲突。
