1.4 换位密码：栅栏与矩阵重排

1.4 换位密码：栅栏与矩阵重排

本节摘要：换位密码不替换字母，只重排位置——字母集原封不动，频率分布原样保留。本节拆解栅栏密码与列置换两种代表形态，分析它们为何注定只能当配角，并说明"替换加换位"的乘积思想如何成为后世分组密码（Feistel 与 AES）的构造原点。

为什么需要另一条路线

替换密码的破绽出在"字母换成别人"这件事本身：明文统计特征被原样搬进密文。古人对症的直觉很自然——那就干脆不换字母，只把位置打乱。这就是换位密码（transposition cipher）：密文使用的字母与明文完全相同、个数相同、频率分布一模一样，改变的只有出场顺序。斯巴达人的密码棒（见 1.2 节）正是这一思路的器械化鼻祖。

这个家族里流传最广的是栅栏密码（rail fence cipher）。把明文沿"之"字形写上若干条假想的横栏，再逐栏抄出。以三栏为例，明文 WEAREDISCOVEREDFLEEATONCE 的走位如下：

图：三栏栅栏密码的之字形走位与按行抄写

栅栏密码的密钥只有"栏数"一个参数：两栏、三栏、四栏……对一段几十个字母的密文，尝试所有栏数的成本几乎为零，判据也简单——哪种栏数读出的内容像人话。下面的代码把加密与穷举都写出来：

def rail_fence(text, rails):
    """三步：分栏、之字下行、按栏拼接"""
    rows = [[] for _ in range(rails)]
    r, step = 0, 1
    for ch in text:
        rows[r].append(ch)
        if r == 0:            step = 1    # 到顶向下走
        elif r == rails - 1:  step = -1   # 到底向上走
        r += step
    return "".join("".join(row) for row in rows)

ct = rail_fence("WEAREDISCOVEREDFLEEATONCE", 3)
print(ct)   # WECRLTE ERDSOEEFEAOCAIVDEN（去空格）

# 穷举栏数：栏数不可能超过字母数的一半左右，试遍即可
for r in range(2, 8):
    print(r, rail_fence(ct, r)[:20])   # 观察哪种栏数出现可读片段
​

二、列置换：给位置重排配上真正的密钥

栅栏密码的"栏数"参数太贫瘠，古典换位的成熟形态是列置换（columnar transposition）：把明文逐行填进一个矩阵，按密钥规定的列序逐列抄出。密钥是一个关键词，例如 BERYL——其字母在字母表中的次序决定了各列被抄出的先后（B 第 1、E 第 2、L 第 3、R 第 4、Y 第 5，诸如此类）。密钥空间随列数阶乘增长，五列就有 120 种排列，八列 40320 种，比栅栏的"栏数"体面得多；十一、十二列的列置换在第一次世界大战的战场上仍是现役体制，法国陆军在战争初期就依赖它。

但它有换位家族的共同命门：字母频率分布原样暴露。破译者知道密文里 T 占了百分之几、E 占了百分之几——这些数字与英语文本的正常比例严丝合缝，一看便知这是换位而非替换。接下来的工作虽然繁琐（按列长拼出矩阵、利用常见双字母组合如 TH 与 EN 定位列序），却是纯机械的力气活；密文越长，统计特征越稳，破得越快。换位密码无法单独成军，原因尽在于此。

三、乘积思想：换位真正的历史遗产

单独孱弱，不代表没有价值。换位与替换的弱点恰好互补：替换抹掉"字母是什么"的痕迹却保留"谁与谁相邻"，换位保留字母却搅乱相邻关系。把两者交替叠用——替换一次、换位一次、再替换、再换位——密文的统计特征会被一层层搅碎。这就是乘积密码（product cipher）的思想，二十世纪香农在信息论层面将其提炼为"混淆与扩散"两条设计公理（见第 2 章）。

💡 关键直觉：DES 内部那道把半块数据反复"扩展、异或、压缩替换、交换左右"的流水线，AES 里行移位加列混淆的组合，本质上都是 1.4 节"换位"与 1.3 节"替换"的现代再版——古典密码死于统计，但它的两块尸骨拼成了现代分组密码的骨架。

双重换位与一次大战的战场回响

换位密码在二十世纪战场的最后亮相是双重换位：用两个不同的密钥矩形先后换位两次，单次换位的列结构被第二次打散，破译难度成倍上升。第一次世界大战中德军与法军都曾以双重换位为战役级密码，各国的战前训练教材里也普遍保留着它——在没有机器的时代，它是对抗统计的性价比之选。

1918 年春，德军的 ADFGVX 密码把这条路线推向古典的极致：先把每个字母与数字编码成 A、D、F、G、V、X 六个字母的两两组合（这六个字母在摩尔斯电码里音差最大，天然抗误码），再做列换位。替换与换位在一次加密里先后登场——乘积密码的雏形已清晰可见。法军破译师潘万在战役间隙以数理直觉破开它，直接影响了几场关键战役的走向。

这段尾声的价值在于预告：替换加换位、单次叠多次、编码层加混淆层——古典时代的所有直觉，都将在第 3 章以比特为单位重演一遍。Feistel 轮函数里的扩展置换与 S 盒，正是 ADFGVX 思想的直系后代。

一张表看清两大门派的分工

这张表的最后一行就是本节真正的落点：两大门派的弱点是互补的，死法是相同的，而它们的活法也是互补的——现代分组密码把替换与换位交替叠用，正是让"混淆"与"扩散"互相掩护。下一节的维吉尼亚在多表轮换上的探索，会把"组合"这个思想再推进一步。

本节要点回顾

• 换位密码只重排位置，字母频率分布原样保留，这个特征既是身份标签也是死穴；
• 栅栏密码密钥仅栏数一个参数，穷举成本趋近于零，只能用于临时遮眼；
• 列置换以关键词规定列序，一战战场上仍是现役体制，但统计分析照样可破；
• 乘积思想是换位真正的遗产：替换与换位交替叠用，直接启发了香农的混淆扩散与后来的 DES、AES。

替换与换位两条路线至此都已看清。下一节回到替换门派的巅峰之作——维吉尼亚密码，看它如何用多张替换表轮换使用把频率分析逼入绝境，又如何亲手埋下自己的死因。