密码哈希函数

密码哈希把消息压成固定长度的短“指纹”：摘要容易从文件算出，却应难以反向恢复原像、替换成同指纹内容或找到任意碰撞。三种困难来自不同挑战接口，不能不加条件地互相替换。抗碰撞能排除相应高效可采样挑战分布下的第二原像攻击，因为先采样消息再调用攻击者即可制造碰撞；但抗原像性还取决于消息分布及压缩程度，不能只凭性质名称推出。它是公开、无密钥的确定函数，所以不能单独提供消息来源认证；实际构造还要求域分离、无歧义编码和适当输出长度。

对理想随机函数做经典查询，取 $q$ 个互异输入时共有 $q(q-1)/2$ 对可能碰撞；当 $q\ll 2^{n/2}$ 时，碰撞概率约为 $q(q-1)/2^{n+1}$。达到常数成功概率约需 $2^{n/2}$ 次查询，寻找一个独立随机目标的原像则约需 $2^n$ 次。这是理想模型中的通用攻击尺度，不是对任一现实哈希的无条件下界。SHA-256 常用于完整性组件，但单独附加公开哈希不能阻止攻击者同时修改消息和哈希；抗碰撞也不会把无密钥哈希变成消息认证码。普通程序哈希表只追求速度和均匀分布，不必满足密码安全。

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

消息分布也会压倒输出长度：若原像挑战从公开的十条固定消息中均匀抽取，攻击者枚举这十条并比较摘要即可获胜，即便摘要有 $256$ 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 证明不会在选择某个现实哈希后自动变成标准模型定理。

哈希到曲线理路哈希到椭圆曲线Hash to curve · Hash-to-curve · SSWU hash to curve将字节串先扩展为域元素，再经两次SSWU映射和群加法得到P256曲线点，逐项检查异常分母、符号与域分离。将输出对象换为合法曲线点：先扩展为域元素，再经确定映射与点加法完成P256编码。它与点反序列化的输入域不同；输出满足曲线方程也不足以证明适用于理想群随机预言机，还须检查域分离、映射分布及上层所需性质。

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