Arnold 变换

2023-1-21

Arnold 变换（普通）

现代互联网信息传递过程中，通常需要对图片进行加密。Arnold 变换是针对正方形矩阵的一种映射，能够很好地用于图像加密。数字图像置乱和信息文件加密思想类似，它主要是通过对数字图像的像素位置做变换来“扰乱”图像，使其变得面目全非、杂乱无章，从而隐藏图像所要表达的真实信息。数字图像的置乱可以在位置空间、色彩空间、频率空间上进行。随着计算机技术和数字图像处理技术的发展，很多文献对图像置乱提出了不同的置乱算法，大体上可以分为线性变换、几何变换和仿射变换。目前研究较多的置乱技术包括Fibonacci 变换、Arnold 变换、Hilbert 曲线变换、E-曲线变换、Gray 变换、仿射变换、幻方、正交拉丁方变换等方法。无论哪一种置乱技术都是可逆的，或者是具有周期性的，即多次迭代或者做反变换均能恢复原图像。本文主要讲述 Arnold 变换。

为了方便演示，我们这里选用一张 4x4 大小的像素图片，只有白色像素和蓝色像素构成，如图所示。

首先，对于一个图像，我们以左下角为原点，给每一个像素赋予坐标。

然后，我们将对于每一个像素点$P(x,y)$，将$P$ 移动到$(2x+y,x+y)$的位置上。注意这张图上的格子上面写的坐标其实是他们原本一开始时的坐标，而不是现在的实际坐标。

然后是最为神奇的一步，将多余原本的图片的部分裁剪掉，并平移回来，补成一个完整的图。这么说有点抽象，你可以理解为，对于新的图中的每一个像素的坐标，对原来图片的边长取模。

如果你还是理解不了，看这个：图中红色虚线全出的部分是超出原图右边界（蓝色激光柱）的，我们将其向左移动，平移到原图内。应当注意的是，这里的“平移”其实是指“对边长取模”，所以不是随便模的。还有一个很重要的一点图中所有的坐标都是刚开始时的编号，而不是真正的坐标。比如，右上角，用红色虚线框起来的格子，原图中$(3,3)$坐标的那个，在现在这张图上的实际坐标其实是$(9,6)$，那么平移后的新坐标必须是$(9 \bmod 4,6 \bmod 4)$，也就是$(1,2)$，哦，在这张图上我们只处理了 x 坐标的情况，y 坐标与之类似。

好了，最终我们能得到如下的图片。

那么这就是简单的 Arnold 变换啦！下面我们动手实践一下吧！

# Arnold 变换

import numpy as np
import cv2 as cv

def catmap(img):
	img = np.rot90(img)
	img = np.rot90(img)  # 原始图片的存储数组是行列不是上文所讲的横纵坐标，需要旋转-90°的转换
	img = np.rot90(img)
	n = img.shape[0]  # n 为图像的边长
	result = np.zeros((n, n, 3), dtype=np.uint8)  # 结果最开始为空白图像
	for x in range(n):
		for y in range(n):
			result[(2*x + y)%n][(x + y)%n] = img[x][y]
	result = np.rot90(result)  # 旋转90°将横纵坐标转换为行列
	return result

def main():
	img = cv.imread('img/city.png')  # 读取图片
	cv.imshow('result', catmap(img))  # 显示结果

if __name__ == '__main__':
	main()
	cv.waitKey(0)

显然，一次 Arnold 变换是不够的。如果我们多做几次呢？

可以看到，图像越来越杂乱无章，到最后已经看不出来原图了。

解密与加密基本一致，只不过将过程反着操作。这是刚才加密得到的图片，我们从现在开始以这个为原图。

只不过这一次，我们将每一个像素$(x,y)$移到$(x-y,2y-x)$去。

啊，完好如初，简直就是破镜重圆，覆水再收的感觉。

完整过程如下：

于是我们很容易写出它的代码：

def decode_catmap(img):
	img = np.rot90(img)
	img = np.rot90(img)
	img = np.rot90(img)
	n = img.shape[0]
	
	result = np.zeros((n, n, 3), dtype=np.uint8)
	for x in range(n):
		for y in range(n):
			result[(x - y)%n][(2*y - x)%n] = img[x][y]
	result = np.rot90(result)
	
	return result

小结

好，如果你理解了上面的知识，那么还不够。因为如果一张图片的加密算法是这样的，没有密钥，那么它啥也不是。很轻松就破解了，特别是这种我把破解方法直接写在这段文字的上方的时候。

Arnold 变换（扩展）

我们修改 Arnold 变换的定义为：

我们有初始图像$G$和初始参数$a,b$，记加密后的图像为$G'$，那么

容易发现，矩阵$\begin{bmatrix} 1 & -a \\ -b & ab+1 \end{bmatrix}$为$\begin{bmatrix} ab+1 & a \\ b & 1 \end{bmatrix}$的逆矩阵。这一点很好理解。

可以看出，刚才我们所探讨的情况属于$a=b=1$的特殊情况。

好，这样我们就能写出最终的代码了：

# Arnold 变换

import numpy as np
import cv2 as cv

def catmap(img, times=1, a=1, b=1):
	for i in range(times):
		img = np.rot90(img)
		img = np.rot90(img)
		img = np.rot90(img)
		n = img.shape[0]
		result = np.zeros((n, n, 3), dtype=np.uint8)
		
		for x in range(n):
			for y in range(n):
				result[(a*b*x + x + a*y)%n][(b*x + y)%n] = img[x][y]
		
		result = np.rot90(result)
		img = result
	return result

def decode_catmap(img, times=1, a=1, b=1):
	for i in range(times):
		img = np.rot90(img)
		img = np.rot90(img)
		img = np.rot90(img)
		n = img.shape[0]
		result = np.zeros((n, n, 3), dtype=np.uint8)
		
		for x in range(n):
			for y in range(n):
				result[(x - a*y)%n][(a*b*y + y - b*x)%n] = img[x][y]
		
		result = np.rot90(result)
		img = result
	return result

def main(t, a, b):
	img = cv.imread('img/city.png')
	coded = catmap(img, t, a, b)
	decoded = decode_catmap(coded, t, a, b)
	cv.imshow("coded", coded)
	cv.imshow("decoded", decoded)
	cv.imwrite('temp/output.png', coded)
	cv.imwrite('temp/output2.png', decoded)

if __name__ == '__main__':
	main(1, 1, 1)
	cv.waitKey(0)

尝试一下 $a=114514,b=1919810$的情况：

跟我们之前得出的结论一样，好耶。

后记

众所周知，Arnold 变换主要被用于图像加密/解密，那么必须要具有一定的鲁棒性（即能扛得住一定的恶意攻击）

那么第一步就是让敌人无法知道这张图片的意思。即混淆图片的内容，隐藏图片的信息。

如果敌人截获了左图的加密后的图像那么只要他不知道$a,b$的值，那么这几乎是无解的！ 因为$a$和$b$所形成的组合高达$n^2$种（因为要对$n$取模）。

第二步就是抗干扰性，让敌人即使对图片进行恶意修改也没有办法都达到预期的效果。

除此之外还有一个特点，这是大多数加密算法的同性。

如果你一直对一个图片进行同样参数的 Arnold 变换，那么你最终会发现：有一次我加密后，竟然变成了最开始的图像。具有周期性！

以下内容参考自论文《Arnold变换的周期性与安全性分析》。

图像的 Arnold 变换的周期性与$N$的取值有关，F. J. Dyson 和 H. Falk 给出了对于任意$N>2$，Arnold 变换的周期$T_N=N^2/2$的结论。此文献更是得出它的周期等于以$N$的两两互素的因数为模的变换的周期之最小公倍数。

以我的能力我是没有办法知道为什么具有周期性，不过没有关系，从中我们可以发现，Arnold 变换的缺点为：

针对第二个问题有一个小改进：将转换矩阵$\begin{bmatrix} ab+1 & a \\ b & 1 \end{bmatrix}$更换为$\begin{bmatrix}c_{11} & c_{12} \\ c_{21} & c_{22}\end{bmatrix}$，且$c_{ij} \in \mathbb{N}_+,c_{11}c_{22}-c_{12}c_{11}=\pm 1$。那么这个加密方式仍具有混沌映射的性质。为什么？

用变换矩阵参数作密钥时的有效密钥空间如下表：

$N=$ $2$ $4$ $5$ $8$ $10$ $16$ $32$ $64$ $100$ $128$ $256$ $512$
矩阵密钥空间 2 14 28 70 106 286 1230 4910 11974 19830 79278 318382