Lec04 Symmetric Key Cryptography

How to use a block cipher?

  • 分组密码加密固定大小的块
    • 例如，DES 加密 64 位块，AES 加密 128 位块
  • 用某种方法来加密任意长度的消息

我们如何使用 AES 加密 256 位消息？

我们可以使用 AES 两次！避免像 one-time pads 这样的情况，需要很长的键。

Modes of Operation

  • 电子密码簿模式 （ECB）Electronic Codebook Mode
  • 密码块链接模式 （CBC）Cipher Block Chaining Mode
  • 输出反馈模式 （OFB）Output Feedback Mode
  • 密码反馈模式 （CFB）Cipher Feedback Mode
  • 计数器模式 （CTR）Counter Mode

Electronic Code Book (ECB)

我们刚刚就设计了一个 ECB 模式。

  • 最简单模式
  • 明文一次处理 b 位
  • 每个块都使用相同的密钥进行加密
  • 对于给定的密钥，每个 b 位纯文本块都有一个唯一的密文
  • 每个 b 明文位块都使用相同的密钥独立编码

AES-ECB 不是 IND-CPA 安全的。为什么？

  • 因为 ECB 是确定性的。
Strength and Weakness of ECB
  • Strength
    • 简单
    • 有效
  • Weakness
    • 加密的消息块是独立的
    • 消息重复可能以密文形式显示
      • 如果与消息块对齐
      • 特别是对于图形等数据
      • 或者使用变化很小的消息，这成为 Codebook 分析问题
例子

在这种情况下，ECB 失效了。

Cipher block chaining mode (CBC) ——最受欢迎

我们现在要努力重新设计一个，因为 ECB 不是 IND-CPA 安全的，他是确定性的。

想法：第一个密文块的计算具有一定的随机性。让我们用它来为第二个块添加随机性，并以此类推，这就是 CBC 模式。

  • 明文被分成块：P1、P2、P3、…

  • 在加密之前，每个明文块都与前一个密文块进行 XOR 运算（链接）：

    Ci = Ek ( C i - 1 ⨁ Pi)

    C0 = IV

  • 使用初始向量 （IV） 启动该过程，该向量是随机生成的。

  • 解密

    Pi = Ci - 1 ⨁ Dk (Ci)

CBC 模式：效率和并行性
  • 加密可以并行化吗？
    • 不，我们必须等待区块 i 完成，然后才能加密区块 i + 1
  • 解密可以并行化吗？
    • 是的，解密只需要密文作为输入
CBC 模式：填充

如果要加密不是块大小的倍数的消息，该怎么办？

  • 仅当明文长度是块大小的倍数时，才定义 AES-CBC
  • 填充消息，直到它是块大小的倍数
    • 用 0 填充？不起作用：如果我们的消息已经以 0 结尾怎么办？
    • 用 1 填充？同样的问题。

填充方案

  • 附加一个 ‘1’，然后用 ‘0 填充 ‘0’
    • 如果明文是 n 的倍数，你仍然需要用整个块填充
  • 用填充的字节数来填充
    • 如果你需要 1 个字节，用 01 填充;如果需要 3 个字节，请用 03 03 03 填充
    • 如果需要 0 个填充字节，请填充整个虚拟块
    • 这称为 PKCS #7
Strength and Weakness of CBC
  • Strength
    • 块的加密取决于当前块和之前的所有块。
    • 因此，重复的纯文本块的加密方式不同。
  • Weakness
    • 修改密文块
    • 仍然不保证完整性

设计流密码

CBC 模式很好，但它不是流密码，我们如何基于分组密码设计流密码？

  • 为了加密 P1、P2、P3、…，我们想用 Ek 为每个 P 生成不同的密钥： K1、K2、K3、…，
  • 然后加密 Pi为 Ci = Pi ⨁ Ki
  • 生成 K1、K2、K3、… 的三种不同方法
    • 计数器模式 （CTR）
    • 密码反馈 （CFB） 模式
    • 输出反馈 （OFB） 模式

CTR Mode

使用一个随机数 nonce 然后随着每个 block 加密递增，以确保每个数据块密码输出都不同。

CTR 模式：效率
  • 加密可以并行化
  • 解密也可以并行化
CTR 模式：填充

不需要填充消息，可以剪掉比消息长的部分。

Cipher Feedback Mode (CFB)

  • 明文是 s 位 （s ≤ block size） 的段序列：P1、P2、P3、…

  • 加密用于生成一系列密钥，每个密钥都是 s 位：K1、K2、K3、…

  • 密文为 C1、C2、C3、… ，其中

    Ci = Pi ⨁ Ki

CFB 模式：生成 Key 流

  • 分组密码的输入是一个移位寄存器 x，其在阶段 i 的值表示为 xi

  • Initially,

    x1 = an initial vectot (IV)

  • For i > 1,

    xi = shift-left-s-bits (xi - 1) | Ci - 1

  • Then

    Ki = s-most-significant-bits(EK(xi))

加密 解密
Strength and Weakness of CFB
  • Strength
    • 与 ECB 和 CBC 相比：
      • 分组密码用作流密码。当数据以位/字节为单位到达时适用。（s 可以是任何值;常用值为 s = 8）
      • 密文段取决于当前和所有前面的纯文本段。
    • 与 OFB 相比：
      • 可以随时解密。无需从头开始。这使得 CFB 模式非常适合解密加密的随机访问文件等应用程序。
  • Weakness
    • 传输过程中损坏的密文段最多会影响 （b/s） + 1 个明文段。

OFB mode

  • 结构与 CFB 非常相似

  • 不同之处：

  • Initially,

    x1 = an initial vectot (IV)

  • For i > 1,

    xi = shift-left-s-bits (xi - 1) | Ki - 1

  • Then

    Ki = s-most-significant-bits(EK(xi))

Comparing Modes of Operation

  • 如果你需要高性能，哪种模式更好？
    • CTR 模式，因为您可以并行加密和解密
  • 如果您对安全性偏执，哪种模式更好？
    • CBC 模式更好