第二十章 哈希

散列函数

20.1 哈希函数概述

什么是哈希函数

哈希函数（Hash Function）是一种将任意长度的输入数据映射为固定长度输出数据的函数。这个固定长度的输出通常被称为哈希值（Hash Value）、摘要（Digest）或指纹（Fingerprint）。无论输入数据是一个字节还是数个 TB，哈希函数始终输出相同长度的结果。

从数学角度来看，哈希函数可以定义为：

$$H: {0,1}^* \to {0,1}^n$$

其中，${0,1}^*$ 表示任意长度的二进制串集合，${0,1}^n$ 表示长度为 $n$ 的二进制串集合。例如，SHA-256 的输出长度 $n = 256$。

哈希函数的核心性质

一个合格的哈希函数通常需要满足以下核心性质：

其中，抗碰撞性又分为两种：

• 弱抗碰撞性：给定一个输入 $x$，很难找到另一个不同的输入 $y$ 使得 $H(x) = H(y)$。
• 强抗碰撞性：很难找到任意两个不同的输入 $x \neq y$ 使得 $H(x) = H(y)$。

对于密码学应用，通常要求满足强抗碰撞性。根据生日攻击理论，对于一个 $n$ 位输出的哈希函数，找到碰撞的期望尝试次数约为 $\sqrt{2^n}$。因此，SHA-256（256 位输出）的安全性远高于 MD5（128 位输出）。

哈希函数的分类

哈希函数按用途可分为两大类：

1. 非加密哈希（Non-cryptographic Hash）：追求速度，用于哈希表、数据校验、布隆过滤器等场景。不要求抗碰撞性等密码学安全性质。
2. 加密哈希（Cryptographic Hash）：追求安全性，用于密码存储、数字签名、消息认证等场景。必须满足单向性和抗碰撞性。

// 非加密哈希 vs 加密哈希的简单对比示例
use std::collections::HashMap;
use sha2::{Sha256, Digest};

fn main() {
    // 非加密哈希：HashMap 内部使用 SipHash
    let mut map = HashMap::new();
    map.insert("key1", "value1");
    println!("HashMap 查找 key1: {:?}", map.get("key1"));

    // 加密哈希：SHA-256
    let mut hasher = Sha256::new();
    hasher.update(b"hello world");
    let result = hasher.finalize();
    println!("SHA-256('hello world') = {}", hex::encode(result));
}

20.2 非加密哈希

非加密哈希函数的设计目标是速度优先，通常用于不需要密码学安全性的场景。它们不保证抗碰撞性，但在正常使用中碰撞概率极低。

主要用途

• 哈希表：将键映射到桶（bucket）中，实现快速查找
• 数据校验：检测数据传输中的错误
• 布隆过滤器：高效的概率型数据结构
• 负载均衡：一致性哈希（Consistent Hashing）
• 指纹识别：快速判断两个数据块是否相同

CRC32

CRC32（Cyclic Redundancy Check，循环冗余校验）是一种基于多项式除法的校验算法，广泛用于网络通信和文件校验。其原理是将数据视为一个大的二进制多项式，除以一个预定义的生成多项式，余数即为 CRC 值。

CRC32 的数学原理：将输入数据 $M(x)$ 视为多项式，生成多项式为 $G(x)$，则：

$$CRC(M) = M(x) \cdot x^{32} \mod G(x)$$

常用的 CRC32 生成多项式为：

$$G(x) = x^{32} + x^{26} + x^{23} + x^{22} + x^{16} + x^{12} + x^{11} + x^{10} + x^8 + x^7 + x^5 + x^4 + x^2 + x + 1$$

// Cargo.toml: crc32fast = "1"
use crc32fast::Hasher;

fn main() {
    let mut hasher = Hasher::new();
    hasher.update(b"hello world");
    let checksum = hasher.finalize();
    println!("CRC32('hello world') = {:08x}", checksum);
}

MurmurHash

MurmurHash 是一种非加密哈希算法，由 Austin Appleby 创建。名字来源于 “multiply” 和 “rotate” 两个操作的组合。它速度快、分布均匀，但不提供加密安全性。MurmurHash 有多个版本（MurmurHash1/2/3），其中 MurmurHash3 最为常用。

SipHash

SipHash 是一种快速但“密码学强度“的伪随机函数，由 Aumasson 和 Bernstein 设计。SipHash is a fast but ‘cryptographically strong’ pseudo-random function by Aumasson and Bernstein.

Rust 的 HashMap 和 HashSet 默认使用 SipHash 作为哈希算法，这是 Rust 标准库的一个重要安全设计决策。SipHash 能够有效抵抗 HashDoS（哈希碰撞拒绝服务）攻击，攻击者无法通过构造特定输入来制造大量哈希碰撞。

// Rust 标准库 HashMap 默认使用 SipHash
use std::collections::HashMap;
use std::hash::{Hash, Hasher};
use std::collections::hash_map::DefaultHasher;

fn get_hash<T: Hash>(t: &T) -> u64 {
    let mut s = DefaultHasher::new();
    t.hash(&mut s);
    s.finish()
}

fn main() {
    let hash1 = get_hash(&"hello");
    let hash2 = get_hash(&"world");
    println!("SipHash(\"hello\") = {}", hash1);
    println!("SipHash(\"world\") = {}", hash2);

    // HashMap 内部自动使用 SipHash
    let mut scores = HashMap::new();
    scores.insert("Alice", 95);
    scores.insert("Bob", 87);
    println!("scores: {:?}", scores);
}

XxHash / XXH3

XxHash 是一种非常快速的非加密哈希算法，由 Yann Collet 设计。XXH3 是其最新版本，在大数据量场景下性能极为出色。

twox-hash 是 XxHash 的 Rust 实现，XxHash是一种非常快速的哈希算法。

// Cargo.toml: xxhash-rust = { version = "0.8", features = ["xxh3"] }
use xxhash_rust::xxh3::xxh3_128;

fn main() {
    let hash = xxh3_128(b"hello world");
    println!("XXH3-128('hello world') = {:016x}", hash);
}

HighwayHash

HighwayHash 是 Google 开发的一种高速哈希算法，设计目标是能够在短字符串和长字符串上都达到极高的吞吐量。它支持 64 位、128 位和 256 位输出。

highway-rs 是 HighwayHash 的 Rust 实现。

// Cargo.toml dependencies:
// highway = "1"

use highway::{HighwayHash, HighwayHasher, Key};

fn main() {
    // Generate 128bit hash
    let key = Key([1, 2, 3, 4]);
    let mut hasher128 = HighwayHasher::new(key);
    hasher128.append(&[255]);
    let res128: [u64; 2] = hasher128.finalize128();
    println!("128-bit hash: {:?}", res128);
    assert_eq!([0xbb007d2462e77f3c, 0x224508f916b3991f], res128);
    println!("128-bit hash assertion passed!");

    // Generate 256bit hash
    let key = Key([1, 2, 3, 4]);
    let mut hasher256 = HighwayHasher::new(key);
    hasher256.append(&[255]);
    let res256: [u64; 4] = hasher256.finalize256();
    println!("256-bit hash: {:?}", res256);
    let expected: [u64; 4] = [
        0x7161cadbf7cd70e1,
        0xaac4905de62b2f5e,
        0x7b02b936933faa7,
        0xc8efcfc45b239f8d,
    ];
    assert_eq!(expected, res256);
    println!("256-bit hash assertion passed!");
}

非加密哈希算法对比

20.3 加密哈希

加密哈希函数（Cryptographic Hash Function）是密码学中的核心原语，除了满足哈希函数的基本性质外，还必须具备单向性和抗碰撞性等安全性质。

主要用途

• 密码存储：存储用户密码的哈希值而非明文
• 数字签名：对消息摘要进行签名，提高效率
• 数据完整性：验证文件或消息是否被篡改
• 消息认证：结合密钥生成消息认证码（MAC）
• 区块链：工作量证明、区块链接

MD5

MD5（Message-Digest Algorithm 5）由 Ronald Rivest 于 1991 年设计，输出 128 位（16 字节）哈希值。MD5 曾广泛用于文件校验和数字签名，但现已不安全——2004 年王小云教授团队发现了 MD5 的碰撞攻击方法，此后 MD5 不再被推荐用于任何安全敏感场景。

// Cargo.toml: md-5 = "0.10"
use md5::{Md5, Digest};

fn main() {
    let mut hasher = Md5::new();
    hasher.update(b"hello world");
    let result = hasher.finalize();
    println!("MD5('hello world') = {}", hex::encode(result));
    // 输出: 5eb63bbbe01eeed093cb22bb8f5acdc3
}

SHA 系列

SHA256（Secure Hash Algorithm）是美国国家安全局（NSA）设计的一系列加密哈希算法，由 NIST 发布为联邦信息处理标准（FIPS）。

SHA-256 是目前最广泛使用的加密哈希算法之一。其处理流程包括：

1. 消息填充：在消息末尾添加填充位，使消息长度满足 $L \equiv 448 \pmod{512}$
2. 附加长度：追加原始消息的 64 位长度值
3. 分块处理：将填充后的消息分为 512 位的块
4. 压缩函数：每个块经过 64 轮压缩运算，更新 8 个 32 位的工作变量
5. 输出拼接：最终将 8 个工作变量拼接为 256 位输出

// Cargo.toml: sha2 = "0.10"
use sha2::{Sha256, Sha512, Digest};

fn main() {
    // SHA-256
    let mut hasher256 = Sha256::new();
    hasher256.update(b"hello world");
    let result256 = hasher256.finalize();
    println!("SHA-256('hello world') = {}", hex::encode(result256));

    // SHA-512
    let mut hasher512 = Sha512::new();
    hasher512.update(b"hello world");
    let result512 = hasher512.finalize();
    println!("SHA-512('hello world') = {}", hex::encode(result512));
}

SHA-3 / Keccak

SHA3（Keccak）是 NIST 在 2015 年发布的最新加密哈希标准，采用与 SHA-2 完全不同的海绵结构（Sponge Construction）。

海绵结构的核心是一个固定宽度的置换函数 $f$，其处理过程为：

1. 吸收阶段（Absorbing）：将输入消息分块后与状态进行异或，然后应用置换函数 $f$
2. 挤压阶段（Squeezing）：从状态中提取输出

$$Keccakr, c, d = Sponge[f, pad, r](M, d)$$

其中 $r$ 为比特率（rate），$c$ 为容量（capacity），$d$ 为输出长度。安全性与容量 $c$ 成正比。

// Cargo.toml: sha3 = "0.10"
use sha3::{Sha3_256, Digest};

fn main() {
    let mut hasher = Sha3_256::new();
    hasher.update(b"hello world");
    let result = hasher.finalize();
    println!("SHA3-256('hello world') = {}", hex::encode(result));
}

BLAKE3

BLAKE3 是 BLAKE2 的继任者，由 Jean-Philippe Aumasson、Samuel Neves、Zooko Wilcox-O’Hearn 和 Christian Winnerlein 设计。BLAKE3 的特点包括：

• 极高性能：在多核 CPU 上可达到每秒数十 GB 的哈希速度
• 并行化设计：基于 Merkle 树结构，天然支持并行计算
• 多功能：支持哈希、密钥派生（KDF）、可扩展输出（XOF）
• 安全性：基于 BLAKE2s 的安全证明

// Cargo.toml: blake3 = "1"
use blake3::Hasher;

fn main() {
    // 基本哈希
    let hash = blake3::hash(b"hello world");
    println!("BLAKE3('hello world') = {}", hash);

    // 流式哈希
    let mut hasher = Hasher::new();
    hasher.update(b"hello ");
    hasher.update(b"world");
    let hash = hasher.finalize();
    println!("BLAKE3(streaming) = {}", hash);

    // 密钥派生
    let key = blake3::derive_key("my-app-key", b"some-derivation-context");
    println!("Derived key: {}", hex::encode(key.as_bytes()));
}

SM3

SM3 是中国国家密码管理局发布的密码杂凑算法，属于国密（SM）标准体系的一部分。SM3 输出 256 位哈希值，安全性 comparable to SHA-256，在金融、政务等场景中被广泛使用。

#![allow(unused)]
fn main() {
// 使用 OpenSSL 命令行计算 SM3
// openssl sm3 Rust实战配套代码.zip
}

// Cargo.toml: sm3 = "0.4"
use sm3::{Sm3, Digest};

fn main() {
    let mut hasher = Sm3::new();
    hasher.update(b"hello world");
    let result = hasher.finalize();
    println!("SM3('hello world') = {}", hex::encode(result));
}

加密哈希算法对比

20.4 消息认证码（MAC）

MAC(Message Authentication Code, 消息认证码) 是一种带密钥的哈希函数，用于验证消息的完整性和真实性。与普通哈希不同，MAC 需要一个密钥，只有拥有密钥的人才能生成和验证 MAC 值。

GMAC (Galois message authentication code mode, 伽罗华消息认证码) 是 MAC 的一种实现方式，基于伽罗华域（Galois Field）的乘法运算，常与 AES 结合形成 GCM（Galois/Counter Mode）认证加密模式。

HMAC 原理

HMAC（Hash-based MAC）是最常用的 MAC 构造方法，其定义为：

$$HMAC(K, m) = H\big((K’ \oplus opad) \parallel H((K’ \oplus ipad) \parallel m)\big)$$

其中：

• $H$ 是底层哈希函数（如 SHA-256）
• $K$ 是密钥
• $K’$ 是从 $K$ 派生的密钥（若 $K$ 长度超过块大小则先哈希，否则右端补零）
• $ipad$（inner padding）是重复块大小次的 $0x36$
• $opad$（outer padding）是重复块大小次的 $0x5c$
• $\parallel$ 表示拼接操作
• $\oplus$ 表示异或操作

HMAC 的计算过程分为两步：

1. 内层哈希：计算 $H((K’ \oplus ipad) \parallel m)$
2. 外层哈希：计算 $H((K’ \oplus opad) \parallel \text{内层结果})$

// Cargo.toml: hmac = "0.12", sha2 = "0.10", hex = "0.4"
use hmac::{Hmac, Mac};
use sha2::Sha256;

type HmacSha256 = Hmac<Sha256>;

fn main() {
    // 创建 HMAC-SHA256
    let mut mac = HmacSha256::new_from_slice(b"my-secret-key")
        .expect("HMAC can take key of any size");
    mac.update(b"hello world");
    let result = mac.finalize();
    println!("HMAC-SHA256 = {}", hex::encode(result.into_bytes()));

    // 验证 HMAC
    use hmac::Mac;
    let mut mac2 = HmacSha256::new_from_slice(b"my-secret-key").unwrap();
    mac2.update(b"hello world");
    mac2.verify(result.into_bytes()).expect("HMAC verification failed");
    println!("HMAC verification passed!");
}

GMAC / GCM 模式

GCM（Galois/Counter Mode）是一种同时提供加密和认证的模式，其中的认证部分使用 GMAC。GCM 模式广泛应用于 TLS 1.2/1.3、IPsec 等协议中。

// Cargo.toml: aes-gcm = "0.10"
use aes_gcm::{Aes256Gcm, Key, Nonce};
use aes_gcm::aead::{Aead, KeyInit};

fn main() {
    let key = Key::<Aes256Gcm>::from_slice(b"an example very very secret key!");
    let cipher = Aes256Gcm::new(key);
    let nonce = Nonce::from_slice(b"unique nonce"); // 96-bits; unique per message

    let ciphertext = cipher.encrypt(nonce, b"plaintext message".as_ref())
        .expect("encryption failure");
    println!("Ciphertext: {}", hex::encode(&ciphertext));

    let plaintext = cipher.decrypt(nonce, ciphertext.as_ref())
        .expect("decryption failure");
    println!("Plaintext: {}", String::from_utf8_lossy(&plaintext));
}

20.5 哈希在实际应用中的签名验证

在实际的互联网应用中，哈希函数常用于 API 签名验证。签名验证的核心流程是：将请求参数按规则排序、拼接后追加密钥，再进行哈希运算，将得到的签名值与请求中携带的签名进行比对。

支付宝签名验证

以下是一个完整的支付宝签名验证实现，支持 MD5 和 SHA256 两种签名方式：

// Cargo.toml dependencies:
// md-5 = "0.10"
// sha2 = "0.10"
// digest = "0.10"
// chrono = { version = "0.4", features = ["clock"] }
// lazy_static = "1"
use md5::Md5;
use sha2::Sha256;
use digest::Digest;
use std::collections::HashMap;
use chrono::Utc;
use lazy_static::lazy_static;

const ALIPAY_SIGN_SECRET_KEY: &str = "abcdefgh";

lazy_static! {
    static ref SUPPORT_SIGN_TYPE: Vec<&'static str> = vec!["MD5", "SHA256"];
}

pub fn verify_alipay_sign(params_map: HashMap<String, String>) -> Result<bool, &'static str> {
    params_map.get("timestamp").expect("required timestamp");
    let sign_type = params_map.get("sign_type").expect("required sign_type");
    let sign_type_str = sign_type.as_str();

    if !SUPPORT_SIGN_TYPE.contains(&sign_type_str) {
        return Err("not support this sign type");
    }
    params_map.get("sign").expect("required sign");

    let mut keys: Vec<&String> = params_map
        .keys()
        .filter(|k| *k != "sign" && *k != "sign_type")
        .collect();
    keys.sort();

    let mut params_str = String::new();
    for key in &keys {
        if let Some(value) = params_map.get(*key) {
            params_str.push_str(&format!("{}={}&", key, value));
        }
    }
    params_str.push_str(ALIPAY_SIGN_SECRET_KEY);

    let sign = compute_sign(sign_type_str, &params_str);

    if let Some(param_sign) = params_map.get("sign") {
        Ok(*param_sign == sign)
    } else {
        Ok(false)
    }
}

fn compute_sign(sign_type: &str, data: &str) -> String {
    if sign_type == "MD5" {
        let mut md = Md5::new();
        md.update(data.as_bytes());
        md.finalize().iter().map(|b| format!("{:02x}", b)).collect()
    } else if sign_type == "SHA256" {
        let mut sha256 = Sha256::new();
        sha256.update(data.as_bytes());
        sha256.finalize().iter().map(|b| format!("{:02x}", b)).collect()
    } else {
        String::new()
    }
}

fn alipay_sign() {
    let mut params_map = HashMap::<String, String>::new();

    params_map.insert("service".to_string(), "api-demo".to_string());
    params_map.insert("partner".to_string(), "2088101568338364".to_string());
    params_map.insert(
        "timestamp".to_string(),
        Utc::now().timestamp_millis().to_string(),
    );

    let mut keys: Vec<&String> = params_map
        .keys()
        .filter(|k| *k != "sign" && *k != "sign_type")
        .collect();
    keys.sort();

    let mut params_str = String::new();
    for key in &keys {
        if let Some(value) = params_map.get(*key) {
            params_str.push_str(&format!("{}={}&", key, value));
        }
    }
    params_str.push_str(ALIPAY_SIGN_SECRET_KEY);

    println!("params_str=>{}", params_str);

    let sign_type = SUPPORT_SIGN_TYPE[1]; // "SHA256"
    let sign = compute_sign(sign_type, &params_str);
    println!("sign=>{}", sign);

    params_map.insert("sign_type".to_string(), sign_type.to_string());
    params_map.insert("sign".to_string(), sign);

    let ok = verify_alipay_sign(params_map);
    println!("verify_alipay_sign : {:?}", ok);

    // 测试不支持的签名类型
    let mut params_map2 = HashMap::<String, String>::new();
    params_map2.insert("sign_type".to_string(), "SHA512".to_string());
    params_map2.insert(
        "timestamp".to_string(),
        Utc::now().timestamp_millis().to_string(),
    );
    let result = verify_alipay_sign(params_map2);
    println!("SHA512 (unsupported) result: {:?}", result);
    assert!(result.is_err(), "Expected error for unsupported SHA512");
    println!("All tests passed!");
}

fn main() {
    alipay_sign();
}

签名流程详解

上述支付宝签名验证的完整流程如下：

1. 参数收集：获取所有请求参数（HashMap<String, String>）
2. 参数过滤：排除 sign 和 sign_type 字段
3. 参数排序：将剩余参数按 key 的字母序升序排列
4. 参数拼接：按 key=value& 格式拼接所有参数
5. 追加密钥：在拼接字符串末尾追加签名密钥
6. 哈希计算：根据 sign_type 选择 MD5 或 SHA256 计算哈希值
7. 签名比较：将计算得到的签名与请求中携带的签名进行比对

微信支付签名简介

微信支付的签名流程与支付宝类似，但使用的是 MD5 或 HMAC-SHA256，并且签名串的构造方式略有不同。微信支付 v3 API 使用 SHA256-RSA2048 签名，签名串的构造格式为：

HTTP请求方法\n
URL路径\n
时间戳\n
随机字符串\n
请求报文主体\n

然后使用商户的 RSA 私钥对签名串进行签名，接收方使用商户的 RSA 公钥进行验签。

20.6 哈希的常见应用场景

数据完整性校验

哈希函数最常见的用途之一是验证数据的完整性。下载文件时，发布方通常会提供文件的哈希值（如 SHA-256），用户下载后可以重新计算哈希值并与发布方提供的值比对，确认文件未被篡改。

use sha2::{Sha256, Digest};
use std::fs::File;
use std::io::{self, Read};

fn compute_file_hash(path: &str) -> Result<String, io::Error> {
    let mut file = File::open(path)?;
    let mut hasher = Sha256::new();
    let mut buffer = [0u8; 8192];
    loop {
        let n = file.read(&mut buffer)?;
        if n == 0 { break; }
        hasher.update(&buffer[..n]);
    }
    Ok(hex::encode(hasher.finalize()))
}

fn main() -> Result<(), io::Error> {
    let hash = compute_file_hash("Cargo.toml")?;
    println!("SHA-256(Cargo.toml) = {}", hash);
    Ok(())
}

密码存储（加盐哈希）

存储用户密码时，绝对不能存储明文密码，也不应直接存储密码的哈希值（容易被彩虹表攻击）。正确的做法是使用加盐哈希（Salted Hash）：

$$\text{stored} = H(password \parallel salt)$$

其中 $salt$ 是一个随机生成的值，每个用户的 salt 都不同。更推荐的做法是使用专门的密码哈希算法如 bcrypt、scrypt 或 Argon2，它们内置了 salt 管理并增加了计算成本以抵抗暴力破解。

// Cargo.toml: bcrypt = "0.15"
use bcrypt::{hash, verify, DEFAULT_COST};

fn main() -> Result<(), bcrypt::BcryptError> {
    let password = "my-secret-password";

    // 哈希密码（自动生成 salt）
    let hashed = hash(password, DEFAULT_COST)?;
    println!("Hashed password: {}", hashed);

    // 验证密码
    let valid = verify(password, &hashed)?;
    println!("Password valid: {}", valid);

    let invalid = verify("wrong-password", &hashed)?;
    println!("Wrong password valid: {}", invalid);

    Ok(())
}

数字签名

数字签名是公钥密码学与哈希函数的结合。发送方用自己的私钥对消息的哈希值进行签名，接收方用发送方的公钥验证签名。由于哈希函数将任意长度的消息压缩为固定长度，数字签名只需要对短得多的哈希值进行运算，大大提高了效率。

数字签名的流程：

1. 发送方计算消息的哈希值：$h = H(m)$
2. 发送方用私钥签名：$\sigma = Sign_{sk}(h)$
3. 接收方用公钥验证：$Verify_{pk}(h, \sigma)$

布隆过滤器

布隆过滤器（Bloom Filter）是一种空间高效的概率型数据结构，用于判断一个元素是否属于某个集合。它使用多个哈希函数将元素映射到位数组中。布隆过滤器可能产生假阳性（误判为存在），但不会产生假阴性（不会漏判）。

对于 $m$ 位的位数组和 $k$ 个哈希函数，插入 $n$ 个元素后，假阳性概率为：

$$P(\text{false positive}) \approx \left(1 - e^{-kn/m}\right)^k$$

// Cargo.toml: bloom = "0.3"
use bloom::Bloom;

fn main() {
    let mut bloom = Bloom::new_for_fp_rate(1000, 0.01);

    bloom.insert("hello");
    bloom.insert("world");

    println!("Contains 'hello': {}", bloom.contains(&"hello")); // true
    println!("Contains 'world': {}", bloom.contains(&"world")); // true
    println!("Contains 'rust':  {}", bloom.contains(&"rust"));  // 可能 false（假阳性概率约1%）
}

Git 版本控制（SHA-1 内容寻址）

Git 使用 SHA-1 哈希作为内容寻址的基础。Git 中的每个对象（blob、tree、commit）都通过其内容的 SHA-1 哈希值来标识，这个哈希值被称为 object ID（OID）。这种设计保证了：

• 相同内容必定产生相同的哈希值（数据去重）
• 不同内容几乎不可能产生相同的哈希值（数据完整性）
• 任何内容的修改都会导致哈希值变化（变更追踪）

// Cargo.toml: sha1 = "0.10"
use sha1::{Sha1, Digest};

fn main() {
    let mut hasher = Sha1::new();
    hasher.update(b"hello world");
    let result = hasher.finalize();
    println!("SHA-1('hello world') = {}", hex::encode(result));
}

注意：虽然 SHA-1 在理论上已被破解，但 Git 仍在使用它。Git 社区正在逐步迁移到 SHA-256（Git v2.29+ 开始支持 SHA-256 对象格式）。

20.7 总结

加密哈希 vs 非加密哈希对比

算法选择建议

关键要点

1. 不要用 MD5 或 SHA-1 做任何安全相关的事情，它们已被破解。
2. Rust 的 HashMap 默认使用 SipHash，这是一个优秀的安全设计决策。
3. 密码存储请使用 bcrypt/Argon2，不要自己实现加盐哈希。
4. API 签名验证是哈希函数在互联网应用中最常见的实际用途之一。
5. BLAKE3 是目前综合性能最好的加密哈希算法，适合新项目使用。
6. 非加密哈希和加密哈希的用途完全不同，选择时务必根据场景判断。

20.8 练习题

练习 1：基础概念

请解释哈希函数的“雪崩效应“，并编写一个 Rust 程序，计算 hello 和 hellp（仅一个字母不同）的 SHA-256 哈希值，统计两个哈希值中有多少位不同。

练习 2：非加密哈希性能对比

使用 crc32fast、xxhash-rust 和 highway 三个 crate，分别对 1MB 的随机数据进行哈希计算，测量并比较它们的耗时。使用 std::time::Instant 进行计时。

练习 3：实现简单文件校验工具

编写一个 Rust 命令行工具，接受文件路径作为参数，计算并输出该文件的 SHA-256 哈希值。要求支持流式读取大文件（不要一次性读入内存）。

练习 4：HMAC 签名与验证

编写一个 Rust 程序，实现以下功能：

• 使用 HMAC-SHA256 对消息 "transfer 1000 to account A" 进行签名
• 使用相同的密钥验证签名
• 使用不同的密钥验证签名（预期失败）

练习 5：密码存储系统

使用 bcrypt crate 实现一个简单的用户注册和登录系统：

• 注册时对密码进行 bcrypt 哈希
• 登录时验证密码是否正确
• 测试错误密码是否能通过验证

练习 6：理解碰撞概率

根据生日攻击理论，对于输出长度为 $n$ 位的哈希函数，找到碰撞的期望尝试次数约为 $\sqrt{2^n}$。请计算：

• MD5（128位）的碰撞期望次数
• SHA-256（256位）的碰撞期望次数
• SHA-256 的碰撞难度是 MD5 的多少倍？

练习 7：API 签名扩展

基于本章的支付宝签名验证代码，扩展 SUPPORT_SIGN_TYPE 以支持 HMAC-SHA256 签名方式。要求：

• 添加 HMAC-SHA256 到支持的签名类型列表
• 在 compute_sign 函数中实现 HMAC-SHA256 签名逻辑
• 编写测试验证新签名类型的正确性

练习 8：布隆过滤器实现

不使用第三方布隆过滤器库，使用 Rust 标准库中的 Vec<bool> 和两个不同的哈希函数（如 SipHash 的不同种子），手动实现一个简单的布隆过滤器。要求支持 insert 和 contains 操作，并测试其假阳性率。

参考链接

Hash 算法

• MD5
• SHA256
• SHA3
• SipHash SipHash is a fast but ‘cryptographically strong’ pseudo-random function by Aumasson and Bernstein.
• highwayhash
• highway-rs
• twox-hash XxHash是一种非常快速的哈希算法
• BLAKE3
• XxHash 非常快速的非加密哈希算法
• SM3 SM3密码杂凑算法

CRC32 循环冗余校验