密码学基础：确定性与概率加密、哈希函数及轻量级特性

### 密码学基础：确定性与概率加密、哈希函数及轻量级特性 #### 1. 确定性加密算法转化为概率行为 在密码学中，概率公钥加密算法是可以被设计出来的，但概率对称密钥加密算法却很难设计。这是因为对称密钥加密算法通常要考虑硬件实现，而随机逻辑在对称密钥算法设计中未得到充分运用。不过，我们可以让确定性加密算法呈现出概率行为，这里并非改变加密算法本身，而是改变其使用方式。 假设 E 是一个确定性的对称密钥加密算法，其块大小为 n。对于消息 m，为了让密文具有概率特性，需将消息分割成更小的块，比如 k（k < n）位。具体的加密和解密过程如下： - **加密过程**： 1. 生成一个 n - k 位的随机数 r。 2. 计算 c = E(k, m∥r)，其中 m∥r 是 m 和 r 的字符串拼接。 3. 将 c 作为 m 的密文输出。 - **解密过程**： 1. 使用解密算法 D 对 c 进行解密，得到 m′ = D(k, c)。 2. 取 m′ 的最高 k 位作为 m，即解密后的消息。 通过上述加密过程生成的密文是具有概率性的，相同的明文消息 m 在不同时间加密会得到不同的密文，这是因为随机数 r 的参与。然而，密文的随机性是有限的，在相同加密密钥下，同一个明文最多可能有 2^(n - k) 种可能的密文。如果 n - k 较大，那么 k 相对较小，这意味着加密效率会降低，额外的处理开销也会进一步降低算法效率，这是为了实现随机行为所做出的牺牲。 这种使用确定性加密算法的过程仅适用于小尺寸的消息，特别是当消息大小小于块大小时。在实际应用中，有很多消息是小尺寸的，例如物联网设备的身份可以用 64 位或更少的位数表示，而大多数分组密码的块大小为 128 位，这就允许消息加密时附加一个 64 位的随机数，使密文具有足够的随机性。 下面是加密和解密过程的 mermaid 流程图： ```mermaid graph TD; A[开始] --> B[生成 n - k 位随机数 r]; B --> C[拼接 m 和 r 得到 m∥r]; C --> D[计算 c = E(k, m∥r)]; D --> E[输出密文 c]; E --> F[接收密文 c]; F --> G[使用 D(k, c) 解密得到 m′]; G --> H[取 m′ 最高 k 位作为 m]; H --> I[输出解密消息 m]; I --> J[结束]; ``` #### 2. 密码哈希函数 密码哈希函数（用 H(x) 表示）是一类重要的密码学函数，它应具备以下特性： - **压缩性**：对于任意长度的输入，哈希函数应产生固定长度的输出。在大多数应用中，输入消息的长度远大于输出长度，此时哈希函数就像一个压缩函数。但在某些极端情况下，当输入消息长度小于输出长度时，哈希函数的作用则是扩展。 - **单向性**：给定任意 x，计算 H(x) 应该很容易；但给定任意值 y = H(x)，在计算上几乎不可能找到一个输入 x 使得 H(x) = y 成立，这一特性被称为抗前像性。需要注意的是，前像并非唯一，所以计算 y = H(x) 的前像不一定是原始消息 x。 - **弱抗碰撞性**：给定输入 x 及其哈希值 H(x)，在计算上几乎不可能找到一个 x′ ≠ x 使得 H(x′) = H(x) 成立，这一特性也被称为抗第二前像性。 - **强抗碰撞性**：如果在计算上几乎不可能找到两个不同的值 x ≠ y 使得 H(x) = H(y) 成立，那么哈希函数 H() 就具有强抗碰撞性。这一特性与“生日攻击”问题密切相关，找到碰撞 x ≠ y 使得 H(x) = H(y) 成立的计算成本约为 2^(length(H)/2)，即 2 的哈希输出长度一半的幂次方，这为设置合适的哈希函数输出长度提供了很好的参考。 常见的哈希函数有： | 哈希函数 | 输出位数 | 特点 | | ---- | ---- | ---- | | MD5 | 128 位 | 第一个成功商业化使用的哈希函数，但现在由于能以可承受的计算量找到碰撞，被认为不安全。 | | SHA - 1 | 160 位 | 已发现一些弱点。 | | SHA - 2 | 有 SHA - 224、SHA - 256、SHA - 384、SHA - 512 等版本 | 最流行的版本是 SHA - 256 和 SHA - 512。 | | SHA - 3 | - | 新的哈希函数标准，旨在比 SHA - 2 更高效。 | #### 3. 哈希函数的应用 - 消息认证码 哈希函数类似于压缩函数，结合其其他密码学特性，它是一类重要的密码学函数。其中一个应用是构建消息认证码（MAC）算法。 消息认证码（MAC）是一种将消息空间 M 映射到更大空间  的函数，该映射由一个密钥控制。实际上，MAC 空间是通过在原始消息