浅谈散列运算

散列运算是什么？

提到散列运算，很多人可能首先想到的就是MD5：

Message-Digest Algorithm 5

消息摘要算法第5版

一般情况我们系统的数据库中的用户密码都是采用MD5进行加密的。

实际上，严格来说，MD5并不能称为加密，它只是一种散列运算（Hash）。

对消息进行散列运算，可以获得消息的摘要（Digest，也叫哈希值，或者指纹）。

“指纹”一词形象地描述了散列运算的结果。在现实生活中，两个人可能长得很像，但是他们的指纹不同，根据指纹就能对这两个人进行区分。

在计算机中，对数据进行散列运算，就得到了这个数据的“指纹”。只要数据不同，它的指纹就不会相同。

如果不同数据拥有相同的指纹，就叫做“碰撞”，目前MD5发生碰撞的概率极低。

散列运算具有4个特点：

1. 散列运算是不可逆的，可以将散列运算理解为单向的加密：根据原消息经过散列运算可以得到摘要（密文）；但是根据摘要，无法推导出原消息。

2. 任何两个不相同的文件，哪怕只有一个字节的细微差别，得到的摘要都是完全不同的。可以用来判断文件是否相等。

3. 不论原始消息的大小如何，运算得出的摘要信息是固定长度的。摘要的长度根据散列算法的不同而不同，如64位或128位等。

4. 散列运算可以接受字节数组，因此像MD5这样的算法，可以对任何数据进行散列运算并获取摘要，而不仅仅限于字符串形式的用户密码。

可以这样去理解散列算法和MD5的关系：

散列算法是一个种类，而MD5是这个种类中具体的一个实例。

除了MD5以外，还有很多种其他的散列算法，比如MD4、SHA1（Secure Hash Algorithm，安全哈希算法）等。

利用散列运算判断消息是否被篡改:

1.发送方对消息进行散列运算，得到消息摘要（原始摘要），发送消息和摘要，并说明获得摘要所使用的散列算法，如MD5。

2.接收方获得消息和原始摘要，使用相同的散列算法对收到的消息进行散列运算，重新获得一个摘要（本地摘要）。

3.对比原始摘要和本地摘要，如果两个相同，则认为消息没有被篡改；否则认为消息被篡改过了。

上面的验证机制存在一个假设，那就是原始摘要没有被篡改。如果第三方在截获并篡改了消息之后，重新计算摘要，然后将原始摘要替换掉，那么这个机制就失效了。

解决的办法是采用“密钥散列算法（Keyed Hashing Algorithms）”，具体流程如下：

1. 假设发送方要发送消息"Hello world!"。在发送之前，并不对原始消息进行散列运算，而是对消息"[MyKey]Hello world!"进行散列运算，并得到摘要，其中"[MyKey]"相当于一个密钥（此处是关键，在上一种方式中，直接对消息本身，即"Hello world!"进行了散列运算）。

2. 将消息"Hello world!"和摘要发送给接收者。

3. 假设第三方截获了消息"Hello world!"和摘要，并将消息改为了"Hi world!"，但它并不知道密钥"[MyKey]"，因此，它仍对消息"Hi world!"进行散列运算，得到摘要后一起发送给接收方。

4. 接收方知道密钥机制，它在收到篡改过的消息"Hi world!"和摘要后，为消息加上密钥"[MyKey]"，此时消息为"[MyKey]Hi world!"，然后对消息进行散列运算，重新获得一个摘要。对比"Hi world!"和"[MyKey]Hi world!"两个摘要，发现摘要不一样，就会发现消息已经被篡改过了。

在整个过程中，发送方和接收方必须保证密钥不被泄露。

从上面的例子可以看出，散列算法保证了消息的完整性，但不具备保密性，因为第三方可以直接看到消息的内容。

.Net中对散列运算支持

在.NET框架中，散列算法位于System.Security.Cryptography命名空间下，该命名空间位于mscorlib.dll程序集，由一个抽象基类HashAlgorithm和一系列子类构成，下图显示了这种关系。

散列运算的类型之间共有三级的层级关系，以SHA1为例：第一级为抽象类HashAlgorithm；第二级为抽象类SHA1，第三级为普通类SHA1Managed和密封类SHA1CryptoServiceProvider。

SHA1Managed和SHA1CryptoServiceProvider的作用相同，区别是Managed后缀的类是由托管代码写的，CryptoServiceProvider后缀的类调用的是Windows Crypto API，相当于一个包装类。

最下面的三个类SHA256、SHA384、SHA512是SHA家族的变体，它们也有对应的实现类，例如SHA256Managed和SHA256CryptoServiceProvider，简单起见，图中并未列出。

代码快速入门：

string plainText = "Hello, world!";
// 初始化对象
// 也可以：SHA1Managed alg = new SHA1Managed();
HashAlgorithm alg = HashAlgorithm.Create(HashAlgorithmType.SHA1);
// 将字符串转化为字节数组
byte[] plainData = Encoding.UTF8.GetBytes(plainText);
// 获得摘要
byte[] hashData = alg.ComputeHash(plainData);
// 输出结果
foreach (byte b in hashData)
{
  Console.Write("{0:X2}", b);
}

public class HashAlgorithmType
{
  public const string SHA1 = "SHA1";
  public const string SHA256 = "SHA256";
  public const string SHA384 = "SHA384";
  public const string SHA512 = "SHA512";
  public const string MD5 = "MD5";
}

上面代码有两点需要注意：

1. 创建算法对象时，接受的参数类型是字符串类型，字符串的取值为：MD5、SHA、SHA1、SHA256（或SHA-256）、SHA384（或SHA-384）、SHA512（或SHA-512），也可以是类型名称，例如System.Security.Cryptography.SHA1。

2. ComputeHash()方法不仅可以接受字节数组，还可以接受流，因此可以方便地对多种数据源进行散列运算。

创建算法对象的函数签名：

public static HashAlgorithm Create(string hashName);

ComputeHash()方法的重载：

public byte[] ComputeHash(byte[] buffer);
public byte[] ComputeHash(Stream inputStream);

.NET还提供了一些类型用作密钥散列运算，例如MACTripleDES、HMACSHA1、HMACMD5，它们与HashAlgorithm的关系如下图所示：

密钥散列运算类型的使用和普通的散列运算类似，不过多传了一个密钥作为参数而已。

下面是示例代码：

string key = "secret key";
byte[] keyData = Encoding.UTF8.GetBytes(key);
KeyedHashAlgorithm alg = new HMACSHA1(keyData);
//KeyedHashAlgorithm alg = KeyedHashAlgorithm.Create(KeyedHashAlgorithmType.HMACSHA1);
//alg.Key = keyData;

string plainText = "Hello, world!";
// 将字符串转化为字节数组
byte[] plainData = Encoding.UTF8.GetBytes(plainText);
// 获得摘要
byte[] hashData = alg.ComputeHash(plainData);
// 输出结果
foreach (byte b in hashData)
{
  Console.Write("{0:X2}", b);
}

public class KeyedHashAlgorithmType
{
  public const string MACTripleDES = "MACTripleDES";
  public const string HMACSHA1 = "HMACSHA1";
  public const string HMACMD5 = "HMACMD5";
}

文本回顾：

散列运算是什么

散列运算具有4个特点

散列算法保证了消息的完整性

散列算法与密钥散列算法

.Net中对散列运算支持