九思札记 · 探索区块链 · AI

graph TD
    H[密码学哈希函数<br/>H: {0,1}* → {0,1}^n]
    H --> P1[确定性<br/>同一输入必有同一输出]
    H --> P2[单向性<br/>(原像阻力)]
    H --> P3[碰撞阻力<br/>(Collision Resistance)]
    H --> P4[隐藏性<br/>(Hiding)]
    H --> P5[谜题友好性<br/>(Puzzle-Friendliness)]
    P2 --> P3
    P3 --> P4
    P4 --> P5
    style H fill:#bbdefb
    style P3 fill:#c8e6c9

2.1.1 精确的定义

密码学哈希函数（Cryptographic Hash Function）是一个确定性函数：

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

它将任意有限长度的二进制输入 $\{0,1\}^*$ 映射为固定长度的 $n$ 位输出。 $n$ 称为摘要长度或哈希位数，常见的取值有 256（SHA-256、Keccak-256）、384（SHA-384）、512（SHA-512）。

这一定义中有四个关键约束，缺一不可：

属性	精确表述	失效后果
确定性	$\forall x: H(x)$ 唯一确定	同一输入产生不同输出导致验证失败
压缩性	输出长度固定为 $n$ ，与输入长度无关	无法用于摘要
高效计算	对任意 $x$ ， $H(x)$ 可在多项式时间内计算	系统吞吐量为零
原像抗性（单向性）	给定 $y = H(x)$ ，在计算上不可行地找到任意 $x' = H(x') = y$	哈希可被"逆转"，承诺机制失效

关键区分："确定性"与"随机性"并不矛盾。 $H$ 本身是确定性的函数，但对于攻击者来说，在没有额外信息时， $H(x)$ 的行为必须如同随机函数（无法预测、无法逆推）。这就是密码学对"单向性"的严格表述。

2.1.2 碰撞阻力（Collision Resistance）

形式化定义

设 $\lambda$ 为安全参数（通常 $\lambda = 128$ ），如果对于任何概率多项式时间（PPT）敌手 $\mathcal{A}$ ：

\Pr\left[ (x_1, x_2) \gets \mathcal{A}(1^\lambda) : x_1 \neq x_2 \land H(x_1) = H(x_2) \right] \leq \text{negl}(\lambda)

其中 $\text{negl}(\lambda)$ 是一个关于 $\lambda$ 的可忽略函数（比任何多项式的倒数下降得更快）。则称 $H$ 具有碰撞阻力。

为什么碰撞阻力如此关键？

在数字签名中，我们不是对消息 $m$ 本身签名（因为 $m$ 可能很长），而是对 $H(m)$ 签名。如果攻击者能找到 $m_1 \neq m_2$ 使得 $H(m_1) = H(m_2)$ ，那么：

Alice 对 $H(m_1)$ 签名（她认可 $m_1$ ）。
攻击者截获签名，与 $m_2$ 组合。
Bob 验证： $H(m_2) = H(m_1)$ ，签名有效，但消息内容却变成了 $m_2$ 。

结论：签名伪造，信任体系崩塌。

生日攻击（Birthday Attack）与安全强度

寻找碰撞的直观暴力方法是：尝试随机输入 $x_1, x_2, \ldots$ ，记录所有 $H(x_i)$ ，直到发现重复。但这需要大约 $2^n$ 次尝试——远比实际需要多。

生日悖论（Birthday Paradox） 告诉我们：在一个 $N = 2^n$ 大小的输出空间中，只需约 $k \approx \sqrt{2N \ln 2} \approx 1.177\sqrt{N} \approx 2^{n/2}$ 次尝试，就能以 50% 概率找到碰撞。

推导：设 $k$ 次独立采样，没有碰撞的概率为：

P(\text{no collision}) = \prod_{i=0}^{k-1} \left(1 - \frac{i}{2^n}\right) \approx e^{-\sum_{i=0}^{k-1}\frac{i}{2^n}} \approx e^{-\frac{k(k-1)}{2 \cdot 2^n}} \approx e^{-\frac{k^2}{2^{n+1}}}

当 $k = 2^{n/2}$ 时， $P \approx e^{-1/2} \approx 0.607$ ；碰撞概率 $= 1 - 0.607 = 0.393$ （约 39%）。当 $k \approx 1.177 \cdot 2^{n/2}$ 时，碰撞概率恰好为 50%。

哈希算法	输出长度 $n$	碰撞安全（ $n/2$ ）	生日攻击尝试次数（约）
SHA-256	256 bit	128 bit	$2^{128} \approx 3.4 \times 10^{38}$
SHA-1	160 bit	80 bit	$2^{80} \approx 1.2 \times 10^{24}$
MD5	128 bit	64 bit	$2^{64} \approx 1.8 \times 10^{19}$ （实际已被攻破）

实际案例：2017 年 Google 与 CWI 联合宣布了对 SHA-1 的实际碰撞攻击，用 $2^{63}$ 次计算找到了 PDF 碰撞。现代密码学标准已废弃 SHA-1，MD5 更已被完全攻破。

TypeScript：生日攻击概率计算器

typescript

/**
 * 生日攻击概率计算器
 * 计算 k 次独立采样在 N = 2^n 空间中的碰撞概率
 */
function birthdayCollisionProb(n: number, k: number): number {
  const N = 2 ** n;
  // 精确公式: P(collision) = 1 - e^(-k*(k-1)/(2*N))
  const exp = -(k * (k - 1)) / (2 * N);
  return 1 - Math.exp(exp);
}

// 演示：SHA-256 输出空间 n=256，不同 k 值
console.log("=== 生日攻击概率分析 ===");
console.log(`n=256, k=2^100: P ≈ ${birthdayCollisionProb(256, 2**100).toExponential(2)}`);
console.log(`n=256, k=2^128: P ≈ ${birthdayCollisionProb(256, 2**128).toExponential(2)}`);
console.log(`n=256, k=2^140: P ≈ ${birthdayCollisionProb(256, 2**140).toExponential(2)}`);

// 类比：经典的 365 人生日问题
function birthdayClassic(people: number): number {
  return birthdayCollisionProb(Math.log2(365), people);
}
console.log("\n=== 经典生日悖论 ===");
[10, 23, 40, 50, 100].forEach(k => {
  console.log(` ${k} 人中至少一对同生日的概率:$ {birthdayClassic(k).toFixed(4)}`);
});

预期输出：

text

=== 生日攻击概率分析 ===
n=256, k=2^100: P ≈ 4.17e-48
n=256, k=2^128: P ≈ 0.39
n=256, k=2^140: P ≈ 1.00e+00

=== 经典生日悖论 ===
10 人中至少一对同生日的概率: 0.1169
23 人中至少一对同生日的概率: 0.5073
40 人中至少一对同生日的概率: 0.8912

关键结论： $2^{128}$ 次尝试（约等于全球所有沙粒的 $10^{18}$ 倍）在 SHA-256 上才有 ~39% 的碰撞概率。这在当前及可预见的计算能力下是计算不可行的。

2.1.3 隐藏性（Hiding）与承诺机制

形式化定义

隐藏性要求：给定 $y = H(x)$ ，对于未知且均匀分布的 $x$ ，任何 PPT 敌手在统计学意义上无法推断 $x$ 的任何部分信息。更严格地说， $H(x)$ 必须"看起来"与随机函数不可区分。

注意：如果 $x$ 的分布是有偏的（例如 $x$ 是从一个极小的集合中选择的），仅靠 $H(x)$ 的隐藏性不足以保证安全。此时需要引入盐值（Salt）： $c = H(r \parallel x)$ ，其中 $r$ 是均匀随机数。

承诺机制（Commitment Scheme）

承诺机制是密码学的核心原语，应用于密封拍卖、区块链时间锁定交易、零知识证明等场景。它是一个两阶段协议：

承诺阶段（Commit Phase）：承诺方选择值 $v$ ，生成随机数 $r \gets \{0,1\}^\lambda$ ，计算 $c = H(r \parallel v)$ ，将 $c$ 发送给验证方。
揭晓阶段（Reveal Phase）：承诺方公开 $(r, v)$ 。验证方验证 $c \stackrel{?}{=} H(r \parallel v)$ 。

该机制需要同时满足两个属性：

属性	保证	依赖的哈希属性
绑定性（Binding）	承诺方不能找到一个 $v' \neq v$ 使得 $H(r \parallel v') = c$	碰撞阻力
隐藏性（Hiding）	验证方在揭晓前无法推断 $v$	单向性 + 加盐随机性

TypeScript：密码学承诺机制实现

typescript

/**
 * 密码学承诺机制（Commitment Scheme）
 * 演示绑定性与隐藏性
 */
class CommitmentScheme {
  private salt: Uint8Array | null = null;
  private committedValue: string | null = null;
  private commitmentHash: string | null = null;

  // 承诺阶段：生成随机盐 + 计算 H(salt || value)
  commit(value: string, entropy: Uint8Array): string {
    // 真实的随机盐应由 CSPRNG 生成；这里用参数传入模拟
    this.salt = entropy;
    this.committedValue = value;
    this.commitmentHash = this._hash(this.salt, value);
    return this.commitmentHash;
  }

  // 揭晓阶段：公开 (salt, value)，验证方重算哈希比对
  reveal(): { salt: string; value: string; commitment: string } | null {
    if (!this.salt || !this.committedValue || !this.commitmentHash) return null;
    return {
      salt: this._bytesToHex(this.salt),
      value: this.committedValue,
      commitment: this.commitmentHash,
    };
  }

  // 验证承诺
  verify(saltHex: string, value: string, commitment: string): boolean {
    const salt = this._hexToBytes(saltHex);
    const recomputed = this._hash(salt, value);
    return recomputed === commitment;
  }

  // 简化的 SHA-256-like 32-byte hash (演示用，非安全实现)
  // 真实环境使用 2.2 节的完整实现或 crypto.subtle
  private _hash(salt: Uint8Array, value: string): string {
    const data = new TextEncoder().encode(this._bytesToHex(salt) + ":" + value);
    // 演示：用多个 round 的简单哈希模拟安全属性
    let h = 0x6a09e667;
    const k = [0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5];
    for (let i = 0; i < data.length; i++) {
      h = (h ^ data[i]) + k[i % 4] | 0;
      h = ((h << 7) | (h >>> 25)) + ((h << 15) | (h >>> 17));
    }
    // 扩展到 32 字节模拟
    let result = '';
    for (let i = 0; i < 8; i++) {
      const v = (h + i * 0x9e3779b9 | 0) >>> 0;
      result += v.toString(16).padStart(8, '0');
    }
    return result;
  }

  private _bytesToHex(bytes: Uint8Array): string {
    return Array.from(bytes).map(b => b.toString(16).padStart(2, '0')).join('');
  }
  private _hexToBytes(hex: string): Uint8Array {
    const bytes = new Uint8Array(hex.length / 2);
    for (let i = 0; i < bytes.length; i++) {
      bytes[i] = parseInt(hex.slice(i * 2, i * 2 + 2), 16);
    }
    return bytes;
  }
}

// --- 演示：Alice 承诺一个预测 ---
const scheme = new CommitmentScheme();
const prediction = "Bitcoin_price_over_100k_2025";
const salt = new Uint8Array([0x8a, 0x3f, 0x12, 0x9d, 0x54, 0xe7, 0x88, 0x01]); // 应随机生成

const commitment = scheme.commit(prediction, salt);
console.log(`承诺值: ${commitment}`);
// 验证方无法从 commitment 反推 prediction（隐藏性）

// 揭晓时
const reveal = scheme.reveal();
console.log(`\n揭晓: salt= ${reveal!.salt}, value=$ {reveal!.value}`);

// 验证
const isValid = scheme.verify(reveal!.salt, reveal!.value, commitment);
console.log(`验证结果: ${isValid}`);

// 尝试作弊：改变值
const isCheating = scheme.verify(reveal!.salt, "Different_value", commitment);
console.log(`作弊检测: ${isCheating}`);

2.1.4 谜题友好性（Puzzle-Friendliness）

形式化定义

设 $H$ 为哈希函数， $T \subseteq \{0,1\}^n$ 为一个"谜题目标集"（如"前 $d$ 位为 0 的所有输出"）， $|T| \ll 2^n$ 。如果对于任何输入分布，不存在比穷举搜索（从 $\{0,1\}^m$ 中随机选取 $x$ 计算 $H(x)$ ）更高效的方法找到满足 $H(x) \in T$ 的 $x$ ，则称 $H$ 具有谜题友好性。

与工作量证明的关系

比特币的 PoW 谜题可以精确表述为：

\text{找 } \text{nonce} \in \{0,1\}^{32} \text{ 使得 } H(\text{block_header} \parallel \text{nonce}) < T

其中 $T$ 是难度目标（一个远小于 $2^{256}$ 的数值）。满足条件的 expected 尝试次数为：

\frac{2^{256}}{T} = \text{难度值（Difficulty）}

如果 $H$ 不满足谜题友好性——即存在某种结构可以指导搜索（例如知道某些 nonce 范围更可能产生小输出），则矿工可以用远少于 "预期尝试次数" 的算力找到解，PoW 的安全性假设就崩塌了。

均匀分布假设

谜题友好性等价于要求：当输入 $x$ 是均匀随机的， $H(x)$ 必须在输出空间中均匀分布。 没有任何区域被"偏爱"或"避免"。这是对密码学哈希的统计学检验标准之一。

性质	核心含义	应用场景
碰撞阻力	找不到两个不同输入产生相同输出	数字签名、数据完整性
原像抗性	给定输出，找不到任何能生成它的输入	密码存储、承诺隐藏
第二原像抗性	给定 $x$ ，找不到 $x' \neq x$ 使得 $H(x) = H(x')$	防篡改保护
谜题友好性	唯一策略是均匀穷举	工作量证明、验证码

下节预告：2.2 将深入 SHA-256 和 Keccak-256 的内部结构，从零实现两种算法的完整流程，并通过雪崩效应（Avalanche Effect）实验验证"输入 1 位变化导致输出约 50% 位翻转"这一理想特性。

核心认知

哈希函数是密码学的瑞士军刀，碰撞阻力、隐藏性、谜题友好性分别从"防伪造""防泄露""防捷径"三个维度构建安全性。

安全强度由输出长度的一半决定。SHA-256 提供 128 位碰撞安全——不是 256 位，这是生日攻击的必然结果。

承诺机制是密码学中最优雅的协议之一。两阶段（承诺+揭晓）、两属性（绑定+隐藏），直接对应现实生活中的"密封信封"。

谜题友好性 = 均匀分布 + 无捷径。这是 PoW 挖矿的数学基础——如果存在捷径，算力优势就不存在，整个经济激励机制就失效。

本页目录

2.1.1 精确的定义

2.1.2 碰撞阻力（Collision Resistance）

形式化定义

为什么碰撞阻力如此关键？

生日攻击（Birthday Attack）与安全强度

TypeScript：生日攻击概率计算器

2.1.3 隐藏性（Hiding）与承诺机制

形式化定义

承诺机制（Commitment Scheme）

TypeScript：密码学承诺机制实现

2.1.4 谜题友好性（Puzzle-Friendliness）

形式化定义

与工作量证明的关系

均匀分布假设

核心认知

评论

发表评论