列置换密码

I现象

把明文按行写在关键词下方，再把关键词的字母按字母序编号，最后按编号顺序逐列读出。

关键词 BRASS，明文 LOOM NEVER STOPS：

关键词的字母序是 A(3)、B(1)、R(2)、S(4)、S(5)，因此读取顺序是第 3 列、第 1 列、第 2 列、第 4 列、第 5 列。按此读出得 OEP、LET、OVO、MRS、NSX，连起来是 OEPLETOVOMRSNSX。

然后是填充：最后一行需要一个 X 才能补满矩形，接收方必须知道要丢弃它。这就是全部方法——而请注意它的失效方式与替换密码多么不同。所有字母都还待在字母表原本放置它们的地方，变的只是邻居。

II密钥空间

包含 k 个互异字母的关键词给出 k! 种列序。k = 8 时是 40320；k = 10 时是 360 万。

这相当可观，也是军方使用它的原因。但两个实际因素会严重压缩它。第一，关键词必须好记，因此真实密钥来自一个小词池。第二，更重要的是：攻击者很少需要密钥——他们需要的是列序，而列序可以被统计地恢复。

对置换密码的攻击不是对密钥的搜索，而是对排列顺序的搜索，由语言的统计特性引导。

标准技术是比较候选列对之间的双字母组与三字母组频率。某些字母对共同出现的频率远高于随机——TH、HE、IN、ER——而错误的列相邻关系会杀死这些配对。有几百个密文字母，列序就会自己浮现出来。

III加密步骤

• 选一个尽量不含重复字母的关键词，横写在页面顶端。
• 按每个关键词字母的字母序从左到右给列编号。
• 在关键词下方按行写明文，每列一个字母。
• 用填充补满最后一行以闭合矩形；如有可能，选择不会扭曲双字母统计的填充——X 和 Q 是好选择，E 不是。
• 按编号顺序逐列读取，列内自上而下，列间按编号升序。
• 把结果写成连续字符串，按五个一组断开。
• 对军用通信，把结果再用一次替换加密，并且绝不通过同一信道发送关键词。

IV解密步骤

• 数出密文字母个数，除以密钥长度得到行数。若有余数，说明最后若干列各少一个字母——先算出是哪些列。
• 按编号顺序把密文写进各列，每列填到其计算出的高度。
• 用关键词把列按原本顺序重排。
• 按行横向读出，恢复明文。
• 丢弃末尾的填充。
• 面对未知密钥时，由消息长度与可能的矩形数量推测长度，再用双字母组频率给候选列序打分。TH、HE、IN 三个配对合起来通常就能在几百个字母内定出正确顺序。

V弱点

易位构词有效。 由于所有字母都在，分析者可以尝试候选排列并按语言统计打分，搜索会迅速收敛。

填充泄露长度。 不能闭合的矩形需要填充，而填充的数量会告诉分析者消息长度对密钥长度取模的结果。

短密钥致命。 少于大约七个字母时，空间小到可以廉价穷举，尤其在有已知明文的情况下。

重复短语致命。 发信方在同一位置写了两遍的任何内容——标准开头、署名、路由报头——都会在列中对齐，直接暴露结构。

单层置换不够。 每一个严肃的使用者都会把它与别的手法组合：先做替换以消除字母频率，再做置换以消除顺序。德国的 ADFGVX 与英国的双重置换系统都是这个模式。

VI实战挑战

·史料

列置换没有单一的发明人，从十八世纪起就出现在欧洲的军事手册中。它在 1918 年德国的 ADFGVX 野战密码中达到顶峰——那是把 6 × 6 的分馏替换与以单词为密钥的列置换组合起来。法国密码分析家乔治·潘万在 1918 年 6 月在极大压力下破开 ADFGVX，读出了一条暴露德军春季攻势炮兵位置的电报，这份情报被认为促成了当年协约国的转机。英国一战期间的双重置换系统与后来 SOE 特工使用的密码都是它的直系后代。

·继续读

列置换是本织机上机器时代之前最后一个纯机械密码，也很适合用来观察二十世纪密码学的总体模式：用一个破坏字母身份的替换，去组合一个破坏顺序的置换，然后重复。

它也是最清楚地说明“顺序携带信息”的例子。被打乱的消息保留了每一个字母，失去了每一段关系——而意义正住在关系里。现代分组密码在每一轮里做的都是同一件事。

下一台织机：baconian-cipher 回到替换，但用一套把消息藏在文本形式而非内容里的方案。

+相关织线