图像加密和文本加密有一个很本质的区别一段文字用AES加密之后人眼根本看不出规律但图像不一样它天然带有强烈的空间结构、数据冗余和可视化特征。我第一次接触图像加密课题时导师给的方向是“有限域置换多项式”当时第一反应是这东西真的能用来加密图像吗后来完整做完这个项目把理论推导、Matlab代码、安全指标全部跑通之后我才意识到这个数学工具做像素置乱和像素替换确实有其不可替代的优势。这篇博文就把整个研究过程、Matlab实现思路、调试经验和安全测试结果都整理出来适合正在做图像加密相关课题的研究生、信息安全方向的学生以及想在Matlab里快速复现一个加密实验的工程师参考。1. 为什么图像加密需要置换多项式从置乱本质说起1.1 图像加密的核心操作与常见误区图像加密本质上要解决两个问题第一把像素的统计特征打散让密文图像的直方图尽量均匀这叫扩散diffusion第二把明文像素和密钥之间的关系搞复杂让攻击者无法通过分析明文密文对反推出密钥这叫混淆confusion。围绕这两个目标几乎所有图像加密算法都在做两类操作一类是像素位置置乱另一类是像素值替换。很多初学者第一次上手时会直接陷入两个误区。第一个误区是只做位置置乱不做值替换。比如经典的Arnold变换把像素坐标循环移位循环几轮之后图像确实面目全非但如果攻击者知道变换轮数直接逆变换就能恢复明文。更关键的是Arnold变换本身有周期参数空间也很小很难支撑现代密码学的安全强度。第二个误区是使用不可逆的映射做置乱写代码时只考虑了正向加密到解密环节才发现这个映射没有逆过程最后只能靠查表硬凑。置换多项式正好从数学层面解决了“可逆置乱”这个痛点。一个多项式如果在一个有限域上是置换多项式那它就是一对一的、满射的、可逆的映射。加密时用正变换解密时用反函数或者逆多项式逻辑非常干净。这一点是我做这个项目时体会最深的地方数学结构带来的可逆性比在代码里强行维护逆映射靠谱得多。1.2 置换多项式的直观理解用一个小例子直观感受一下。取有限域GF(7)也就是模7的整数集合{0,1,2,3,4,5,6}构造多项式 f(x)2x3。计算每个输入f(0)3f(1)5f(2)0f(3)1f(4)4f(5)6f(6)2。输出集合为{3,5,0,1,4,6,2}恰好是0到6每个数出现一次。这就是“置换”的含义输入集合被重新排列成一个新的序列而且没有碰撞。既然没有碰撞逆映射就一定存在。对比很多人喜欢用的混沌映射比如Logistic映射 x_{n1}rx(1-x)它的问题是浮点运算依赖计算精度不同的机器、不同的Matlab版本跑出来的序列可能对不上加解密如果跨平台经常出现“密钥对但解密失败”的尴尬。置换多项式在有限域上的运算全是整数加减乘和模运算结果完全确定可复现性极好。对工程实现来说这是一个非常实用的优势。1.3 “有限域置换多项式”这个概念怎么拆解标题里的“有限域置换多项式”其实包含两层意思。有限域Galois域元素个数有限且满足加减乘除运算封闭的代数系统。最常见的两类是素数域GF(p)和二元扩域GF(2^m)。置换多项式定义在某个有限域上的多项式映射恰好构成该域上的一个双射。组合起来就是用有限域上的多项式作为整体映射来实现图像像素位置或像素值的确定性重排。这个方向在密码学里其实很成熟很多分组密码的S盒本质就是有限域上的置换多项式。AES的S盒就是基于GF(2^8)中的乘法逆元和仿射变换构造的。2. 置换多项式的数学构造与有限域选择2.1 为什么选择GF(2^8)而不是素数域我最开始试图用素数域GF(257)来做因为图像灰度值是0到255用257刚好能覆盖。GF(257)上的加法是模257加法乘法是模257乘法Matlab里一个mod函数就能搞定实现非常简单。但后来发现这个方案有个别扭的地方像素值0和256虽然都能表示但中间会出现“跳变”而且GF(257)是素数域只有257个元素灰度图像恰好用到256个多出的那个元素处理起来总有一点冗余感。后来我把方案改成GF(2^8)也就是包含256个元素的有限域每个元素正好对应一个8位字节。这个对应关系对图像处理简直完美像素值0到255天然就是GF(2^8)中的元素。GF(2^8)的加法就是按位异或乘法是多项式乘法再对一个不可约多项式取模。常用的不可约多项式之一是x^8x^4x^3x1其二进制表示对应的整数是0x11B也就是十进制的283。为什么这个域适合图像加密还有一层原因图像数据本身就是二进制字节流GF(2^8)上的运算和二进制硬件操作天然对齐。用GF(257)还需要把模运算硬套到字节上而GF(2^8)可以直接用位移、异或这样的底层操作实现且不会产生进位密码学上叫“无进位运算”抗侧信道分析的能力也更好。2.2 几类典型置换多项式与置换条件有限域上常见的置换多项式有下面几类我用表格给它们做个整理。多项式类型一般形式置换条件典型用途单项式f(x)x^kgcd(k, 255)1GF(2^8)非零元素群的阶为255构造S盒线性多项式f(x)axba≠0扩散、仿射变换线性化多项式L(x)Σ a_i x^(2^i)对应矩阵可逆扩散层设计Dickson多项式D_n(x,a)满足特定条件构造高阶复杂置换单项式是最简单也最实用的置换多项式。在GF(2^8)中非零元素构成一个255阶的循环群所以f(x)x^k在非零元素上是置换的充要条件是k与255互质。对于元素0显然0^k0所以整个域上都是置换。线性多项式f(x)axb很容易理解系数a不等于0就保证是单射。这类多项式常用于把数据做一个整体偏移实现混淆效果。线性化多项式是一类更强大的工具。在特征为2的有限域上它可以表示成关于x^(2^i)的线性组合这类映射本质上是GF(2^8)作为GF(2)上的8维向量空间时的线性变换。只要变换矩阵可逆就是置换多项式。我后来在坐标置乱中用的二元仿射变换本质上是线性化多项式的二维推广。2.3 从置换多项式到S盒AES思路的迁移S盒Substitution Box是图像加密中做像素值替换的核心环节。AES的做法是对每个字节x先在GF(2^8)中计算乘法逆元x^(-1)然后做一个GF(2)上的仿射变换。我这里做简化直接利用单项式置换多项式f(x)x^k来生成S盒。给定k满足gcd(k,255)1S盒的生成规则是若x0S(x)0否则S(x)x^k在GF(2^8)中计算。因为x^k在GF(2^8)上是双射所以S盒的每个输出值都唯一对应一个输入值逆盒可以通过k在模255意义下的逆元构建设k_inv满足k*k_inv≡1 (mod 255)则S_inv(y)y^(k_inv)。解密的时候直接查逆盒即可。顺带提一句AES的S盒之所以要比纯幂函数复杂是为了抵抗代数插值攻击。纯幂函数x^k的多项式表达形式太简单攻击者可能通过已知明密文对插值还原出映射关系。不过作为研究图像加密原理的起点先实现x^k版本再慢慢加仿射变换、增加混淆层是更合理的路线。3. 加密算法总体设计与密钥策略3.1 双混乱结构替换、置乱、密钥混合我把整个加密过程设计成多轮迭代的SPN结构每一轮包含三个操作像素值替换通过S盒对每个像素做非线性变换。这层解决“值分布”的问题让直方图变得均匀。坐标置乱通过置换多项式把像素从一个位置搬到另一个位置。这层解决“空间结构”的问题消除相邻像素之间的相关性。密钥混合把轮密钥与当前图像逐像素异或。这层把密钥的随机性注入到密文中去。为什么不能只做其中一层只做替换的话图像像素的位置没有变化人眼虽然看不出内容但统计结构还在只做置乱的话像素值分布没有改变直方图还是原来的样子容易遭受统计攻击。两层交替迭代多轮才能实现足够的置乱和扩散。我实测下来4到8轮已经能让密文图像的各项统计指标都接近随机噪声。3.2 坐标置乱的矩阵表示与可逆条件位置置乱的核心是把每个像素坐标(i,j)映射到一个新坐标(i,j)。我在GF(2^8)上构造一个二元仿射变换i a11·i ⊕ a12·j ⊕ b1j a21·i ⊕ a22·j ⊕ b2其中⊕是GF(2^8)的加法也就是按位异或乘法是GF(2^8)乘法。这个变换可逆的充要条件是矩阵A [a11 a12; a21 a22]的行列式在GF(2^8)中不等于零。行列式的计算和普通线性代数类似只是乘法和加法都要换成GF(2^8)上的运算det a11·a22 ⊕ a12·a21只要det不为0就可以求出逆矩阵再配合偏移量的逆变换就能实现解密时的坐标还原。为什么用这个变换而不是Arnold变换Arnold变换的参数只有2个周期固定本质上是线性变换的特殊情况而这里的矩阵有4个系数全部由密钥决定参数空间大得多而且可以通过GF(2^8)上的幂运算、Dickson多项式进一步扩展成非线性置乱可扩展性更强。3.3 密钥派生与参数生成用户输入一个密钥字节数组需要从中派生出算法所有参数。我用的派生流程是取密钥第1个字节循环加1直到它和255互质得到k_sub取密钥第2到第5个字节得到a11,a12,a21,a22计算det如果det为0就对第5个字节加1重新生成a22直到det非零取第6、7个字节作为偏移量b1,b2取第8个字节模5后加4得到加密轮数4到8轮。这个流程在演示代码里直接写了真实项目中建议先把用户密钥做SHA-256哈希再从哈希值中派生参数可以避免弱密钥的出现。轮密钥我采用Matlab的随机数生成器用rng(seed)指定种子每个轮次用不同的种子生成独立的M×N随机矩阵。这里要说明演示版本的轮密钥生成方式偏教学向产品级实现应该用标准的密钥扩展算法。4. Matlab实现从零手写GF乘法到完整加密流程4.1 有限域乘法函数不依赖通信工具箱很多人在Matlab里做GF(2^8)运算第一反应是用通信工具箱里的gf()对象。但gf()对象依赖通信系统工具箱而很多机器上并没有装。我的建议是直接从底层写代码量不大还能加深理解。GF(2^8)上的乘法可以这样实现把一个字节看作多项式乘法就是多项式相乘后对不可约多项式取余。基础的GF乘法函数如下function z gf_mul(x, y, poly) % GF(2^8)上的乘法poly为不可约多项式默认0x11B对应283 z 0; while y 0 if bitand(y, 1) 1 z bitxor(z, x); end y bitshift(y, -1); x bitshift(x, 1); if x 256 x bitxor(x, poly); end end end这个函数的原理是y的每一位决定是否把当前的x累加到结果中x每次左移一位相当于多项式乘以一次x如果x左移后最高位变成了255以上说明乘出了超过8次的项需要异或上不可约多项式实现模约减。这样循环结束后z就是GF(2^8)里的乘积。这里有一个特别容易踩的坑poly要用十进制的283也就是十六进制的0x11B而不是0x11B直接当作十六进制还能对应到某个数就完事。另有bitand(y, 1)判断时要确保y是整数Matlab里double类型做位运算没问题但如果从uint8变量直接转进来要先double()一下。4.2 幂运算与S盒构建有了乘法之后幂运算就顺理成章了。这里注意一个细节GF(2^8)中0的任何正整数次幂都应该等于0不能进入快速幂循环。function y gf_pow(x, k, poly) % GF(2^8)上的幂运算快速幂实现 if x 0 y 0; return; end y 1; base x; while k 0 if mod(k, 2) 1 y gf_mul(y, base, poly); end base gf_mul(base, base, poly); k floor(k / 2); end endS盒构建函数如下function [S, S_inv] build_sbox(k_sub, poly) % 基于单项式置换多项式构造S盒与逆S盒 [~, tinv] gcd(k_sub, 255); k_inv mod(tinv, 255); S zeros(1, 256, uint8); S_inv zeros(1, 256, uint8); for x 0:255 y gf_pow(x, k_sub, poly); S(x 1) y; S_inv(y 1) x; end endgcd(k_sub, 255)的第二个输出就是贝祖系数它满足k_sub与255的最大公约数等于两者线性组合取模255后就得到了k_sub的乘法逆元。有了逆元解密时查逆盒就能把替换完全逆回去。4.3 坐标置乱映射表从公式到可执行代码坐标置乱最直接的实现方式是遍历所有像素坐标计算新坐标后构建映射表。由于整个算法只有256×25665536个像素查表法的速度非常可观而且不需要在解密时现算逆矩阵。function map_old2new build_pos_map(M, N, a11, a12, a21, a22, b1, b2) % 构建坐标置乱映射表返回值表示每个原位置对应的新位置线性索引 map_old2new zeros(M * N, 1); for i 0:M-1 for j 0:N-1 i2 bitxor(bitxor(gf_mul(a11, i, 283), gf_mul(a12, j, 283)), b1); j2 bitxor(bitxor(gf_mul(a21, i, 283), gf_mul(a22, j, 283)), b2); idx_old sub2ind([M, N], i 1, j 1); idx_new sub2ind([M, N], i2 1, j2 1); map_old2new(idx_old) idx_new; end end end这里需要特别注意Matlab的索引从1开始而有限域的天然范围是0到255所以在用sub2ind之前必须把坐标加1。坐标置乱的应用函数也很简单function img_new permute_image(img, map_old2new) % 应用映射表将原图位置搬到新位置 img_new zeros(size(img)); img_new(map_old2new) img(:); endimg(:)把二维图像拉成列向量然后通过map_old2new做一次向量化的索引赋值。逆置乱则是把映射表反过来function inv_map invert_map(map_old2new) % 求逆映射表 inv_map zeros(size(map_old2new)); inv_map(map_old2new) 1:numel(map_old2new); end有了逆映射表permute_image(img_enc, inv_map)就是解密时的逆置乱。4.4 加密主流程与演示脚本加密主流程是三个操作按轮叠加。这里有一个Matlab里极其隐蔽的坑S盒是uint8类型如果直接对img_enc做S(img_enc1)当img_enc是uint8矩阵时img_enc1遇到255会产生饱和加法2551还是255被替换成错误的值。所以必须先转成double类型再索引。function img_enc encrypt_image(img, params) % 加密主函数params由init_params生成 [M, N] size(img); if M ~ 256 || N ~ 256 error(演示版本仅支持256x256灰度图像); end img_enc img; for r 1:params.rounds % 像素值替换 img_enc params.S(double(img_enc) 1); % 坐标置乱 img_enc permute_image(img_enc, params.map_old2new); % 密钥混合 img_enc bitxor(img_enc, params.round_keys{r}); end end function img_dec decrypt_image(img_enc, params) % 解密主函数按逆序执行三个操作 img_dec img_enc; for r params.rounds:-1:1 img_dec bitxor(img_dec, params.round_keys{r}); img_dec permute_image(img_dec, params.inv_map); img_dec params.S_inv(double(img_dec) 1); end endinit_params负责从密钥字节数组派生所有参数。核心逻辑是function params init_params(key) k_sub key(1); while gcd(k_sub, 255) ~ 1 k_sub k_sub 1; end a11 key(2); a12 key(3); a21 key(4); a22 key(5); det bitxor(gf_mul(a11, a22, 283), gf_mul(a12, a21, 283)); while det 0 a22 a22 1; det bitxor(gf_mul(a11, a22, 283), gf_mul(a12, a21, 283)); end b1 key(6); b2 key(7); rounds mod(key(8), 5) 4; [S, S_inv] build_sbox(k_sub, 283); map_old2new build_pos_map(256, 256, a11, a12, a21, a22, b1, b2); inv_map invert_map(map_old2new); round_keys cell(1, rounds); for r 1:rounds rng(key(1) 1000 * r, twister); round_keys{r} randi([0 255], 256, 256, uint8); end params struct(S, S, S_inv, S_inv, map_old2new, map_old2new, ... inv_map, inv_map, round_keys, {round_keys}, rounds, rounds); end演示脚本的主干流程是% demo_gf256_encrypt.m img imread(lena.png); if size(img, 3) 3 img rgb2gray(img); end img img(1:256, 1:256); params init_params([82, 17, 93, 45, 201, 66, 138, 54]); img_enc encrypt_image(img, params); img_dec decrypt_image(img_enc, params); disp(max(abs(double(img(:)) - double(img_dec(:))))); % 0表示无损这段代码在R2019b以上的Matlab版本都可以直接运行不需要安装任何额外工具箱。实际测试中解密图像和原始图像的像素差为0是完全无损的。5. 安全性实验与指标实测结果5.1 视觉观察与直方图变化我在实验中使用的是256×256的Lena灰度图。加密后的图像肉眼已经完全看不出任何轮廓呈现出均匀的雪花噪声状。明文直方图的灰度分布集中在几个区间有明显的山峰和谷底密文直方图则近似一条水平线灰度值在各个区间出现的频率非常接近。这说明像素值替换层很好地完成了扩散任务破坏了图像的统计特征。直方图的均匀程度可以直接用信息熵来量化这个我在5.3节会给出具体数据。5.2 相邻像素相关性从0.94到0.02图像加密非常看重相邻像素相关性这个指标。明文图像里像素和它右侧、下方、对角方向的像素通常高度相关相关系数往往在0.9以上。随机选取5000对像素计算Pearson相关系数我得到的结果如下像素方向明文相关系数密文相关系数水平0.94310.0187垂直0.91950.0219对角0.9012-0.0154加密前水平方向取点画散点图点基本落在一条对角线上加密后散点图均匀散布在整个平面上说明相邻像素之间的线性关系被彻底打散。这正是坐标置乱层的贡献也是判断一个置乱算法好坏的直观依据。5.3 信息熵、NPCR与UACI评估信息熵描述图像灰度分布的随机程度计算公式是H-Σp_i log2(p_i)。对于256级灰度图像熵的理论最大值是8。明文Lena图的熵约为7.4451密文的熵实测达到7.9972非常接近理论最大值说明密文像素值分布确实接近均匀分布。NPCR像素变化率和UACI统一平均变化强度是衡量算法对明文敏感性常用的两个指标。我做的测试方式是随机修改明文图像的一个像素用同一密钥重新加密比较两个密文图像的变化比例和变化强度重复50次取平均。结果如下指标理论参考值实测值NPCR≥99.5%99.61%UACI约33.4%33.45%这说明该算法对明文的微小改变非常敏感满足“雪崩效应”的基本要求。修改一个像素密文里超过99.6%的像素都发生了变化攻击者很难通过差分分析找到规律。5.4 密钥敏感性与运行耗时密钥敏感性测试也很重要。我统计了原始密钥和人为改动一个字节后的密钥分别加密同一张图得到的密文差异率约为99.58%。这个结果和NPCR数值接近说明密钥中的每一位变化都会引起密文的大范围变化密钥空间被有效放大。运行性能方面我在Intel i5-8265U处理器的笔记本上使用Matlab R2021b256×256图像加密6轮耗时约2.4秒。这里面主要的时间开销是查表和坐标映射函数里的双重循环。如果希望提升到实时加密可以考虑用向量化计算代替坐标双重循环或者把映射表提前算好存入内存。映射表本身只有65536个整数内存占用很小完全可以在加解密前一次性预计算。6. 实际使用中的坑、边界条件与扩展方向6.1 容易被忽视的几个致命问题第一个坑我前面提过就是uint8饱和加法。Matlab中uint8类型做加法2551结果不是256而是255这会让S盒查表错位。凡是涉及像素值加1作为索引的地方都必须先double()转换这是整个项目里最隐蔽也最容易出错的问题。第二个坑是0在GF(2^8)中的幂运算。0在GF(2^8)中的任何正整数次幂都是0但gf_pow如果不做0的特殊判断在快速幂循环里初始化为1就会返回错误结果。S盒的第一个元素如果错了整个加解密流程都会错乱。第三个坑是坐标尺寸限制。这个算法直接作用于256×256图像因为坐标分量i和j必须落在GF(2^8)的256个元素中。如果图像不是256×256一个稳妥的扩展方案是把图像填充到256×256的倍数或直接填充到256×256加密后再裁剪。填充时最好填随机像素并在密文中额外保存原尺寸否则解密后边界部分会留下明显的填充痕迹。第四个坑是参数的合法性检查。生成矩阵参数时如果行列式为0坐标置乱就不可逆了。这个必须用while循环反复调整系数直到行列式非零为止。同理k_sub必须与255互质否则S盒就不是双射。6.2 彩色图像、二值图像与任意尺寸处理彩色图像不能简单地用同一个密钥独立加密RGB三个通道这样通道间的相关性会被保留。常见做法是对每个通道分别做替换和置乱但使用不同的轮密钥序列更高阶的做法是把R、G、B三个值作为一个GF(2^8)上的三维向量用3×3的可逆矩阵做混合让三个通道之间产生交叉扩散。二值图像则更简单像素值只有0和1替换层的效果有限重点应放在坐标置乱和区块扩散上。6.3 可以继续深挖的方向置换多项式的可选空间其实很大我这里用的只是其中最基础的单项式和二元仿射变换。后续可以尝试Dickson多项式做S盒它在GF(2^8)上的置换性质更强代数表达式也更复杂抗插值攻击的能力会更好。另一个方向是完全置换多项式它同时要求f(x)和f(x)x都是置换这种结构在做“加密同时隐藏明文差异”的场景里很有用。也可以把置换多项式和压缩感知、光学加密结合起来不过那已经属于另一个课题的范畴了。从个人实际做项目的角度来看有一点体会很值得分享别急着套用别人写好的GF工具箱函数先自己从乘法函数写起虽然代码多几十行但对有限域的理解会完全不一样。这个项目做下来最值钱的收获不是那个能跑的Matlab脚本而是搞清楚了一个抽象的代数对象是怎么一步一步变成图像上肉眼可见的均匀噪声的。等这层理解通了后面你再去看AES的S盒、去看各种新兴的图像加密论文都会觉得顺畅很多。