基于图的消息加密算法：原理、应用与安全性分析

### 基于图的消息加密算法：原理、应用与安全性分析 #### 1. 加密基础：图 G1 与消息表示 在信息加密领域，我们从一个完整图 G1 开始。G1 包含 n1 个顶点，记为 \(V_1 = \{v_1, v_2, \cdots, v_{n_1}\}\)，以及 \(m_1 = \frac{n_1(n_1 - 1)}{2}\) 条边，记为 \(E_1 = \{e_1, e_2, \cdots, e_{m_1}\}\)。这里所有边的权重均为正数，连接顶点 \(v_i\) 和 \(v_j\) 的边 \((v_i, v_j)\) 的权重记为 \(w_{i,j}\)。 G1 的特殊之处在于，其某个特定子图的结构和边权重代表了要从发送者 A 安全传输到接收者 B 的消息 M。A 和 B 共享一个秘密的加密/解密密钥 K，且只有他们知晓该密钥。 #### 2. 加密第一步：构建图 G2 加密过程的第一阶段是将图 G1 转换为图 G2。发送者通过添加一组 n 个顶点 \(V = \{v_{n_1 + 1}, v_{n_1 + 2}, \cdots, v_{n_1 + n}\}\) 和一组 m 条加权边 \(E = \{e_{m_1 + 1}, e_{m_1 + 2}, \cdots, e_{m_1 + m}\}\) 来扩充 G1。 这样得到的新图 G2 有 \(n_2 = n_1 + n\) 个顶点，即 \(V_2 = V_1 \cup V\)，以及 \(m_2 = m_1 + m\) 条边，即 \(E_2 = E_1 \cup E\)。添加新顶点和边的目的是隐藏 G1 中顶点和边的身份以及边权重的值。 密钥 K 由两部分组成： - 一系列四元组 \(t_k = (i, j, w_{i,j}^E, o_{i,j})\)，其中： - \(i\) 和 \(j\) 是两个顶点 \(v_i\) 和 \(v_j\) 的索引，且 \(v_i, v_j \in V_2\)，\((v_i, v_j)\) 是要添加到 G1 以得到 G2 的新无向边。 - \(w_{i,j}^E\) 是新边 \((v_i, v_j)\) 的权重。 - \(o_{i,j}\) 为 0 或 1，分别代表加法或乘法。对于所有具有相同 \(i\) 和 \(j\) 的四元组，\(o_{i,j}\) 的值相同，该操作将在加密的倒数第二步使用。 - 一个随机的一对一映射 \(\pi\)，用于在加密的最后一步隐藏顶点的身份，防止恶意窃听者获取信息。 #### 3. 关于加密/解密密钥 密钥 K 仅使用一次。对于每条消息 M，A 和 B 使用商定的均匀随机数生成器和商定的种子同步但连续地生成一个新的加密/解密密钥。新密钥的种子可以是当天早上报纸上商定的数据。 创建密钥 K 的过程如下： 1. 重复 m 次生成以下量（每次迭代生成一个四元组）： - 从集合 \(\{1, 2, \cdots, n_2\}\) 中生成两个不同的正整数 \(i\) 和 \(j\)。 - 生成一个正整数 \(w_{i,j}^E\)。 - 为 \(o_{i,j}\) 生成 0 或 1（如果当前对 \((i,j)\) 之前已为另一个四元组生成过，则 \(o_{i,j}\) 取相同的值）。 2. 生成一组随机正整数 \(U = \{u_1, u_2, \cdots, u_{n_2}\}\) 用于映射 \(\pi\)。 #### 4. 多图 G2 的特性 添加 n 个顶点 V 是为了将 V1 中的顶点隐藏在更大的集合 V2 中。添加 m 条边 E 旨在使 G2 成为一个多图，即两个顶点之间可能有多条边相连。为实现这两个目标，n 和 m 需足够大，但通常是关于 \(n_1\) 的多项式，例如 \(n = n_1^{\alpha} + \beta\) 和 \(m = \gamma \frac{n_2(n_2 - 1)}{2} + \delta\)，其中 \(\alpha, \beta, \gamma, \delta\) 是商定的正整数。 添加到 G1 以创建 G2 的边的权重是随机生成的，但与 G1 中原始边的权重类型和大小相同。 #### 5. 加密第二步：构建图 G3 当多图 G2 构建完成后，加密的第二阶段开始。从 G2 得到一个新的简单图 G3，具体方法是：对于 G2 中的每对顶点 \((v_i, v_j)\)，在 G3 中用一条边连接它们，该边的权重根据 \(o_{i,j}\) 的值确定： - 若 \(o_{i,j} = 0\)，则权重为 G2 中连接这两个顶点的所有边的权重之和。 - 若 \(o_{i,j} = 1\)，则权重为 G2 中连接这两个顶点的所有边的权重之积。 图 G3 是一个简单、无向且完整的图，即每对顶点之间恰好有一条边相连。它有 \(n_3 = n_2 = n_1 + n\) 个顶点，\(V_3 = V_2 = \{v_1, v_2, \cdots, v_{n_1}, v_{n_1 + 1}, \cdots, v_{n_1 + n}\}\)，以及 \(m_3 = \frac{n_2(n_2 - 1)}{2}\) 条边。 加密 G3 的最后一步是使用一对一函数 \(\pi\) 隐藏其顶点的身份。但为了便于理解，我们仍用原始索引 \(v