密码学基石：哈希函数与公钥密码体系 | Cryptographic Foundations: Hash Functions and Public Key Cryptography

密码学基石：哈希函数与公钥密码体系 | Cryptographic Foundations: Hash Functions and Public Key Cryptography

现代区块链系统的安全性建立在坚实的密码学基础之上。在中本聪于2008年发表比特币白皮书之前，分布式账本与密码学的结合已历经数十年的理论探索与技术演进。区块链之所以能够实现去中心化环境下的可信交易验证与不可篡改的账本维护，根本原因在于它有效整合了密码学哈希函数的抗碰撞特性与公钥密码体系的身份认证机制。这两项密码学原语构成了区块链技术信任大厦的基石——前者确保数据的完整性校验与工作量证明的可验证性，后者则实现了去中心化环境下的身份确权与交易授权。本章将系统阐述这两类密码学原语的数学原理、算法实现及其在区块链系统中的关键应用，同时前瞻性地探讨后量子时代密码学面临的挑战与应对策略。

1.1 密码学哈希函数：信息安全的瑞士军刀 | Cryptographic Hash Functions: The Swiss Army Knife of Information Security

密码学哈希函数是现代信息安全体系中最基础也最不可或缺的密码学原语之一。与普通哈希函数仅关注数据映射与查找效率不同，密码学哈希函数必须满足一系列严格的安全属性，使其能够在数字签名、消息认证、数据完整性校验等安全协议中发挥关键作用。在区块链系统中，哈希函数被广泛应用于区块链接力、工作量证明、默克尔树构建以及地址生成等核心环节，其安全性直接关系到整个区块链网络的可信性与健壮性。

1.1.1 哈希函数的数学定义与基本性质 | Mathematical Definition and Basic Properties of Hash Functions

从数学角度而言，哈希函数（Hash Function）$H$ 是一个将任意长度的输入消息 $m$ 映射为固定长度输出摘要的函数：

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

其中 $\{0,1\}^*$ 表示所有有限长度的二进制串集合，$\{0,1\}^n$ 表示长度为 $n$ 位的二进制串集合。对于密码学哈希函数，输出长度 $n$ 通常选取为128位、160位、256位或512位等标准值。以比特币系统中使用的SHA-256为例，其输出长度为256位；而以太坊采用的Keccak-256同样输出256位哈希值。

密码学哈希函数必须满足以下三个核心安全属性，这些属性构成了其在安全协议中应用的理论基础：

原像抗性（Preimage Resistance）是哈希函数最基本的单向性要求。给定一个哈希值 $h$，计算上不可找到满足 $H(m) = h$ 的任意消息 $m$。换言之，哈希函数必须是一个“单向函数”——易于计算正向映射，但难以通过逆向运算恢复原始输入。这一属性确保了哈希函数可用于密码存储场景：系统仅保存用户密码的哈希值而非明文，即使攻击者获取了哈希数据库也无法恢复出原始密码。在区块链中，原像抗性保证了哈希指针的安全性——给定区块的哈希值，攻击者无法逆向推算出区块内容。

原像抗性的计算困难性可形式化定义为：对于任意给定输出 $h$，寻找满足 $H(m) = h$ 的输入 $m$ 的最优算法时间复杂度应为 $\Theta(2^n)$，其中 $n$ 为哈希值位数。这意味着攻击者只能通过暴力枚举所有可能的输入来寻找原像，对于256位的哈希函数，这相当于在约$2^{256}$个可能输入中进行搜索——这一数量远超宇宙中原子总数的估计值（约为$10^{80} \approx 2^{266}$）。

第二原像抗性（Second Preimage Resistance）要求对于给定消息 $m_1$，计算上不可找到另一个不同消息 $m_2$ 使得 $H(m_1) = H(m_2)$。即对于已知的输入输出对 $(m_1, H(m_1))$，攻击者无法找到与之产生相同哈希值的另一输入。这一属性确保了哈希函数在数字签名等协议中的实用性——签名者对消息 $m_1$ 的签名不能被攻击者通过寻找另一消息 $m_2$ 并声称是对 $m_2$ 的签名来伪造。在区块链语境下，第二原像抗性保证了一旦某区块内容被确认，攻击者无法构造出内容不同但哈希值相同的替代区块来篡改历史记录。

碰撞抗性（Collision Resistance）是三者中最强的安全属性。它要求计算上不可找到两个不同的消息 $m_1$ 和 $m_2$，使得 $H(m_1) = H(m_2)$。与第二原像抗性不同，攻击者在寻找碰撞时没有固定输入的约束，可以自由选择任何两个不同的消息来产生相同哈希值。碰撞抗性的满足意味着第二原像抗性必然满足（反之则不然），但实现碰撞抗性的技术难度更高。

根据密码学理论，由于哈希函数的输入空间远大于输出空间（对于$n$位输出，每个哈希值对应约$2^m/2^n$个原像），碰撞在数学上必然存在。碰撞抗性的意义在于保证这些碰撞在计算上不可找到——即寻找碰撞的最优算法时间复杂度应为 $\Theta(2^{n/2})$，这对应于著名的生日攻击（Birthday Attack）复杂度。之所以是$2^{n/2}$而非$2^n$，源于概率论中生日悖论现象：在$N$个可能的哈希值中寻找碰撞，当采样数量达到约$\sqrt{N}$时，发生碰撞的概率显著增加。对于256位哈希函数，这意味着在约$2^{128}$次尝试后就有可观概率发现碰撞。

1.1.2 SHA-256算法结构与实现原理 | Structure and Implementation of SHA-256

安全哈希算法256位（Secure Hash Algorithm 256-bit, SHA-256）是美国国家标准与技术研究院（NIST）于2002年标准化的密码学哈希函数，作为SHA家族中的重要成员在比特币及众多加密系统中得到广泛应用。理解SHA-256的算法结构有助于深入把握哈希函数的工程实现细节及其安全边界。

SHA-256属于基于Merkle-Damgård结构的迭代哈希函数，其设计哲学基于抗原像（Preimage Resistant）、抗碰撞（Collision Resistant）和雪崩效应（Avalanche Effect）三大安全目标。雪崩效应指输入的微小变化（如翻转一位）应导致输出的每一位以约50%的概率发生变化，这一特性保证了哈希值的伪随机特性，使得输出难以预测且与输入具有强相关性。

SHA-256算法的核心组成部分包括：消息预处理（Message Padding and Parsing）将任意长度消息转换为512位分块的迭代处理格式；初始化哈希值（Initial Hash Values）由前8个素数平方根的小数部分的前32位构成；64个常数（Round Constants）由前64个素数立方根的小数部分的前32位构成；以及64轮压缩函数（Compression Function）每轮采用不同的消息调度值与常数进行混合运算。

消息预处理阶段首先在消息末尾添加一位"1"，随后添加若干"0"直到消息长度≡448（mod 512），最后附加原始消息长度的64位大端序表示。这一padding机制确保每个消息都能表示为512位的整数倍分组，同时保证不同原始消息在padding后必然不同，从而避免碰撞攻击的一种可能路径。

预处理后的消息被划分为$N$个512位消息块 $M^{(1)}, M^{(2)}, \ldots, M^{(N)}$，每个消息块经过消息扩展（Message Expansion）生成64个32位字 $W_0, W_1, \ldots, W_{63}$，供64轮压缩函数使用。消息扩展的规则为：

$$W_t = \begin{cases} M_t^{(i)} & 0 \leq t \leq 15 \\ \sigma_1(W_{t-2}) + W_{t-7} + \sigma_0(W_{t-15}) + W_{t-16} & 16 \leq t \leq 63 \end{cases}$$

其中$\sigma_0$和$\sigma_1$是针对消息字的操作函数，分别定义为：

$$\sigma_0(x) = ROTR^7(x) + ROTR^{18}(x) + SHR^3(x)$$ $$\sigma_1(x) = ROTR^{17}(x) + ROTR^{19}(x) + SHR^{10}(x)$$

这里$ROTR^n(x)$表示将32位字$x$右旋$n$位，$SHR^n(x)$表示将$x$右移$n$位（左侧补0）。这些非线性操作确保了消息位的充分混合与扩散。

压缩函数的核心是64轮迭代，每轮使用6个逻辑函数与32位消息字及32位常数进行混合。第$t$轮的计算更新8个工作变量$a, b, c, d, e, f, g, h$：

$$T_1 = h + \Sigma_1(e) + Ch(e, f, g) + K_t + W_t$$ $$T_2 = \Sigma_0(a) + Maj(a, b, c)$$ $$h = g, \quad g = f, \quad f = e, \quad e = d + T_1$$ $$d = c, \quad c = b, \quad b = a, \quad a = T_1 + T_2$$

其中$Ch(x, y, z) = (x \wedge y) \oplus (\neg x \wedge z)$为选择函数，$Maj(x, y, z) = (x \wedge y) \oplus (x \wedge z) \oplus (y \wedge z)$为多数函数，$\Sigma_0$和$\Sigma_1$是针对哈希值的扩展函数：

$$\Sigma_0(x) = ROTR^2(x) + ROTR^{13}(x) + ROTR^{22}(x)$$ $$\Sigma_1(x) = ROTR^6(x) + ROTR^{11}(x) + ROTR^{25}(x)$$

所有64轮完成后，将8个工作变量加到当前哈希值上，得到新的哈希状态。处理完所有消息块后，输出的256位哈希值即为8个32位工作变量的级联。

以下Python实现展示了SHA-256的核心计算流程，有助于理解其工作原理：

```python import struct

SHA-256 Constants

K = [ 0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5, 0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5, 0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3, 0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174,

... 64 constants total

]

def rotr(x, n): return ((x >> n) | (x << (32 - n))) & 0xffffffff

def sigma0(x): return rotr(x, 7) ^ rotr(x, 18) ^ (x >> 3)

def sigma1(x): return rotr(x, 17) ^ rotr(x, 19) ^ (x >> 10)

def Sigma0(x): return rotr(x, 2) ^ rotr(x, 13) ^ rotr(x, 22)

def Sigma1(x): return rotr(x, 6) ^ rotr(x, 11) ^ rotr(x, 25)

def Ch(x, y, z): return (x & y) ^ (~x & z)

def Maj(x, y, z): return (x & y) ^ (x & z) ^ (y & z)

def sha256(message):

Initialize hash values (first 32 bits of fractional parts of square roots of first 8 primes)

h = [ 0x6a09e667, 0xbb67ae85, 0x3c6ef372, 0xa54ff53a, 0x510e527f, 0x9b05688c, 0x1f83d9ab, 0x5be0cd19 ]

Preprocessing: pad message

ml = len(message) * 8 message += b'\x80' while (len(message) % 64) != 56: message += b'\x00' message += struct.pack('>Q', ml)

Process each 512-bit (64-byte) block

for i in range(0, len(message), 64): block = message[i:i+64] w = [0] * 64

Copy block into first 16 words

for j in range(16): w[j] = struct.unpack('>I', block[j*4:j*4+4])[0]

Extend the first 16 words into remaining 48 words

for j in range(16, 64): w[j] = (sigma1(w[j-2]) + w[j-7] + sigma0(w[j-15]) + w[j-16]) & 0xffffffff

a, b, c, d, e, f, g, h_ = h[0], h[1], h[2], h[3], h[4], h[5], h[6], h[7]

64 rounds of compression

for j in range(64): t1 = (h_ + Sigma1(e) + Ch(e, f, g) + K[j] + w[j]) & 0xffffffff t2 = (Sigma0(a) + Maj(a, b, c)) & 0xffffffff h_ = g g = f f = e e = (d + t1) & 0xffffffff d = c c = b b = a a = (t1 + t2) & 0xffffffff

Add compressed chunk to current hash value

h[0] = (h[0] + a) & 0xffffffff h[1] = (h[1] + b) & 0xffffffff h[2] = (h[2] + c) & 0xffffffff h[3] = (h[3] + d) & 0xffffffff h[4] = (h[4] + e) & 0xffffffff h[5] = (h[5] + f) & 0xffffffff h[6] = (h[6] + g) & 0xffffffff h[7] = (h[7] + h_) & 0xffffffff

Produce final hash value

return b''.join(struct.pack('>I', x) for x in h) ```

1.1.3 Keccak-256与SHA-3家族：海绵结构的革命 | Keccak-256 and SHA-3 Family: The Sponge Construction Revolution

Keccak（Keccak Team发明的哈希函数家族）是NIST于2015年标准化的SHA-3哈希算法的基础，其设计采用了一种革命性的海绵结构（Sponge Construction），从根本上区别于SHA-256等基于Merkle-Damgård结构的传统哈希函数。以太坊从诞生之初便采用Keccak-256作为其默认哈希函数，这一选择在当时的密码学界引发了广泛讨论——以太坊选择Keccak而非最终标准化的SHA-3，体现了对算法本质的深刻理解与前瞻性考量。

海绵结构的核心思想将哈希函数的工作过程类比为一块海绵吸收并挤出水分的过程。算法维护一个$s$位的内部状态（对于Keccak-256，状态为1600位），通过吸收阶段（Absorbing Phase）将输入消息分组逐块混入状态，再通过挤出阶段（Squeezing Phase）从状态中逐块提取输出。这种优雅的结构使得Keccak可以产生任意长度的输出，同时提供了固化的理论安全性边界。

Keccak的1600位状态被组织为一个$5 \times 5 \times 64$的三维数组，每个元素为64位字。状态转换通过Keccak-$f$[1600]置换函数实现，该置换由24轮迭代组成，每轮包含五个步骤：$\theta$（异或相邻列以增强扩散）、$\rho$（对每个切片进行旋转移动）、$\pi$（重排平面位置以增加线性复杂度）、$\chi$（引入非线性5进制的类AES S盒操作）、$\iota$（与轮常数异或打破对称性）。

SHA-3与原始Keccak算法之间存在微妙的差异。NIST在标准化过程中对Keccak的参数进行了调整：在SHA-3标准FIPS 202中，输出长度被固定而非可配置，同时采用了不同的填充规则。这一差异意味着SHA3-256与Keccak-256的输出并不相同。以太坊选择Keccak-256而非等待SHA-3标准化，反映了其对算法安全性与成熟度的审慎评估——Keccak在SHA-3标准化竞争中脱颖而出前已在密码学社区经历了充分的分析与测试。

以下C++实现展示了Keccak-256的核心计算逻辑：

```cpp #