跳到主要内容

Appendix A. 与 SHA-1 和 SHA-256 的工作量比较

本附录对短消息 (即小于约 50 字节的消息) 计算 FNV-1a, SHA-1 [RFC3174] 和 SHA-256 [RFC6234] 所需的工作量级别给出一种简化的粗略比较. 某些 CPU 可能具有特殊指令或其他硬件来加速某些密码学操作, 因此, 如果性能对某个应用特别重要, 则适合在目标平台上进行基准测试.

忽略控制转移和条件测试, 并将所有逻辑和算术操作等同看待, FNV 每个字节需要两个操作: 一个 XOR 操作和一个乘法操作.

SHA-1 和 SHA-256 实际上被设计为接受 bit vector 输入, 尽管几乎所有计算机用途都会将它们应用于整数个字节. 它们都处理 512 bit (64 字节) 的块, 这里估计处理一个完整块所涉及的工作量. 每条消息都有一些开销, 用于指示消息终止和大小. 假设消息是偶数字节数, 则 SHA-1 的该开销为 9 字节, SHA-256 的该开销为 17 字节. 因此, 假设带有该开销的消息适合放入一个块, 则 SHA-1 的消息最多为 55 字节, SHA-256 的消息最多为 47 字节.

SHA-1 是一种相对较弱的密码学哈希函数, 产生 160-bit 哈希. 它已经在实质上被攻破 [RFC6194]. 忽略 SHA-1 的初始设置, 控制转移和条件测试, 但计入所有逻辑和算术操作, 包括将索引计作一次加法, SHA-1 对每个 64 字节块需要 1,744 次操作, 或者对 55 字节消息为每字节 31.07 次操作. 按这种粗略衡量, 它所需工作量略高于 FNV 的 15.5 倍.

在发布时, SHA-256 被认为是比 SHA-1 更强的密码学哈希函数. 忽略 SHA-256 的初始设置, 控制转移和条件测试, 但计入所有逻辑和算术操作, SHA-256 对每个 64 字节块需要 2,058 次操作, 或者对 47 字节消息为每字节 48.79 次操作. 按这种粗略衡量, 它所需工作量超过 FNV 的 24 倍.

不过, FNV 通常用于短输入, 因此对这类输入进行比较是有意义的. 使用上述比较方法, 对于 N 字节输入, 其中 N <= 55 且 SHA-1 将处理一个块, SHA-1 与 FNV 的工作量比值为 872/N. 对于 N 字节输入, 其中 N <= 47 且 SHA-256 将处理一个块, SHA-256 与 FNV 的工作量比值为 1029/N. 下面给出一些示例.

   +=========+==========+=======================+================+
   | Example |   Length | SHA-1 Effort Relative | SHA-256 Effort |
   |         | in Bytes |         to FNV Effort |    Relative to |
   |         |          |                       |     FNV Effort |
   +=========+==========+=======================+================+
   | IPv4    |        4 |                   218 |            514 |
   | address |          |                       |                |
   +---------+----------+-----------------------+----------------+
   | MAC     |        6 |                   145 |            171 |
   | address |          |                       |                |
   +---------+----------+-----------------------+----------------+
   | IPv6    |       16 |                    54 |             64 |
   | address |          |                       |                |
   +---------+----------+-----------------------+----------------+

                               Table 3
最后于 更新