Page 381 - 《软件学报》2026年第5期

2260 软件学报 2026 年第 37 卷第 5 期

1 基础知识

本节首先给出必要的符号说明, 其次简要叙述 DS-MITM 攻击的基本原理, 最后介绍本文使用的量子算法和
量子随机存储器的相关知识.
1.1 符号说明
+
n
+
N : 正整数集; F : 二元有限域 F 2 上的 n 维向量空间, n ∈ N .
2
0 ℓ 长度为 ℓ 的全零比特, ℓ ∈ N .
+
[s]: 集合 {1,2,..., s}, s ∈ N ; : +
P/C: 明/密文; ∆P/∆C: 明/密文差分.
1.2 DS-MITM 攻击
本节介绍 DS-MITM 攻击的相关定义和基本原理.
定义 1. 令 b, n ∈ N , 且 b < n, 若集合 W 满足 n ∈ F 2 ,1 ⩽ i 1 < i 2 < ... < i k < ... < i b ⩽ n, 其
+
2
{r = (x 1 , x 2 ,..., x n ) ∈ F |x i k
(n−b) 个比特取值分别固定为 0 或 b 比特遍历.
余 1}, 则称集合 W 为一个 b-δ-集. 一般地, 取连续的
性质 1. S 盒的性质 [33] . 若给定 S 盒的非零输入差分 ∆x 和输出差分 ∆y, 则方程 S (t)⊕S (t ⊕∆x) = ∆y 平均有一
个解.
DS-MITM 攻击由构造区分器的预计算阶段和进行密钥恢复攻击的在线阶段组成. 攻击的具体过程如下.
1) 预计算阶段
(1.1) 假设存在 N c 个满足 ∆A → ∆B 的差分特征.
(1.2) 选取步骤 (1.1) 中的一条差分特征, 构造满足差分 ∆A 的输入对 (A 0 ,A), 根据定义 1, 利用 A 0 生成一个 b-δ-集,
W = {A 0 ,A 1 ,A 2 ,...,A 2 b −1 }, 如图 1(a) 所示, 其中, b
记为 A r = A 0 ⊕r, r ∈ [2 −1].

(P 0 ,P) ΔP
A r =A 0 ⊕r
密钥恢复 K 1 Pr=p 1
b-δ-集 W={A 0 ,A 1 ,...,A 2 b −1 }
(A 0 ,A 1 ),A 2 ,...,A 2 b −1 (A 0 ,A) ΔA
中间相遇区分器 N c 个特征
(B 0 ,B) ΔB
(B 0 ,B 1 ),B 2 ,...,B 2 b −1
Δ 2 b −1 密钥恢复
Δ 2 K 2 Pr=p 2
Δ 1
Δ-序列 Γ=(Δ 1 ,Δ 2 ,...,Δ 2 b −1 )
(C 0 ,C) ΔC
(a) Δ-序列生成过程 (b) 密钥恢复过程
图 1 DS-MITM 攻击概述

b
(1.3) 将输入对 (A 0 ,A r ) 进行加密得到输出对 (B 0 ,B r ), 并计算 ∆ r = B 0 ⊕ B r , r ∈ [2 −1].
(1.4) 由 ∆ r 生成 ∆-序列 Γ = (∆ 1 ,∆ 2 ,...,∆ 2 b −1 ) ∈ F (2 b −1)×λ , λ 为 ∆ r 的比特长度, 并删除此差分特征.
2
(1.5) 重复步骤 (1.2)–(1.4), 以 ∆ r 为索引, 将 N c 个序列存储在表 T δ 中.
2) 在线阶段

(2.1) 选择足够多的明文对进行加密, 使得其中至少存在一对明密文 (P 0 ,P) 和 (C 0 ,C) 同时满足 ∆P → ∆A,
∆C → ∆B, 如图 1(b) 所示.
b
(2.2) 根据 P 0 构造对应的 b-δ-集, 由此得到 2 个明文, 对其依次进行加密得到相应的密文.
(2.3) 分别猜测子密钥 K 1 , K 2 的值, 并利用 K 2 对步骤 (2.2) 的密文进行部分解密, 可得区分器输出处的 ∆-序
′
列 Γ .
′ Γ 进行匹配, 若匹配成功, 则猜测的子密钥为正确密钥; 否则, 匹配不成功, 另外选取一对明文重
(2.4) 将 Γ 与
复上述步骤 (2.1)–(2.4).
/
−1
需要说明的是, 当 (p 1 p 2 ) N c ×2 −(2 b −1)×λ ≪ 1, 即 b ≫ log [1−log (p 1 p 2 / N c ) λ] 时, 一定存在正确密钥.
2
2