造福下一届，人人有责。

所属实验：西安邮电大学 - 网络空间安全学院 - 密码学基础 - 课程设计实验

实验时间：2024年上半年

接 信息安全密码学基础 - 实验代码，这里有各个实验的实验代码。

Markdown 文件位于 daaihang/static-resource/docs/2024-06-28-信息安全-密码学基础实验-实验原理.md。

对称加密

古典密码Hill密码

数学公式原理

在 Hill 密码中，加密和解密过程都依赖于矩阵运算。对于一个给定的加密矩阵 $A$ 和明文向量 $P$，密文向量 $C$ 可以通过矩阵乘法得到：

$$ C = A \times P \pmod{n} $$

这里，$n$ 是字符集的大小。例如，对于标准的字母表（A-Z），$n$ 为 26；对于ASCII可见字符集，$n$ 为 94。

要对密文进行解密，我们需要找到加密矩阵 $A$ 的逆矩阵 $A^{-1}$，使得：

$$ A \times A^{-1} \equiv I \pmod{n} $$

其中，$I$ 是单位矩阵。

逆矩阵 $A^{-1}$ 的计算步骤如下：

  1. 行列式的计算：首先计算矩阵 $A$ 的行列式 $\det(A)$。行列式的计算方法如下： $$ \det(A) = \sum_{i=1}^n (-1)^{i+j} a_{ij} \det(M_{ij}) $$ 其中，$M_{ij}$ 是从矩阵 $A$ 中删除第 $i$ 行和第 $j$ 列得到的子矩阵。

  2. 行列式的模逆：为了在模 $n$ 的情况下找到逆矩阵，我们需要行列式 $\det(A)$ 的模逆 $(\det(A))^{-1} \pmod{n}$。行列式 $\det(A)$ 的模逆必须满足： $$ \det(A) \times (\det(A))^{-1} \equiv 1 \pmod{n} $$ 这要求 $\det(A)$ 和 $n$ 互质，即 $\gcd(\det(A), n) = 1$。

  3. 伴随矩阵的计算：计算矩阵 $A$ 的伴随矩阵（即代数余子式矩阵的转置）。伴随矩阵 $\text{adj}(A)$ 的计算方法如下： $$ \text{adj}(A) = \left( (-1)^{i+j} \det(M_{ij}) \right)^T $$ 其中，$M_{ij}$ 是从矩阵 $A$ 中删除第 $i$ 行和第 $j$ 列得到的子矩阵。

  4. 求逆矩阵：将伴随矩阵 $\text{adj}(A)$ 与行列式的模逆 $(\det(A))^{-1}$ 相乘，取模 $n$ 即得矩阵 $A$ 的逆矩阵： $$ A^{-1} \equiv \text{adj}(A) \times (\det(A))^{-1} \pmod{n} $$

代码原理

在代码中，我们使用 Python 的 SymPy 库来实现上述数学运算。具体步骤如下：

  1. 生成可逆矩阵：使用 numpy 生成一个随机的 $n \times n$ 矩阵，并确保其行列式在模 $n$ 下是可逆的（即 $\gcd(\det(A), n) = 1$）。如果行列式不可逆，则重新生成矩阵，直到找到可逆矩阵。

  2. 计算行列式和模逆：使用 SymPy 的 Matrix 类将 numpy 数组转换为 SymPy 矩阵，并计算其行列式。然后，使用 inv_mod 方法计算行列式的模逆。

  3. 计算伴随矩阵和逆矩阵：使用 SymPy 的 adjugate 方法计算伴随矩阵，然后将伴随矩阵与行列式的模逆相乘，得到逆矩阵。

  4. 文本和数字转换：定义函数将文本转换为数字列表（对应于 ASCII 值减去最小的可见 ASCII 值），以及将数字列表转换回文本。

  5. 加密和解密函数：定义 Hill 加密和解密函数，分别使用加密矩阵和逆矩阵对消息进行矩阵乘法运算，结果取模 $n$，然后转换回文本。

通过这些步骤，我们可以实现包含所有可见 ASCII 字符的 Hill 密码加密和解密。

置换密码

数学公式原理

置换密码是一种简单且有效的对称加密方法。它通过将明文中的每个字符替换为另一个字符来实现加密。置换密码使用一个置换表来定义这种映射。具体步骤如下：

  1. 置换表的生成： 生成一个包含所有可能字符的随机排列，形成置换表。对于长度为 $n$ 的字符集 ${a_1, a_2, \ldots, a_n}$，置换表可以视为一个排列 $\sigma$，其将字符 $a_i$ 映射到字符 $a_{\sigma(i)}$。

  2. 加密： 用置换表 $\sigma$ 将消息中的每个字符 $m_i$ 映射为密文字符 $c_i$： $$ c_i = \sigma(m_i) $$

  3. 解密： 使用逆置换表 $\sigma^{-1}$ 将密文字符 $c_i$ 还原为明文字符 $m_i$： $$ m_i = \sigma^{-1}(c_i) $$

  4. 逆置换表的计算： 若置换表 $\sigma$ 将字符 $a_i$ 映射到字符 $a_j$，则逆置换表 $\sigma^{-1}$ 将字符 $a_j$ 映射回字符 $a_i$。

代码原理

在代码实现中，我们使用 Python 语言来生成置换表、计算逆置换表，并进行加密和解密操作。具体步骤如下：

  1. 定义可见 ASCII 字符范围： 包含从 ASCII 码 32 到 126 的所有可见字符，这些字符将构成我们的字符集。

  2. 生成随机置换表： 创建一个包含所有字符的列表，然后使用 random.shuffle 函数对其进行随机排列，得到置换表。

  3. 生成逆置换表： 根据置换表生成逆置换表，逆置换表中的每个位置指向置换表中对应字符的位置。

  4. 置换加密函数： 定义加密函数，使用置换表对消息中的每个字符进行替换。

  5. 置换解密函数： 定义解密函数，使用逆置换表对密文中的每个字符进行替换。

AES

数学公式原理

AES（高级加密标准）是一种对称加密算法，用于加密和解密数据。AES 使用固定长度的密钥（128, 192 或 256 位）来对数据进行加密和解密。AES 支持多种工作模式，包括 CBC（Cipher Block Chaining）和 OFB（Output Feedback）。

CBC模式：

  • 加密：每个明文分组在加密前与前一个密文分组进行异或（XOR）操作。第一个明文分组与初始化向量（IV）进行异或。 $$ C_i = E_K(P_i \oplus C_{i-1}) $$ 其中，$C_i$ 是第 $i$ 个密文分组，$P_i$ 是第 $i$ 个明文分组，$E_K$ 是加密函数，$K$ 是密钥，$C_{i-1}$ 是前一个密文分组，$C_0$ 是 IV。

  • 解密：每个密文分组在解密后与前一个密文分组进行异或操作。第一个密文分组与 IV 进行异或。 $$ P_i = D_K(C_i) \oplus C_{i-1} $$

OFB模式：

  • 加密：使用加密函数对前一个输出块进行加密，然后与明文分组进行异或操作。初始块是 IV。 $$ O_i = E_K(O_{i-1}) $$ $$ C_i = P_i \oplus O_i $$

  • 解密：解密过程与加密过程相同，因为 OFB 是流模式。 $$ P_i = C_i \oplus O_i $$

代码原理

在 Python 中，我们可以使用 cryptography 库来实现 AES 加密和解密。以下是具体步骤：

  1. 安装 cryptography 库：确保安装 cryptography 库。
  2. 导入库和模块：导入 cryptography.hazmat.primitives.ciphers 模块中的 Cipher, algorithms, modes 以及相关的 padding 模块。
  3. 定义密钥和 IV：生成或指定用于加密和解密的密钥和初始化向量（IV）。
  4. 实现 AES 加密和解密函数：使用 Cipher 创建 AES 加密器和解密器。
  5. 实现 CBC 和 OFB 模式：使用相应的模式进行加密和解密。

非对称加密

RSA算法

RSA算法是一种基于数论的公钥密码算法，其主要原理包括大素数生成、模运算和欧拉函数等数学概念。以下是RSA算法的详细数学原理：

1. 生成大素数 $p$ 和 $q$

选择两个大素数 $p$ 和 $q$，它们需要足够大以确保安全性。我们通过以下方式生成它们：

$$ p, q \in \text{Prime Numbers} $$

2. 计算模数 $n$

将两个素数相乘得到模数 $n$：

$$ n = p \times q $$

3. 计算欧拉函数 $\phi(n)$

欧拉函数 $\phi(n)$ 表示小于 $n$ 且与 $n$ 互质的整数个数。对于两个素数 $p$ 和 $q$ 而言：

$$ \phi(n) = (p - 1) \times (q - 1) $$

4. 选择公钥指数 $e$

选择一个整数 $e$，使得 $1 < e < \phi(n)$ 且 $e$ 与 $\phi(n)$ 互质。通常选择 65537 作为 $e$，因为它既是素数，又能高效计算：

$$ \gcd(e, \phi(n)) = 1 $$

5. 计算私钥指数 $d$

计算私钥指数 $d$，使得 $d$ 是 $e$ 模 $\phi(n)$ 的乘法逆元，即满足以下条件：

$$ d \times e \equiv 1 \ (\text{mod} \ \phi(n)) $$

6. 公钥和私钥

公钥由 $(e, n)$ 组成，私钥由 $(d, n)$ 组成。

$$ \text{Public Key} = (e, n) $$ $$ \text{Private Key} = (d, n) $$

7. 加密过程

将消息 $m$ 转换为整数 $m$ 后，使用公钥加密：

$$ c = m^e \ (\text{mod} \ n) $$

8. 解密过程

将密文 $c$ 使用私钥解密得到原文 $m$：$$ m = c^d \ (\text{mod} \ n) $$

ElGamal

密钥生成

密钥生成的步骤如下：

  1. 生成循环群描述

    Alice利用生成元 $g$ 产生一个 $q$ 阶循环群 $G$ 的有效描述。该循环群需要满足一定的安全性质。

  2. 选择私钥

    Alice从集合 ${1, \ldots, q-1}$ 中随机选择一个整数 $x$。

  3. 计算公钥

    Alice计算 $ h := g^x $。

  4. 公开公钥

    Alice公开 $h$，以及循环群 $G$、阶数 $q$ 和生成元 $g$ 的描述作为其公钥，并保留 $x$ 作为其私钥。私钥必须保密。

加密

使用Alice的公钥 $(G, q, g, h)$ 向她加密一条消息 $m$ 的加密算法工作方式如下：

  1. Bob生成临时密钥

    Bob从集合 ${1, \ldots, q-1}$ 随机选择一个整数 $y$，然后计算 $ c_1 := g^y $。

  2. 计算共享秘密

    Bob计算 $ s := h^y $。

  3. 映射消息

    Bob把他要发送的秘密消息 $m$ 映射为 $G$ 上的一个元素 $m’$。

  4. 计算密文

    Bob计算 $ c_2 := m’ \cdot s $。

  5. 发送密文

    Bob将密文 $ (c_1, c_2) = (g^y, m’ \cdot h^y) = (g^y, m’ \cdot (g^x)^y) $ 发送给Alice。

    注意：如果一个人知道了 $m’$，那么它很容易就能知道 $h^y$ 的值。因此，对每一条信息都产生一个新的 $y$ 可以提高安全性。因此 $y$ 也被称作临时密钥。

解密

利用私钥 $x$ 对密文 $(c_1, c_2)$ 进行解密的算法工作方式如下：

  1. 计算共享秘密

    Alice计算 $ s := c_1^x $。

  2. 计算消息

    然后计算 $ m’ := c_2 \cdot s^{-1} $，并将其映射回明文 $m$，其中 $s^{-1}$ 是 $s$ 在群 $G$ 上的逆元。

解密算法能够正确解密出明文，因为：$ c_2 \cdot s^{-1} = m’ \cdot h^y \cdot (g^{xy})^{-1} = m’ \cdot g^{xy} \cdot g^{-xy} = m’ $。

认证技术

消息认证码（MAC）

MAC

HMAC数学原理

消息认证码（Message Authentication Code, MAC）是一种保证消息完整性和认证性的算法。基于Hash算法的MAC通常称为HMAC（Hashed Message Authentication Code）。HMAC结合一个秘密密钥与一个哈希函数来生成消息摘要，从而验证消息的完整性和真实性。

HMAC

1. HMAC的基本结构

HMAC由以下元素组成：

  • 哈希函数 $H$：如SHA-256
  • 密钥 $K$：长度为 $B$ 字节，其中 $B$ 是哈希函数的块大小
  • 内部填充值 $ipad$：通常是0x36
  • 外部填充值 $opad$：通常是0x5C

2. 密钥填充

如果密钥 $K$ 的长度超过块大小 $B$，则对 $K$ 进行哈希：

$$ K’ = \begin{cases} K & \text{if } |K| = B \ H(K) & \text{if } |K| > B \ K \parallel \text{(zero-padding to } B \text{ bytes)} & \text{if } |K| < B \end{cases} $$

其中，$|K|$ 表示密钥 $K$ 的字节长度，$\parallel$ 表示字符串的连接操作。

3. 内部密钥和外部密钥

将密钥 $K’$ 与内部填充值 $ipad$ 和外部填充值 $opad$ 进行异或操作：

$$ K_{ipad} = K’ \oplus ipad $$ $$ K_{opad} = K’ \oplus opad $$

4. 生成MAC

将消息 $M$ 与内部密钥连接，进行一次哈希：

$$ \text{inner} = H(K_{ipad} \parallel M) $$

然后将内部哈希结果与外部密钥连接，进行第二次哈希，得到最终的HMAC值：

$$ HMAC(K, M) = H(K_{opad} \parallel \text{inner}) = H(K_{opad} \parallel H(K_{ipad} \parallel M)) $$

5. HMAC公式总结

根据RFC 2104，HMAC的数学公式为：

$$ HMAC(K, M) = H((K’ \oplus opad) \parallel H((K’ \oplus ipad) \parallel M)) $$

其中：

  • $K’$ 是填充后的密钥。如果K短于散列函数的输入块大小，则向右填充（Padding）零；如果比该块大小更长，则对K进行散列
  • $ipad$ 和 $opad$ 是内部和外部填充值
  • $\parallel$ 表示字符串连接
  • $\oplus$ 表示按位异或操作
  • $H$ 是所选择的哈希函数（如SHA-256）

RSA数字签名算法

1. 密钥生成

RSA数字签名算法的密钥生成步骤与RSA加密算法相同，包括以下步骤：

  1. 选择两个大素数 $p$ 和 $q$： $$ p, q \in \text{Prime Numbers} $$

  2. 计算模数 $n$： $$ n = p \times q $$

  3. 计算欧拉函数 $\phi(n)$： $$ \phi(n) = (p - 1) \times (q - 1) $$

  4. 选择公钥指数 $e$，满足： $$ 1 < e < \phi(n) \quad \text{且} \quad \gcd(e, \phi(n)) = 1 $$

  5. 计算私钥指数 $d$，使得： $$ d \times e \equiv 1 \ (\text{mod} \ \phi(n)) $$

公钥和私钥分别为： $$ \text{Public Key} = (e, n) $$ $$ \text{Private Key} = (d, n) $$

2. 签名生成

签名生成使用消息摘要（哈希值）和私钥。具体步骤如下：

  1. 计算消息 $M$ 的哈希值 $H(M)$： $$ h = H(M) $$

  2. 使用私钥 $(d, n)$ 对哈希值进行签名，计算签名 $S$： $$ S = h^d \ (\text{mod} \ n) $$

3. 签名验证

签名验证使用公钥。具体步骤如下：

  1. 接收者使用相同的哈希函数计算消息 $M$ 的哈希值 $H(M)$： $$ h’ = H(M) $$

  2. 使用发送者的公钥 $(e, n)$ 对签名 $S$ 进行验证，计算验证值 $V$： $$ V = S^e \ (\text{mod} \ n) $$

  3. 检查验证值 $V$ 是否等于接收者计算的哈希值 $h’$： $$ V \stackrel{?}{=} h’ $$

如果 $V = h’$，则签名验证通过，消息的真实性和完整性得到保证；否则，验证失败。

ElGamal数字签名算法

ElGamal数字签名算法是一种基于离散对数问题的数字签名方案。它由三个主要步骤组成：密钥生成、签名生成和签名验证。

1. 密钥生成

  1. 选择素数 $p$：选择一个大素数 $p$。

  2. 选择生成元 $g$：选择一个生成元 $g$，使得 $g$ 是模 $p$ 的一个原根。

  3. 选择私钥 $x$：选择一个随机数 $x$，其中 $1 < x < p-1$。

  4. 计算公钥 $y$：根据私钥 $x$ 和生成元 $g$ 计算公钥 $y$： $$ y = g^x \ (\text{mod} \ p) $$

公钥和私钥分别为： $$ \text{Public Key} = (p, g, y) $$ $$ \text{Private Key} = x $$

2. 签名生成

为了对消息 $M$ 进行签名，签名者执行以下步骤：

  1. 计算消息哈希值 $H(M)$：将消息 $M$ 通过哈希函数 $H$ 生成哈希值 $h$： $$ h = H(M) $$

  2. 选择随机数 $k$：选择一个随机数 $k$，其中 $1 < k < p-1$ 且 $k$ 与 $p-1$ 互质。

  3. 计算临时值 $r$：根据生成元 $g$ 和随机数 $k$ 计算临时值 $r$： $$ r = g^k \ (\text{mod} \ p) $$

  4. 计算签名值 $s$：根据哈希值 $h$、私钥 $x$、随机数 $k$ 和临时值 $r$ 计算签名值 $s$： $$ s = (h - xr)k^{-1} \ (\text{mod} \ (p-1)) $$ 其中，$k^{-1}$ 是 $k$ 模 $(p-1)$ 的乘法逆元。

签名为： $$ \text{Signature} = (r, s) $$

3. 签名验证

为了验证签名 $(r, s)$ 是否由消息 $M$ 生成，验证者执行以下步骤：

  1. 计算消息哈希值 $H(M)$：将消息 $M$ 通过哈希函数 $H$ 生成哈希值 $h$： $$ h = H(M) $$

  2. 验证签名值 $r$：检查 $r$ 是否在区间 $1 \leq r \leq p-1$ 内。如果不在，则签名无效。

  3. 计算验证值： $$ v_1 = y^r \cdot r^s \ (\text{mod} \ p) $$ $$ v_2 = g^h \ (\text{mod} \ p) $$

  4. 验证： 如果 $v_1 \equiv v_2 \ (\text{mod} \ p)$，则签名有效；否则，签名无效。

密钥管理

DH密钥交换协议

Diffie-Hellman（DH）密钥交换协议是一种公钥密码体制，用于安全地交换密钥。它允许两个通信方在公开信道上交换信息，而无需事先共享密钥。

1. 参数选择

  1. 选择素数 $p$：选择一个大素数 $p$。

  2. 选择生成元 $g$：选择一个整数 $g$，称为生成元，它是模 $p$ 的一个原根。通常情况下，$g$ 的选择是一个小质数，如 $g = 2$ 或 $g = 5$。

2. 密钥生成

假设有两个通信方，Alice 和 Bob，他们希望在公开信道上安全地交换密钥。

  1. Alice 和 Bob 各自生成私钥：

    • Alice 选择一个随机整数 $a$，称为私钥。
    • Bob 选择一个随机整数 $b$，称为私钥。

  2. 计算公钥：

    • Alice 计算公钥 $A$： $$ A = g^a \ (\text{mod} \ p) $$
    • Bob 计算公钥 $B$： $$ B = g^b \ (\text{mod} \ p) $$

  3. 交换公钥：

    • Alice 将公钥 $A$ 发送给 Bob。
    • Bob 将公钥 $B$ 发送给 Alice。

3. 密钥协商

  1. 计算共享密钥：
    • Alice 使用 Bob 发送的公钥 $B$ 计算共享密钥 $K$： $$ K = B^a \ (\text{mod} \ p) $$
    • Bob 使用 Alice 发送的公钥 $A$ 计算共享密钥 $K$： $$ K = A^b \ (\text{mod} \ p) $$

DH密钥交换协议的安全性依赖于离散对数问题的难度。具体来说，即使攻击者可以监听公开信道上的所有通信，但由于他们无法有效地计算离散对数，因此无法推导出通信双方的私钥或共享密钥。

Shamir秘密共享方案

Shamir秘密共享方案是一种多方安全密钥管理技术，由Adi Shamir于1979年提出。它允许将秘密分成多个部分，称为共享，这些共享可以分发给不同的实体，只有当足够多的共享组合在一起时才能重构出原始秘密。

1. 参数选择

  1. 选择一个大素数 $p$：用作有限域的模数，通常要求 $p$ 足够大以确保安全性。

  2. 选择秘密 $S$：要共享的原始秘密，通常表示为一个整数，$0 \leq S < p$。

  3. 选择阈值 $t$ 和参与者数 $n$ **：阈值 $t$ 表示重构秘密所需的最少共享数，参与者数 $n$ 表示生成的共享数。

2. 共享生成

  1. 生成随机系数 $a_1, a_2, \ldots, a_{t-1}$：在 $\mathbb{Z}_p$ 中随机选择 $t-1$ 个系数，其中每个系数 $a_i$ 都是随机选择的。

  2. 构造多项式 $f(x)$：多项式 $f(x)$ 的形式如下，其中 $f(0) = S$ 是原始秘密： $$ f(x) = S + a_1 x + a_2 x^2 + \ldots + a_{t-1} x^{t-1} \ (\text{mod} \ p) $$

  3. 生成共享：对于每个参与者 $i$，计算共享 $(x_i, y_i)$： $$ y_i = f(x_i) \ (\text{mod} \ p) $$ 其中，$x_i$ 是一个不同的非零元素 $\mathbb{Z}_p^*$，通常 $x_i = i$。

3. 重构秘密

为了重构原始秘密 $S$，至少需要 $t$ 个共享。这是通过拉格朗日插值法实现的。

  1. 拉格朗日插值法：假设我们有 $t$ 个共享 $(x_i, y_i)$，其中 $x_i$ 是非零元素 $\mathbb{Z}p^*$。拉格朗日插值多项式 $L(x)$ 定义如下： $$ L(x) = \sum{j=1}^{t} y_j \cdot \prod_{\substack{1 \leq m \leq t \ m \neq j}} \frac{x - x_m}{x_j - x_m} \ (\text{mod} \ p) $$

  2. 计算原始秘密 $S$：通过插值多项式计算 $L(0)$： $$ S = L(0) \ (\text{mod} \ p) $$

Shamir秘密共享方案的安全性基于大整数分解问题和离散对数问题的复杂性，这些问题在有限域 $\mathbb{Z}_p$ 中很难解决。只有持有足够的共享数 $t$ 才能重构出原始秘密 $S$，而持有少于 $t$ 个共享数的任何组合都无法揭示秘密。