基于变步长约瑟夫遍历和DNA动态编码的图像加密算法的安全性分析

冯 伟 张 靖* 秦振涛 何怡刚

①(攀枝花学院数学与计算机学院 攀枝花 617000)

②(武汉大学电气与自动化学院 武汉 430072)

1 引言

如今，数字图像作为能生动传达信息的载体，应用变得日益广泛[1]。由于涉及隐私保护等，在使用过程中，为其提供安全、高效的保护成为人们关注的焦点[2]。在各种保护技术中，图像加密最直接和有效。不同于文本，图像有许多显著特征。例如，数据量大、信息冗余度高等。在众多应用环境下，数据加密标准等传统加密算法并不适合图像数据[3]。为了不断提高图像加密的效率和安全性，研究人员一直致力于利用新的技术和方法来设计图像加密算法[4—11]。其中，混沌系统因具有众多适合设计密码系统的特性，正日益受到研究人员的青睐[1—3,5,7,8,11]。

混沌系统于20世纪90年代开始应用于图像加密[12]。从此，基于混沌系统的图像加密就逐渐受到了人们的关注。近年来，研究人员仍在致力于不断提高混沌图像加密的合理性、实用性和安全性[13—18]。2018年，Wu等人[13]设计了基于脱氧核糖核酸(Deoxyribo Nucleic Acid, DNA)序列操作和时空混沌的图像加密算法。其中，明文图像先被转换为DNA矩阵，后再进行置乱。多次DNA序列操作后，所得矩阵最终被转换成密文图像。2019年，采用离散混沌映射，Chai等人[14]提出了基于DNA序列操作的图像加密算法。该算法进行DNA平面级置乱，并通过对置乱矩阵进行异或来生成密文图像。2020年，Zefreh[15]利用DNA计算、混沌系统和散列算法设计了一种图像加密算法，该算法对明文图像进行DNA级置乱和扩散。随着图像加密技术的发展，也有研究人员致力于相关的密码分析工作。2016年，对于仅置乱的图像加密算法，Jolfaei等人[16]证实了此类加密算法是不安全的。2018年，对于采用DNA计算的超混沌图像加密算法，Feng等人[17]指出了其中存在的合理性、实用性和安全性问题，并通过选择明文攻击将其破解。同年，对于经常被用来评估图像加密算法安全性的相关测试，Preishuber等人[18]证实了这些测试只是确保算法具有安全性的必要条件，而非充分条件。2020年，对于基于混沌映射和DNA编码的图像加密算法，Chen等人[19]将其简化为替换-置乱结构，并利用选择明文攻击将其破解。另外，特别值得注意的是，Li等人[10]回顾了图像加密及其密码分析领域的一些代表性工作，并对这些工作进行了分类和总结。更为重要的是，他们还指出了图像加密及其密码分析领域中存在的一些挑战性问题。

毋庸置疑，对于密码分析工作中指出的问题，研究人员在设计新的图像加密算法时都会加以重视。因此，针对图像加密算法的密码分析工作能促进图像加密技术的发展与完善。本文对名为基于变步长约瑟夫遍历和DNA动态编码的图像加密算法(Image Encryption Algorithm based on Variable step length Josephus traversing and DNA dynamic encoding, IEA-VJD)[20]进行了分析与评估。简要描述IEA-VJD后，本文讨论了其中存在的问题，对其加密过程进行了密码分析，并提出了相应的选择明文攻击算法。最后，本文还针对现有图像加密算法中的常见问题，提出了一些改进建议。

2 算法简要描述与讨论

本节简要描述IEA-VJD，相关详细信息，请参阅文献[20](如无特别说明，本文以下所有“原论文”均指文献[20])。如图1所示，IEA-VJD分为4个部分，即混沌序列的生成、基于变步长约瑟夫遍历的像素行列置乱、基于DNA动态编码的像素替换及像素行列扩散。由于原论文的算法描述存在问题，本文描述IEA-VJD时，调整了其中的部分公式和符号。

2.1 混沌序列的生成

对于大小为M×N的明文图像P，用Keccak算法计算其散列值K，并等分为32个字节，即k1, k2,···, k32。利用中，系统控制参数(a, b, c)=(10, 28, 8/3)。最后，利用

将x,y,z转换成序列X,Y,Z。其中，mod(r1,r2)为对参数r1进行模r2运算，floor(r)为对参数r向下取整。

2.2 基于变步长约瑟夫遍历的像素行列置乱

以列优先方式将序列X和Y重组为M×N矩阵。将X的每个行向量作为变步长约瑟夫遍历的步长序列，利用变步长约瑟夫遍历来逐行置乱明文图像P。再利用Y以类似方式进行逐列置乱，得到置乱图像T。

2.3 基于DNA动态编码的像素替换

对置乱图像T进行DNA动态编码。每个像素均采用不同的编码规则编码为4个碱基，得到DNA编码序列E。每个像素所采用的编码规则Ri,j取决于像素Ti,j所处的位置(i, j)以及序列Z。

其中，i = 1, 2, ···, M，j = 1, 2, ···, N。从GenBank数据库下载DNA序列，截取其中的4×M×N个碱基。将这些碱基与DNA编码序列E进行DNA异或运算。最后，采用编码规则1对运算结果进行DNA解码，并将其重组为中间密文图像I。

2.4 像素行列扩散

以列优先方式将序列Z重组为M×N矩阵。行扩散操作以列向量形式在行的方向上进行。

其中，C'i为行扩散操作后得到的中间密文图像C'的第i列，Ii和Zi分别为I与Z的第i列，i = 3, 4,···, N。接着进行列扩散操作，从而得到最终密文图像C。

其中，Ci为列扩散操作后得到的C的第i行，C'i和Zi分别为C'与Z的第i行，i = 3, 4, ···, M。IEA-VJD的解密过程是其加密过程的逆过程，在此不再重复。

2.5 算法相关讨论

本节讨论和分析IEA-VJD中存在的一些问题。

讨论1 混沌序列x转换成序列X时，原论文式(2)使用的模数是256，而不是图像的列数N。

分析：矩阵形式的X被用来实现像素的逐行置乱。因此，约瑟夫遍历可变步长的取值范围应为[1,N]，而不是[1, 256]。否则N ≫256时，像素的置乱会被局限在较小范围。混沌序列y的转换同样如此。

讨论2 根据原论文式(5)计算DNA编码规则Ri,j，其取值范围为[0, 7]。此外，原论文式(5)中使用的混沌序列元素为Z(i—1)×N+1。

分析：根据原论文表1(算法1)、3.6节和第4节的描述，编码规则取值范围应为[1, 8]。另外，为最大限度确保编码规则的随机性和动态性，应更充分地利用Z。因此，计算Ri,j应使用本文式(5)中的Z(i—1)×N+j。

表1 像素扩散效果消除算法

讨论3 扩散过程的描述不一致。此外，如输入图像行数或列数小于4，扩散过程无法正常工作。

分析：结合原论文图1对行置乱效果的展示，从原论文式(6)来看，IEA-VJD的行扩散是以列向量形式进行的。即同时将某个列上的像素对应地扩散到其他列，是在行的方向上对列进行扩散。而原论文在对式(6)进行说明时，又称“Pi表示图像矩阵的第i行。同样地，也可以用式(6)对列进行扩散”。

扩散过程无法正常工作的问题，仅讨论N ＜4的情况，M ＜ 4与之类似。N = 1时，原论文式(6)中的PN—1无意义。N = 2时，原论文式(6)退化成

显然，这也是不合理且无意义的扩散结果。N =3时，原论文式(6)退化成

由式(9)可知，此时扩散不可逆。即已知P'和Q，只能求得P3，无法求得P1和P2。另外，原论文式(6)中的模256运算也是冗余的。对P2进行扩散操作时，也应使用Q2。

讨论4 IEA-VJD需从GenBank数据库下载DNA序列，从中截取4×M×N个碱基。

分析 加密大小为M×N的明文图像，加密方至少需安全地从GenBank数据库获取4×M×N个碱基。解密方要完成解密也同样如此。换言之，通过不安全信道传送大小为M×N的明文图像，选择IEA-VJD来实现图像的加密保护，加密方和解密方都需安全地从第三方下载至少相同长度的数据。显然，这一设计使得加密毫无意义。合理的设计应为采用混沌系统来生成所需碱基数据。

讨论5 对IEA-VJD秘密密钥的描述不一致。此外，出现的两种秘密密钥描述都有问题。

讨论6 对密文图像进行简单处理，即可使加密结构从置乱-替换-扩散结构退化为置乱-替换结构。

此时虽不能直接获得C'，但可完全消除列扩散过程的像素扩散效果，从而使处理后的密文只有与Z异或所产生的替换效果。类似地，也可消除行扩散过程的像素扩散效果，并最终得到只有像素替换效果的密文图像。此时，IEA-VJD已退化为置乱-替换-替换结构。而连续的二次替换，其加密效果与一次替换无异。

3 密码分析和攻击算法

对于大小为M×N的密文图像C，已知其由IEAVJD生成，使用未知秘密密钥K，对应明文图像为P。选择明文攻击条件下，攻击者可任意选择特殊明文图像，并获得利用未知秘密密钥K生成的对应密文图像[16—17]。如第2.5节所述，无论IEA-VJD是否将图像散列值用作秘密密钥，其秘密密钥设计都有问题，都不符合现代密码系统的设计要求。因此，合理假设攻击者能使Keccak算法失效，即不能不停更换K。

3.1 密码分析

根据第2节及原论文的3.6节，可将IEA-VJD描述为

在E(S)的第i列中，查找任意密文图像的每个像素c*i(i = 1, 2, ···, M×N)，从而确定每个像素在替换操作之前的值。这样一来，就能消除IEA-VJD的像素替换效果，使其进一步退化为只有像素置乱效果。仅置乱的图像加密算法已被证实是不安全的[16]，本文选择较为简便的方式来获得其等价置乱矩阵E(P)。首先，将大小为M×N的全0值明文图像的前255个像素分别替换为1, 2, ···, 255。得到其对应密文图像后，消除该密文图像的像素扩散和替换效果。经过处理的密文图像只有像素置乱效果，可在其中找到每个非0值明文像素的对应位置。这样一来，就可确定明文图像前255个非0值像素置乱之后的位置。以此类推，可同样确定剩余的M×N—255个明文像素置乱之后的位置。每次可最多确定255个像素的位置，因此最多需要floor(M×N/255)+1张选择明文图像及其对应密文图像来确定E(P)。

3.2 选择明文攻击算法

从3.1节可看出，利用最多256+floor(M×N/255)+1张选择明文图像及其对应密文图像，即可完全破解IEA-VJD。以下给出具体的攻击算法。先给出像素扩散效果消除算法，如表1所示。

接下来，给出完整的选择明文攻击算法，如表2(算法2)所示。

表2 选择明文攻击算法

4 实验结果与分析

为确认所提攻击算法的有效性与可行性，本节进行实验验证。实验图像为Lena, Cameraman及USC-SIPI图像数据库的5.2.09.tiff与gray21.512.tiff。实验软硬件配置为Intel(R) Xeon(R)CPU E3-1231处理器、8 GB内存、64 bit Windows 7 U l t i m a t e 操作系统及M A T L A B R 2 0 1 7 a(9.2.0.538062)实验平台。

不失一般性，使用10组随机生成的秘密密钥进行实验。首先对明文图像P进行加密，得到并保存密文图像C；其次，使用算法1消除C的扩散效果，并保存消除扩散效果后的密文图像C(2)；再次，使用算法2恢复明文图像。即先获取等价替换矩阵和等价置乱矩阵。然后，利用等价替换矩阵消除C(2)的替换效果，并保存消除替换效果后的密文图像C(3)；最后，利用等价置乱矩阵消除C(3)的置乱效果，并保存消除置乱效果后的图像P(R)。在10轮共200次的攻击实验中，本文所提攻击算法都完全恢复了明文图像。表3展示了最后一轮攻击实验中保存的各攻击阶段的图像。可见，本文所提攻击算法是有效的。

表3 攻击算法有效性测试结果

攻击算法主要包含3个部分，即消除密文图像的扩散效果、替换效果及置乱效果。由于选择明文图像的加密可由多个计算单元并行完成，能事先准备，以下的计算复杂性分析和实验时间统计均不考虑选择明文图像的加密。即攻击者可直接读取准备好的所有选择明文图像对应的密文图像。根据算法1，消除扩散效果需对长度为N的行向量进行2×M次计算，对长度为M的列向量进行2×N次计算，故计算复杂性为O(M×N)；根据算法2，消除替换效果，需获取等价替换矩阵，并在其中查找每个密文像素。而获取等价替换矩阵，需读入256张大小为M×N的密文图像。查找每个密文像素，需在等价替换矩阵的M×N个列中依次查找，列长为256。因此，消除替换效果的计算复杂性为O(M×N)；类似地，消除置乱效果，需获取等价置乱矩阵，并根据其重排每个密文像素，可知其计算复杂性为O((M×N)2)。表4展示了不同输入规模下，各攻击步骤所需平均时间。可看出，这些实验结果与上述计算复杂性分析基本一致。因此，本文所提攻击算法在计算上也是可行的。

表4 攻击算法各攻击步骤平均耗时(s)

5 常见问题及改进建议

基于本文及以往的密码分析工作，在此指出IEAVJD及部分图像加密算法中存在的一些问题：

(1) 部分设计者直接将明文图像散列值用作秘密密钥。在有大量图像需加密的应用场合，这种1次1密的秘密密钥设计不具有实用性。另外，这也使得图像加密算法的设计变得无意义。因为在此情况下，只需利用一次性使用的秘密密钥生成与明文图像等长的等价密钥流，然后与明文图像直接异或加密即可。

(2) 加密过程中，有些图像加密算法使用随机值或秘密参数。显然，这样的设计不符合柯克霍夫原则。

(3) 有些图像加密算法在等价密钥流的生成过程中，使密钥空间内存在大量的等价秘密密钥。

(4) 加密过程中，依赖外部数据源会降低图像加密算法的实用性。以IEA-VJD为例，如GenBank数据库变得不可用，或其中的基因数据发生变化，都会使其无法正常工作。另外，加密大小为M×N的明文图像，需安全地传输同等数量级的数据，同样会使加密变得无意义。

(5) 加密过程中，连续使用具有相同加密效果的加密步骤。例如，连续的置乱或连续的替换。

(6) 加密结构不完善或不完备，容易退化或被攻击者简化。同样以IEA-VJD为例，在唯密文攻击条件下，攻击者只需通过简单计算即可使其退化为置乱-替换结构。

(7) 安全性分析和验证不充分。目前绝大多数图像加密算法都只依靠统计性测试或随机性测试来验证安全性。实际上，通过这些测试只是图像加密算法具有安全性的必要条件而非充分条件[18]。

以上问题主要涉及秘密密钥设计、加密过程设计及安全性验证。本文在此提出一些改进建议，以便为未来的设计者提供有益参考。当然，也期待研究人员未来能给出更好或更具体的解决方案。

(1) 秘密密钥的设计应具有实用性和合理性，图像加密算法的安全性应建立在设计合理的加密过程以及秘密密钥的未知性之上，而非不实用或不合理的秘密密钥设计。其次，对于攻击者而言，秘密密钥应是整个加密过程中唯一的未知元素，图像加密算法的安全性也不应建立在随机值或秘密参数之上。再者，秘密密钥的构成应是明确的和规范的，最好以二进制位序列的形式给出，并保证足够大的有效密钥空间。将秘密密钥转换成等价密钥流的过程中，应避免大量等价秘密密钥的存在。

(2) 设计加密过程时，对于所引入的每一个加密步骤，都应考虑其必要性、实用性和合理性。谨慎分析和评估每一个加密步骤的实际加密效果，避免冗余加密步骤。另外，加密过程也应是完备和自包含的，能实现良好的混淆和扩散效果，通常应采用包含置乱、替换和扩散等加密步骤的类Feistel迭代结构。

(3) 验证图像加密算法的安全性时，不仅要进行统计性测试和随机性测试，而且要从攻击者的角度来对整个加密过程进行深入和全面的分析。即应分析每个加密步骤下，输入与输出之间的关系，并考虑特定攻击条件下，这些关系是否会退化或被简化。

6 结论

本文对一种基于变步长约瑟夫遍历和DNA动态编码的图像加密算法进行了简要描述，并讨论和分析了其中存在的一些问题。这些问题包括混沌序列转换问题、DNA编码规则计算问题、扩散过程描述与工作异常问题、依赖外部数据源与加密无意义问题、秘密密钥描述与实用性问题以及扩散过程可简化问题。接着在选择明文攻击条件下，对其加密过程进行了密码分析，发现最多256+floor(M×N/255)+1张选择明文图像及其对应密文图像，即可完全将其破解。随后的仿真实验和理论分析确认了所提攻击算法的有效性与可行性。最后，本文还指出了部分图像加密算法中存在的问题，并提出了一些改进建议，以便为未来的图像加密算法设计者提供有益参考。