Alice and Bobの神秘小屋

在前面的章节中，我们已经分析了分组密码的加密算法和分组模式，这些都是对称加密算法的核心内容。然而，在实际应用中，我们经常需要在多个参与者之间共享一个秘密，而不希望任何单一参与者能够独自获得这个秘密或者一旦有一个人背叛就无法恢复秘密。这就引入了门限秘密共享算法（Threshold Secret Sharing），其中最著名的就是 Shamir 门限秘密共享算法。 Shamir 门限秘密共享算法是一种基于多项式插值的秘密共享方案，它允许将一个秘密分成 $n$ 份，并且只要有 $k$ 份（$k \leq n$）就可以恢复出原始的秘密，而任何少于 $k$ 份的信息都无法获得任何关于秘密的线索。这种算法在分布式系统、密钥管理和安全多方计算等领域有着广泛的应用。 Shamir 门限秘密共享算法的数学原理 😇Shamir 门限秘密共享算法加密首先，我们来思考一个问题，对于一个 $k$ 次多项式 $F(x) = a_0 + a_1 x + a_2 x^2 + … + a_k x^k$，我们要求出 $F(0)$ 的值，也就是多项式的常数项 $a_0$，我们需要知道多少个点 $(x_i, F(x_...

前面我们已经分析了经典的分组加密算法 DES 和 AES，这两个算法都是分组密码的代表。分组密码是对称加密算法中最重要的一类算法，但是我们经过前面学习会发现，分组密码算法本身只能对固定大小的块进行加密，而实际应用中我们需要加密的数据往往是任意长度的，这就引入了分组模式（Block Cipher Mode）的概念。 分组模式是一种将分组密码算法扩展到任意长度数据的技术，它定义了如何将明文分成块、如何处理最后一个块以及如何将加密结果组合成最终的密文。常见的分组模式有 ECB（Electronic Codebook）、CBC（Cipher Block Chaining）、CFB（Cipher Feedback）、OFB（Output Feedback）和 CTR（Counter）等。 在本章中，我们将深入分析这些分组模式的工作原理、优缺点以及它们在实际应用中的安全性表现，帮助读者全面理解分组模式的设计思想和使用场景。 明文填充 🫡分组密码迭代加密要求每一个明文分组都是块长度(8或16字节)当分组到最后一组时，其长度不足块长度，就需要对其进行填充，将长度扩展为块长度 常见的填充方式有如...

AES（Advanced Encryption Standard）是当前最广泛使用的对称分组加密算法，由美国国家标准与技术研究院（NIST）于 2001 年正式发布。AES 以其卓越的安全性和高效的性能，成为现代加密协议中的核心组件，广泛应用于 TLS、IPsec、Wi-Fi 等众多安全通信协议中。 在本章中，我们将深入剖析 AES 加密算法的核心原理与实现细节。我们将从分组密码的基础特性出发，逐步拆解 AES 的 10、12 或 14 轮加密过程，详细分析其状态矩阵的构造、每轮的操作步骤（SubBytes、ShiftRows、MixColumns、AddRoundKey）以及最终的密钥扩展机制，全面理解 AES 的加密过程和安全性分析。 AES 加密算法 🫡AES 块长度为 128 位，密钥长度可以是 128 位、192 位或 256 位，分别对应 10、12 或 14 轮加密过程，明文按照 128 位分组，加密得到 128 位密文。 AES 算法不同于 DES 的 Feistel 结构，而是采用了 Substitution-Permutation Network（SPN）结...

从这一章开始，我们进入分组密码的世界。在此之前，建议先回到 密码学前置内容 - 密码分类与简介 复习一下分组密码的基本概念和构成，方便理解。 分组密码是对称加密算法中最重要的一类算法，它将明文分成固定大小的块进行加密，常见的分组大小有 64 位和 128 位。DES（Data Encryption Standard）是分组密码的经典代表之一，虽然现在已经被认为不安全，但它在密码学史上具有重要地位。 话不多说，我们直接进入 DES 加密算法的核心原理与实现细节。我们将从 DES 的基本结构出发，逐步拆解其初始置换、16 轮 Feistel 结构、子密钥生成等关键步骤，深入理解 DES 的加密过程和安全性分析。 DES 加密算法 🫡DES 块长度为 64 位，密钥长度为 64 位（其中 8 位为校验位，实际有效 56 位），明文按照 64 位分组，加密得到 64 位密文。DES 对明文进行 16 轮加密运算，每一轮都有一个相应的子密钥参与（子密钥由密钥扩展算法计算得出）。此外，开头和结尾分别有初始置换和最终置换的操作，用于适应硬件电路的算法实现。 这里给出一个简单示意图： 密钥扩展...

Salsa20 是一种基于 Salsa20 的流密码算法，由 Daniel J. Bernstein 设计。它以其速度快、安全性高、实现简洁而闻名，广泛应用于安全通信、加密存储等场景。 在本章中，我们将深入剖析 Salsa20 加密算法的核心原理与实现细节。我们将从流密码的基础特性出发，逐步拆解其核心的 20 轮加密过程，详细分析其状态矩阵的构造、每轮的操作步骤以及最终的密钥流生成机制，全面理解 Salsa20的加密过程和安全性分析。 Salsa20 加密算法 😋Salsa20 的核心原理基于一个 4x4 的状态矩阵，包含了常量、密钥、计数器和随机数。每轮加密过程中，算法通过一系列的加法、异或和位移操作来混合这些元素，从而生成一个伪随机的密钥流。这个密钥流随后与明文进行异或操作，产生密文。 初始状态矩阵Salsa20 的初始状态是一个 4×4 的 32 位无符号整数矩阵（共 512 位），由固定常量（”expand 32-byte k” 的 ASCII 编码）、256 位密钥、计数器、随机数（nonce） 四部分按固定位置填充构成： \begin{bmatrix} c_0 & ...

RC4 算法是一种基于伪随机密钥流生成的对称流密码算法，它由 Ronald Rivest 于 1987 年设计，凭借极致简洁的结构和高效的运行性能，曾广泛应用于 TLS、WEP、SSL 等众多经典安全协议中。 在本章中，我们将深入剖析 RC4 算法的核心原理与实现细节。我们将从流密码的基础特性出发，逐步拆解其密钥调度算法（KSA）与伪随机生成算法（PRGA）的核心流程，但是由于内部设计缺陷，RC4 算法实际上已经在现代安全场景中已被认定为完全不安全，必须禁用。 RC4 加密过程 😁RC4 加密算法的加密过程可以分为两个主要阶段：密钥调度算法（KSA）和伪随机生成算法（PRGA）。 密钥调度算法（KSA）首先，RC4 用密钥把 0~255 打乱成一个乱序表，我们把这个乱序表叫做 S 盒（Substitution Box），S 盒的初始状态是 $S = [0, 1, 2, \ldots, 255]$，然后通过密钥对 S 盒进行打乱，相当于把短密钥变成均匀混乱的状态。 具体来说，KSA 的过程如下： 初始化 S 盒：$S[i] = i$，对于 $i = 0, 1, \ldots, ...

从古典密码的单表替换，到现代非对称加密，我们已经分析了多种加解密模式。现在，我们将进入对称加密中的流密码（也叫序列密码）的世界，本章重点分析一次性密码本（One-Time Pad, OTP）和伪随机数生成器（Pseudo-Random Number Generator, PRNG）这两种重要的加解密模式。 一次性密码本（One-Time Pad） 😎流密码是一种对称加密算法，它通过将明文与一个密钥流进行逐位异或（XOR）操作来实现加密。流密码的核心思想是使用一个足够长且随机的密钥流来保证加密的安全性。 一次性密码本（OTP）是一种特殊的流密码，由现代密码学的创始人之一克劳德·香农提出。它使用一个与明文长度相同的完全随机密钥流进行加密，这很臃肿，但却是理论上绝对安全的加密方法。 OTP 的加密过程非常简单：对于每个明文字符，使用对应位置的密钥字符进行异或操作，得到密文字符。 OTP 的解密过程也是一样的：对于每个密文字符，使用对应位置的密钥字符进行异或操作，得到明文字符。 没错，OTP 的加密和解密过程是完全对称的。而且只要密钥流是完全随机的，并且每次使用后都不再使用（即一次性）...

今天我们将分析 Diffie-Hellman 密钥交换协议（DH Key Exchange Protocol），这是一种基于离散对数问题的非对称加密算法。这和之前的 ElGamal 加密算法不同，DH 密钥交换协议的主要目的是让两个通信方在不安全的信道上安全地协商出一个共享的密钥，而不是直接加密消息。 实际上，经过我们前面的非对称加密算法的学习，会发现加密的时候，如果选择直接加密消息，效率会非常低。例如，当明文过长时，RSA 算法要有足够大的素数才行。 所以我们通常会使用 DH 密钥交换协议来协商出一个共享的密钥，然后使用对称加密算法（如 AES）来加密实际的消息，这样既保证了安全性，又提高了效率。 DH 密钥交换协议过程 😛由于经典的 DH 密钥交换协议就是基于离散对数难题的，我们这里就不再赘述它的数学原理了。 首先通信双方先共享两个公共参数，模数 $p$ 和生成元 $g$。 Alice 本地随机生成一个私钥 $a$，并计算 $A ≡ g^a \mod p$，将 $A$ 发送给Bob。 Bob 收到 $A$ 后，本地随机生成一个私钥 $b$，并计算 $B ≡ g^b \mod...

今天我们将分析背包加密算法（Knapsack Cryptosystem），这是一种基于陷门问题的非对称加密算法。背包加密算法的安全性依赖于背包问题的困难性，这使得它成为一个有趣的研究对象。 不过，我们要知道，所有基于超递增序列和模变换的背包，其陷门结构存在致命漏洞：模乘法无法完全隐藏超递增序列的结构，格基规约（LLL） 可高效还原私钥。所以绝大多数背包加密都已破解，不再使用了，但它的设计思想和分析方法对于理解现代密码学的原理仍然非常有帮助。 这里我们只介绍最经典的 Merkle-Hellman 背包加密算法，其他的背包加密算法基本上都是在这个基础上进行改进的，只有部分是基于格的（但我们不在这里讲解）。 Merkle-Hellman 背包加密数学原理 😇Merkle-Hellman 背包加密的安全性基于背包问题的困难性。 背包问题是指给定一组物品的重量和一个背包的容量，判断是否存在一种组合使得物品的总重量恰好等于背包的容量。 举个例子：有集合 $A = {3, 5, 7}$ 和一个背包容量 $C = 10$，我们需要判断是否存在一个子集 $S \subseteq A$ 使得 $\...

当我们计算有限域下高次根式的求解时，AMM（Adleman-Manders-Miller）算法就派上了用场。AMM 算法是一种高效的算法，可以在多项式时间内求解有限域下的高次根式问题，这在密码学中有着重要的应用，比如在 RSA 加密算法中求解模 $n$ 下的 $e$ 次根式问题。 欢迎来到《密码学核心算法实战》的 AMM 算法专题！这里没有纸上谈兵的理论空谈（真的不画大饼😉），只有一把把能直接撬动数据安全的精密齿轮⚙️。 AMM 算法 🌟AMM 算法是密码学中专门用于在有限域 $\mathbb{F}_p$ 下求解高次根式的算法。给定一个质数 $p$，一个整数 $a$ 和一个正整数 $e$，我们想要找到一个整数 $x$，使得 $x^k \equiv a \mod p$。 要解之前，首先要先验满足条件： $a \equiv 0 \mod p$，此时 $x = 0$ 是一个解。 $a \not \equiv 0 \mod p$，要先验证解是否存在：a^{\frac{p-1}{\gcd(e, p-1)}} \equiv 1 \mod p AMM 算法的原理 😵首先设 $d = ...