密码哈希函数

密码哈希把消息压成固定长度的短“指纹”：摘要容易从文件算出，却应难以反向恢复原像、替换成同指纹内容或找到任意碰撞。三种困难来自不同挑战接口，彼此在一般函数族上不自动推出。它是公开、无密钥的确定函数，所以不能单独提供消息来源认证；实际构造还要求域分离、无歧义编码和适当输出长度。

理想 $n$ 位哈希的碰撞搜索约需 $2^{n/2}$ 次、原像约需 $2^n$ 次。SHA-256 常用于完整性组件，但单独附加公开哈希不能阻止攻击者同时修改消息和哈希；抗碰撞也不会把无密钥哈希变成消息认证码。普通程序哈希表只追求速度和均匀分布，不必满足密码安全。

SHA-256 输出 $256$ bit；修改一个输入 bit 通常会大幅改变摘要，但“雪崩效应”只是设计现象，不等价于安全证明。校验下载文件时，若摘要来自可信渠道，可检测传输篡改；若攻击者能同时替换文件与网页上的摘要，普通哈希无法认证。

密码哈希不是密码存储的直接方案：快速哈希会帮助攻击者大规模猜测，应使用带盐、内存困难的专用 KDF。长度扩展等性质也使直接写 $H(k\Vert m)$ 不一定是安全 MAC，应使用 HMAC 等标准构造。

固定输入长度的压缩函数 $h:\{0,1{\}}^{b+n}\to \{0,1{\}}^n$ 只是构造部件；可变长哈希通常再用迭代结构、填充和域分离把它扩展到 ${\mathcal{M}}_{\lambda }$。随机预言机公理库随机预言机模型Random oracle model · ROM把所有参与者共享的哈希接口理想化为可自适应查询且响应一致的真随机函数。是所有参与者共享、响应一致且可自适应查询的理想随机函数；ROM 证明不会在选择某个现实哈希后自动变成标准模型定理。

密码哈希用于签名、承诺、口令派生、Merkle 树、内容寻址和消息认证构造。抗碰撞性公理库抗碰撞性Collision resistance高效对手找到两个不同输入具有相同哈希值的概率可忽略。是其核心性质，消息认证码公理库消息认证码Message authentication code · MAC用共享密钥生成并验证消息完整性标签的机制。在哈希上加入密钥实现认证；数字签名公理库数字签名Digital signature由私钥签名、公开验证并提供不可伪造性的认证机制。常采用 hash-then-sign，Merkle 树、内容寻址和承诺则依赖摘要绑定长数据。通用哈希公理库通用哈希Universal hashing · Universal hash family从函数族随机选择哈希函数，使任意预先固定的不同键对以至多 1/m 的概率碰撞。控制随机函数族对预先固定输入对的碰撞概率，可用于信息论 MAC 与提取器；它既不等于现实哈希的抗碰撞性，也不等于 ROM。