简介一份面向高等代数/密码学初学者的PDF讲义以置换矩阵为切入点梳理置换密码的加密与解密原理。资料先解释置换矩阵如何表示字符重排规则并通过一个典型英文长句作为示例完整演示明文预处理、分组、按加密向量置换生成密文、再用逆置换还原的流程也给出改变矩阵维数提升复杂度以及从加密矩阵求解密矩阵的策略。内容同样指出该类密码结构简单、易于破译更适用于教学演示。压缩包内为74KB的单个PDF文档共1个文件文档结构清晰包含摘要、数学推导、实际示例及C语言源程序代码便于读者对照理解或二次开发。已有223人在线浏览学习适合希望结合高等代数知识入门古典密码学、完成课程报告或实验的学生与爱好者。1. 置换矩阵与置换密码把顺序重排变成矩阵乘法很多讲置换密码的资料会把加密写成数组下标交换几分钟就讲完。置换矩阵给出另一个视角一个映射对应一个行列只有一个 1 的方阵明文向量乘上它元素被整体重排。更关键的结论是逆矩阵等于转置加密和解密共用同一个矩阵对象解密只是多写一个.T。把明文的顺序重排写进矩阵除了看起来更“线性代数”还让可逆、可组合、可验证三件事同时成立。这篇梳理以置换矩阵与置换密码的交叉点为坐标先讲数学性质再给可直接运行的加解密代码最后落到参数设计与排错。如果你正在做列转置密码、图像置乱、数据洗牌或样本重排且被逆映射表、多轮顺序、固定点这类问题困扰下面这套方案可以直接拿过去。2. 置换矩阵的数学性质逆等于转置与排列奇偶性2.1 一行一列只有一个 1置换矩阵的定义与方向约定设perm是长度 n 的排列表示“原来在位置 i 的元素最后出现在perm[i]这个位置”。对应的置换矩阵 P 由规则P[perm[i], i] 1构造其余位置全是 0。也就是说第 i 列的唯一一个 1 落在第perm[i]行行号决定去向列号决定来源。很多资料使用相反的坐标这是阅读不同版本时最常见的分歧所以代码里要先固定“去向”这一侧。import numpy as np def perm_matrix(perm): # perm[i] 表示原位置 i 的元素在结果中的位置 n len(perm) P np.zeros((n, n), dtypenp.uint8) for i, dst in enumerate(perm): P[dst, i] 1 return P print(perm_matrix([2, 0, 1])) # [[0 1 0] # [0 0 1] # [1 0 0]]循环里逐一写P[dst, i] 1生成的是 0/1 方阵dst是目标行号i是来源列号。用dtypenp.uint8是为了把矩阵本身压缩成字节不占内存。示例排列[2, 0, 1]的含义是位置 0 的元素去位置 2位置 1 的去位置 0位置 2 的去位置 1。把行向量old右乘这个矩阵结果就是old P。因为P[k, j] 1只出现在k perm[j]对应的位置所以结果向量的第 j 位拿到的是old[perm[j]]也就是old[perm]。这个右乘方向一旦固定下来后面所有代码都按同一方向推导避免混用。2.2 逆矩阵等于转置为什么解密只有一行代码置换矩阵的每一列都是单位向量的一列不同列互不相同所以列向量两两正交且模长为 1。这意味着 P 是正交矩阵满足P P.T I于是P⁻¹ Pᵀ解密不需要做矩阵求逆也不需要单独保存反向映射表。下面这段直接验证P perm_matrix([2, 0, 1]) m np.array([0, 1, 2], dtypenp.int32) c m P m2 c P.T # c [2 0 1] # m2 [0 1 2]c P.T的结果由转置矩阵的列与 c 做内积得到等价于对c再施加一次方向相反的置换。参数上要注意m必须是行向量形状是(n,)如果你把明文写成列向量m.reshape(-1, 1)加密公式要变成P.T m解密变成P c乘法位置完全对称。提示工程上我建议始终坚持行向量写法并且把“加密右乘 P、解密右乘 P.T”这一约定写进代码注释因为列向量版本很容易在组合多轮置换时把顺序搞反。2.3 行列式、奇偶性与固定点三个容易被忽略的性质置换矩阵虽然构造简单却有四个性质直接左右密码实现。性质数学表达实现时的注意点可逆性P⁻¹ Pᵀ解密直接转置不保存反向表行列式det(P) ±1奇置换为负偶置换为正乘法封闭P₁ · P₂ 仍是置换矩阵多轮置换不会扩大置换空间固定点perm[i] i固定点过多会泄露明文位置信息行列式符号看起来不参与加解密但当你用浮点库校验一个来源不明的矩阵时np.linalg.det(P.astype(float))返回 -1 或 1 可以作为“这确实是置换矩阵”的快速旁证。奇偶性在密码学里更常出现在“置换后是否保持某些代数结构”的分析中实际工程只需记录不必刻意控制。固定点则是密钥质量指标。一个随机置换里位置 i 恰好满足perm[i] i的期望是 1n 越大固定点比例越小但当 n 只有 8 或 16 时出现两三个固定点的概率并不低。如果明文中某些位置的字符有固定语义这些位置在密文里原样保留信息泄漏就发生了。提示我在真实项目里会限制固定点数量不超过 n/4生成后统计一次超过就重新采样。代价很小但对抗已知明文分析的第一层防御就这样建立起来了。3. 用置换矩阵实现置换密码最小可运行加解密代码3.1 分组设计块长度、尾部补齐和字节编码置换密码操作的是一段有限长度的向量所以明文先要变成整数数组。最常见做法是把字符串按 UTF-8 编码成字节再转成np.uint8数组分组长度 n 决定一次重排的规模。尾部不足 n 字节时需要补齐否则最后一块无法用同样的矩阵处理。def pad_to_blocks(data, n): pad_len (n - len(data) % n) % n if pad_len: data np.concatenate([data, np.full(pad_len, pad_len, dtypedata.dtype)]) return data.reshape(-1, n)pad_len的计算方式是如果data长度恰好是 n 的倍数len(data) % n为 0(n - 0) % n也是 0不补否则补到下一个整数倍。补的字节值等于补多少个解密时看最后一块的最后一个字节就能知道去掉多少。这套规则与 PKCS#7 类似但不完全相同因为置换密码本身不涉及密钥协商补位规则需要写进协议。3.2 从随机置换到置换矩阵生成与构造有了分组下一步是生成密钥。这里的密钥是一个排列perm而不是矩阵本身矩阵完全可以由排列动态构造密钥存储和传输都只需要排列数组。n 8 perm np.random.permutation(n) P np.eye(n, dtypenp.uint8)[:, perm]np.random.permutation(n)返回0..n-1的一个随机排列np.eye(n)是单位矩阵按perm抽取列之后每一行每一列仍然只有一个 1且列的顺序正好反映置换方向。这个方法比循环逐格写 1 更简洁但它依赖[:, perm]这样的高级索引阅读时要意识到“按列抽取”就是在构造置换。如果你担心习惯问题用上一章的perm_matrix(perm)函数也是一样的结果。这个阶段我只持有permP 在每次加解密临时构造原因是矩阵是 n×n 的n 稍大时浪费空间排列数组长度只有 n。3.3 加解密与往返验证一段可直接运行的代码下面是完整的单块加解密脚本逻辑、验证、输出都放在一起直接复制就能跑。import numpy as np def make_perm_matrix(perm): n len(perm) P np.zeros((n, n), dtypenp.uint8) for i, dst in enumerate(perm): P[dst, i] 1 return P def encrypt_block(m, P): return m.astype(np.int32) P def decrypt_block(c, P): return c P.T n 8 perm np.random.permutation(n) P make_perm_matrix(perm) m np.array([65, 66, 67, 68, 69, 70, 71, 72]) c encrypt_block(m, P) restored decrypt_block(c, P) print(perm:, perm) print(cipher:, c) print(restored:, restored) print(roundtrip ok:, np.array_equal(m, restored))encrypt_block里m.astype(np.int32)是为了避免uint8在大块数据上做矩阵乘时产生截断风险虽然置换只搬运数值、不做加法但一些底层 BLAS 实现会对整数做中间累加显式转成int32更稳妥。decrypt_block直接用P.T与加密函数形成对称关系。np.array_equal的返回结果应该一直是True这是每次修改代码后都该跑一遍的最小回归。3.4 分组长度 n 的选择依据与密钥空间参考n 的选择决定可表达的置换数量。n 越大排列数越多但这不直接等于密码越强因为置换结构太规则。先看一张参考表分组长度 n置换总数 n!密钥强度 log₂(n!)典型用途424约 4.6 bit教学样例840320约 15.3 bit小规模调试162.09×10¹³约 44.3 bit图像置乱原型322.63×10³⁵约 117.7 bit结构化数据洗牌log₂(n!)只是暴力搜索排列的复杂度。n16 时排列总数约 20 万亿在穷举视角下已经有实际防护价值但置换密码是线性变换攻击者一旦拿到足够多的明密文对可以直接解线性方程组恢复 P不需要逐一遍历。所以这套结构更适合教学、置乱和洗牌场景单独作为加密体系是不够的。3.5 固定点抑制把质量指标放进密钥生成生成密钥时把固定点限制加上能避免很多后期排错。def gen_perm(n, max_fixed0): while True: p np.random.permutation(n) if np.sum(p np.arange(n)) max_fixed: return pp np.arange(n)对每个位置检查是否原地不动np.sum统计固定点总数超过阈值就重新采样。n16 时重采样的期望次数很低基本一次通过n32 时也可以接受。想再严格一点可以扫描perm的循环分解把长度为 1 的循环全部去掉那相当于要求max_fixed0的更强版本但代价是生成时间增加。4. 置换矩阵在置换密码中的借鉴多轮组合与图像置乱4.1 先认清线性结构的边界明密文对可以直接恢复置换置换密码的矩阵描述把安全边界暴露得很清楚。设攻击者拿到 n 个明密文对把明文块按行排成矩阵 M密文块按行排成矩阵 C因为C M P只要 M 可逆立刻得到P M⁻¹ C。这不是理论攻击而是一行线性代数就能完成的操作。密钥空间再大也挡不住这种确定性的析出。所以置换矩阵在置换密码中的应用借鉴应该定位在“可逆的乱序层”而不是安全性的全部。真实的设计中它要么与非线性变换组合要么用在安全性要求不高的数据脱敏场景。4.2 多轮置换组合仍是置换矩阵强度不会叠加有人会想单轮弱那就加一轮。置换矩阵给出了反直觉的结论两个置换矩阵相乘结果仍然是置换矩阵。P1 make_perm_matrix(np.random.permutation(8)) P2 make_perm_matrix(np.random.permutation(8)) P_total P1 P2 assert P_total.shape P1.shape assert np.all(P_total.sum(axis0) 1) assert np.all(P_total.sum(axis1) 1)两个断言说明P_total每行每列仍然只有一个 1它是一个新的置换矩阵。意思是先用 P1 再用 P2整体效果等价于某一个单次置换。多轮置换既没有扩大密钥空间也没有引入非线性单纯堆轮数只会徒增计算量。但组合本身有工程价值把主密钥拆成若干轮子密钥每轮用不同的排列可以在不增加 n 的前提下改变整体置换形态。解密时的顺序必须反过来m c P2.T P1.T先乘最外层的转置。顺序错了还原结果就是乱的。4.3 图像置乱与数据洗牌矩阵做推导索引做执行置换矩阵在实际工程里有一个很舒服的用法矩阵负责推导、组合和验证真正对数据动手时改用数组索引省去构造大矩阵的开销。def shuffle_arr(arr, perm): return arr[perm] def unshuffle_arr(arr, perm): inv np.argsort(perm) return arr[inv]以 32×32 灰度图像为例先把像素矩阵img.reshape(-1)展成一维数组调用shuffle_arr得到置乱后的一维数组再reshape回原尺寸。视觉效果是整张图被打乱还原时只需np.argsort(perm)一次逆排列构造好后同样用索引取回。argsort的含义是inv[perm[i]] i这正是 perm 的逆映射。实际执行用索引复杂度是 O(n)而构建 n×n 稠密矩阵再乘复杂度是 O(n²)两者差距在图像像素规模下非常明显。所以我在置乱类任务里的做法是用矩阵在设计和验证阶段工作在线上代码里只保留 perm 和 argsort 的结果。彩色图像可以分别对三个通道做相同 perm也可以把三通道拼接成一个长向量整体置换。前者保留通道间的颜色结构后者打乱更彻底。数据洗牌时如果需要可还原的随机顺序这套逻辑同样适用只是要记住把perm本身持久化否则洗过就回不去了。5. 置换矩阵版置换密码的三个关键排错与验证技巧5.1 用一个小函数确认“真的是置换矩阵”矩阵来源不明时先验证再使用这不是仪式而是兜底。下面这个函数检查三条方阵、元素全为 0/1、每行每列和都是 1。def is_perm_matrix(P): if P.ndim ! 2 or P.shape[0] ! P.shape[1]: return False if not np.all((P 0) | (P 1)): return False return bool(np.all(P.sum(axis0) 1) and np.all(P.sum(axis1) 1))(P 0) | (P 1)用布尔或组合两次比较能同时处理整数和浮点矩阵P.sum(axis0)按列求和axis1按行求和。只有两个方向都全是 1才能保证置换是双射。5.2 检查索引方向排列差一位的问题几乎都出在这里最常见的排错点是文档里的 1 基准下标与代码里的 0 基准混淆。资料里写[1, 2, 0]直接塞进 Python 数组取出来的元素会整体偏一位。调试时最好的手段是打印小规模样例而不是盯着矩阵看。debug_perm np.array([2, 0, 1]) debug_m np.array([100, 200, 300], dtypenp.int32) debug_c debug_m perm_matrix(debug_perm) print(expect [300, 100, 200], got, debug_c) # expect 的值就是 debug_m[debug_perm]每次代码改动后先看一眼这个输出是否符合预期再跑大块明文。方向约定一旦固定所有子函数都要沿用否则多轮置换时第一轮就能把错误放进去。5.3 往返测试与边界情况让随机测试替你盯住顺序把前面几个验证拼在一起形成一次注册测试。仍沿用gen_perm生成无固定点密钥随机构造明文块加密后立刻解密比对。def run_roundtrip_test(n, rounds200): for _ in range(rounds): perm gen_perm(n) P make_perm_matrix(perm) m np.random.randint(0, 256, sizen).astype(np.int32) c encrypt_block(m, P) assert np.array_equal(decrypt_block(c, P), m)边界情况至少覆盖三种n1 时置换没有意义应该直接透传n2 时只有两种排列固定点检查会频繁重采样确认生成器不陷入死循环分组长度与明文长度相等时pad_to_blocks返回的矩阵行数应为 1。把这些断言放进自动化测试里每次重构置换逻辑时跑一遍方向错、组合错、矩阵构造错都会在几毫秒内暴露。本文还有配套的精品资源点击获取