散列算法概述

散列函数（Hash Function）是一种将任意长度的输入数据映射为固定长度输出的函数，该输出称为散列值或哈希值。散列算法在计算机科学中具有广泛应用，尤其在密码学和数据完整性校验领域。

核心性质

一个优秀的散列函数应具备以下核心性质：

  • 确定性：相同的输入始终产生相同的输出。这是散列函数的基本要求，确保了散列值的一致性和可验证性。

  • 单向性：从散列值无法反向推导出原始输入。这一性质使散列函数适用于密码存储等场景，即使数据库泄露，攻击者也无法直接获取明文密码。

  • 雪崩效应：输入数据的微小变化会导致输出散列值的剧烈变化。修改输入的任意一位，输出的散列值应有约50%的位发生变化。这一特性保证了散列值对输入的高度敏感性。

  • 抗碰撞性：难以找到两个不同的输入产生相同的散列值。抗碰撞性分为弱抗碰撞性（给定输入，难以找到另一个输入产生相同散列值）和强抗碰撞性（难以找到任意两个不同输入产生相同散列值）。

常见散列算法家族

MD5

MD5（Message Digest Algorithm 5）输出128位散列值，曾广泛应用于文件校验和密码存储。然而，MD5已被证明存在严重的安全漏洞。2004年，王小云教授团队提出了高效的MD5碰撞攻击方法，能够在极短时间内找到产生相同MD5值的两个不同文件。由于碰撞攻击的可行性，MD5不再适用于需要安全性的场景，但仍可在非安全相关的校验和场景中使用。

SHA-1

SHA-1（Secure Hash Algorithm 1）输出160位散列值，是Git版本控制系统默认使用的commit散列算法。然而，SHA-1的安全性同样受到质疑。2017年，Google与CWI Amsterdam合作发布了SHAttered攻击，成功构造了两个具有相同SHA-1值的不同PDF文件，证明了SHA-1的碰撞攻击在实践中的可行性。目前Git社区正在进行从SHA-1向SHA-256的迁移工作。

SHA-2 家族

SHA-2是第二代安全散列算法，包含SHA-224、SHA-256、SHA-384、SHA-512、SHA-512/224和SHA-512/256六个成员，分别输出224位、256位、384位和512位散列值。SHA-2基于Merkle-Damgård结构，是目前广泛使用的主流安全散列算法。SHA-256是其中应用最广泛的成员，被用于TLS协议、比特币系统等多种场景。

SHA-3（Keccak）

SHA-3于2015年由NIST标准化，基于Keccak算法，采用海绵结构（Sponge Construction）。与SHA-2不同，SHA-3采用了完全不同的内部结构设计，因此即使SHA-2被发现存在安全漏洞，SHA-3仍能保持安全性。SHA-3被视为SHA-2的补充而非替代，两者可以长期并存使用。

散列算法在工程中的应用场景

数据完整性校验

散列算法常用于验证文件或数据在传输或存储过程中的完整性。发送方计算文件的散列值并随文件一同发送，接收方重新计算散列值并比对，若一致则说明文件未被篡改。常见的应用场景包括软件下载校验、数据备份验证等。

密码存储

散列算法可用于密码存储，但不应直接使用MD5、SHA-1或SHA-2等快速散列算法，因为这些算法容易受到暴力破解和彩虹表攻击。正确的做法是使用专用的密码哈希函数，如bcrypt、scrypt或Argon2。这些算法专门设计用于密码存储，具有以下特点：

  • 加盐：在密码中加入随机盐值，防止彩虹表攻击
  • 计算慢：故意增加计算成本，抵御暴力破解
  • 内存硬：scrypt和Argon2需要大量内存，增加GPU/ASIC攻击成本

数字签名

在公钥密码学中，散列算法用于数字签名。发送方对消息的散列值使用私钥进行签名，接收方使用公钥验证签名。由于散列值长度固定，签名算法只需处理固定长度的输入，提高了效率。常见的应用包括SSL/TLS证书、代码签名等。

分布式系统中的一致性哈希

一致性哈希是一种特殊的哈希技术，用于解决分布式系统中的数据分片和负载均衡问题。当节点数量变化时，一致性哈希只需迁移少量数据，保证系统的稳定性。这一技术广泛应用于分布式缓存、分布式文件系统等场景。

数据结构

散列函数是许多数据结构的核心组件：

  • HashMap：使用散列函数将键映射到数组索引，实现平均O(1)的查找、插入和删除操作
  • BloomFilter：基于多个散列函数的概率数据结构，用于判断元素是否在集合中，允许一定的误判率但空间效率极高

Java 中的散列算法使用

Java提供了java.security.MessageDigest类用于计算散列值。以下示例展示了如何使用MD5和SHA-256计算字符串的散列值：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.nio.charset.StandardCharsets;
import java.math.BigInteger;

public class HashExample {
    
    public static String calculateHash(String algorithm, String input) 
            throws NoSuchAlgorithmException {
        MessageDigest digest = MessageDigest.getInstance(algorithm);
        byte[] hashBytes = digest.digest(input.getBytes(StandardCharsets.UTF_8));
        return String.format("%064x", new BigInteger(1, hashBytes));
    }
    
    public static void main(String[] args) throws NoSuchAlgorithmException {
        String text = "Hello, World!";
        
        String md5Hash = calculateHash("MD5", text);
        System.out.println("MD5: " + md5Hash);
        
        String sha256Hash = calculateHash("SHA-256", text);
        System.out.println("SHA-256: " + sha256Hash);
    }
}

安全建议

在工程实践中使用散列算法时，需注意以下安全建议：

  1. 密码存储：绝不应直接使用MD5、SHA-1或SHA-2存储密码，应使用bcrypt、scrypt或Argon2等专用密码哈希函数
  2. 避免使用已破解算法：MD5和SHA-1已被证明存在碰撞攻击，不应在安全敏感场景中使用
  3. 使用标准算法：优先使用SHA-256或SHA-3等经过广泛验证的算法
  4. 加盐：在密码存储等场景中必须使用随机盐值，防止彩虹表攻击
  5. 定期评估：随着密码学研究的进展，需定期评估所使用算法的安全性，及时迁移到更安全的算法

参考