Arnold 猫脸变换逆变换:矩阵求逆 + 多轮还原 + a/b 参数爆破
ctf/forensics · verified
一句话结论
当图片被 Arnold 猫脸变换(x'=(a·x+b·y) mod n, y'=(c·x+d·y) mod n)置乱时,先求变换矩阵在模 n 下的逆矩阵,按题目给的轮数反复应用逆变换即可还原;若参数 a,b,c,d 未知,则根据提示范围(如 a,b∈10..15)暴力枚举并用 QR/可读性/直方图筛选。
原理
- Arnold 猫脸变换:对
n×n图像,逐像素做线性变换(x,y) → ((a·x+b·y) mod n, (c·x+d·y) mod n)。经典形式是(1,1,1,2)(x'=x+y, y'=x+2y),它是一一映射,可逆。 - 逆变换:变换矩阵
M=[[a,b],[c,d]]在模n下求逆(det(M)必须与n互素);逆矩阵M^{-1}作用于置乱图即可还原。多轮变换只需重复应用M^{-1}相应次数(本题 hint 为 35 次)。 - 参数未知:若 EXIF/hint 给出
a,b范围,枚举所有候选矩阵,逐一对图做逆变换,用 QR 解码成功、直方图/边缘连续性、可读文字等判据选正确参数。 - 为什么成立:Arnold 变换是双射,信息没有丢失;只要知道矩阵和轮数,逆变换就能精确还原。未知参数只是有限搜索空间(本题 10..15)。
- 注意:不同题目可能用变体矩阵(如
(2,1,1,1));必须按题目公式/代码核对,不能默认经典矩阵。
触发条件
- 图片呈现明显置乱/噪声,但尺寸为正方形或接近正方形;题目名称/提示出现“猫脸/Arnold/置乱”。
- 已知或可推测变换矩阵/轮数;EXIF/hint 可能给出参数范围。
- 置乱图为无损 PNG/BMP(JPEG 压缩会破坏双射,还原效果差)。
- 有 PIL/OpenCV 与 QR 解码库(pyzbar)用于验证。
利用步骤
- 读取图片尺寸
n,确认是正方形/可按n取模;读取 EXIF/提示得到轮数与参数范围。 - 对候选矩阵
M=[[a,b],[c,d]]求det与模n逆;构造M^{-1}。 - 定义
transform_once(img, M):dst[(a*x+b*y)%n, (c*x+d*y)%n] = src[x,y]。 - 对置乱图应用
M^{-1}共rounds次;保存结果,用 QR 解码/直方图/可读性判断。 - 参数未知时枚举
a,b(必要时 c,d),对每个候选重复 2-4;正确结果通常 QR 可解或图像边缘连续。 - 本题
Arnold_image用 BF 提示 35 轮,逆变换后 QR 解码得到 flag;cat cat cat从 foremost 分离出图,EXIF 给出 a,b∈10..15,暴力破解后得到二维码/flag。
PoC
from PIL import Image
def inverse_matrix(a, b, c, d, n):
det = (a * d - b * c) % n
inv_det = pow(det, -1, n)
return ((d * inv_det) % n, (-b * inv_det) % n,
(-c * inv_det) % n, (a * inv_det) % n)
def transform_once(img, matrix):
n = img.size[0]
src, dst_img = img.load(), Image.new("RGB", (n, n))
dst = dst_img.load()
a, b, c, d = matrix
for x in range(n):
for y in range(n):
nx, ny = (a * x + b * y) % n, (c * x + d * y) % n
dst[nx, ny] = src[x, y]
return dst_img
def undo(img, forward, rounds):
n = img.size[0]
inv = inverse_matrix(*forward, n)
cur = img
for _ in range(rounds):
cur = transform_once(cur, inv)
return cur
# 经典矩阵 (1,1,1,2) 的逆是 (2,-1,-1,1) mod n = (2,n-1,n-1,1)
img = Image.open("enc1.png").convert("RGB")
out = undo(img, (1, 1, 1, 2), 35)
out.save("restored.png")
变体与关联
- 变体(参数未知):枚举 a,b,c,d 的小范围;用 QR/文本/边缘连续性筛选;也可用已知明文(水印/边框)反推矩阵。
- 变体(其他置乱):Fibonacci 变换、仿射变换、像素交换、螺旋/蛇形;先识别变换公式再求逆。
- 变体(多图层):foremost/binwalk 分离出多张图,分别还原;EXIF 可能藏参数。
- 关联卡片:[[ctf-forensics-png-lsb-column-major-scan-order]](PNG LSB 扫描顺序)、[[ctf-misc-selectric-typeball-tilt-rotation]](图像旋转/倾斜隐写)、[[crypto-classical-hill-cipher-3x3-matrix-inverse-mod26]](模矩阵求逆)。
- 边界:JPEG 有损压缩会破坏双射;
det与n不互素时矩阵不可逆;轮数/矩阵错误会得到另一种置乱图。
检测与防御
- CTF 识别:图像呈规则置乱、题为“猫脸/Arnold”、EXIF 给参数范围,按本卡先求逆再爆破。
- 图像处理:Arnold 变换不是加密,只是置乱;敏感图像应使用真正的加密/水印。
- 实现:注意
n为图像边长、矩阵取模、逆矩阵负元素取模;多轮逆变换顺序不能反。