Page 382 - 《软件学报》2025年第5期

2282 软件学报 2025 年第 36 卷第 5 期

100
90
80
70
成功率 (%) 50 成功率 (%) 100 SEI
60
MLE
90
40
30 HW
80 AD-SEI
20 1 100 1 300
AD-MLE
10 故障数 (个)
AD-HW
0
0 200 400 600 800 1 000 1 200 1 400 1 600 1 800 2 000
故障数 (个)
图 6 各区分器不同故障数下恢复原始密钥的成功率

300
SEI
250 MLE
HW
200
AD-HW
耗时 (min) 150 AD-MLE
AD-SEI
100
50
0
0 400 800 1 200 1 600 2 000
故障数 (个)
图 7 不同故障数下各区分器恢复原始密钥的耗时累加

4.4 复杂度
时间复杂度通常用加解密次数或内存访问次数来衡量, 即在密钥恢复过程中处理所有数据所需的时间资源.
数据复杂度指在恢复密钥过程中所需的数据资源. 计算公式如下:

u
u
mn+2 m+2 w (20)

u
(2 +1)mv (21)
u
其中, m 为区分器达到最大成功率时所需的总故障数, n 为密码的变换轮数, u 为实验需要枚举的密钥长度, 2 m 为
u
实验过程中对所有密文进行处理的次数, w 表示半字节中间状态的可能取值个数, 2 w 为区分器对中间状态进行分
析的次数, v 为密码的分组长度, mv 表示获取受故障影响的密文的数据量. 各区分器的时间复杂度和数据复杂度如
表 7 所示. 在所有的区分器中, 本文提出 AD-SEI、AD-HW 和 AD-MLE 区分器所需的时间复杂度和数据复杂度更低.

表 7 各区分器恢复 128 比特原始密钥的参数比较

区分器 成功率 故障数 时间复杂度 数据复杂度
SEI:AD-SEI 6:99 ∞:2048 ∞:2 35.01 ∞:2 42.00
MLE:AD-MLE 84:99 2080:1408 2 34.92 :2 34.48 2 41.91 :2 41.46
HW:AD-HW 99:99 1472:1408 2 34.54 :2 34.41 2 41.52 :2 41.39

从图 5−图 7 和表 7 的实验结果来看, 新型组合区分器 AD-SEI 和 AD-MLE 能提升 SEI 和 MLE 经典区分器的
较低成功率, 达到 99% 及以上的成功率. 因此, 新型组合区分器能在较短的时间内以更少的故障数、更高的成功
率破解 DEFAULT 密码.