密码学备忘录-哈希函数

2020-08-05

1. 散列函数

哈希函数H是一公开函数，用于将任意长的消息M映射为较短的、固定长度的一个值H(N)，作为认证符。
- 称函数值H(M)为杂凑值、杂凑码、散列值、散列码或消息摘要等
- 散列码（message authentication code）是消息的“指纹”
散列码是消息中所有比特参与运算产生的，因此提供了一种错误检测能力，即改变消息中任何一个比特或几个比特都会使散列码发生改变

1.1. Trapdoor One-Way Function（单向陷门函数）

A trapdoor one-way function is a one-way function with an additional requirement. Informally, a one-way function might be described as a function for which evaluation in one direction is straightforward, while computation in the reverse direction is far more difficult. Such a function becomes a trapdoor one-way function when we add the requirement that computation in the reverse direction becomes straightforward when some additional (trapdoor) information is revealed.

1.2. 特性

A hash function is a single,fully defined, computable function which takes as input bit sequences of arbitrary（任意的） length, and outputs values of a fixed length r (e.g. r = 256 bits for SHA-256).
A hash function h is deemed secure if:
It is computationally infeasible to find preimages: given a r-bit value x, it is not feasible to find m such that h(m) = x. 不可逆
It is computationally infeasible to find second preimages: given m, it is not feasible to find m’ distinct from m, such that h(m) = h(m’). 抗弱
It is computationally infeasible to find collisions: it is not feasible to find m and m’, distinct from each other, such that h(m) = h(m’). 抗强

1.3. MD5

算法的输入分为512比特长的分组
输出为128比特的消息摘要

步骤

对消息填充
- 对消息填充，使得其比特长在模512下为448，即填充后消息的长度为512的整数倍减64，留出的64比特备第②步使用。
附加消息的长度值
- 用步骤①留出的64位来表示消息被填充前的长度。
- 如果消息长度大于$2^{64}$，则以$2^{64}$为模数取模。
初始化消息摘要(MD)缓存器
- MD5使用128比特长的缓冲区以存储中间结果和最终杂凑值，缓冲区可表示为4个32比特长的寄存器(A B C D)，每个寄存器都存储固定的32位整数参数，即初始链接变量，这些参数用于第1轮运算
处理每一个512位的报文分组
输出

算法过程

MDS抗密码分析的能力较弱