对称加密

介绍

加密技术在很长一段时间内都是密码学的主要应用。它的目标是将一条消息转换成另一条消息，并通过不安全的信道发送，这样只有预期的接收方（他们知道反转此转换所需的所有元素）才能读取它，而对其他人来说，它看起来就像是绝对的胡说八道。例如，假设你是一名战争时期的将军，你需要将作战计划传达给你的增援营（他们仍然离你很远），并在精确的时刻发起突袭。如果你派一个信使送一封包含计划的未加密的信，那么任何阅读这封信的人都会知道你的策略并采取相应的行动。此外，信使可能会背叛你，与你的敌人交换信息，并挫败你精心策划的战术。

加密使用一种叫做 密码 的算法和一些 密钥，将消息变为看起来随机的文本。更准确地说，它接受 明文，并通过一些数学计算输出 密文。只有在知道密钥的情况下才能解密密文。在现代加密技术中，只有密钥是秘密的；加密算法的细节是公开的。这种构造符合 克尔克霍夫原则，该原则指出，在密码系统中，只有密钥应该是秘密的。在过去，人们试图通过使用未知的算法或策略来隐藏消息，希望敌人无法弄清楚秘密；我们称之为 通过混淆实现安全。无需指出的是，这种策略已经多次失败，并造成了灾难性的后果。

对称加密在今天被广泛使用，并且存在高效的算法，有些甚至在硬件上实现。对称加密算法的例子有 AES（高级加密标准）、3DES、ChaCha、Salsa、Twofish、Blowfish 和 Serpent。在这种类型的加密中，我们使用相同的密钥来加密和解密消息（因此，如果有人可以发送加密消息，他也可以解密它们）。我们将在后面的章节中看到非对称加密（或公钥密码学），其中我们有两个不同的密钥：一个公钥（用于加密消息）和一个私钥（用于解密）。

一旦我们有了密钥，我们就可以在各方之间发送安全的消息。由于其背后的数学原理和启发式方法以及适当的安全级别，不必要的各方不太可能解密它们。但是，我们发现自己面临着使相关各方就密钥达成一致的问题。如果我们试图通过不安全的信道以明文形式发送它，它可能会受到威胁，并且对称加密将毫无意义，因为对手可能已经获得了它。我们将在后面的文章中重点介绍如何执行密钥交换。

对称加密主要有两种密码类型：分组密码和流密码。我们将在以下各节中分析它们的特性。

形式化

我们有两个想安全通信的各方，我们将分别称他们为 Alice 和 Bob（分别代表 A 和 B）。Alice 想要向 Bob 发送一条明文 $P$，以便只有 Bob 可以阅读它并了解其内容。他们之前已经商定了一个共同的密钥 $k$，并且他们将使用一些算法，例如 AES。加密算法是一些函数 $E$，它接受明文和密钥并输出密文 $C$：

$E(P,k)=C$

另一方面，解密算法 $D$ 接受密文和密钥并返回明文

$D(C,k)=P$

我们希望我们的加密算法和输出密文能够提供一些功能。首先，密文应显示为没有明显模式的随机文本。我们还希望，即使我们更改消息中的单个位，生成的密文也与原始密文完全不同：我们称之为 雪崩效应。

这些与安全密码应具有的两个属性有关：混淆 和 扩散。混淆用于隐藏密钥和密文之间的关系。扩散与以下事实有关：密文中一个位的值取决于其他位；等效地，如果我们从明文中更改一位，我们可以预期许多位也会更改其值，这与雪崩效应有关。

密码的置换应满足以下三个条件才能安全：

• 密钥应确定置换。
• 不同的密钥应产生不同的置换。
• 置换应看起来是随机的。

第一个条件保证我们需要密钥才能解密。如果密钥不能确定置换，则它在此过程中不起作用，并且任何人都可以在没有它的情况下解密事物。第二个条件意味着没有两个密钥产生相同的置换。如果是这样，那么我们可以使用另一个密钥解密用一个密钥加密的消息，这将使破解密码系统变得更容易。第三个条件意味着我们不应该能够从密文中了解有关明文的任何信息（未能满足此条件的一个示例是使用 ECB 模式加密的一些位图）。

信息安全与计算安全

一个重要的关键与我们的密码方案的安全证明有关。在某些情况下，即使攻击者具有无限的计算能力，也可以证明特定方法在数学上是安全的。这些方案被称为 信息理论上安全。但是，我们需要引入一些假设来构建实用的密码方案。可以证明现代密码算法在 计算上安全，即对手具有有界的计算能力，并且即使使用当今可用的最快和最强大的设备，也只能在花费大量时间或资源后才能破解系统。

计算安全不是完美的安全性，而是依赖于以下几点：

• 仅针对高效的对手才能保持安全。
• 对手可能会成功，但概率可忽略不计。

如果我们对计算能力有足够合理的限制，并且成功的概率足够小，我们可以认为我们的方案在实践中是安全的。

有两种常用的方法来分析我们的密码协议的安全性：

1. 具体方法。
2. 渐近方法。

在具体案例中，我们限制了攻击者花费时间 $t$ 后的成功概率 $\epsilon$。 如果一个花费时间 $t$ 的对手的成功概率最多为 $\epsilon$，我们就说该方案是 $(t,\epsilon)$-安全的。

渐近方法与复杂度理论有关。它将攻击者的运行时间和他的成功概率视为安全参数 $\lambda$（例如，密钥大小）的函数。它仅保证在 $\lambda$ 足够大的情况下才是安全的。

如果一个算法的运行时间是 $\lambda$ 的多项式，即对于某些数字 $c_1$ 和 $c_2$，$c_1\lambda^{c_2}$，我们就说它是有效的。我们也可以用大 O 符号写成 $\lambda^{c_2}$。

至于成功的概率，如果它们小于 $\lambda$ 中的任何逆多项式，我们就认为它们很小。更准确地说，对于每个常数 $c$，攻击者的成功概率小于 $\lambda$ 中的逆多项式 $\lambda^{-c}$。增长速度慢于任何逆多项式的函数称为 可忽略。

如果每个概率式的、多项式时间攻击者仅以可忽略的概率成功破解一个方案，则该方案是安全的。

位运算：异或 (XOR)

密码学中经常使用的一种运算是异或运算符 (XOR)。它是一种二元运算，取两个位并输出另一个位；我们将用 $\oplus$ 符号表示该运算。它的真值表是：

$0\oplus0=0$

$0\oplus1=1$

$1\oplus0=1$

$1\oplus1=0$

我们也可以将 XOR 运算视为模 2 加法：

$0+0\equiv0 \pmod{2}$

$1+0\equiv1 \pmod{2}$

$1+1\equiv0 \pmod{2}$

这些结果是预期的：两个奇数或两个偶数相加总是偶数，而一个奇数和一个偶数相加总是奇数。

为什么这个操作有帮助？假设我们要加密一个给定的消息，该消息表示为一系列位。一种加密方法是生成一系列（伪）随机位，并对每个位进行 XOR 运算以获得密文。攻击者可以尝试解密文本，但他会发现以下问题：

• 如果他在密文中看到 $0$，可能是因为明文有 $1$，并且随机位也是 $1$，或者两者都是零。所以，他有 $50$ 的机会猜对！
• 如果他在密文中看到 $1$，要么明文是 $1$，随机位是 $0$，要么反过来。 同样，他有 $50$ 的机会猜对。

如果消息由几个字节组成（例如，16 个字节 - 128 位），则猜对正确消息的概率为 $3\times10^{-39}$！

我们看到 XOR 操作很难反转，除非我们知道原始输入之一。 在这种情况下，如果 $c=m\oplus r$，则

$m=c\oplus r$

流式密码和块密码

块密码采用固定长度（例如，128 位）的消息，并通过对其元素执行某些随机置换来对其进行加密。块密码的特征在于两个值：块大小（例如，16 字节 -128 位-）和密钥大小。两者都决定了密码的安全级别。此密码不使用单个位进行操作，而是使用固定大小的块进行操作。

块大小既不能太大也不能太小。 在第一种情况下，它可能会影响加密的成本和性能，因为内存占用量和密文长度将非常大。 但是，如果块大小很小，则容易受到密码本攻击。

实际上，块密码是置换和替换步骤的重复应用； 这些发生在轮次中。 主要组成部分是：

• 替换盒 (S-boxes)。
• 混合置换。
• 密钥调度。

如果我们调用 $f_k$ 与第 $k$ 轮相对应的函数，则密文为

$C=fn(f{n-1}(...f_2(f_1(P))))$

轮函数具有相同的操作，但由不同的密钥参数化（这会导致其他替换和置换）。 我们不应该对所有步骤使用相同的密钥； 否则，我们的密码系统可能容易受到滑动攻击。

解密是连续应用反函数 $g_k=f_k^{-1}$，

$P=g_1(g2(...g{n-1}(g_n(C))))$

流密码的工作方式非常不同； 它们不是组合文本块和密钥，而是从密钥确定性地生成一系列“随机”位（称为密钥流），并对文本执行 XOR 运算。

密钥流 $KS$ 来自密钥 $k$ 和公共 nonce $nonce$。 如果我们有要加密的消息 $m$，我们执行 $C=KS\oplus m$。 要解密，我们只需再次 XOR，$m=KS\oplus C$。 我们可以很容易地看到，加密和解密操作本质上是相同的； 我们只需要密钥流就可以做到这一点。 重要的是，不需要保密的 $nonce$ 永远不会被重用。 为了了解原因，假设我们有两条消息 $m_1$ 和 $m_2$，以及它们对应的密文，这些密文已使用相同的密钥 $k$ 和 $nonce$ 加密。 我们可以使用以下操作恢复消息 $m_1$：

$m_1=C_2\oplus C_1\oplus m_2$

以上是 Microsoft Excel 和 Word 存在的一个实现错误：它们重用了相同的 nonce，这意味着如果两个版本的同一文件可用，则可以进行解密。

加密算法

在以下各节中，我们将介绍每种密码类型的基础知识，分析两种常用的密码类型。我们将从 AES（一种块密码）开始，它是当今使用最广泛的密码，然后是 ChaCha（一种流密码），通常以 ChaCha20-Poly1305 的形式用于 Android 系统。

AES

高级加密标准 (AES) 源于 NIST 于 1997 年组织的为期三年的公开竞赛。Rijmen 和 Daemen 的提案被提名为获胜者，并于 2001 年由 NIST 标准化。我们实现了 AES 及其算术化，以用于零知识证明 这里。

AES 提供三个安全级别：AES-128、AES-192 和 AES-256，密钥大小分别为 16、24 和 32 字节。 随着密钥大小的增加，安全性也随之提高。 但是，对于大多数应用程序，AES-128 提供了足够的安全级别（针对 AES 的最著名的攻击仅比蛮力攻击略好，蛮力攻击将需要 $2^{128}$ 次运算）。

AES 是一种块密码：它采用一个 16 字节的块（128 位）和可变长度的密钥，并输出一个 16 字节的密文。 如果文本小于 16 个字节，则会方便地进行填充。 执行解密后，应该可以消除填充以恢复消息； 因此，我们不能使用随机填充，因为我们无法区分原始消息和随机位。

请记住，块密码是置换：它们将所有可能的明文映射到所有可能的密文。

密码将明文视为一个 $4\times4$ 的字节矩阵。 AES 有一个轮函数，该函数多次应用于明文，以扰乱和混合所有内容，直到我们获得密文。 每一轮都使用不同的密钥（以确定性方式从密钥生成），从而使密钥的位发生最细微的变化，从而导致完全不同的加密。 每一轮函数中的步骤（最后一轮除外）是：

• SubBytes
• ShiftRows
• MixColumns
• AddRoundKey

前三个步骤很容易恢复，但最后一个步骤不是：它在文本和轮密钥之间执行 XOR 运算。 但是，所有步骤对于达到所需的安全性级别都是必需的。

AES 使用十轮来执行加密。 所有步骤都包含四个操作，除了第一个操作（仅添加了轮密钥）和第 10 个操作（省略了 MixColumns）。

SubBytes（也称为替换盒）提供了替换步骤，并且是非线性函数。 鉴于我们加密 16 字节的块，我们可以借助查找表进行替换。

在 ShiftRows 和 MixColumns 中，列/行的字节被移动。

调用密钥调度函数来生成每一轮的密钥：所有密钥都来自密钥，使用替换盒和 XOR 运算。 此密钥调度的一个缺点是，如果攻击者了解其中一个密钥，则他可以反转该算法并发现所有其他密钥，包括密钥。

为什么我们需要所有这些操作才能获得安全的密码？

• MixColumns 和 ShiftRows 保证所有元素都“混合良好”。 如果缺少其中一个，那么我们可以将密码分成更小的块，并对 $2^{32}$ 种可能性执行密码本搜索，这比 $2^{128}$ 好得多。
• SubBytes 为密码提供非线性部分。 如果没有它，所有操作都是线性的并且更容易反转。
• AddRoundKey 使密文依赖于密钥。 如果我们跳过此步骤，则我们不需要任何密钥来解密。
• 密钥调度可以防止我们一直重复使用相同的密钥，从而使密码容易受到滑动攻击。

当我们要加密大于块大小的消息时，我们可以将其分成 16 字节的块，并在必要时填充最后一个。 这种简单的方法称为电子密码本模式 (ECB)，不应使用。 由于加密是确定性的，因此每次我们加密给定的明文时，都会得到相同的密文。 当我们有例如具有重复模式或大面积单一颜色的图像时，这会成为问题，因为密文也会显示这些模式。 我们可以使用几种模式来避免此问题：

• 密码块链接 (CBC)
• 传播密码块链接 (PCBC)
• 密码反馈 (CFB)
• 输出反馈 (OFB)
• 计数器 (CTR)

例如，在 CBC 模式下：

1. 初始化一个 16 字节的随机向量 (IV)，
2. 执行 $B_1'=IV\oplus B_1$，其中 $B_1$ 是第一个块并设置 $k=1$。
3. 使用 AES 加密 $E_1=B_1'$。
4. 执行 $B_{k+1}'=Ek\oplus B{k+1}$
5. 使用 AES 加密 $E{k+1}=B{k+1}'$ 并执行 $k=k+1$
6. 如果 $k\neq k_{max}$，转到步骤 4。否则，加密结束。

即使加密相同的明文，IV 也保证生成的密文将有所不同。

我们面临的另一个问题是，即使消息已加密，我们也无法知道攻击者是否已对其进行修改。 为了防止修改密文，我们可以添加消息身份验证码 (MAC)，我们将在另一篇文章中介绍。

ChaCha20

ChaCha20 是对 Salsa20 密码的修改，由 Daniel J. Bernstein 于 2005 年发明。 它的工作原理与所有流密码相同：它从密钥生成密钥流，并通过在明文和密钥流之间执行 XOR 运算来进行加密。

ChaCha20 通过重复调用一个块函数来生成密钥流，该函数输出 64 字节的密钥流。 它将以下各项作为输入：

• 256 位密钥。
• 96 位 nonce。
• 32 位计数器。

每次该函数输出 64 字节的密钥流时，计数器都会增加 1，并且该过程会一直持续到密钥流大于明文为止； 然后，我们将其截断为明文长度，并执行 XOR 运算。 我们可以加密的最大大小由计数器的总值 $2^{32}$ 和每一轮的输出（64 字节）给出，从而产生最大值 $2^{32}\times64=256$ GB。

核心操作是 Quarter Round。 它采用 4 个 32 位无符号整数，表示为 $a,b,c$ 和 $d$，并执行以下操作：

$a=a+b; d=d\oplus a; d<<<16$

$c=c+d; b=b\oplus c; b<<<12$

$a=a+b; d=d\oplus a; d<<<8$

$c=c+b; b=b\oplus c; b<<<7$

其中 $<<<n$ 表示向左旋转 $n$ 位。

ChaCha 状态包括 16 个 32 位字：前四个是常量； 接下来的八个对应于密钥，然后是计数器和 nonce。

总结

对称加密是当今使用最广泛的加密方案之一； 它还提供了我们可以用来构建哈希函数的工具。 我们可以将对称密码分为两大类：块密码（如 AES）和流密码（如 Chacha20）。 两者都通过扰乱和替换消息来提供机密性。 在后续文章中，我们将讨论各方如何通过不安全的信道就密钥达成一致。

• 原文链接： blog.lambdaclass.com/sym...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～