密码学拾遗

本文最后更新于：2024年12月29日 下午

仿射密码的密钥空间

仿射密码是一种基于字母表映射的加密方式，其加密函数为：

E(x)=(ax+b)mod  mE(x) = (ax + b) m

其中：

  • xx 是明文字符的数字表示（例如，A=0, B=1, C=2, ...）
  • aa 是乘法密钥
  • bb 是加法密钥
  • mm 是字母表的大小（例如，对于英语字母表，m=26m = 26）

密钥空间的计算：

  1. 乘法密钥 aa：为了确保加密函数是可逆的，aa 必须是与 mm 互质的数（即，gcd⁡(a,m)=1(a, m) = 1）。对于英语字母表，m=26m = 26，所以 aa 必须是与 26 互质的数字。与 26 互质的数字有 12 个：1, 3, 5, 7, 11, 13, 15, 17, 19, 21, 23, 25。
  2. 加法密钥 bb：加法密钥 bb 可以是任意的数字，范围从 0 到 m−1m-1，即 0 到 25（对于英语字母表）。

密钥空间大小：

  • 乘法密钥 aa 有 12 个可能的选择（与 26 互质的数）。
  • 加法密钥 bb 有 26 个可能的选择（从 0 到 25）。

因此，仿射密码的密钥空间大小为：

12×26=31212 = 312

总结：

仿射密码的密钥空间大小为 312，其中乘法密钥有 12 个选择，加法密钥有 26 个选择。

分组密码的工作模式中的错误传播

是指在加密或解密过程中，如果输入或中间数据发生了某些错误，这些错误是否会影响后续的输出结果，以及影响的范围。

有错误传播

当某一位或某一块数据出错时，错误会传播到多块甚至整个消息中，导致后续的加密或解密结果也出错。

特点：

  • 错误影响范围大。
  • 在解密时，可能导致无法恢复大量正确数据。

示例：

反馈模式（如 CBC、CFB）：

  • 在 CBC 模式中，如果某个密文块发生错误，会导致对应的明文块和下一个明文块解密出错。

无错误传播

当某一位或某一块数据出错时，错误只影响有限范围的输出，例如仅影响当前块，不会扩散到其他块。

特点：

  • 错误的影响范围小，后续数据可能依然正确。
  • 更容易定位和修复错误。

示例：

电子密码本模式（ECB）：

  • 如果某个密文块出错，解密时只会影响对应的明文块，而不会影响其他块。

实际应用中的考虑

  1. 安全性： 有错误传播的模式通常具有更强的安全性（如抗攻击能力更高）。
  2. 可靠性： 无错误传播的模式在数据传输中可能更实用，因为单个错误不会导致整个消息解密失败。

选择工作模式时，需要根据具体应用场景在安全性和可靠性之间权衡。

流密码模式

是一种将分组密码转换为类似流密码的方法，使其能够逐位或逐字节操作，而不需要填充。下面逐项解释您列出的内容：

1. 流密码模式

流密码模式使得分组密码（如 DES）可以逐位或逐字节处理明文，而不是分块处理。这种方式更适合实时传输和交互式通信场景。

用 DES 来构建流密码的三种模式：

1.1 密文反馈模式（CFB，Cipher Feedback）

  • 工作原理：
    • 使用加密函数将上一个密文块加密，并将其输出的一部分与当前明文块进行异或（XOR）生成新的密文块。
    • 第一个块加密时，使用一个初始化向量（IV）作为输入。
  • 特点：
    • 仅使用加密函数。
    • 适合流式数据加密。
    • 错误传播有界性： 如果某个密文块出错，会导致后续若干块解密错误。

1.2 输出反馈模式（OFB，Output Feedback）

  • 工作原理：
    • 将加密函数的输出作为伪随机数流的一部分，与明文块进行异或生成密文块。
    • 第一个块使用初始化向量（IV）加密，后续以前一次的加密结果为输入。
  • 特点：
    • 不直接使用密文作为输入，因而避免了密文错误传播。
    • 生成的伪随机数流独立于明文，因此可以预先计算。

1.3 计数器模式（CTR，Counter Mode）

  • 工作原理：
    • 使用一个计数器值（counter）作为加密函数的输入，每次加密生成的伪随机数流与明文异或生成密文。
    • 计数器按固定步长递增。
  • 特点：
    • 并行性强（计数器值可以提前生成）。
    • 不存在错误传播问题。
    • 与 OFB 类似，也可以预先计算伪随机数流。

2. 一般性质

2.1 使用分组密码的加密函数

  • 这三种模式中，所有操作都只使用分组密码的加密功能（而不是解密功能）。
  • 即使在解密时，也通过重复加密函数来生成伪随机数流或反馈值。

2.2 可塑性（Malleability）

  • 定义： 可塑性指的是攻击者在不解密密文的情况下，能够对密文进行修改，导致解密后的明文发生可预测的变化。
  • 原因：
    • 由于密文直接参与某些模式（如 CFB）的操作，攻击者可能通过修改密文来影响解密结果。
  • 影响：
    • 可塑性是一种弱点，需要通过消息认证码（MAC）或其他完整性校验机制来弥补。

流密码模式的选择应根据具体需求来确定：

  • 高效并行计算： CTR 模式。
  • 抗错误传播： OFB 或 CTR。
  • 实时流式加密： CFB 或 OFB。

流密码的通式

\[ C = M ⊕ PRNG(seed) \]

AES

  • DES 走到了生命的尽头
    • 56-bits 密钥太短 (穷举密钥攻击)
    • 软件实现效率低
    • 3-DES对于小的分组实现速度慢

强无碰撞与弱无碰撞的区别

在密码学中，无碰撞性（Collision Resistance）是哈希函数的重要性质，分为强无碰撞性和弱无碰撞性。两者的区别如下：

1. 定义上的差异

强无碰撞性（Strong Collision Resistance）

  • 问题描述：找到两个不同的输入 \(m_1 \neq m_2\)，使得它们的哈希值相同，即 $h(m_1) = h(m_2) $。
  • 难度要求：在计算上不可行，意味着即使攻击者拥有哈希函数的所有信息，也无法在合理时间内找到这对 m1m_1 和 m2m_2。
  • 特点：没有任何一个输入是已知的，攻击者需要在无约束的情况下找到碰撞。这是一种更严格的要求。

弱无碰撞性（Weak Collision Resistance）

  • 问题描述：对于给定的输入 \(m_1\)，找到另一个不同的输入 \(m_2 \neq m_1\)，使得它们的哈希值相同，即 $ h(m_1) = h(m_2) $。
  • 难度要求：在计算上不可行，意味着即使攻击者能够选择 \(m_1\)，也无法在合理时间内找到符合条件的 \(m_2\)。
  • 特点：攻击者需要从一个固定的输入出发进行攻击，难度较强无碰撞性低。

2. 攻击者能力的差异

  • 强无碰撞性：攻击者可以自由选择任意输入，不需要以特定输入为基础。这种碰撞更难以找到，因此需要更强的安全性。
  • 弱无碰撞性：攻击者需要从一个已知输入开始，尝试找到另一个输入与之碰撞。由于限制了起点，计算难度相对较低。

3. 实际意义与用途

  • 强无碰撞性：
    • 用于保障哈希函数的全面安全性，特别是在数字签名和密码协议中，防止攻击者伪造数据。
    • 强无碰撞性要求更高，设计更复杂的哈希函数通常需要确保此属性。
  • 弱无碰撞性：
    • 在防止特定消息的伪造（如消息认证码）时更为重要。
    • 对性能要求较高的系统可能优先满足弱无碰撞性，而未必确保强无碰撞性。

4. 难度比较

  • 强无碰撞性更难实现，因为它需要防止攻击者在没有任何已知输入的情况下找到碰撞。
  • 弱无碰撞性相对容易满足，因为攻击者需要以给定的 \(m_1\) 为基础，约束更强。

总结

  • 强无碰撞性：适用于所有可能的输入，难度较高，安全性更强。
  • 弱无碰撞性：限制于给定的输入，难度较低，适用场景相对有限。

SHA 算法比较

算法 输出 (bits) 分组大小 (bits) 明文长度 (bits) 迭代次数 操作 攻击复杂度 备注
SHA-0 160 512 \(2^{64}-1\) 80 \(+,and,or,xor,rotl+, \text{and}, \text{or}, \text{xor}, \text{rotl}\) 已有攻击方法 早期版本，已被淘汰。
SHA-1 160 512 \(2^{64}-1\) 80 \(+,and,or,xor,rotl+, \text{and}, \text{or}, \text{xor}, \text{rotl}\) O(263)O(2^{63}) 攻击可行 不再推荐使用。
SHA-256/224 224 或 256 512 \(2^{64}-1\) 64 \(+,and,or,xor,shr,rotr+, \text{and}, \text{or}, \text{xor}, \text{shr}, \text{rotr}\) O(2128)O(2^{128}) 安全性高 SHA-2 家族。
SHA-512/384 384 或 512 1024$ \(2^{128}-1\) 80 \(+,and,or,xor,shr,rotr+, \text{and}, \text{or}, \text{xor}, \text{shr}, \text{rotr}\) O(2256)O(2^{256}) 安全性极高 高效但计算复杂度较高。
SHA-512/3 512 1024 \(2^{128}-1\) 80 \(+,and,or,xor,shr,rotr+, \text{and}, \text{or}, \text{xor}, \text{shr}, \text{rotr}\) 未列出攻击方法 尚未广泛应用。
notes > CS
#密码学
密码学拾遗
https://cdro.tech/notes/CS/cryptography-course/
作者
k9Q6CK42
发布于
2024年12月28日
更新于
2024年12月29日
许可协议