密钥密码学（一）

原文：annas-archive.org/md5/b5abcf9a07e32fc6f42b907f001224a1

译者：飞龙

协议：CC BY-NC-SA 4.0

前言

序言

从秘密解码环到政府政策声明，隐藏和发现信息的挑战长期以来一直吸引着智慧。密码学是一个引人入胜的主题，几乎每个学童都有一些实践经验。然而，出于良好的原因，它是一个被深度保密包裹的学科，并被政府用来保护其最敏感的武器。密码学在军事和外交事务中的作用一直非常严肃。毫不夸张地说，密码学的成功和失败塑造了战争的结局和历史的进程；而且毫不夸张地说，密码学的成功和失败正在制定我们当前的历史进程。

回想一下美国南北战争中的安提塔姆战役，发生在 1862 年 9 月，当时乔治·麦克莱兰指挥联盟军对抗罗伯特·E·李的南方联盟军，位于马里兰州夏普斯堡附近。几天前，两名联盟士兵在他们的营地附近发现了一张纸条，结果证明这是李发出的一份详细说明马里兰入侵计划的命令副本。这份命令没有加密。凭借其中的信息，麦克莱兰准确地知道了李散兵游勇的位置，并在他们重新联合之前摧毁了李的军队。

密码学的成功和失败也塑造了更近期的历史。1914 年 8 月，俄罗斯在坦尼斯堡的可怕失败是德军截获俄罗斯通讯的直接结果。令人惊讶的是，俄罗斯的通讯完全是明文的，因为俄罗斯没有为其野战指挥官配备密码和密钥。因此，俄罗斯无法安全地协调各军中邻近单位的活动。

第二次世界大战后即将发生的 50 年冷战也是由一个密码学失误引起的，这次是在 1942 年中途岛战役中对日本人的失败。美国密码分析员破译了日本的密码，并阅读了大量联合舰队的消息。这类故事属于古典密码学的范畴。秘钥密码学就是在这个领域中发挥作用的。

没有人比 Frank Rubin 博士更能启发对古典娱乐性密码学各个方面感兴趣的读者，从其数学传承到社会学影响。Frank Rubin 博士的教育背景是数学和计算机科学。他在 IBM 的设计自动化领域工作了 30 年，并从事密码学工作超过 50 年。Frank Rubin 博士曾担任《Cryptologia》等出版物的编辑。他撰写了数十种数学和计算机算法，并创建了数千个数学谜题。

秘钥密码学 不仅仅是 Helen F. Gaines 的经典作品 Elementary Cryptanalysis 的更新。它涵盖了从古代到量子计算时代的领域。秘钥密码学 提出了新的方法和“破译”技术。最后，它解释了一种测量密码强度的独特方法。^(1,2)

这本书出版在密码学发展史上一个战略性的时刻。它为理解这一关键技术提供了及时而重要的贡献。无论读者是寻求关于密码学本身的启迪，还是信息安全从业者，这些页面中包含的知识的深度和广度都将是一份有用的信息来源和图书馆的宝贵补充。

——Randall K. Nichols，DTM

Randall K. Nichols 是美国密码协会（ACA）的前任主席、贵族和书评编辑；堪萨斯州立大学萨利纳分校无人机系统网络安全证书课程的主任；以及尤蒂卡学院研究生网络安全与取证的名誉教授。

参考文献

Gaines, H. F.（1956）。密码分析：密码及其解决方案研究。纽约市：Dover。

LANAKI.（1998）。古典密码学课程 Vol. I.。加州拉古纳山：爱琴海公园出版社。

LANAKI.（1999）。古典密码学课程 Vol. II。加州拉古纳山：爱琴海公园出版社。

Nichols, R. K.（1999）。ICSA 密码学指南。纽约市：麦格劳希尔。

Rubin, F.（2022）。秘钥密码学。纽约州 Shelter Island：Manning Books。

Schneier, B.（1995）。应用密码学：C 语言协议、算法和源代码。纽约：John Wiley & Sons。

前言

写这本书有几个线索。让我们从我的高中朋友查理·罗斯开始。查理在学校书店工作。有一天，在为商店订购书籍时，他注意到了 Helen F. Gaines 的书 Cryptanalysis。查理想要这本书，他也想要员工折扣。但出现了一个问题。商店最少订购数量是三本。

查理需要让其他两个人购买这本书。他承诺我们会一起阅读这本书，然后制作其他人解密的密码。我买了这本书，读了它，然后制作了密码，但查理失去了兴趣。

Cryptanalysis 的封底上给出了美国密码协会（www.cryptogram.org）的一个长期不更新的街道地址，但我找到了他们并加入了。我开始解决他们在业余爱好者通讯 The Cryptogram 中发布的各种类型的密码，几年后我成为了一名助理编辑。我在那里是会员超过 40 年。

1977 年，一个更专业的密码学期刊Cryptologia开始发行。你可以在www.tandfonline.com/toc/ucry20/current找到它。我开始阅读这些文章，然后贡献文章，最终成为一名编辑。不知何故，我成了“疯子处理者”。所有那些文章都送到了我手上，我不得不摸索出其中的道理，看看是否隐藏着一个好主意。仅有一个案例符合条件。我把它写成了一篇文章发表在The Cryptogram上。作者非常感激，他以我的名义在以色列种了一棵树。

这段经历教会了我如何区分那些只是写得很糟糕的文章，或者作者简单地高估了密码强度的文章，与那些真正离谱的文章。我学到了这个：用一个弱密码的业余爱好者可以描述密码并写出步骤。真正的疯子无法将他们模糊而宏大的想法写在纸上。他们可以滔滔不绝地写自己的密码有多么精彩，但他们无法写出步骤。他们无法将他们的初步想法转化为具体的算法。

大约在 2005 年左右，我开始在马里斯特学院 CLS（继续生活学习）上课。不久后，我开始就数独、SumSum 和其他谜题（我写了三本数独谜题书）进行讲座；我的坦桑尼亚和蒙古之行；帝国大厦的建造；艾伦·图灵的一生；以及其他主题。我成为了课程委员会的一员。

2018 年，我自愿为一门两学期的密码学课程做讲师。在为课程准备近 450 张幻灯片的过程中，我意识到我有足够的材料写一本书。幸运的是，我发现一年前我已经开始写了这样一本书。就是这本。

致谢

几天前，我无意中听到妻子米里亚姆在电话里对朋友说：“就像我和弗兰克和这本书住在一个ménage à trois里一样。”谢谢你，米里亚姆，在写这本书花了 18 个月的时间里，一年寻找出版社，6 个月找文学经纪人，一年看文学经纪人毫无进展，最后一个月才在 Manning 找到了这本书的归属。再加上 18 个月的审阅、修改、编辑、修订、排版、修订、索引、撰写营销文案等等。

我要感谢所有在 Manning 出版社帮助过我这本书的人，特别是迈克尔·斯蒂芬斯，他冒了险给了我一个合同，并在整个过程的每个阶段都给予了帮助；玛丽娜·迈克尔斯为她的许多编辑改进；丽贝卡·莱因哈特为平滑道路；詹·霍尔和苏珊·霍尼韦尔为插图工作；蒂凡尼·泰勒在语法和标点方面提出了许多宝贵的建议；保罗·威尔斯和凯里·哈尔斯为书的制作工作；萨姆·伍德为营销文案；丹尼斯·达林尼克为排版；当然，还有出版商马尔金·巴斯。

特别感谢 Randall K. Nichols 教授在极短时间内撰写本书前言并在《密码》杂志上进行评论。同时也感谢 Enigma 博物馆的 Thomas Perera 教授提供 Fialka 图像。

感谢那些阅读手稿并提出许多建议和有用批评的审稿人：Christopher Kardell、Alex Lucas、Gabor Hajba、Michal Rutka、Jason Taylor、Roy Prins、Matthew Harvell、Riccardo Marotti 和 Paul Love。你们的建议帮助使这本书更加优秀。

最后，我必须感谢李·哈维·奥斯瓦尔德，他那令人发指的暗杀总统约翰·F·肯尼迪的行为阻止了我去联邦调查局总部进行安全面试，这也使我无法加入国家安全局，否则我写这本书就会成为一种重罪。

关于本书

谁应该阅读这本书？

本书面向广泛的读者群体：一般读者、密码学爱好者、历史爱好者、计算机科学学生、电气工程师、数学家和专业的密码学家。这使得我的工作变得更加困难，因为不可能使书中的每一部分都适合每一类读者。对于某些读者来说，书中的某些部分可能需要太多的数学知识。对于某些读者来说，有些部分可能太基础了。在本节中，我试图引导读者找到我认为最适合他们的材料。

• 一般读者可以直接阅读至第八章结束。只需跳过数学太难或技术性太强的部分。从第九章开始，情况开始变得棘手。从这一点开始，他们可以略读，并挑选感兴趣的主题。他们可能想阅读第十二章以获取一般概念，而不深入细节。

• 密码学爱好者可能会想阅读整本书，然后再仔细研究第 4.2 至 5.11 节，第 6.1 至 6.5 节，第 6.7 节，大部分第七章以及第 9.1 至 9.9 节，加上有趣的页面和挑战页面。

• 历史爱好者可以阅读整本书，忽略数学部分，以了解每种方法是何时以及由谁开发的时间线。

• 计算机科学学生可能会特别重视第 5.6 至 5.11 节，第八章和第 11 至 16 章。

• 电气工程师将寻找实用方法。他们应首先阅读第二章和第四章以建立基础，然后阅读第 7.2 至 7.8 节，第九章和第 11 至 16 章，特别强调第十二章。

• 数学家对第 4.5 节，第 5.6 至 5.12 节，第 10.4 至 10.7 节，第 11.7 至 11.10 节，第 12.3 至 12.6 节，第 13 至 16 章，特别是第 16.4.6 节和第十八章最感兴趣。

• 专业的密码学家对第 7.8、8.2、10.5、10.7、11.4、12.3 至 12.6、13.8、13.15、14.2、14.4、15.4 至 15.14、16.4、16.5 和 18.12 节最感兴趣。

关于密码学

我包含了一些有趣的密码和挑战密码，供想尝试解决的读者使用。 有趣的密码使用书中描述的标准方法。

挑战密码使用我自己发明的方法。 它们非常简单，以至于业余爱好者既可以猜测方法，又可以解决它们。 我试图做到公平，以便感兴趣的读者可以解决它们。 没有奇怪或复杂的东西。 没有奇怪的词语或扭曲的字母频率。 而且提供足够的材料来解决它们。

您可能会注意到一些以粗体 ***** 开头并以 ***** 结尾的部分。 这些是可选部分，可能包含计算机算法或更深层次的数学。 一些读者可能选择跳过这些部分。

liveBook 讨论论坛

购买 密钥密码学 包括免费访问 liveBook，Manning 的在线阅读平台。 使用 liveBook 的独家讨论功能，您可以将评论附加到全书或特定部分或段落。 为自己做笔记，提出和回答技术问题，并从作者和其他用户那里获得帮助，都是轻而易举的。 要访问论坛，请转到 livebook.manning.com/book/secret-key-cryptography/discussion。 您还可以在 livebook.manning.com/discussion 上了解有关 Manning 论坛和行为规则的更多信息。

Manning 对我们的读者的承诺是提供一个有意义的对话场所，个别读者之间以及读者与作者之间可以进行对话。 这并不是对作者参与的任何特定数量的承诺，他在论坛上的贡献仍然是自愿的（并且无报酬）。 只要这本书还在印刷中，论坛和以前讨论的档案将可以从出版商的网站访问。

其他在线资源

您可以在作者的网站 www.mastersoftware.biz 上找到作者的密码学产品。

作者简介

弗兰克·鲁宾拥有数学学士和硕士学位以及计算机科学博士学位。他在 IBM 工作了 28 年，从事设计自动化领域，在那里他设计并编写了专门用于设计计算机和电路的软件，IBM 工程师使用这些软件。他是 Master Software Corp.的所有者，该公司生产密码软件。弗兰克已获得四项关于密码方法的美国专利。弗兰克在密码学、计算机电路、图论和纯数学等领域发表了约 50 篇经过同行评议的期刊论文，以及几本（用户手册和项目规范）在 IBM 内部出版的书籍。在密码学领域，他以解决杰斐逊密码轮而闻名。在计算机科学领域，弗兰克以算术编码而闻名，这现在是文本压缩的标准方法之一，以及他的寻找哈密顿路径的算法。在纯数学领域，他可能以引入有限状态识别器概念而闻名。弗兰克有三本数独谜题书和两本自出版的 SumSum 谜题书。他是The Cryptogram，Technology Review和Journal of Recreational Mathematics等刊物上发表的超过 3500 个谜题的作者，他是唯一一个被授予专门为他自己的谜题而献给的JRM特刊的人。

关于封面插图

秘钥密码学封面上的图案是“Le Garçon de Bureau”，或者“办公室助理”，取自路易·库尔默编辑的一本 1841 年出版的书。每幅插图都是精心绘制和手工上色的。

在那些日子里，人们很容易通过他们的服装来辨认他们住在哪里，以及他们的行业或社会地位是什么。曼宁通过基于几个世纪前地区文化的丰富多样性的书籍封面，再现了今天计算机业的创造力和主动性，这些插图来自于这样的收藏品。

---

^(1.) R. K. 尼科尔斯的ICSA 密码学指南和 Bruce Schneier 的应用密码学都介绍了密码强度和随机性方法。前者集中在古典密码学上，后者集中在现代密码（尼科尔斯，1999；Schneier，1995）。

^(2.) 秘钥密码学的定义和写作比我前两本关于古典密码学的书更好，即古典密码学课程第一卷和第二卷（LANAKI，1998；1999）。

第一章：介绍

我从事密码学已经超过 50 年了。在这段时间里，我学到了很多东西。在这本书中，我试图将这些知识传授给下一代密码学家。其中很多是新的发现，在文献中找不到。

我知道已经有许多密码学书籍可供阅读。如果我希望人们阅读我的书，我需要提供其他书籍没有的想法，其他作者不知道的想法，或者认为不可能的想法。我需要让这本书轰动。让我们开始吧。我将

• 用简单的非技术性语言告诉你如何构建一个不可破解的密码。

• 提供了 140 种可直接使用的密码。其中有 30 种被评为不可破解。

• 给你一套工具和技术，让你可以结合并加强它们。

• 描述一个可以精确测量密码强度并保证其不可破解的计算方法。

• 展示如何构建和整合数据压缩代码。

• 揭示了实现不可破解一次性密码本密码的实用方法。

• 告诉如何批量生成真随机数。

• 展示如何构建大素数和安全素数。

• 教你如何向密码添加一个不可检测的后门。

• 揭示了量子密码学中可能存在的致命缺陷。

• 解释如何击败可能在未来几十年内开发的假设的超级计算机。（或者，可能已经存在，但是被列为机密。）

我在整本书中都使用对话的语气，就好像你和我面对面交谈一样。当我说“我们”或“我们”时，那意味着你，读者，和我，作者，一起合作解决问题或保守秘密。

这不是一本学术性的著作。我在了解来源时会给予方法和想法以及尽可能接近的日期，但我所学到的大部分都是非正式获得的。书中几乎没有参考文献、脚注或博学的注释。这本书是为了实用而写的。遵循它的建议，你将制作出一个安全的密码。保证。

我还会不时插入一些历史趣闻，部分是为了缓和气氛，部分是为了纠正历史记录。我知道像密码学这样的沉重主题可能会让人感到困难。我希望使用第一人称，一些小轶事和一点幽默可以让读者更容易吸收。

这本书中的许多材料都是新的。它包含了构建密码和破译密码的方法，这些方法以前从未被公开过。甚至还有一些我自己的数学发现。你只能在这本书中找到它们。书中还有很多关于如何做事情的实用技巧，以及一些可以更快或使用更少存储空间的计算机方法。

本书的重点是高安全性密码学。你有需要保密的信息，面对可能拥有超级计算机甚至量子计算机的对手。这本书告诉你如何做到。我提供了一套方法工具箱，包括新的和历史悠久的方法，可以以各种方式组合，制作出任意强大的密码。密码学学生和开发人员将找到最广泛的实用方法，可用于开发新的密码产品和服务。

话虽如此，我希望这些材料对专业人士和业余爱好者都能够轻松理解。有很多方法可以手工完成，只需纸和铅笔即可。你可以在第 9.6.1 节的末尾找到这样一种方法。这些方法适用于现场使用，当电力和电子设备可能不可用时。甚至有一些儿童可以使用的密码。

任何人都可以创建一个不可破解的密码。

你可以创建一个不可破解的密码。你所需要的只是正确的知识。如果你能阅读并理解这本书，甚至只是其中一半，那么你就可以创建一个不可破解的密码。这本书教会任何有愿望的人如何构建一个能够经受住受过训练的密码学家和超级计算机的严格攻击的密码。没有其他书能做到这一点。事实上，你甚至可以使用纸和铅笔方法开发自己的安全密码。我从 15 世纪开始构建了大量的方法和概念，教会你哪些组合可以加强你的密码，哪些只是徒劳无功。我将为你提供一系列经过验证的技术，以及新颖的技术，让你可以构建一个坚不可摧的堡垒。

提前警告：我是一名受过数学训练的数学家，职业是计算机科学家，所以我倾向于自由使用数学符号和数学概念。这本书面向更广泛的受众，不仅仅是工程师和科学家。我会尽力解释所有需要的数学知识，使得这本书是自包含的。如果你理解下标和指数，并且能够阅读包含括号的表达式，那么你所需的数学背景就差不多了。我会解释所有超出这个范围的数学知识，比如质数、模运算，以及更高级章节中的矩阵运算和数学环。

如果你不理解某个数学概念，你有三个选择：（1）相信我的话，（2）完全跳过该部分，或者（3）不使用相关的密码方法。仍然有很多方法。一定有适合你需求的方法。

或者，直接深入阅读数学部分。你可能会惊讶于自己学到了多少。如果你不理解某个主题，不要灰心。你可能会觉得下一个主题很容易。即使是专业数学家也不会理解每个主题。

第二章：什么是密码学？

本章涵盖

• 密码学中使用的基本术语

• 什么是不可破解的密码？

• 有哪些不同类型的密码学？

密码学通常被称为“秘密写作的艺术”。它不仅仅是那样。它涵盖了从隐形墨水到通过光子的量子纠缠传输消息的所有内容。特别是，密码学包括制作和破译代码和密码。

不同的作者以不一致的方式使用密码学术语，因此让我们首先就一些基本术语达成一致。

明文 或 纯文本 是你希望保密的消息或文档。在传统密码学中，消息是发送者和接收者都知道的某种语言编写的文本。在计算机环境中，这可以是任何类型的文件，例如 PDF（文本）、JPG（图像）、MP3（音频）或 AVI（多媒体）。

密码 是一种用于使消息变得不可读的方法，或 算法：例如，通过改变字符的顺序或用不同的字符替换一些字符。通常，密码对文本中的单个字符或字符组进行操作，而不考虑它们的含义。

密钥 是仅知道发送者和合法接收者的秘密信息，用于选择每条消息使用的转换的信息。例如，如果密码（方法）是改变消息中字母的顺序，密钥可能指定当天消息使用的顺序。密钥可以是字母、单词或短语、数字或字母、单词和数字的序列。密码的强度高度依赖于它使用的密钥的总大小。

关键字 或 关键短语 是用作密钥的单词或短语。

加密 或 加密 是将明文变成不可读杂乱的过程，合法发送者知道密钥。

密文 是结果杂乱不可读的消息或文档，将被传输或存储。

解密 或 解密 是合法接收者使用的过程，合法接收者知道方法和密钥，将杂乱的密文转换回原始明文消息。

代码 也是一种使消息变得不可读的方法。与密码相比，代码通常是对消息中的单词或短语进行操作。典型的代码用数字或字母组成的组替换单词或短语。（令人困惑的是，“代码”这个词也用来表示字母的标准化表示，例如莫尔斯电码。希望从上下文中可以清楚地理解其含义。）

密码学 是对密码学的形式化研究，用于构建和解决密码的数学和方法论。学者们研究密码学；破译者研究密码分析。

密码分析 是研究代码和密码的专门目的，以识别弱点并找到突破它们或相反，加强它们的方法。

破译是指通过没有密钥并且可能不知道加密方法的第三方（敌人或对手）解决加密消息的过程。这可以通过数学方法或通过耐心地收集和整理拦截来完成，但实际上通常归结为三个 B：贿赂、勒索和入侵。

2.1 无法破解的密码

现在我们有了一些共同的语言，让我来解决主要问题。我所说的“无法破解”到底是什么意思？首先，我指的是一个密码不能通过密码学手段破解。这排除了入侵、贿赂、胁迫、叛变、敲诈勒索、诱捕等手段。这些超出了我们的范围。其次，我指的是密码在实践中无法被破解。任何对手都有有限的资源和有限的时间来投入到破译任务中。在选择密码时，你需要对你的潜在对手可能用来破解你的密码的人力资源和计算机资源有一定的了解。做一个保守的猜测，考虑计算机的改进，增加安全边际，然后选择一个数字。然后，当你选择一个密码时，你就有了一个目标。达到这个目标，你的密码就是有效无法破解的。

记住，许多消息的寿命有限。如果你的消息是攻击在黎明时分，而你的敌人在中午读到了你的消息，那就太晚了。你已经发动了攻击。一个在 12 小时内可以被破解的密码，在你的对手没有 12 小时的情况下是无法被破解的。

只是为了让这个概念更加清晰，当我说一个密码已经被破解时，我是指对手可以读取使用该密码发送的消息。即使对手只能读取 1%或 0.01%的消息，该密码也被破解了。但是有一个截止点。如果对手只有在拦截了许多使用相同密钥加密的相同长度的消息，或者其中 63 个密钥位为零时才能读取消息，则密码仍然未破解。对手没有先验的方法来确定哪些消息使用了哪些密钥，或者哪些密钥几乎全为零。你可能永远不会发送两条相同长度且使用相同密钥的消息，或者其中 63 个密钥位中有 64 个为零的消息。

如果你的密码使用了一个 256 位的密钥，而一个敌方密码分析家找到了一个将其减少到 200 位甚至 150 位的数学或计算方法，那么该密码可能会被削弱，但如果你选择的安全级别是 128 位，它仍然未被破解。使用 256 位密钥来实现 128 位安全级别提供了巨大的安全保障。

当政府决定旧的数据加密标准不再安全时，它举行了一场新密码的国际竞赛。在全球范围内征集提案。数十种密码被提交。数百名密码学家评估了这些候选密码的安全性、速度和易于实施性。从 1997 年到 2000 年 4 月，进行了三轮淘汰，直到选出了一个获胜者。当你的密码将成为政府、银行、工业和军事的全球标准时，你需要做的就是这样。如果你决定参加下一次的竞赛，这本书将帮助你做好准备。

大多数读者不会尝试那样做。他们的密码会有更有限的范围。他们可能会信任自己的判断，或者他们设计的任何验证过程，来评估他们的密码。第十二章的原则将帮助他们做出明智和自信的决定。

2.2 密码学的类型

密码学有许多不同的类型。过去使用的一些类型是

• 隐藏消息：例如，信使可以吞下消息，或将其藏在靴子跟或马鞍中，或者简单地记住它。在古代，让信使把消息以他们不理解的语言的发音记忆是很常见的。

• 秘密方法，比如凯撒密码，其中字母表中的每个字母都被替换为后面 3 个位置的字母。也就是说，A 变成了 D，B 变成了 E，C 变成了 F，依此类推。

• 伪装消息，其中消息被制成看起来像其他东西，比如信使的衣服设计。

• 隐形信息，如微点或在加热或暴露于酸性物质时变得可见的隐形墨水。

• 误导：例如，签名或纸张的形状和颜色是真正的消息，而其他一切都是干扰或虚假信息。

所有隐藏消息的方法统称为隐写术，最早在 1499 年本笃会修士约翰内斯·特里特米乌斯（Johannes Trithemius）的著作《隐写术》（Steganographia）中描述，特里特米乌斯出生于约翰内斯·海登贝格。特里特米乌斯的书本身就是一种隐写术，因为它伪装成一本魔法书。

这些隐写术方法有现代对应物。例如，可以通过仅使用每个像素的低阶位在 JPEG 图像文件中隐藏消息。另一个例子是使用随机数生成器来选择文件的每个字节中的特定位。所选位包含消息，其余位可以是随机的无用信息。

在描述现代密码之前，让我介绍一个有用的简化方法。一条消息从发送者发送给接收者，加密的目的是阻止某个敌人阅读消息。为了简洁起见，我将发送者称为桑德拉，预期接收者称为莉娃，敌人称为艾米丽。这比艾丽斯、鲍勃和卡罗尔更自然，不是吗？

通常桑德拉在本地对消息进行加密，然后再发送给莉娃。消息可以通过任何方式发送：信件、电话、互联网、短波无线电、阿尔迪斯灯、微气泡、电报、光纤电缆、信号旗、量子纠缠，甚至如果有直线视野的话，还可以使用烟信号。为了使这个图像更加完整，密码可能需要一个密钥以及明文，可能会有敌人在监听。这是一个更完整的图像。

现代密码通常分为三大类：秘钥、公钥和个人钥匙。它们的主要区别如下。

秘钥：桑德拉有一个秘密密钥，用于加密消息。莉娃有一个对应的秘密密钥，用于解密这些消息。这可能是相同的密钥或者一个反向密钥。通常情况下，桑德拉控制着密钥。当桑德拉更改密钥时，她必须将新密钥或其反向密钥发送给莉娃。这是经典密码学的标准范例。

公钥：莉娃有一个公共加密密钥，她向所有人公开。每当桑德拉想要给莉娃发送消息时，她都会使用莉娃的公钥对其进行加密。莉娃还有一个秘密解密密钥，只有她自己知道，她可以用来解密她收到的消息。要使这个方案工作，重要的是没有其他人可以从公共信息计算出这个秘密密钥。主要的公钥方法是由罗纳德·里韦斯特、阿迪·沙米尔和伦·阿德曼于大约 1975 年发明的 RSA 算法。

个人钥匙：桑德拉和莉娃各自拥有一个个人钥匙，不与任何人分享，甚至不与彼此分享。由于从未传输或分享任何密钥，个人密钥密码学有时被称为无密钥密码学。它是如何工作的：（第一步）桑德拉用她的个人密钥对消息进行加密，并将加密的消息发送给莉娃。 （第二步）莉娃用她的个人密钥对该消息进行再次加密，并将这个双重加密的消息发送回给桑德拉。 （第三步）桑德拉使用她的个人密钥对该消息进行解密，并将其发送回给莉娃。 现在消息只使用莉娃的密钥加密，她可以使用该密钥来阅读消息。

这里的棘手之处在于桑德拉的加密和莉娃的加密需要交换律。也就是说，无论桑德拉先加密还是莉娃先加密，它们都必须产生相同的结果。符号上，我们将其表示为 SRM=RSM，其中 M 是消息，S 和 R 分别是桑德拉和莉娃的加密。个人密钥加密的优势在于，任何人都可以与任何其他人安全地通信，而无需预先安排任何密钥或传输任何密钥，因此不存在密钥被拦截的可能性。

个人密钥密码学也称为三次传递协议。协议只是用于某种目的（如传输消息）的一系列步骤。换句话说，协议就是一种算法。三次传递协议的基本思想是由 Adi Shamir 在大约 1975 年发明的，我在本书中介绍的具体方法则是我自己的。

2.3 对称与非对称密码学

许多书籍指出，密码学可以分为两种类型：对称和非对称密码。其观点是，在秘密密钥密码学中，Sandra 和 Riva 使用相同的密钥来加密和解密消息，而在公钥密码学中，Sandra 使用一个密钥，而 Riva 使用其逆密钥。这种二分法忽视了个人密钥密码学，既不对称也不对称，以及第 2.2 节开头描述的各种经典方法。此外，对称/非对称分类并不总是准确的。在第 15.1 节中，我描述了 希尔密码，一种加密方法，其中加密是通过密钥乘以消息来完成的，而解密是通过乘以逆密钥来完成的——就像公钥密码学一样。

将密码作为对称或非对称的分类并不特别有用。它未能捕捉到秘密密钥和公钥密码学之间的本质区别，即在秘密密钥密码学中，所有密钥都保持秘密，而在公钥密码学中，每个参与方都保持一个密钥秘密，并将一个密钥公开并提供给所有人。

公钥密码学和个人密钥密码学都诞生于 1975 年左右。公钥密码学引发了人们的想象力，因此自那时以来，秘密密钥和个人密钥方法受到了少数关注。许多书籍对公钥密码学有详尽的介绍。本书主要关注秘密密钥密码学，这是密码学的主要支柱和基石。

2.4 块密码与流密码

另一种分类是将密码分为块密码和流密码。块密码对消息中的字符块进行操作，比如 5 个字符的块。通常所有的块大小都相同，并且每个块都使用相同的密钥。

流密码是一次处理消息的一个字符。每个字符都有自己的密钥，称为字符密钥，通常取自称为消息密钥的较大密钥。在旧的流密码中，消息密钥被重复使用。例如，如果消息密钥大小为 10 个字符，那么第一个密钥字符将用于加密消息的第 1、11、21、31 等字符，第二个密钥字符将用于加密消息的第 2、12、22、32 等字符，依此类推。使用定期重复密钥的密码称为周期性密码。在较新的流密码中，消息密钥通常与消息本身一样长，并称为密钥流。这种非周期性或非周期性的加密方式称为一次性密码本。在第十三章中，将讨论如何生成密钥流。

区块/流分类并不是互斥的。还有混合密码，其中消息被分成块，但不同的块用不同的密钥加密，因此密码是对一系列块而不是一系列字符进行操作。

2.5 机械与数字

密码也可以根据产生它们的方法进行分类。最早的密码完全是手工完成的。不是用铅笔和纸，而是用尖笔和羊皮纸，或尖笔和粘土板。

第一种机械加密手段是由古希腊人和斯巴达人使用的天线或斯底尔（发音为 SKIT-a-lee），可能早在公元前 700 年就已经存在了。它由一个棒状物组成，周围缠绕着一条窄窄的皮革或羊皮纸条，以便每个转的边缘与相邻转的边缘完全匹配。换句话说，没有间隙，也没有重叠。消息的字母被写在带子的两个或更多转上。当带子解开时，只有断断续续的字母片段可见，以便敌人不会意识到其中包含一条消息。还可以添加额外的波纹或颜色斑块，使其看起来像是装饰品。

发件人保留棒以供阅读和编写未来的消息。信使可以将带子当作腰带佩戴，或用来扎头发或勒马鞍。收件人需要一个与之直径相同的棒来重建消息。当然，信使们不会被告知带子或鞍带的目的。它甚至可能被偷偷地缝进他们的衣服中而不被察觉。

在乔瓦尼·巴蒂斯塔·波尔塔（Giovanni Battista Porta）的 1593 年版《关于隐秘文字记号》中有一张关于天线的图片。它展示了每个希腊字母是如何跨越几个转的皮带的。这是一个现代版本。

希腊人保守了 skytale 的秘密约 700 年。然而，罗马人并不那么成功。最终，他们在北欧的敌人了解了这些棒子的意义和用途。因此，罗马人发明了一种特殊的测量工具，由一个空心的黄铜或青铜十二面体组成，这是一个具有 12 个相同五边形面的固体形状，每个面上有一个圆孔。这些孔允许他们制作精确直径的木棍。当派驻需要穿越敌对领土的总督（satrap）、大使或间谍时，携带这种工具比携带可能被捕获的实际 skytale 更安全。这 12 个孔具有不同的直径，以便与其他总督、大使和间谍进行安全通信：例如，伦敦（现为伦敦）的小孔，里昂（现为里昂）的中等孔，以及塔拉戈纳（现为加泰罗尼亚的塔拉戈纳）的大孔。

据所知，这些十二面体的用途从未被北欧人或现代考古学家发现。考古学家为这些物品提出了许多荒谬的目的，如儿童玩具、鞍饰、铁匠的练习作品、烛台、火炮测距器，或者最后的答案，宗教物品。

这是在比利时最古老的城镇汤根附近发现的一枚青铜罗马十二面体，并展示在加洛-罗马博物馆。

这里有一个有趣的注释：如果你在维基百科和其他网站上查找 skytale，它说 skytale 被用来通过在带子的一个转动内写每个字母来生成换位密码。这是错误的。这样的带子很容易被识别为密码信息。无论敌人能否读懂这条消息，他们肯定不会让信使传递它。关于整个字母与断开字母问题的彻底审查可以在 cryptiana.web.fc2.com/code/scytale.htm 找到。1841 年，埃德加·爱伦·坡，一个才华横溢的密码学家，写了一篇名为“关于秘密写作的几句话”的论文，其中描述了 skytale 和他通过匹配断裂字母碎片来解密这些消息的方法。

要进一步弄错，如果你在维基百科中查找“换位密码”，它说 skytale 被用来制造“栅栏密码”，也称为“锯齿密码”。栅栏密码有交替向上和向下的列。在棒子上写信息不涉及任何方向的改变。因此，如果使用 skytale 生成换位密码，结果可能是列置换，而不是栅栏。 （我在维基百科上更正了这些错误，但我的更正被删除了。我已经放弃了试图成为维基百科警察。）

20 世纪 60 年代的一种天线是对一叠计算机打孔卡进行排序，用铅笔在卡片的外表面写下消息，然后彻底洗牌，只留下零散的点。当卡片通过卡片分类机时，卡片将恢复到原始顺序，消息可以被读取。程序员们广泛讨论了这个想法，但我不知道它是否被实践过。另一个现代等价物是在拼图的空白背面写下消息，然后打乱拼图块。接收者需要解决拼图，然后翻转它以阅读消息。

另一种机械密码是托马斯·杰斐逊在 1790 年至 1793 年间发明的杰斐逊轮密码机。它由 36 个相同大小的木制圆盘穿在一根铁棒上形成一个木制圆柱。在每个盘的外缘，按某种乱序写有 26 个字母。盘可以独立旋转以拼写任何消息。使用盘或纸条的杰斐逊密码的版本直到 20 世纪 60 年代仍在使用。

从 15 世纪到 19 世纪，许多类型的盘式密码机被发展出来。最常见的类型使用几个薄平面同心圆盘，可以围绕中心枢轴旋转。每个盘的上表面边缘写有字母或某些数字或符号，按某种顺序。盘逐渐变小，以便同时看到所有字母表。盘被对齐在某个位置，加密包括在一个盘上找到明文字母，然后使用另一个盘上对应的字母或符号作为密文字母。后来的盘式密码机在每个字母被加密后，手动或通过钟表机构推进内盘。

这是奥古斯托·布纳法尔切绘制的莱昂·巴蒂斯塔·阿尔贝蒂密码盘的图片，取自他 1467 年的著作De compendis cifri。（图片由维基共享资源分发。）

从 1915 年开始，一系列长期的电机机械转子密码机被发明出来。最著名的是 20 世纪 20 年代由德国工程师阿瑟·谢比乌斯开发的恩尼格玛机。直到计算机时代开始，几十种类型的密码机被推出市场。它们都产生流密码。基本思想是，字母的替代品由电流通过一系列旋转转子的路径确定。每个字母被加密后，一些转子转动，由各种凸轮、齿轮、凸耳和爪控制，以各种方式改变替代品。因此，如果单词 INFANTRY 变成PMRNQGFW，可能在数十亿次转动后不会再次发生。

自 1960 年代以来，密码学变得越来越计算机化和数字化。数据加密标准（DES）是由 IBM 在 1975 年开发的，并在 1977 年获得了国家标准局的认证。这引发了一系列带有名称的分组密码，如 Serpent 和 Twofish，最终以 2001 年由国家标准技术研究所（NIST）采用的高级加密标准（AES）告终。这类密码在第十一章中涵盖。

进展已经从手动 ➔ 机械 ➔ 电动机械 ➔ 数字化。

为什么选择秘密密钥？

在这个公钥密码学时代，自然会产生一个问题，为什么有人会选择秘密密钥密码学？有几个原因。

秘密密钥密码学速度更快。即使是最强大、最复杂的秘密密钥方法，其速度也往往是领先的公钥方法的数百甚至数千倍。事实上，公钥密码学的主要用途是为秘密密钥密码学加密密钥。密钥是使用公钥方法发送的，但消息本身是使用秘密密钥方法发送的。

公钥密码学（PKC）需要公钥基础设施。必须有公钥服务器将公钥分发给潜在的通信者。PKC 受到各种中间人和欺骗攻击的影响，对手冒充发送者、和/或接收者和/或密钥服务器，因此 PKC 需要大量的身份验证和验证。请求公钥的人必须证明与接收者在同一网络中。包含公钥的消息必须经过验证，以确保其来自服务器。接收者在首次在服务器上发布公钥时和每次更改时必须进行身份验证。当向网络中添加新方时，必须对授权新方的人进行身份验证。当将新网络添加到服务器时，必须对所涉及的每一方进行身份验证。接收者必须验证接收到的消息未经第三方篡改或替换。所有这些都导致了大量的消息。

秘钥密码学可以在没有任何行政负担的情况下运作。两个个体可以交换秘密密钥消息，而不需要涉及任何其他人或任何中间系统。当几个人交换秘密密钥消息时，唯一需要的授权是每个参与方都有当前的密钥。未经授权的人将没有密钥，也无法阅读消息。

交换消息并不是密码学的唯一用途。同样重要的作用是保护存储在计算机上、外部设备（如闪存驱动器）或云存储中的数据文件的机密性，通常需要很长时间。PKC 不能用于此目的。只有秘密密钥方法适用于保持数据文件机密。

当需要向许多接收者同时广播消息时，可以很容易地使用秘钥方法来实现。每个参与方只需拥有秘钥即可。他们可以使用一个特殊的广播秘钥，与他们的个人秘钥分开。或者，每个参与方可以通过使用一个单独的秘钥传输秘钥来发送消息秘钥。使用公钥方法，您需要获取所有接收者的个人公钥，以及所有相关的授权和验证。这不能事先安排，因为参与者可以随时更改他们的公钥。

最常见的公钥方法是 RSA 方法。该方法的强度取决于目前很难分解大数的事实（见第 3.4 节）。给定一个没有小质因数的 200 位十进制数，目前没有可行的方法来分解它。然而，当量子计算机可用时，这一切都会改变。麻省理工学院教授彼得·肖尔开发了一个可以轻松分解那么大数字的量子算法。当这发生时，存储在计算机上的所有 RSA 消息都将能够被读取。

到目前为止，尚无已知方法可以利用量子计算机来破解秘钥密码。如果量子计算机是一个问题，秘钥密码学是唯一的选择。

为什么要自己构建？

如果您是一个密码爱好者，为什么要构建自己的密码是显而易见的。您构建自己的密码是因为这是您的爱好。模型火车爱好者设计、构建和运行模型火车。模型飞机爱好者设计、构建和飞行模型飞机。密码爱好者设计、构建和解密密码。

如果您是一个密码学学生，构建自己的密码是很好的训练。这是学习如何构建和评估密码的最佳方式。当前标准密码 AES（第 11.5 节）不会永远持续下去，必须有人设计它的替代品。如果您想成为这一努力的一部分，这本书可能是您最好的起点。

如果您是一名负责保护高价值数据和通信的严肃密码学家，您可能会出于对政府批准的密码是否像您的政府声称的那样安全的健康怀疑而构建自己的密码。让我给您一个故事来支持您的怀疑。

大约在 1975 年，IBM 提出了现在称为 DES 的密码，即数据加密标准。它成为了全球标准的秘钥加密。正如 IBM 最初设计的那样，DES 具有 64 位秘钥。国家安全局（NSA）要求将秘钥从 64 位减少到 56 位，并将其他 8 位用作校验和。

这毫无意义。如果真的需要一个校验和，那么秘钥可以从 64 位增加到 72 位。人们普遍认为，NSA 提出这一要求的真正原因是它知道如何破解使用 56 位秘钥的消息，但不知道如何破解使用 64 位秘钥的消息。这被证明是真实的。

你可以合理地得出结论，NSA 绝不会批准任何它无法破解的加密标准。在这种情况下，你可以推断 NSA 可以破解所有不同形式的 AES。如果 NSA 可以破解 AES，那么它的俄罗斯和中国的对手很可能也可以破解 AES。

只有少数几位专家构建候选密码，从中选择全球标准密码。众所周知，这些专家在马里兰州的 NSA 总部 Fort Meade 接受简报。在这些会议期间，NSA 人员向他们提供可能加强或削弱密码的技术。可能隐藏在推荐方法中的是一些后门，让 NSA，只有 NSA，能够轻松解决这些密码。NSA 还可能提供工作、合同和研究资助，可能诱使专家采用那些脆弱的方法。

这里有很多猜测，但密码学家往往非常保守。如果你能想象出一个可能的弱点或漏洞，无论你的对手是否真的能够利用它，最好在能够时防范。

最后，你可能只是追求速度、更简单的实现或更便宜的硬件。你可能想构建自己的密码来实现这些目标而不放弃安全性。你会在这本书中找到可以帮助你做到这一点的方法。

话虽如此，请记住存在许多陷阱。不要仅仅创建一个密码并假设它足够“强大”。许多密码最终被发现存在意想不到的弱点。即使是最强大的密码也可能被操作员的错误所击败，比如每条消息都以标准头部开始，频繁重用密钥，或者使用不同密钥发送相同消息。例如，许多德国消息在二战期间被解密，因为它们都以“希特勒万岁”开始。

这本书包含了构建不可破解密码所需的所有信息，但请记住，仅阅读一本关于密码学的书并不会让你一夜之间成为专家。一定要使用第十二章详细介绍的原则来检查你的密码的强度。

第三章：初步概念

本章涵盖

• 位和字节

• 函数和布尔运算符

• 素数和模算术

在我们深入主题之前，让我们先看一些初步概念。我会快速地介绍这些主题，因为如今许多这些想法甚至在低年级就开始教授。更多这些基本概念将在书中后面根据需要给出。

3.1 位和字节

数据以位的形式存储在计算机中，这是二进制数字的简称。一个位只是一个可以取值为 0 或 1 的数字。一个位可以以几种方式存储在计算机中。开关可以是打开或关闭的。磁铁的北极可以朝上或朝下。光可以是顺时针或逆时针极化的。电脉冲可以具有小幅度或大幅度。

这些二进制数字可以用来形成二进制数。以下是 3 位二进制数及其十进制等价物。这些 3 位数被称为八进制数，意味着它们是基数为 8 的数：

位也用于表示计算机逻辑中的逻辑值或真值。0 表示逻辑值假，1 表示逻辑值真。

一个字符，比如字母或数字，可以用一个 8 位二进制数表示，这被称为字节。术语字节是由 IBM 的 Werner Buchholz 在 1954 年创造的。由于每个位有 2 个可能的值，8 位可以表示 2⁸个不同的字符：也就是 2 的 8 次方，即 256。这足以表示 26 个小写字母、26 个大写字母、10 个十进制数字、33 个标点符号，如=和$，再加上一些控制字符，如制表符和换行符。

有几种方案可以表示额外的字符，比如西里尔字母Ж，阿拉伯字母س，甚至中文是，每个表意符号最多使用 4 个字节。这对我们来说并不相关。密码可以处理字符串而不考虑它们的含义。被加密的字节可能是表示某个中文表意符号的 4 个字节中的第三个是无关紧要的。

对于我们的目的，一个字节有 3 个身份：（1）它是一个包含 8 个逻辑真/假值的字符串；（2）它是一个 8 位二进制数，因此是一个介于 0 和 255 之间的整数，包括 0 和 255；（3）它是某个字符的表示，比如字母、数字、标点符号或表意符号的一部分。

3.2 函数和运算符

数学函数现在在小学阶段就开始教授，所以我相信我不需要解释这个概念，但建立一些符号和术语是有帮助的。一个函数接受一个或多个值，并产生另一个值作为结果。被接受的值称为函数的输入或参数，返回的值称为输出或结果。我们说你应用函数到参数上以产生结果。

一个函数可以用符号表示，例如+或字母。当使用符号时，它被称为运算符，因此+和×是运算符，参数被称为操作数。当函数有一个参数时，符号可以放在参数前面，如-5 或√9，或者在参数后面，如 5！（5 的阶乘，即 1×2×3×4×5 = 120）。如果有两个参数，符号就放在它们之间，如 3+4 或 6×7。当符号是一个字母时，参数被括在括号中，如 f(x)。函数由 f 表示，参数由 x 表示。如果有多个参数，则用逗号分隔，如 f(a，b，c)。一些关于计算机语言的书籍区分参数和参数，但这在这里并不重要。

3.3 布尔运算符

正如加法、减法、乘法等函数对数字进行操作一样，当位表示真值时，有几个函数对位进行操作。这些函数被称为逻辑运算符，或者为了英国数学家乔治·布尔而称之为布尔运算符。

如果 A 和 B 是真值，则逻辑函数not，and，or和xor定义如下：

not A 如果 A 为假，则为真，如果 A 为真，则为假。

如果 A 和 B 都为真，则 A and B 为真，否则为假。

如果 A 或 B 或两者都为真，则 A or B 为真，否则为假。

如果 A 或 B 中只有一个为真，则 A xor B 为真，否则为假。

换句话说，如果 A 为真且 B 为假，或者如果 B 为真且 A 为假，则 A xor B 为真。xor被称为异或运算符。它通常用符号⊕表示，里面有一个带加号的圆圈。and和or运算符通常用符号∧和∨表示。很容易记住哪个是哪个，因为and的符号∧看起来像一个没有横杠的大写 A。

这里是四个布尔函数的值的表格形式：

这四个运算符可以通过对应的位对操作来将单个位扩展为位字符串。如果 A 是 0011，表示逻辑值为 false,false,true,true，如果 B 是 0101，表示逻辑值为 false,true,false,true，则应用四个布尔运算符得到

异或运算符在密码学中被广泛使用。例如，一次性密码本的简单实现（见第十四章）是将消息的字节与密钥流的字节进行异或运算，如下所示：

3.4 数字进位制

在普通算术中，数字用十进制表示。这种表示法是印度人和阿拉伯人在 5 至 7 世纪之间发明的。因此十进制数字也称为阿拉伯数字。这个系统由比萨的列奥纳多（列奥纳多·皮萨诺）引入欧洲，他在他那个时代被称为斐波那契。

历史趣闻

在莱昂纳多的时代，大约 1175-1250 年，滑动块拼图是风靡一时的。 （有些人认为这个谜题与据说是由诺伊斯·查普曼（Noyes Chapman）于 1874 年发明的十五拼图相同。）公开竞赛并奖金丰厚。莱昂纳多在这个谜题上是一个天才。他每次都赢。他的竞争对手给了他一个嘲笑的名字“斐波那契”，意思是“笨蛋”，莱昂纳多接受了这个名字。斐波那契在整个意大利都出名了。当斐波那契在 1202 年写了他的*《计算之书》（Liber Abaci）时，他想让人们知道其作者是著名的斐波那契。直接说出这样的话会显得自夸和不体面，所以在封面上他写着Filius Bonacci*，这可以理解为“幸运之子”或“Bonacci 之子”。

后来的作者没有理解这个意图，并拒绝认为伟大的莱昂纳多·皮萨诺应该被称为“笨蛋”。他们猜测莱昂纳多的姓可能是 Bonacci。出于同样的原因，为了提醒他的读者他是著名的斐波那契，莱昂纳多在他的私人文集中有时会狡猾地称自己为莱昂纳多·博纳奇（Lucky Leonardo）。

随着时间的推移，人们忘记了数学谜题天才斐波那契的名字和声誉，直到 1836 年，当书籍爱好者和臭名昭著的书籍盗窃犯古古列尔莫·利布里（Guglielmo Libri）将碎片拼凑在一起，并领悟到Filius + Bonacci = Fibonacci。术语斐波那契数和斐波那契数列是由法国数学家爱德华·卢卡斯（Edouard Lucas）于 1870 年左右创造的。

好的，回到工作上。为了解释十进制数，我们使用指数表示法。指数意味着一个数字乘以自身指定的次数。例如，5³表示 5 乘以自身 3 次，即 5×5×5，等于 125。在指数表达式 B^E 中，读作“B 的 E 次方”，或简称“B 的 E 次方”，B 称为底数，E 称为指数。如果 N 是任何数字，则 N¹是 N 本身。按照惯例，除了 0 之外的任何数字 N⁰均为 1。术语 0⁰没有定义的值，因为对 0⁰进行不同的计算会得到不同的结果。

当我们写一个十进制或者十进制，即底数为 10 的数，比如 3456 时，它表示 3×1000+4×100+5×10+6×1。使用指数表示法，这等同于 3×10³+4×10²+5×10¹+6×10⁰。从右边开始，低位数字，即此处的 6，乘以 1，下一个数字，即 5，乘以 10，接下来的数字分别乘以 10²，然后是 10³，依此类推。如果有 50 位数，左边的高位数字将乘以 10⁴⁹。

在其他数制中也是一样的。例如，二进制系统使用基数 2。二进制数 11001 被计算为 1×2⁴+1×2³+0×2²+0×2¹+1×2⁰，即 16+8+0+0+1，等于 25。计算机工作中常用的一种数制是十六进制，或基数 16。十六进制中使用的数字是 0123456789ABCDEF，或 0123456789abcdef。我更喜欢使用大写字母 ABCDEF，因为这样所有的十六进制数字高度都一样，更容易阅读。十六进制数 9AB 被计算为 9×16²+10×16¹+11×16⁰，即 9×256+10×16+11，等于十进制表示的 2475。

数制在密码学中的一个用途是将文本转换为数字。将字母表的 26 个字母与 26 进制的数字自然地关联起来，如下所示：

单词WORK可以表示为数字 22×26³+14×26²+17×26+10，即 396,588。这个值可以像任何数字一样进行操作，例如加法、减法或乘法。

大数可以用指数表示法，也称为科学表示法，例如：1.23×10⁷。这是 1.23 与 10⁷的乘积，即 10,000,000，所以 1.23×10⁷是 12,300,000。这与将 1.23 移动小数点 7 位的操作相同。

3.5 素数

数字，特别是大于 1 的整数，被分类为素数或合数。如果一个数是两个较小的正整数的乘积，则称为合数；否则它是素数。最初的几个合数是 4 = 2×2，6 = 2×3，8 = 2×4 和 9 = 3×3。最初的几个素数是 2、3、5、7 和 11。数 1 既不是素数也不是合数。

素数的一个重要性质是任何数都可以唯一地写成素数的乘积（除了因子的顺序）。例如，由于 30 = 2×3×5，除了 2、3 或 5 之外的素数都不能整除 30。这里的 2、3 和 5 被称为 30 的素数因子。任何整数的素数因子集合是唯一的。确定整数的素数因子称为因数分解或因式分解。

如果两个整数 A 和 B 没有共同的素数因子，则它们被称为互质或互素。例如，20 和 27 是互质的。如果 N 是一个整数，则 N 和 1 总是互质，而 N 和 0 只有当 N = 1 时互质。N 和 N+1 总是互质。

使用正整数时，当任何数 A 被另一个称为除数的数 B 除时，结果是一个商和一个余数。称商为 Q，余数为 R。然后 Q 被定义为最大的整数，使得 QB 不超过 A。余数指示剩余的量，即 R = A-QB。注意 0 ≤ R < N。例如，假设 A 是 40，B 是 11。不超过 40 的 11 的最大倍数是 33，因此商是 3，因为 3×11 = 33。余数是 7，因为 40-33 = 7。

3.6 模算术

残余的研究被称为模运算。模运算由哥廷根大学的数学家卡尔·弗里德里希·高斯于 1801 年引入。在模运算中，商被忽略，除数称为模数，余数称为剩余。在前面的例子中，模数是 11，剩余是 7。如果模数是 N，而两个数字 X 和 Y 有相同的剩余，我们说 X 和 Y 在模 N 下是同余的，或者等价地说，X 和 Y 在模 N 下属于同一个剩余类。这表示为 X≡Y (mod N)。例如，40≡7 (mod 11)，因此 40 和 7 在模 11 下属于同一个剩余类。只要 X-Y 是 N 的倍数，或者等价地，只要 X = Y+aN 对某个整数 a 成立，X 和 Y 就在模 N 下是同余的。

剩余类遵循与普通整数相同的算术规则，例如

我们将-a 称为a 的加法逆元。记号 a-b 可以被看作 a+(-b)的简写。

乘法逆元的情况更为复杂。同余方程 ax≡b (mod N)有 3 种情况需要考虑：(1) 当 a 和 N 互质时，(2) 当 a 和 N 有一个不整除 b 的公因数 d 时，以及(3) 当 a、b 和 N 都能被公因数 d 整除时。

1. 假设 a 和 N 互素。那么存在唯一的剩余 a’，它是模 N 的乘法逆元，使得 aa’≡1 (mod N)且 a’a≡1 (mod N)。如果 a’存在，那么同余方程 ax≡b (mod N)可以轻松求解为 x≡a’b (mod N)。在第 15.3.2 节中，我介绍了当 N 很大时计算 a’的高效方法。

2. 如果 a 和 N 有一个大于 1 的公因数 d，则 a 在模 N 下没有乘法逆元。就是说不存在一个 a’使得 aa’≡1 (mod N)。如果 b 不能被 d 整除，则同余方程 ax≡b (mod N)没有解。例如，4x≡5 (mod 12)没有解。

3. 假设 d 是 a 和 N 的最大公约数，记为 gcd(a,N)。也就是说，d 是能够同时整除 a 和 N 的最大整数。如果 a、b 和 N 都能被 d 整除，则可以通过将 a、b 和 N 除以 d 来简化同余方程，即(a/d)x≡(b/d) (mod N/d)。

让我们看一个例子。考虑同余方程 8x≡4 (mod 12)。通过除以 4 得到简化的同余方程 2x≡1 (mod 3)。这个同余方程的解为 x≡2 (mod 3)，意味着 x 可以是任何形式为 3n+2 的整数。回到原始同余方程，x 是模 12 的一个剩余，因此 x 必须在 0 到 11 的范围内。落在此范围内的形式为 3n+2 的数字是 2、5、8 和 11。这意味着 x 可以有值 2、5、8 或 11。因此，同余方程 8x≡4 (mod 12)有 4 个解。

在本书的后文中，mod被用作算术运算符。表达式 x mod y，其中 x 是整数，y 是正整数，表示 x 除以 y 的余数。因此 27 mod 3 是 0，27 mod 4 是 3，27 mod 5 是 2。

第四章：密码学家的工具箱

本章涵盖

• 用于密码的评级系统

• 替换密码

• 置换密码

• 分数化，将字母分解为更小的单元

• 伪随机数生成器

秘钥密码是由几个基本元素构建的。您可以将这些视为行业工具。要构建一个强大的密码，您希望在工具箱中拥有所有这些工具。这并不意味着您应该在每个密码中使用每个元素。这可能会导致过度复杂化而没有安全性的改善。您的密码会变得更慢，但没有任何额外的好处。本章涵盖了替换、置换、分数化和随机数等工具。我在第十章介绍了其他工具，如文本压缩，第十一章介绍了块链。

在讨论元素之前，让我们谈谈强度。密码的强度以比特为单位衡量。每个比特代表一个二进制选择。如果有一个密码，每个密文只能代表两种可能的明文之一，那么该密码的强度将为 1 比特。例如，

0 = 我们输了。

1 = 我们赢了。

密钥的大小是确定密码强度的限制因素。如果一个密码使用 64 位密钥，那么它的强度最多可以达到 64 位，但如果密码弱，则强度可能会更低。

4.1 评级系统

为了让您对本书中描述的密码的强度有一个大致了解，我使用了一个从一到十的评级标准。这些是我个人的评级，基于我的经验和我对使用我所知道的最佳技术来破解密码所需的努力以及密码之间以及与历史密码的比较，无论是实际上被破解还是未被破解。我在每个评级前面的部分中给出了大部分分析：

• One 表示一个初学者可以仅使用纸和铅笔以及适度的努力来破解的密码。

• Two 表示一个经验丰富的业余爱好者可以仅使用纸和铅笔破解的密码。

• Three 是一个熟练的业余密码学家可以用手工方法破解的密码。

• Four 或 Five 意味着需要计算机、训练有素的密码学家或两者兼而有之。

• 从六到九表示专家对手需要多少计算能力。

• Ten 表示一个密码可以抵抗拥有大量训练有素的密码学家和当今最大超级计算机的国家加密机构。

有时我会超出这个范围。零表示该密码可以在不需要纸和铅笔的情况下理解，例如 Pig Latin 或 GNITIRW EHT SDROW SDRAWKCAB。十一的评级意味着该密码将能够抵御未来潜在的比我们目前构想的量子计算机或超级计算机更强大得多的超级计算机。

通过查看我对不同密码的评价，您可以了解如何评价您在其他地方看到的或您自己可能发明的密码的要点。每个评分只是一个估计，而不是强度的保证。保证来自于执行第十二章中描述的分析。

4.2 替代

密码学家工具箱中的第一个工具是替代。在文本中，一个单位被另一个单位替换。明文单位可以是单个字母、字母对或更长的块。密文单位可以是字母、字母块、数字块或字母数字组合。当所有单位都是单个字母时，该密码称为简单替换或单字母替代。在计算机密码学中，单位可以是位、字节或任意长度的位或字节块。本节给出了一个快速的预览。在第 5 和第六章中有一个全面的讨论。

已知的最古老的替代密码之一是凯撒密码，由尤利乌斯·凯撒使用并可能发明，其中字母表中的每个字母都被替换为后面第 3 个位置的字母。在现代使用中，这个数字可能是之前或之后的任何固定数字。凯撒密码被评为 One。

并非所有明文单位都要求具有相同的长度。假设密码采用字母表的字母并替换为 2 位数字对。字母表只有 26 个字母，但是 100 个可能的数字对。这意味着密码学家可以使用其他 74 对数字来进行其他用途。一个已经使用了数百年的方法是提供常见字母对的替代，例如 TH、ER、ON、AS 和 NT，以及可能的短词，如 THE 和 AND，除了单个字母。然后，明文单位将是 1、2 或 3 个字母长。这使得数字对的频率更加均匀。由于字母频率的差异可以用于解密密码，使频率更加均匀可以使密码更加强大。

另一种方法是使用额外的对提供某些常见字母的附加替代。这称为同音替代。例如，您可以为 E 提供 10 个替代品，为 T 提供 8 个替代品，依此类推。给定字母的多个替代称为同音字。这类似于同音字 F 和 PH 在英语中代表相同的音素的方式。提供多个替代品使得 100 个数字对的频率更加均匀。当然，字母对和同音替代两种方法可以结合起来，以获得更加均匀的数字对频率。换句话说，这些方法防止对手使用频率分析。

4.2.1 霍夫曼编码

在计算机环境中，密文单元可以是比特串。 一个很好的例子是哈夫曼编码，由 David A. Huffman 在 1952 年在麻省理工学院时开发。 我不会涵盖优化代码集的方法，我只会给出一般概念，作为可变长度二进制代码的示例。 在哈夫曼编码中，最常见的字母获得短代码，而较少见的字母获得长代码，基于底层字母频率表。 因此，需要更少的位来表达消息。 这被称为文本压缩。 在第 10.7 节中甚至有更强大的文本压缩方法。

英语中最常见的字母是 E 和 T，每个字母大约出现 1/8 的时间。 由于 8 = 2³，我们使用 3 位来表示 E 和 T。 我们可以任意选择任何 3 位值，比如 E = 100 和 T = 111。 我称这种方法为混合哈夫曼。 接下来最常见的是 A，O，I，N，S，R，H。 每个字母大约每 16 次出现一次，因此我们为每个字母使用 4 位。 我们可以使用任何 4 位代码，除了以 100 或 111 开头的代码，因为这些代码已经被使用。 下一组字母是 D，L，U，C，M，F，Y，每个字母大约每 32 次出现一次，因此需要 5 位代码。 依此类推。

这是我根据 15 万个英文文本字母计数创建的一组混合哈夫曼代码。 其他语言有所不同。 哈夫曼代码具有前缀属性，即没有代码是任何更长代码的前缀。 例如，如果 ABCD 是一个代码，那么对于任何二进制数字 A，B，C，D，E，ABCD 都不能是代码。 前缀属性最早由数学家埃米尔·莱昂·波斯特在 1920 年描述。

使用这些代码组，单词 STYLE 将被编码为0110 111 11011 01000 100。 将这些重新编写为 4 位组得到0110 1111 1011 0100 0100，这是十六进制6FB44。

尽管对于艾米莉，桑德拉的敌人，来说，要识别密文中每个字母的代码组几乎是不可能的，但艾米莉可以搜索更长的重复比特串。 这些将代表常见的字母对，称为双字母组，字母三元组，称为三字母组，或单词。 例如，任何给定的 10 位比特串应该大约每 2¹⁰，或 1024 次出现一次。 如果一个 10 位比特串在 1024 个字符串中出现 20 次或更多次，那么它几乎肯定代表单词 THE，这是英语中最常见的单词。 如果你在文本中识别出单词 THE，那么你可以寻找类似 THERE 或 THESE 的扩展，因为 E 的重复很容易发现。 混合哈夫曼评为三级。

4.3 转位

第二个主要的加密工具是转位，改变消息中字符的顺序。 最简单的方法是路由转位。 消息的字母按一定顺序写入���格中，然后按不同的顺序读取。 本节只是一个快速的概述。 全面讨论在第七章中。

例如，消息 THERE IS NO LOVE AMONG THIEVES，有 25 个字母，从左到右跨行写入到这个 5×5 网格中，并且从上到下跨列读出。在这个网格中，从上到下读取时，最左边的一列是TIOOI。

将字母写入网格和从网格中读出字母的常见路径包括直接穿过行，要么向左要么向右，直接向上或向下列，交替向左和向右穿过行，交替向上和向下列，对角线从任何角开始，交替方向对角线，或者顺时针或逆时针螺旋，要么向内要么向外。路由置换密码评定为 One。

4.4 分数化

分数化是将字符分割成较小单位。我们已经看到一种方式，将字符表示为二进制数。该二进制数的每一位可以作为一个单独的单位进行操作，替换或转置。本节介绍了分数化。第九章和第十章有详细讨论。

表示字母为两位数字的古典方式是Polybius Square，由希腊历史学家波利比乌斯在公元前二世纪发明。这是一个使用关键字 SAMPLE 的 5×5 方格。请注意，字母 I 和 J 共享一个单元格，以便将 26 个字母的字母表适合到 25 个单元格的网格中。

由于 A 在第 2 行第 3 列，它由 23 表示。B 是 33，C 是 34，依此类推，通过 Z 由 21 表示。I 和 J 都由 44 表示。然后可以以各种方式进行替换、转置和重新分组这些数字。可以使用这个网格或另一个按不同混合顺序排列的 Polybius 方格将数字对转换为字母。

现代版本将每个字符替换为其 ASCII 或 UTF-8 代码中的十六进制表示。因此 A = 41，B = 42，C = 43，一直到 Z = 5A。这些十六进制数字可以类似地被替换、转置、重新分组并重新转换为字节。

一个有趣的例子是M. E. Ohaver在 1910 年发明的分数化摩尔斯。Ohaver 总是使用 M.E.，因为他不喜欢自己的名字，这个名字是 Merle。

历史注解

在克雷格·鲍尔的《秘密历史：密码学故事》第 241 页的脚注中提到，M.E. Ohaver 是多产的低俗小说作家肯德尔·福斯特·克罗森的化名之一。这是不正确的。克罗森有时使用希伯来语的 mechaber，מחבר，意思是 作者，的化名 M.E. Chaber。

在分数化摩尔斯中，字母按固定大小的组，比如 7，被替换为它们的摩尔斯代码等效项，使用/作为字母分隔符。然后，代码组的长度被反转，调整大小后的组被转换回字母。

摩尔斯电码是由阿尔弗雷德·维尔于 1840 年发明的，以他的雇主塞缪尔·F·B·摩尔斯的名字命名。

这种密码有几个明显的弱点。因为它使用标准的摩尔斯字母表，所以唯一的密钥是字母组的长度，这只需要几次尝试就能猜到。明文字母经常被它们自己替换。有 30 个不同的摩尔斯代码组，但只有 26 个字母，所以需要 4 个额外的字符。奥哈弗使用了日耳曼语的ä、ë、ö和ü。分数化摩尔斯评级为一级。

这些问题可以通过两个变化来部分修复：(1) 仅使用长度为 1、3 和 4 的摩尔斯组。有 26 个这样的组，完全符合 26 个字母的字母表。(2) 打乱字母表的顺序，或者等价地打乱摩尔斯代码组的顺序。我称这个增强版为FR-Actionated Morse。例如，使用关键词 MIXEDALPHBT 来混合字母表，摩尔斯组按标准顺序排列，你会得到

即使有了这些改进，FR-Actionated Morse 的评级仍然只有二级。

4.5 随机数生成器

随机数生成器可以是任何在给定范围内产生数字序列的东西。数字可以是单个位、8 位字节、十进制数字，或者是任何其他所需范围内的数字。例如，范围在 0 到 25 之间的数字，对应于 26 个字母表中的字母，对某些加密目的是有用的。本节介绍了该主题。完整的讨论在第十三章中。

重要的是要认识到“随机数”这种东西是不存在的。你不能说 51 是一个随机数，而 52 不是，反之亦然。但是，你可以说序列 51，52，53，54，…不是随机的。那个序列是完全可预测的。随机性是序列或生成器的属性，而不是序列中的个别数字的属性。说“一系列随机数”比说“随机数序列”更准确。

生成器可能是一种物理过程，比如宇宙射线、盖革计数器的嗒嗒声、计算机按键的精确时间、风中飘扬的旗帜、海浪拍打的水花或者人们赶着赶火车的景象。大多数物理来源都不够快以用于加密目的，但数字序列可能会被存储在计算机文件中以供日后使用。

生成器也可以是一个数学函数或计算机程序，在每次调用时产生一个数字。由数学算法产生的随机数被称为伪随机数，以区别于真随机数。它们被认为比真随机数弱，因为确定随机序列的一部分的对手可能能够计算出前后的数字，从而读取消息。真随机数永远不能由数学函数产生。在第 13.8 节中，我展示了生成密码安全的伪随机数序列的方法，设计用于防止对手扩展序列的部分。

伪随机序列和真随机序列之间的一个关键区别是，伪随机序列最终会重复，而真随机序列永远不会重复。序列在重复之前的项数称为其周期。例如，序列 3,1,9,2,4,3,1,9,2,4,3,1,9,2,4,…的周期为 5，以下划线标出。一般来说，周期越长，密码越强。

仅仅因为一串数字是随机的，并不意味着这些数字是等概率的。例如，假设你观察到穿过繁忙桥梁的汽车的颜色。颜色是随机的，但某些颜色比其他颜色更常见。白色、黑色、银色和红色比橙色、紫红色或嫩黄色要常见得多。同样，在 crap 游戏中，如果骰子是公平的，那么每次掷骰子都是随机的，然而掷出 7 的可能性是掷出 12 的六倍。

在第 13.14.1 节和第 13.14.2 节中，我讨论了如何“收获”这种序列中的随机性，以获得数字具有基本相等概率的序列。从现在开始，我将假定任何随机数生成器都产生具有相等概率的数字。这被称为均匀分布或等概率分布。通过一个良好的随机数生成器，生成的数字对、三元组等也将具有均匀的概率，甚至可能达到八元组或更多。

4.5.1 链数字生成器

让我用纸和铅笔轻松完成的样本伪随机数生成器来结束这一节。不需要电脑。我们将其称为链数字生成器。首先写下任意 7 位的十进制数。这 7 位数字称为种子，或初始值，或初始化向量。它们可以被视为任何使用此生成器的密码的密钥，或密钥的一部分。要获得第一个伪随机数字，只需将第一个数字和最后一个数字相加。将这个新数字添加到序列中，并将第一个数字涂黑。所以，从 3920516 开始，我们将 3+6 加起来得到 9。

任何时候，如果总和超过 9，我们就去掉十位数。也就是说，加法是模 10 的。这有时被称为不进位加法。要获得第二个伪随机数字，我们重复这个过程。这里 9+9 得到 18。我们去掉十位数得到 8。

这个过程可以重复，以获得所需的伪随机十进制数字。

结果得到的伪随机序列是9800562199940232…。

注意，如果种子中的所有数字都是偶数，则生成的所有数字都将是偶数。同样，如果所有数字都可被 5 整除，即为 0 或 5，则生成的所有数字都将是 5 的倍数。在这种情况下，周期最多只能为 128，因为种子中有 7 个数字，而且只有 2⁷ = 128 种 0 和 5 的组合。由于这种种子无法产生长周期，因此它们被称为不合格的。对于链式数字生成器，合格的种子必须至少包含一个奇数数字和一个不是 5 的倍数的数字。例如，2222225 是合格的种子，但 2222222 和 5555555 不合格。使用合格的 7 位数字种子，周期将始终为 2,480,437。

这个生成器具有自制伪随机数生成器的典型行为。有 10⁷个可能的 7 位数字种子。如果你从任意种子开始，生成器将循环一些数字序列，直到再次产生该种子，因此 7 位数字的集合被分割成几个离散的周期，每个周期都有自己的周期。如果选择一个合格的种子，那么周期将始终具有最大可能的 2,480,437 个数字的周期。这种长度有 4 个单独的周期，再加上一些由不合格种子产生的远比这个短的周期。

对于其他大小的种子，行为类似。即使最大周期非常短，也经常有很高的概率获得最大周期，因为可能有许多最大周期。此表显示使用合格种子获得给定长度周期的概率：

数字	周期	概率
4	1,560	100%
5	168	86.7%
6	196,812	99.974%
7	2,480,437	100%
8	15,624	98.817%
9	28,515,260	79.999%
至少 2,851,526	99.9988%
10	1,736,327,236	86.9%
至少 248,046,748	99.31%
至少 13,671,868	100%

表格显示，5 位和 8 位数字种子长度不安全。它们产生了大量非常短的周期。7 位和 10 位数字种子长度最好，因为你总是保证有一个长周期。

这个随机数生成器严格来说只是一个演示模型，只是展示了使用简单手工方法可以实现什么。它不适用于高安全性工作。

4.6 有用的组合，浪费的组合

本章的 4 种基本技术可以以无数种方式组合，我将在本书的剩余部分中进行探讨。然而，首先要认识到并非每种组合都是有益的。一些组合会增加工作量而不增加强度。

考虑一种一些初学者尝试的想法。他们对一条消息进行简单替换，然后对结果文本进行第二次简单替换，然后第三次，依此类推，进行 5、10，甚至 100 轮。这是一种浪费精力的做法。进行两次简单替换与进行一次相同，但使用不同的混合字母表，因此进行多次简单替换不会增加任何强度。这里有一个例证。两次替换使用了关键字 FIRST 和 SECOND。第三次替换等同于先进行第一次替换，然后进行第二次替换。

让我们来看一个例子。如果我们使用第一个替换对EXAMPLE进行加密，结果是IUXEJDI。如果IUXEJDI使用第二个替换进行加密，结果是CLQYOXC。你可以自行验证，使用等效替换对EXAMPLE进行加密会得到CLQYOXC。

进行一次加密，然后再进行第二次加密被称为组合这两次加密。前面的例子表明，组合两个简单的替换只会产生另一个简单的替换。如果第一个加密使用了代码，那么在代码后面跟着一个密码被称为超加密。最常见的超加密形式是非进位加法，或者模 10 加法，其工作原理如下：

4.6.1 巴泽里 4 型密码

让我们看看相反的情况。让我们看一个使用替换步骤后跟着一个非常简单的置换产生了更强大密码的密码。

这种密码是由才华横溢、易怒且辱骂性的法国密码学家埃蒂安·巴泽里于 1898 年提出的。我不知道巴泽里给这种密码起了什么名字。我称之为Bazeries Type 4，因为这是他在 1890 年代向外交密码局提出的 4 种密码中的最后一种。这种密码可以很容易地手工完成。

巴泽里 4 型密码由一个简单的替换后跟着一个简单的置换组成，我称之为逐段反转。置换根据一个由小整数序列组成的密钥，对文本的短片段进行反转。这里有一个使用关键字 BAZERIS 混合替换字母表，以及关键字 4,2,3 进行置换的示例。

这种置换可以用来加强许多不同类型的密码，因此它值得拥有自己的名称。让我们称之为逐段反转。你可以通过混合一些正常顺序的文本段来加强这种置换，也许可以使用数值密钥中的负数。这里有一个使用数值密钥 3, 4, -3, 2 的示例。请注意，这个密钥等同于 3, 4, 1, 1, 1, 2。

密码学家们在密码局无法解决巴泽里斯提供的任何样本消息。尽管付出了相当大的努力，这些消息仍然在 40 年内未解决，直到著名建筑师和业余密码学家罗萨里奥·卡德拉解决了它们，并写了一本关于他是如何做到的书（巴泽里斯指挥官的军事密码，卡尔丹纳斯出版社：纽约，1938 年）。

然而，卡德拉无法直接解密这些消息。相反，他确定并利用了巴泽里斯从密钥生成替换字母表的方式中存在的弱点。如果巴泽里斯使用了更强大的方法来混合密码字母表，卡德拉就无法解密这些消息。因此，使用混合良好的字母表的巴泽里斯 4 型被评为五级。将两种分别评为一级的方法结合起来是相当不错的。

历史小贴士

卡德拉是哥伦比亚建筑学院的毕业生，所以他计划在哥伦比亚大学出版他的书。威廉·F·弗里德曼，当时是美国密码学家的院长，得知此事后，秘密阻止了出版。这再次证明了巴泽里斯 4 型密码的强大。

第五章：替换密码

本章包括

• 简单替换和多字母替换密码

• 使用 Kasiski 检测和重合指数解决多字母替换密码

• 自密钥和流动密钥密码以及解决它们的方法

• 模拟转子密码机

我们现在已经准备好更深入地探讨上一章描述的基本工具。在我开始描述所有不同的密码之前，让我明确陈述一下这些密码试图实现的目标。荷兰语言学家和博学家奥古斯特·克尔克霍夫斯（Auguste Kerckhoffs）首次在 1883 年的《军事科学杂志》上发表了这些原则的一对文章：

1. 即使在理论上不可破解，密码在实践中也应该是无法破解的。

2. 即使敌人了解了系统，这也应该成立。

3. 密钥应该容易记忆（无需笔记）且易于更改。

4. 应该能够通过电报传输加密的消息。

5. 仪器和文件应该方便一个人携带和操作。

6. 密码应该易于使用；不应有复杂的规则或计算。

规则 4 可能会更新为“数字方式传输加密的消息”。否则，这些原则今天仍然像 1883 年一样有效。

第二个原则的一个推论是，密码的强度应该完全取决于密钥。克尔克霍夫斯还相信只有密码学家有资格评判密码的安全性。太多时候，选择使用哪种密码的决定是由缺乏密码学专业知识的政府官员做出的，有时会造成灾难性的后果。

5.1 简单替换

简单 替换，也称为单字母替换，是你在报纸和杂志的谜题部分看到的熟悉类型的密码。在简单替换中，消息中的每个字母都被另一个字母一致且均匀地替换。因此，如果字母 M 在一个地方被 T 替换，那么消息中的每个 M 都将被 T 替换，而密码文中的每个 T 将表示一个 M。

由于大多数人熟悉解决简单替换密码的技巧，我只会简单提一下：字母频率、首字母频率、末字母频率、双字母频率、字母对频率、短单词、常见前缀和后缀、元音和辅音的分布、模式单词以及利用标点符号。

对于报纸中的简单密码，通常只需要查看短单词。如果你发现 AB 和 CBA，这些单词可能是 TO 和 NOT，而 AB 和 BAC 最常见是 OF 和 FOR。模式 ABCA 很可能是 THAT，ABCDC 暗示着 THERE，而 ABCDB 可能是 WHICH。如果你在互联网上搜索，你可能会找到出售模式单词列表的网站，或者会根据你提供的模式找到匹配的单词的网站。

对于更难的密码，像 FOXY PIXY MANX AXED TOXIC LUXURY ONYX SPHINX 这样的文本，需要更有组织的方法。

我将使用以下样本密码演示该过程。已知语言为英语。文本有 73 个字母和 11 个单词，平均每个单词长度为 6.64 个字母，而正常的英语为 5.0 个字母。缺少少于 5 个字母的短单词以及缺少模式单词表明这个密码已经被故意构造得很困难。

第一阶段是识别元音和辅音。首先计算每个字母的出现次数以获得频率计数。在样本密码中，A 的字母计数为 0，B 为 3，C 为 3，以此类推。完整的频率计数如下：

注意这里只有两个高频字母，L 和 S，出现的频率分别为 8 和 7。在正常的英文文本中，元音字母占 40%。这个百分比很稳定，即使字母频率被故意操纵也通常保持不变。在这个密码中有 73 个字母，应该有 29 个元音。这几乎要求 L 和 S 都代表元音，除非频率被严重扭曲。

接下来，你需要制作一个联系表格，将字母垂直地列在页面的中心。在密码中出现的每个不同的字母都有自己的行。在每一行上，出现在中心字母之前的每个字母都列在其左侧，而出现在中心字母之后的每个字母都列在其右侧。例如，表格的第一行，EO B DWZ，表示在密码中字母 B 分别被 E 和 O 前导一次，分别被 D、W 和 Z 后导一次。以下是这个密码的完整联系表格（为节省空间显示为 3 列）。

联系表格用于识别元音和辅音。一般来说，元音与左右两侧的字母有广泛的联系，而辅音则往往与有限数量的不同字母有联系。从联系表格中我们可以确定 4 个可能的元音，L、Q、S 和 V，以及 4 个可能的辅音，E、O、R 和 U。让我们用 ° 标记这些元音字母，用 ˟ 标记这些辅音字母，并看看分布是否合理。

在第 3 个单词EYXDO、第 7 个单词KIGXG和第 8 个单词YIWZ中都有 3 个长的没有元音的字母串。这表明I和/或X可能是元音。虽然它们都有很多不同的接触点，但X代表元音的可能性极小，因为那样的话第 11 个单词将以 3 个元音字母开头并以元音结尾。这在英语中很罕见。我找到的唯一例子是 OUIJA。（SQXMV不能是 AIOLI，因为 I 重复了。）因此，I很可能是元音，而X是辅音。

让我们再次尝试区分元音和辅音。在密码中有 5 对暂定元音，VL、VS、VQ、QL和SQ。在英语中，双元音并不常见，因此很可能V或Q实际上是辅音。很可能不是Q，因为那样的话第 10 个单词将以 5 个辅音结尾。我知道的唯一这样的 6 个字母单词是 ANGSTS。

让我们将I作为元音，将V和X作为辅音，看看我们的情况如何。

看起来是正确的。从第 3 个单词中，我们现在可以确定D是元音，从第 11 个单词中，M很可能是元音。现在所有 6 个元音都已找到，所以其他每个字母必须是辅音。以下是辅音和元音的完整分布。

第二阶段是识别单个字母。以下字母接触表显示了英语字母的接触特征。不同的语言会有不同的特征。例如，字母 M、V 和 Z 通常都是前导和后跟元音，而字母 N 通常是前导元音，但后跟辅音。我使用古腾堡计划的英语语料库编制了这个表。

在密码中，有一个很好的 H 明文候选者，即密文U。然而，U在以 US 结尾的双字母组中出现两次，因此这是不太可能的。

在密码中，有两个强有力的 N 候选者，即密文E和O。E和O都代表总是由元音前导和辅音后跟的辅音。然而，O是更强的选择，因为它的频率更高，并且因为它在单词ZLORUS中的两个已知辅音之前。在英语中，3 个辅音组合通常以 N 开头，例如NST和NTH。更有可能O代表 N。这产生了

现在可以尝试找到符合某些模式的可能单词。我找到了 67 个符合ZLORUS ˟°N˟˟°的单词。其中 32 个以 E 结尾，27 个以 Y 结尾。我找到了 37 个符合SQXMV °°˟°˟且不包含 N 的单词。其中 15 个以 Y 开头，但只有 1 个以 E 开头。因此，密文S最有可能代表明文 Y。这给了我们

密文单词 IVQOR 和 ZLORUS 都包含双字母 OR。让我们试着识别一下。知道 IVQOR °˟°N˟ 不含有 Y，剩下的有可能的单词只有 24 个。其中，有 12 个以 G 结尾，有 8 个以 S 结尾，因此密文 OR 可能是 NG 或者 NS。现在，对于 ZLORUS ˟°N˟˟Y 的可能明文单词减少到了 26 个。在这些中，第四个字母是 G 的有 8 次，是 T 的有 6 次，但是只有 1 次是 S。因此，密文 OR 最可能的选择是明文 NG。现在我们有了

对于第一个单词 RULEYS 有 8 种可能性。这些只包含双字母 UL 的 6 种可能性。对于这些选择中的每一个，让我们来看看单词 ZLORUS 的可能性。

选择 ZLORUS = JUNGLY 可以立即被排除，因为 KSYIWZ 将呈现出 ˟Y˟°˟J 的形式。在英语中没有这样的单词。这意味着 RULEYS 表示 GRUMPY，ZLORUS 表示 HUNGRY。填入这些新字母后得到

其余的字母可以凭眼识别填入。现在显然第二个单词是 PUDGY，第三个单词是 BUMPKIN，这使得第八个单词成为 BYPATH，等等。

完成的密码读起来是 GRUMPY PUDGY BUMPKIN CLUMSILY STUMBLED ALONG BACKCOUNTRY BYPATH，HUNGRY UNSHOD YOKEL。

简单替换被评为 One。当字母频率和接触频率被故意扭曲时，就像这个例子一样，评级可以达到 Two 或可能 Three。这是一个很好的谜题，但对于一般通信是无用的。

5.2 混合字母表

简单替换需要一个混合字母表。有几种传统的纸笔方法可以做到这一点。获得混合字母表的一种方法是使用一个关键词。在最简单的情况下，您只需从某个位置开始写入关键词，然后在其后填入剩余的字母，根据需要进行环绕。剩余的字母可以向前或向后填写。以下是三个示例：

这种方法最早由 Argenti 家族使用，他们是约 1600 年教皇和主教的密码秘书。这些字母表混合得不太好。一种稍微好一些的方法是使用两个关键词，就像这样：

列混合

将字母写入一个块中。将关键词写在顶行，其余的字母写在需要的行数中。较长的关键词可以提供更好的混合效果。然后从块中读出字母，沿着列向下读取。在这个例子中，关键词 SAMPLE 已经写在顶行。第一列向下读取是 SBIRY，第二列是 ACJTZ，依此类推。如果愿意，可以交替地沿着列向上和向下读取，或者使用其他路径。

SkipMix

在我上高中的时候，我发明了另一种适合纸笔密码学的方法，我称之为SkipMix。它使用一串称为跳数的小数字作为混合字母表的密钥，例如 3, 1, 4。从标准字母表开始。跳过 3 个字母并取下一个字母，即为 D。

删除该字母，然后跳过 1 个字母并取下一个字母，即为 F。

删除该字母，然后跳过 4 个字母并取下一个字母，即为 K。

然后重复 3,1,4 的循环。跳过 3 个字母并取下一个字母，即为 O。

继续重复键数的循环，直到选择了所有 26 个字母。生成的混合字母表是

SkipMix 可以与关键词一起使用。假设关键词是 SAMPLE。将每个字母替换为它在字母表中的位置，即 19,1,13,16,12,5。可选地，将任何 2 位数替换为其各位数字，即 1,9,1,1,3,1,6,1,2,5。使用这串跳数作为混合密钥。注意，0 是一个有效的值。

SkipMix 非常适合计算机使用。在这种情况下，字母表是 256 个不同的 8 位字符代码。跳数可以是从 0 到 255 的任何整数。数字密钥仍然可以由关键词派生而来。使用关键词而不仅仅是一串整数的优点是人们更容易记住和准确输入。再次假设关键词是 SAMPLE。这些字母在 ASCII 码中的数值等价于 83, 65, 77, 80, 76 和 69。这些值落在从 65 到 90 的窄范围内，这导致混合程度较低。为了将字母代码分散到更广泛的范围内，它们可以乘以某个常数值模 256。乘数可以是介于 7 到 39 之间的任何奇数。例如，关键词 SAMPLE 的 ASCII 码乘以 17 模 256 的结果是 131, 81, 29, 80, 12 和 149。这覆盖了一个范围为 149-12 = 137 的范围，远比原始范围 83-65 = 18 要宽。

跳数仍然只有 26 个可能的值。获得更大的值集合的一种方法是将相邻的数字进行模 256 的乘法。然后，跳数序列为 83×65, 65×77, 77×80, 80×76, 76×69 和 69×83，全部取模 256。因此，83×65 = 5395≡19 (mod 256)。数字密钥变为 19, 141, 16, 192, 124, 95，覆盖了范围 192-16 = 176。

产生更大的跳数集合的另一种方法是将关键词的第一个字母乘以 7，第二个字母乘以 9，第三个字母乘以 11，依此类推，所有乘法都在模 256 下进行。

由于将关键词转换为数字密钥将由计算机而不是人类操作员完成，因此可以使用任意复杂的计算。我建议使用二次函数而不是线性函数，以使对手在获得一些消息的明文后更难推断关键词。例如，如果 N[i]是数字密钥的项，K[i]是关键词中字符的数字值，则一个合适的函数可能是

当下标超过关键词的长度时会循环。例如，如果关键词有 10 个字符，则 K[11]会循环到 K[1]，K[12]会循环到 K[2]，依此类推。

函数 K[i]K[i+1]+K[i+2]K[i+3]的强度不会那么强。如果关键词的长度为 L，则只会有 L 个不同的二次项。艾米莉可以将这些视为 L 个变量，并解出一组 L 个线性方程以找到 L 个乘积 K[1]K[2]，K[2]K[3]，K[3]K[4]，… K[L]K[1]的值。然后很容易找到各个 K[i]的值。*

在本书中，我展示了字母表与简单关键词混合在一起，这样您可以一目了然地看到它们是如何形成的，例如，字母表

样本 BCDFGHIJKNOQRTUVWXYZ

这非常薄弱。实践中不要这样做。我在这里这样做是为了帮助读者。由于您不希望帮助您的对手，始终使用混合良好的字母表，使用列混合、SkipMix 或其他强大的混合功能。有关其他方法，请参见第 12.3.8 节。

5.3 代号书

从 15 世纪到 18 世纪，替代密码的国王是代号书，被国王、教皇、外交官和间谍们广泛使用。每个代号书都有数百甚至数千个项目的列表，单个字母、数字、双字母、音节、单词和名称，为每个提供多达 25 个替代品。代号书更像是代码而不是密码，因此不在本书的范围之内。

5.4 多字母替换

解决简单替换的技术涉及字母频率和字母接触。如果要设计一个密码来抵御这种攻击，一个好的起点是破坏字母频率和字母接触。

假设不是使用相同的字母表对每个字母进行加密，而是使用两个不同的字母表。使用第一个字母表对奇数位置的字母进行加密，并使用第二个字母表对偶数位置的字母进行加密。也就是说，第一个字母表将加密消息中的第一个、第三、第五…个字母，而第二个字母表用于加密第二、第四、第六…个字母。

现在，密文字母的频率一半来自第一个字母表，一半来自第二个字母表。它们是两组频率的平均值。一个密文字母只有在它同时代表两个字母表中的高频字母时才会有高频率。例如，密文K可能代表第一个字母表中的 E，代表第二个字母表中的 A，因此其频率将介于正常文本中 E 的频率和 A 的频率之间。

相反，密文中的一个字母只有在它同时代表两个字母表中的低频字母时才会有低频率，比如第一个字母表中的 K 和第二个字母表中的 V。因此，密文中的高频字母和低频字母会比正常文本少。如果你制作一个字母频率的柱状图，或者直方图，峰值会更低，谷值会更浅。因此，使用两个字母表会使频率计数变得更平坦。

联系频率也会发生同样的情况。任何常见的二字母组合，比如 TH，大约一半时间会在消息中的奇数位置开始，另一半时间会在偶数位置开始。一半时间，T 会与第一个字母表一起加密，而 H 会与第二个字母表一起加密，另一半时间则相反。因此，联系频率也会变得更平坦。

使用的字母表越多，频率就变得越平坦。实际上，从大约美国内战到第一次世界大战期间，使用大约 20 个字母表是很典型的。有一个统计测试可以测量字母频率的平坦度，并使用它来估计字母表的数量，但它不太准确，特别是对于超过 10 个字母表的情况。更好的方法在 5.6 和 5.7 节中描述。

让我们来看看多表密码的历史发展。多表密码的早期形式由利昂·巴蒂斯塔·阿尔贝蒂（Leon Battista Alberti）于 1467 年和约翰内斯·特里西米乌斯（Johannes Trithemius）于 1499 年开发（但直到 1606 年才发表）。多表密码在 1553 年出版的La cifra del Sig. Giovan Battista Belaso一书中开始采用现代形式。

5.5 贝拉索密码

由乔凡·巴蒂斯塔·贝拉索（Giovan Battista Belaso）于 1553 年发明的贝拉索密码使用了 26 个不同的字母表，每个字母表只是标准字母表移位了一定数量的位置。这 26 个密码字母表可以显示为一个表格，其中每个水平行包含一个移位后的字母表，就像这样：

每行的第一个字母标识字母表，所以顶行是 A 字母表，第二行是 B 字母表，依此类推。Belaso 是第一个使用密钥选择消息中哪个字母使用哪个字母表的人。（相比之下，Argenti 家族使用关键字来混合字母表。）Belaso 会水平书写消息。在明文字母的上方，他会重复写入所需次数的密钥。要加密一个字母，他会在表格的顶行找到该字母，使用密钥字母选择表格的行，并将明文字母替换为所选行中直接位于它下面的密文字母。以下是如何使用密钥字母 C 对明文字母 S 进行加密的示例：

我们在表格的顶行找到了字母 S。它的密钥是 C，因此使用表格的第三行进行加密。在第三行，直接在 S 下面，我们找到了字母 U。所以 S 被替换为U。

使用前述表格，使用密钥 CAB 对单词 SAMPLE 进行加密，S 被替换为U。

消息中的下一个字母是 A，使用 A 作为密钥，所以 A 使用顶行进行加密。它被加密成A。样本中的 M 使用密钥 B，它使用第二行加密，变成了N，依此类推。最终的密文是UANRLF。

与使用表格不同，可以使用St. Cyr slide进行加密，该幻灯片以法国圣西尔军校命名。幻灯片在 M 位置显示。

你可以用木头、硬纸板或塑料制作自己的幻灯片。顶部的双宽行固定在原位，而单宽底行滑动。橡皮筋可以使其保持紧绷并处于正确位置。两个字母表中的一个或两个都可以混合。

Belaso 密码是对称的，因为使用密钥 K 加密字母 X 与使用密钥 X 加密字母 K 完全相同。基于将密钥添加到明文或使用异或运算密钥和明文的密码在这个意义上倾向于是对称的。

由于我无法理解的原因，Belaso 密码现在被称为Vigenère Cipher，而由 Blaise de Vigenère 发明的密码，描述在 5.8.2 节中，现在称为Autokey密码。为了给予应有的认可，我将继续称由 Belaso 发明，使用标准字母表的密码为 Belaso 密码。使用混合字母表的密码我将称之为 Vigenère 密码。我将由 Vigenère 发明的自密钥密码称为Vigenère Autokey。

将 Belaso 密码归因于维吉尼亚密码是斯蒂格勒命名法则的一个例子，斯蒂芬·M·斯蒂格勒认为，没有重要的科学发现是以其发现者命名的。一些密码学的例子包括由查尔斯·韦斯顿发明的 Playfair 密码和由阿尔弗雷德·维尔发明的摩尔斯电码。斯蒂格勒法则本身是由罗伯特·K·默顿提出的，他将其命名为马太效应，以纪念圣马太。

5.6 卡西斯基方法

300 多年来，Belaso 密码被认为是无法破解的。法国人称之为Le Chiffre Indéchiffrable，即无法破译的密码。转折点出现在 1863 年，当时普鲁士步兵军官弗里德里希·W·卡西斯基少校出版了一本详细介绍如何确定多表密码周期的书。这就是现在所称的卡西斯基方法或卡西斯基测试。有证据表明查尔斯·巴贝奇可能在 1846 年使用了这种方法，但没有公开发表。丹麦技术大学的奥勒·伊曼纽尔·弗兰克森，他对巴贝奇及其差分机写了大量文章，写了一本名为巴贝奇先生的秘密的书，提出了这一说法。

这个想法是在密文中寻找重复的字母序列。一些序列可能是偶然发生的，尤其是双字母组，但大多数重复序列将是由明文中相同字母被密钥的相同部分加密产生的。重复序列越长，发生偶然性的概率就越低。如果同一密钥部分用于加密两个重复的字母序列，那么它们之间的距离必须是密钥长度的倍数。距离是从一个出现的第一个字符到另一个出现的第一个字符的距离。考虑使用关键词 EXAMPLE 的密码片段。

密文三字母组PTR出现了 3 次，分别在位置 5、12 和 33。所有这三次出现都是由明文 AIN 用密钥字符 PLE 加密产生的。也就是说，它们都是由相同的明文三字母组用密钥的相同部分加密产生的。

明文三字母组 AIN，从位置 21 开始，产生了不同的密文三字母组EMK，因为它是由不同部分的密钥 EEX 加密的。同样，明文三字母组 THE，在位置 1 和 29 出现，以及明文三字母组 INS，在位置 8 和 13 出现，不会产生重复的密文三字母组，因为它们是用密钥的不同部分加密的。

在这个片段中，重复的三字母组之间的距离为 12-5 = 7，33-5 = 28 和 33-12 = 21。这些距离，7、21 和 28，都是 7 的倍数，而 7 是关键词 EXAMPLE 的长度。卡西斯基展示了如何利用这些重复来揭示加密的周期。

让我们看另一个例子，一个密码。

这是一段普通英语文本的贝拉索加密。在搜索重复的字母序列时，我们发现EK位于位置 10、64 和 90，RYR位于位置 17 和 53，等等。重复字母序列的完整列表是：

我们立即注意到两个重复的四元组YHCI和YXYR。重复的四元组几乎不会出现偶然。两个YHCI出现之间的距离是 79-43 = 36，而两个YXYR出现之间的距离是 69-57 = 12。距离 12 和 36 暗示着密钥长度为 4、6 或 12。我们可以通过查看一些其他重复序列来缩小范围。

RYR的距离为 36，ZHZ的距离为 6。另外两个重复的三元组HCI和XYR只是两个重复的四元组YHCI和YXYR的一部分，所以它们不提供额外的信息。这个密码的最可能周期是 6。

好吧，这太容易了。让我们看看在更困难的情况下会发生什么。其他书籍推荐的一种方法是取所有重复序列之间的距离，并找出它们的所有因数。他们声称，最频繁的因子将是周期。例如，如果距离是 36，那么因子是 1、2、3、4、6、9、12、18 和 36。这可能会以几种方式误导你。

首先，你可能会错误地得出周期是其实际值的两倍。这是因为大约一半的距离仅仅是偶然的。有效距离的一半，即由重复的明文序列引起的距离，将是周期的偶数倍。对于某些消息来说，这些周期的偶数倍将超过那些周期的奇数倍的距离。同样，一半的偶然重复的密文序列将有偶数的距离。可能会出现许多偶然的距离。同样，1/3 的距离会偶然成为 3 的倍数。

当你计算距离的因数数量时，你应该将因子 2 出现的次数减少 1/2，将因子 3 出现的次数减少 1/3，依此类推。这样会给你一个更准确的比较。例如，如果距离 3 出现了 6 次，那么将其减少 1/3 到 4 次，因为这 6 次中有 2 次很可能是纯粹的偶然。

第二，当重复的序列出现多次时，这些重复之间的距离可能会误导人。如果有 N 个重复，则对这些重复的成对数量为 N(N-1)/2。在示例密文中，有 4 个YR的出现，因此有 6 对，即 4×3/2 对。因此，有 6 个成对的距离，54-18 = 36，59-18 = 41，71-18 = 53，59-54 = 5，71-54 = 17 和 71-59 = 12。这些中的哪一个，如果有的话，是周期的倍数？假设密文XYZ出现了 5 次，其中有 3 次重复是由相同的明文造成的。将会有 10 个距离，其中只有 3 个是由重复的明文造成的，而其他 7 个是虚假的。

你不想因为无法区分有效重复和偶然重复而将其抛弃。你可以做以下事情。假设你有一个周期候选者。例如，假设你怀疑周期是 6。将重复序列出现的位置减去 6 的模数。（还记得模数算术吗？如果不记得，再看一下第 3.5 节。）

让我们尝试一下模数法。再次看看YR的 4 次出现，并将它们的位置减去 5、减去 6 和减去 7，看看会发生什么。

所有 4 个模 7 余数都不同。如果周期是 7，那么YR的所有重复都是偶然的。模 5 余数只有 2 个相等。如果周期是 5，那么 4 次出现中只有 2 次来自重复的明文。但是如果周期是 6，那么我们现在看到YR的 4 次出现来自明文中的 2 个不同的重复双字母组，一个双字母组在明文的位置 18 和 54 处，距离为 36，另一个双字母组在明文的位置 59 和 71 处，距离为 12。

那是怎么发生的？回顾一下重复序列的列表。你可以看到重复的双字母组YR在重复的三字母组RYR和重复的四字母组YXYR中出现。每个重复都贡献了一个重复。

让我们看看第二种确定多表密码周期的方法。如果重复序列的证据不足以得出结论，那么有备用计划是很好的。

5.7 巧合指数

巧合指数由美国密码分析专家威廉·F·弗里德曼于 1922 年发明。这个想法非常简单，但其重要性深远。想象一下，使用多表密码编写了两条消息，但使用了不同的密钥，可能还有不同的周期。如果逐字比较两个密文，两个对应字母相同的概率是 26 分之 1，约为 0.0385。如果两条消息都是 52 个字符长，你期望有 52/26=2 对相应字母相等。在这里，我使用密钥分别为火星和金星的 Belaso 密码编写了 52 字母的明文“春日少年的幻想变成了棒球”。两个相同的字母已经被突出显示。（两对相同字母都是 F 纯属偶然。）

现在想象一下两条消息被同一个密钥加密。每对相应的字母都被相同的密钥字符加密，所以如果明文字母相同，那么密文字母也将相同。A 的频率约为 0.08，所以明文字母都是 A 的概率为 0.08²，约为 0.0064。它们都是 B 的概率约为 0.015² = 0.000225，依此类推通过字母表。所有 26 个字母的总和约为 0.0645 到 0.0675，约为 1/15，取决于你使用的字母频率表。当使用相同密钥时，两个相应的密码文字母相等的机会大约是 1/15，比不同密钥时的 1/26 机会高出约 73%。

这个事实可以被利用来确定多表密码的密钥长度。让我们给密文中的字符编号为 C[1]、C[2]、C[3]，…，并且让密钥的长度为 L。我们可以将密文中的字符与同一字符移动了一定数量的位置后的字符进行比较，比如移动了 S 个位置。也就是说，我们将 C[1] 与 C[1+S]、C[2] 与 C[2+S]、C[3] 与 C[3+S] 进行比较，依此类推。

当移位 S 是 L 的倍数时，对于每个位置 i，C[i] 就会被与 C[i+S] 相同的字母表进行加密，因此两个相应的密码文字符相等的机会是 1/15。如果移位不是 L 的倍数，则相应的字符将不会被相同的字母表进行加密，它们相等的机会只有 1/26。当 S = L，S = 2L 时，相等字符的数量应该最多。尝试几种不同的移位应该能够清晰地显示这种模式。产生最多匹配的移位通常会是周期的倍数。

尝试许多不同的移位听起来像是计算机的工作，但实际上可以手动完成而不需要太多的努力。将密码文写在两张长条纸上。然后将一条纸滑动到另一条上，并计算每次移位时相等字符的数量。你需要均匀地间隔字母以便正确对齐。这很容易通过使用格子纸或者在写字时在每条纸旁边放置尺子来实现。

相关性指数还有另一种用途，对于密码分析师来说非常有价值。它可以检测出两条消息是否使用相同的密钥进行了加密。想象一下，艾米莉正在使用一个机器密码，它生成一个具有非常长周期的多表密码，比如说 100,000。作为对比，德国军队在第二次世界大战中使用的恩尼格玛机的周期是 26×25×26 = 16,900。假设你有数千条拦截到的消息。每条消息都使用了这个长密钥的一部分进行了加密。将每条消息与其他消息进行比较，并使用相关性指数和重复的密码文序列，你可以检测出被同一密钥部分加密的不同消息段落。

当你找到足够多重叠的密钥片段时，你可以开始将这些片段拼接在一起，以获得更长的片段。一旦找到足够多使用相同密钥片段加密的消息，你就可以开始通过通常的方法解读这些消息，比如字母频率、字母组合频率、识别常见词等。

5.8 再次关于巧合指数

还有另一种估算多表密码周期的方法，也称为巧合指数，同样由威廉·F·弗里德曼提出。这种方法计算了当有 2 个字母表、3 个字母表等时，两个字母相等的概率。这些概率提前计算并保存在表中。其思想是计算给定消息的相同统计数据，并将该数字与表格进行比较。最接近的匹配应该是密码的周期。在实践中，这种方法通常很接近，但通常会偏离 1、2 或 3。当周期超过 10 时，该方法无效。这种方法不比随机猜测好多少，因此没有必要解释细节。

Belaso 和 Vigenère 密码在 1880 年代仍然被广泛使用。随着 Kasiski 方法的知名度逐渐增加，它们的使用减少了，并且在巧合指数发布后基本消失了。然而，直到今天，它仍然是最受欢迎的业余密码之一。有好几次，当我告诉人们我正在写一本关于密码学的书时，他们会告诉我他们知道一种无法破解的密码。这总是指 Belaso 密码，他们称之为 Vigenère。然后我不得不证明它是可以被破解的，通过解读他们编造的密码。这些密码被搞得一团糟，以至于我不得不创建一个网页 mastersoftware.biz/vigenere.htm 来确保密码的正确性。

5.9 解密多表密码

一旦你使用 Kasiski 方法或巧合指数法找到周期，下一步就是解读各个字母。首先让我们看一下最简单的情况，即 Belaso 密码。

5.9.1 解密 Belaso 密码

使用 Belaso 密码，所有替换字母表都只是标准字母表按一定数量的位移。确定这个数量，你就解开了密码。第一步是将使用每个密钥字母加密的字符分开。让我们再次看一下第 5.5 节中的示例。由于我们已经确定周期是 6，让我们将密文写成 6 个一组。

这些组中的每个字母的第一个字母都已经用密钥的第一个字母加密，每个组中的第二个字母都由密钥的第二个字母加密，依此类推。如果我们将密文垂直地写在 6 列中，就像这样

那么第一列字母将用密钥的第一个字母加密，第二列字母将用第二个密钥字母加密，依此类推。

分别考虑每个字母列。每列都将具有正常的英文字母频率，但根据其密钥字母进行了偏移。如果我们能够确定偏移量，那么我们就解密了密码。我将描述两种方法，一种是手工解决方案，一种是计算机解决方案。我们先看看纸和铅笔的方法。

对于每一列，我们可以进行频率统计。这将给我们 26 个数字。对于纸和铅笔解决方案，最好将频率显示为直方图（条形图）。密文的第一列直方图将是

只有 18 个字母，这相当稀疏，但已足够。让我们将其与标准英文字母频率的直方图进行比较，接下来显示，并尝试找出偏移量。

这个频率分布的一些视觉特征是（1）E 是远远最高的峰值；（2）有三个均匀间隔为 4 列的峰，即 A，E，I，其中 I 有伴随 H；（3）在 N，O 有双峰；（4）在 R，S，T 有三重峰。

让我们尝试将这个直方图与密文直方图匹配。我们首先寻找一个可能代表 E 的高峰。有两个高峰，R 和 Y，分别对应密钥字母 N 和 U。也就是说，如果 E 被 N 加密，则结果是 R，如果 E 被 U 加密，则结果是 Y。

接下来，让我们寻找间隔为 4 个空格的 3 个峰。有两个候选者，G,K,O 和 N,R,V，分别对应密钥字母 G 和 N。双峰呢？可能的候选者是 N,O 和 Y,Z，分别对应密钥字母 A 和 L。三重峰呢？只有一个选择，X,Y,Z 的三重峰。这对应于密钥字母 G。

第一列最可能的密钥是 G，它产生A,E,I峰和R,S,T三重峰。第二可能的密钥是 N，它使得 E 成为最常见的字母，并且有N,O双峰。

让我们把注意力转向密文的第二列。字母频率直方图是

这次密文字母 S 引起了我们的注意。如果 S 代表明文 E，则密钥必须是 O。让我们通过比较密文直方图和偏移字母表来检查这一点。

你可以看到密文中所有高频字母，即 C，G，H 和 S，分别对应于高频明文字母，即 O，S，T 和 E。这是一个很好的匹配，第二个密钥字母很可能是 O。关键词以 GO 开始。

另外 4 个关键字母的确定方式相同。关键词是 GOVERN，明文是 THE LEGISLATURE SHALL BE DIVIDED INTO TWO CHAMBERS THE UPPER CALLED THE SENATE AND THE LOWER IS THE HOUSE OF REPRESENTATIVES。

这就是手动方法：通过使用直方图使频率分布可视化，然后通过目视匹配分布。对于计算机解决方案，我们需要一种数值方法来目测分布以找到匹配项。在每本讨论多字母密码的书籍中都可以找到的标准方法是使用相关系数，具体来说是 Pearson 积差相关系数，以 Karl Pearson，现代统计学的创始人命名。

如果你懂统计学，这会很熟悉。毫无疑问，你已经有一个带有此功能的统计软件包。好好使用它。对于其他人，我将向你展示一种更简单、更快速——而且准确无误的方法。

当我们通过目视将两个频率分布进行匹配时，我们试图将一个直方图中最高的峰与另一个直方图中最高的峰进行匹配。如果我们将它们的高度相乘，我们试图获得最大的乘积。如果你沿着字母表向下走，并添加 26 个乘积，那么当高峰与另一个高峰对齐时，总和将最高，当最高峰与最低谷对齐时，总和将最低。

这就是想法。尝试 26 种可能的移位。将密文的字母频率与标准英语的移位频率对齐，并加总 26 个乘积。最高总和将指示最有可能的移位。这告诉你最可能的关键字母。第二高的总和是第二可能的移位，依此类推。我称这种技术为Tall Peaks方法。

Belaso 密码评级为 Two。

5.9.2 解密 Vigenère 密码

在 Belaso 之后大约 30 年，Blaise de Vigenère 对 Belaso 密码进行了两项改进。第一个是在表格的外部添加指南。这样做的效果是产生了一个混合字母表，而不需要混合表格。以下是一个示例，使用水平指南中的关键词 FIRST LOVE，以及垂直指南中的关键词 YOUTH。第二项改进，自动关键字，请参阅第 5.10 节。

要使用关键字 U 加密字母 B，找到左边或右边的行中的关键字 U，在列的顶部或底部的字母指南中找到明文字母 B。密文字母是 U 行和 B 列中的字母，即M。要解密，使用关键字找到行，找到该行上的密文字母，并从顶部或底部的字母指南中获取明文。

如果你是手动加密，我建议每 4 或 5 行和列绘制水平和垂直规则。或者，使用透明的塑料 L 型工具精确找到交点。

这是使用这种形式的维吉尼亚密码加密的样本消息。其周期为 5。

这种密码有一个严重的弱点。由于表中的每一行都是标准字母表移位了一些位置，因此每个密码字母表将与所有其他密码字母表移位了一些位置相同。您无法将密码字母表与标准字母表有用地比较，因为它们是按混合顺序排列的，但是，您可以通过直接比较密码字母表或使用 Tall Peaks 方法来确定移位。

下图显示了 5 个密码字母表的直方图，将它们移位以匹配它们的峰值和谷值。第一列（阴影）中的所有密文字母代表相同的明文字母。这意味着第一个字母表中的 S，第二个字母表中的 C 和第四个字母表中的 L 都代表相同的字母。将所有这些替换为 A。第二列中没有字母。在第三列中，第三个字母表中的 M 和第五个字母表中的 T 代表相同的明文字母。将所有这些替换为 C，依此类推。第 26 列中的密文字母将全部替换为 Z。

这将把密文转换为一个简单的替换，现在可以使用第 5.1 节的方法解决。维吉尼亚密码的评级为 Two。

5.9.3 解决一般多表密码

也可以使用表格来完成一般的多表密码。表格的行可以根据任何方案混合，彼此独立地进行。值得注意的是，行数不必与列数相同。对于计算机密码，将表格宽度设置为 256 个字符，深度设置为 512 行，以便每个密文字符在每列中出现两次。这将使已获得密文及其相应明文的对手难以确定密钥。以下是 100 行表格的部分示例：

该表将与数值键一起使用，其中 2 位小数将用于选择用于加密的行。20 位数字键将产生周期为 10 的多表密码。

解决一般多表密码与解决单表密码非常相似。您首先进行频率统计，并为每一列制作一个接触表。在这种情况下，列 C 的联系将在 C-1 和 C+1 列中，必要时从最右边的列绕到第一列。每列中的每个字母的出现次数会减少，因此您需要从较少的数据中进行推断。这需要很多经验来自的灵感猜测。

让我们从这个多表密码开始。

快速检查此密文显示两个长重复序列，位置分别为 13 和 93 的YSUZONSOO，以及位置分别为 39 和 124 的SNZYYZK。在这两种情况下，两次出现之间的距离是 5 的倍数，证实了周期为 5。这些长重复可能代表常见的单词或短语，或者是与消息主题相关的单词。

每个 5 个关键字母的联系图表如下。为了更容易解释推断，我将使用数字标记每个密文字母，指定其字母编号。所以C1表示字母C在字母表 1 中的密文字母（即使用密钥的第一个字母进行加密），H3表示字母H在字母表 3 中的密文字母（使用密钥的第三个字母），依此类推。

请记住，两边有许多不同接触的字母倾向于是元音，而具有较少不同接触的字母倾向于是辅音。

根据这些联系，我们可以暂时将G2，K2，O2，P2，H3，K5识别为元音，将R1，Z1，K3，N3，D4，S4，O5识别为辅音。基于其高频率，S4可能代表明文 T。

您的操作步骤与简单替换一样。您更新联系图表以显示已被识别为元音和辅音的字母，并且还将带有标记的元音和辅音的密文写下。您使用这个来完善和修复元音/辅音的识别，并识别单个字母。

我不会重复 5.1 节中所采取的所有步骤。逻辑是相同的，但增量步骤更小，更多，需要更多的回溯。一般的多字母密码评定为三。

5.10 自动关键字

您可能还记得我在 5.9.2 节中提到维吉尼亚对贝拉索密码进行了两项改进。第一个改进是将指南放在表的边缘以产生混合字母表。第二个改进是自动关键字。

自动关键字使用消息的明文作为密钥来加密消息的其余部分。早期版本是由意大利医生/数学家/占星家吉罗拉莫·卡尔达诺发明的。在卡尔达诺的系统中，每个字母都使用自身作为密钥进行加密。这仅在您拥有具有奇数字母的字母表时才有效。使用 26 个字母的英文字母表，A 会产生一个A，而 N 也会产生一个A，所以受信者必须弄清楚哪一个是指的。即使使用了奇数大小的字母表，卡尔达诺自动关键字也仅仅产生了简单的替换。

Vigenère 通过使用滞后改进了 Cardano 方法。Vigenère 使用一个字母密钥来加密第一个字母，使用第一个明文字母来加密第二个字母，使用第二个明文字母来加密第三个字母，依此类推。在现代实践中，使用关键词来加密第一组字母，然后使用该组明文字母来加密第二组字母，依此类推。这个例子使用了关键词 SAMPLE 和 Belaso 表，即未混合的字母表。

使用未混合的字母表，解密是直接的。在第 5.7 节中描述的重合指数可以用来确定关键词的长度。当密文偏移了密钥长度的倍数时，指数通常会显著增加，就像这样：

假设你已经发现关键词有 6 个字母。尝试字母表中的每个字母作为密钥的第一个字母。从 A 开始。由于第一个密文字母是 L，第一个明文字母也必须是 L。这也将是消息第 7 个字母的密钥。由于第 7 个密文字母是 X，第 7 个明文字母必须是 M。

按照这种方式进行，对于第一个密钥字母的每个猜测都会给出明文的第 1、7、13、19、25 和 31 个字符。也就是说，它会给出每 6 个明文字母。有 26 组字母，每个可能的密钥字母对应一组。这些 6 个字母的一些组会有正常的英文字母频率，一些则不太可能。对第二个密钥字母重复这个过程。对于第二个密钥字母的每个猜测都会给出明文的第 2、8、14、20、26 和 32 个字符。

现在，取出第 1、7、13 等 5 个字母的最有可能的选择，并将它们与第 2、8、14 等 5 个字母的最有可能的选择配对。这将给出 25 组双字母组合。其中一些可能性很高，一些则不太可能。取出其中最合理的 10 组，并将它们与第三个密钥字母的 5 个最可能的选择配对。这将给出 50 组三字母组合。选择其中最合理的 10 组，并将它们与第四个密钥字母的 5 个最佳选择配对。到这一步，一些明文单词将开始出现，正确的密钥字母选择将变得明显。

如果你是通过计算机进行这个过程，请跳过双字母组合。直接尝试前 3 个密钥字母的所有 26³种组合，然后直接进入三字母组合。然后对第 2、3 和 4 个密钥字母重复这个过程。前 3 个密钥字母和后 3 个密钥字母的最可能选择会有重叠。第三组和第四组密钥字母也会发生同样的情况。这将迅速缩小到正确的关键词。

使用标准字母表的 Vigenère 自动密钥被评为 Three。

5.11 运行密钥

运行密钥类似于自动密钥，但是不是使用一个简短的关键词或短语，而是使用一个密钥文本，它可能和消息本身一样长。运行密钥从未在实践中被广泛使用，因为它要求双方都完全正确地获得密钥文本。如果一方记住或复制了密钥为“MINE EYES HAVE SEEN THE GLORY OF THE COMING OF THE LORD”，而另一方记住了“MY EYES HAVE SEEN THE GLORY OF THE COMING OF THE LORD”，那么他们将无法进行通信。解决这个问题的一种方法是使用双方都有的印刷书籍中的密钥文本，尽管他们必须随身携带这本书。对于计算机通信来说，这不是问题，因为计算机可以存储成千上万本书籍。

假设使用标准的英文字母表构成的贝拉索表，运行密钥的解密方法虽然直截了当，但也很费力。有一种技巧，适用于自动密钥和运行密钥，就是猜测文本中可能出现的一个合适的单词。这个单词可能出现在密钥文本中，也可能出现在明文中。密码学家稍后需要解开这个谜。这个可能的单词，或者暗语，可能是一个常见的英文单词，比如 THE 或 AND，也可能是与疑似主题相关的词。例如，如果消息涉及贸易谈判，那么可能的单词可能是 TARIFF、SHIPPING、REPRESENTATIVE、BARGAINING 等。

思路是在消息中尝试可能的单词的所有可能位置。这被称为词拖拽。知道明文单词和相应的密文可以给你一个密钥的片段。如果单词放置正确，那么这个片段看起来就像正常的英语。可能的单词越长，你就越有信心它是正确的。一旦找到一个单词，你就尝试猜测字母，然后是文本中在它之前或之后的单词，以扩大漏洞。

还有一种技术，适用于计算机求解。这需要一个新的数学概念，叫做条件概率。这是事件 A 在事件 B 发生时发生的概率。单个事件 A 的概率用 P(A)表示，给定事件 B 发生的条件下事件 A 的条件概率用 P(A|B)表示。如果 AB 表示事件“A 和 B”，那么给定 B 的条件下 A 的条件概率是 P(A|B) = P(AB)/P(B)。这意味着 P(AB) = P(A|B)P(B)。

举个例子来帮助澄清这个问题。如果你掷两个标准骰子，掷出 12 的概率是 1/36。然而，如果你掷第一个骰子，结果是 6，那么掷出 12 的机会变成了 1/6。令 A 表示“掷出 12”，B 表示“第一次掷出 6”。那么 P(A) = 1/36，P(B) = 1/6。P(AB) 意味着第一次掷出 6 时掷出 12。P(AB) 也是 1/36，因为如果你掷出 12，第一次掷出的一定是 6。使用条件概率符号，P(A|B) = P(AB)/P(B) = (1/36)/(1/6) = 1/6。因此，当第一次掷出 6 时掷出 12 的条件概率是 1/6。

让我们使用条件概率来解密一个流动密钥密码。所需的工具是单个字母、二字母和三字母概率表。这些可以通过统计大量文本中的字母、二字母和三字母来编制。你可以在古腾堡计划网站 www.gutenberg.org 上找到许多这样的文本。选择明文选项。你也可以在互联网上找到一些统计表。

你需要为每个可能的二字母和三字母分配一个概率，而不仅仅是在那个文本中找到的。对于二字母组，这是显而易见的。如果 AB 是一个没有出现在计数中的二字母组，你可以设置 P(AB) = P(A)P(B)，然而，我建议将其设置得更低，简单地因为 AB 从未被发现。我使用 P(AB) = P(A)P(B)/3。一旦你有了完整的二字母组概率集合，你可以通过将 P(ABC) 设置为 P(A)P(BC) 和 P(AB)P© 中较大的一个来扩展到三字母组。同样，我建议将它们设置得更低，因为三字母组 ABC 从未出现过。例如，将 P(ABC) 设置为 P(A)P(BC)/3 和 P(AB)P©/3 中较大的一个。这些人为的概率意味着所有二字母组和所有三字母组的总概率都大于 1。数学上来说这是无意义的，但它没有实际影响。

现在我们有了必要的工具，可以解决一个流动密钥密码。选择消息中的一个起始位置，比如 s，并尝试位置为 s，s+1，s+2 的所有可能的关键三字母组。查看相应的明文三字母组。将关键三字母组和文本三字母组的概率相乘以获得该位置的概率。保留这些位置中的前 10000 个，并丢弃其余的。对于每个选择的三字母组，尝试 s+3 位置的所有可能的关键字母，并查看相应的明文字母是什么。假设关键三字母组是 JKL，下一个关键字母是 M，相应的明文四字母组是 ABCD。您可以使用条件概率 P(KLM|KL) 来估计关键四字母组 JKLM 的概率，这是 M 跟在 KL 后面的概率。这是根据三字母组的概率计算出来的，如 P(KLM)/P(KL)，这是三字母组 KLM 的概率除以二字母组 KL 的概率。因此，四字母组的概率被估计为 P(JKL)P(KLM|KL)。这对于关键四字母组和明文四字母组都是如此。

通过将关键四字母组和明文四字母组的概率相乘来估计这个位置的概率。同样，保留前 10,000 个，丢弃其余的。一直持续到解决方案变得明显为止。所有这些都可以由计算机完成，无需任何人的监督。

使用标准字母表的维吉尼亚运行密钥评为四级。

*5.12 模拟转子机

多表密码的必不可少之物是从 20 世纪 20 年代开始使用的电机械转子机。这些机器的周期可以达到数十亿或数万亿，或者如果转子的运动取决于明文或密文字符，则根本没有周期。从大约 1915 年到二战后，至少生产了 70 种不同类型的机器。有几个网站有这些机器的图片和描述。

每台机器都有一个或多个转子，通常为 3 到 6 个，但有时多达 10 个。每个转子执行简单的替换。在每个字母被加密后，一些转子会转动，以便下一个字母使用不同的替换。各种齿轮、凸缘、凸轮、杠杆和棘轮的系统使得转子以不可预测的方式转动。也就是说，对于你的对手来说是不可预测的。

如果我们用数字替换字母表中的字母，描述转子机器会更容易。对于机械转子机器，每个转子有 26 个位置对应于字母表的 26 个字母，我们用数字代替 A 为 0，B 为 1，C 为 2，直到 Z，其被 25 代替。换句话说，我们使用经典的数字系统减去 1。对于计算机模拟，我们使用 8 位字节，并用一些标准化系统（如 UTF-8 编码）中的数字代码替换字符。在这个系统中，A 是 65，B 是 66，C 是 67，直到 Z，其为 90。其他字符，如小写字母、数字和标点符号，也被它们的 UTF-8 字符代码替换。

既然我们在处理数字，我们可以对它们进行算术运算，例如加法和取模 26 或 256 的余数，视情况而定。如果你想复习模数算术，请参考第 3.6 节。

生产了多达 16 个转子的密码机。这是俄罗斯制造的菲阿尔卡机器的 10 个转子组件，它从 1956 年直到 1990 年代被华沙条约国家使用。照片由保罗·哈德森提供，并根据 CC BY 2.0 许可证授权。

5.12.1 单转子机

让我们从一个单独的机械转子开始。转子执行简单的替换，因此可以通过替换表 S 进行模拟。表 S 只是一个乱序的字母表，就像一个表的一行。列表中的条目从 0 到 25 编号，对应于字母表的 26 个字母。替换表中的第 N 个条目，表示为 S(N)，是字母表的第 N 个字母的替换。因此，S(0) 是 A 的替换，S(1) 是 B 的替换，依此类推。

当转子转动时，它们会改变位置。位置可以用一个数字 P 来表示，它的范围是从 0 到 25。当一个转子转动了 26 个位置时，它会回到起始位置，即位置 0。当转子处于位置 P 时，第 N 个字母的替代是 S(N+P)。因此，当转子处于位置 5 时，S(5) 是 A 的替代，S(6) 是 B 的替代，依此类推。我们理解 N+P 会循环，所以 S(26) 和 S(0) 是相同的，S(27) 和 S(1) 是相同的，依此类推。换句话说，N+P 实际上是 (N+P) mod 26 的简写。

在机械转子机器中，每个字母加密后，转子的转动量不同。这种不规则的运动可以通过使用一个 步数序列 来模拟，比如 (a,b,c,d,e)。在第一个周期，转子向前推进 a 个位置。在第二个周期，它向前推进 b 个位置，依此类推。第六个周期序列重复。因此，如果转子从位置 P 开始，经过一个周期后，它将处于位置 P+a。经过两个周期后，它将处于位置 P+a+b。经过 5 个周期后，它将处于位置 P+a+b+c+d+e。经过 6 个周期后，转子将处于位置 P+2a+b+c+d+e。在机械设备中，每个转子通常只转动几个位置，通常是 0 或 1 个位置，具体取决于特定凸轮的位置是上还是下。在计算机模拟中，我们没有这样的限制。在模拟机械转子时，步数可以是从 0 到 25 个位置，或者使用 8 位字节来表示字符时，可以是从 0 到 255 个位置。

由于我们选择了 5 步的密钥，这台单转子机器将在 5×26 = 130 个周期后重复。当 a+b+c+d+e 是偶数时，机器将在 65 个周期后重复，如果 a+b+c+d+e 是 13 的倍数，机器将在仅 10 个周期后重复。显然，一个转子不能提供太多安全性。单转子机器密码被评为 Three。

5.12.2 三转子机器

让我们来看看如何模拟一种更实用的转子机器。这台机器有 3 个转子，使用 8 位 UTF-8 代码。三个转子需要 3 个替换表，S[1]、S[2] 和 S[3]。当转子处于位置 P[1]、P[2] 和 P[3] 时，字母表的第 N 个字母被加密为 S3+P[2])+P[3])。

每个 3 个替换表都有自己的步骤列表：假设 S[1] 有步骤 (a[1],a[2],a[3],…,a[i])，S[2] 有步骤 (b[1],b[2],b[3],…,b[j])，而 S[3] 有步骤 (c[1],c[2],c[3],…,c[k])。如果每个转子的步数之和是奇数，并且 i、j 和 k 是互质的，那么该机器的周期是 256ijk。例如，如果 i = 10，j = 11，k = 13，则 ijk 为 1430，周期为 1430×256 = 366,080。效果就像是有一个多表代换密码，其表格有 366,080 行，每个周期只使用一次每行。

假设已知三个替换表和步骤序列，例如，假设它们已经在一个大型网络上标准化。一个可能想象的是，艾米丽只需要尝试 256³ = 1.67×10⁷个初始转子设置就能破解每个消息。这可能在当前的个人电脑上只需要几秒钟。这是误导性的。

考虑机器的两种不同状态。两个状态的转子处于相同的位置，但它们处于步进序列的不同部分。从这两个状态开始加密将会产生不同的密码字母序列，因此相同的消息将会被加密成不同的样子。通过穷举搜索来破解此密码将需要尝试所有可能的转子设置和步骤序列中的所有可能位置，总共为 256³×1430，或 2.40×10¹⁰个情况。这仍然可以使用个人电脑来完成，但需要几个小时，而不是几秒钟。

对于已知转子和已知步骤序列，这个三转子密码的等级是 Four。

如果转子和步骤序列是保密的，那么艾米丽必须回到一般多表密码的技术上，即收集大量拦截并将它们匹配起来找出使用相同设置加密的部分。为了区分真实匹配和偶然匹配，需要对长重叠进行重合指数测试（第 5.7 节）。建议至少 200 个字符。匹配应仅尝试长于 200 个字符的消息。对于长度为 L 个字符的消息，其中 L ≥ 200，可匹配位置的数量为 L-199。当所有拦截消息的可匹配位置的组合总数 M 超过√2.40×10¹⁰ = 1.55×10⁵时，可以开始检测文本部分的匹配。

这似乎不算什么，但是检测这些重叠的工作是按 M²量级的。此外，单个重叠远远不够。你需要足够的重叠，以便开始区分高频字母，并将元音与辅音分开。这将需要一台大型机和一些有才华的密码分析员。未知转子和未知步骤序列的三转子机的等级是 Six。

5.12.3 八转子机器

三个转子是一个很好的开始。为了真正提高模拟转子机的强度，让我们将转子的数量从 3 增加到 8。让转子的步数为 11、13、17、19、23、25、27 和 31，按某种顺序，并且使每个转子的步数总和为奇数。这台机器的周期约为 5.69×10¹²。

如果这是一个硬件设备，转子的内部布线和步骤序列可能已经内置。即使是这种情况，也不可能像我们在 3 转子版本中那样匹配消息。这是因为现在有 256⁸ = 1.84×10¹⁹个 8 个转子的可能初始位置。由于周期为 5.69×10¹²，机器的总状态数变为(1.84×10¹⁹)×(5.69×10¹²) = 1.05×10³²。当转子和步进序列无法更改时，这个 8 转子机器被评为九级。

让我们再深入一点。假设我们有 16 个可能的转子供应。对于每个消息，我们以某种顺序选择其中的 8 个转子。有 5.19×10⁸种这样的排列。对于每种排列，有 1.84×10¹⁹个可能的初始转子位置和 5.69×10¹²个步进序列位置，总共有 5.43×10⁴⁰个状态。

即使艾米丽以某种方式知道所有 16 个转子的替换表和步进序列，使用这台机器加密的消息也不可能被破解，即使使用世界上最大最快的超级计算机也不行。（目前世界上最快的超级计算机是 Summit 计算机，最高可达 200 petaflops。）这个 8 转子密码被评为十级。

如果替换表和步进序列的内容保密，或者经常更改，这个具有 8 个可互换转子的转子密码应该在未来 10、20 或甚至 30 年内仍远远超出最大超级计算机的能力范围。

由于这是一个转子机器的软件模拟，转子可以随意更改。可以通过使用密钥来混合每个 8 个转子字母表，为每个消息更换转子，而不是固定的 16 个转子集合。这将大大增加安全性，但需要为每个消息进行单独的设置阶段。中等安全级别是使用 16 个转子集合中的 7 个标准转子，以及为每个消息独立生成字母表的 1 个转子。这将减少 87%的设置时间。

即使这个密码已经获得了十级评价，你可能仍希望加强它。你可能不相信我的评价，或者你认为你的对手拥有惊人的计算能力。一种方法是使用一些转子的输出来修改操作。我建议在加密过程中的中途取第四个转子的输出，并使用该字符来推进第一个转子。可以直接使用字符，也可以对字符进行简单的替换以获得推进第一个转子的位置数。除了消息中的第一个字符外，第一个转子被推进两次，一次来自其步进序列，一次使用第四个转子的反馈。

这种双步进不会影响当前字符的加密。使用这种修改后的设置对下一个消息字符进行加密。在硬件转子机器上实现双步进可能会很困难，但在模拟机器上可以很容易地完成，因为转子是依次模拟的。

顺便说一下，使用第八转子的输出似乎会更强大，但这是不正确的。第八转子的输出是密文字符，这对窃听者是已知的。中间两个转子的输出，即第四和第五转子，对窃听者的获取是最困难的，因此最安全。

第四转子的反馈使得模拟的 8 转子机器是非周期性的。无论发送多少消息，埃米莉都永远找不到具有相同转子设置序列的两条消息。

第六章：对策

本章内容包括

• 双重加密

• 空字符和空位

• 同音字

• 在图像或计算机文件中隐藏消息

总结第 5.9 节，多表密码可以通过两步过程解决。首先，使用 Kasiski 方法或 Coincidence 指数确定周期或密钥长度。这将把密文分成几个较小的文本，每个文本只有一个字母的密钥。其次，使用标准的简单替换密码方法对这些单独的文本进行解密，包括频率和接触。

让我们把它反过来。密码分析者可以采取哪些措施来防止多表密码被这两个步骤破解？我们将看几种对策。

6.1 双重加密

如果一条消息使用一个周期为 P 的多表密码加密，然后使用周期为 Q 的第二个多表密码加密结果中间文本，那么结果等同于一个周期为 P 和 Q 的最小公倍数的多表密码，表示为lcm(P,Q)。也就是说，周期是 P 和 Q 的最小整数倍数。例如，如果 P 为 10，Q 为 11，那么双重加密将具有 110 的周期，但如果 P 为 10，Q 为 12，那么双重加密将具有 60 的周期，因为 60 是 10 和 12 的倍数。

双重加密中的每个个体字母都是第一次和第二次加密中的两个字母的组合，如第 11.7.4 节所述。如果这些是移位标准字母表，那么结果也是移位标准字母表。如果这些是混合字母表，那么结果很可能是更彻底混合的字母表。

尽管双重加密仍然是多表加密，但它可能比单个多表加密更强，因为周期更长，每个密钥字符将加密的字母更少。这种类型的双重加密评为三级。

如果两个多表加密是自动键、流动密钥或一个键，双重加密将是流动密钥加密。然而，密钥不会是英文文本，所以第 5.11 节的单词拖拽技术无法使用。那节的概率技术，尽管如此，可以用于两个流动密钥。

如果加密使用直接字母表，即使用 Belaso 表，那么加密顺序并不重要。用流动密钥 R 加密消息 M，然后用流动密钥 S 重新加密与用流动密钥 S 加密流动密钥 R 以获取新的复合流动密钥 C，然后用该复合流动密钥 C 加密消息 M 是相同的。

通过用一个流动密钥对另一个流动密钥进行加密而派生的密钥并不是随机的。它们具有自己的特征字母频率和接触频率。有常见的序列，比如 THE 被 THE 加密，或者 AND 被 THE 加密。所有这些都可以列成表。如果将长短语（如 UNITED STATES OF AMERICA 或 NEGOTIATING STRATEGY）拖过文本，您可以寻找符合此分布的流动密钥部分。因此，双流动密钥加密可以通过计算机解决。

使用未混合字母表，两个自动密钥和/或流动密钥加密的组合被评为四。使用混合良好的密钥字母表，该组合被评为六。

6.2 空字符

空字符是阻止敌人破译代码的一种历史悠久的方法。它们至少可以追溯到 15 世纪的阿根提家族。空字符是插入到消息中以迷惑敌方密码分析员的无意义字符。它们最常与代码一起使用。对于多表密码，它们可以污染频率计数并破坏卡西斯基或重合指数分析。

空字符可以有几种使用方式。最直接的方法是向字母表中添加一个空字符。这通常表示为一个星号。然后可以将此字符散布到明文中。应该适度使用，以免显眼和明显。约 3%至 6%的空字符是合理的。使用空字符的一个有用方法是将它们插入高频词中以迷惑卡西斯基攻击。这应该是随机的。如果您将每个* THE 更改为 THE，则正在通过提供 4 个字符重复来帮助 Emily。最好一半时间使用 THE，四分之一时间使用 THE，四分之一时间使用 THE。使用THE 或 THE*并不有益，因为 THE 三字母组保持完整。

加密表将变为 27 列宽，并且星号将出现在密文中。您可能会认为这将透露正在使用空字符，但有一种称为三重密码的密码，描述在第 9.9 节中，它利用了一个 27 字符的字母表。Emily 可能会认为您的多表密码是三重密码（不要与约翰·温德姆 1951 年小说《三脚怪植物的末日》中的三条腿怪物植物混淆）。

以这种方式使用空字符相当薄弱。它不会显著改变字母频率，并且不会对卡西斯基或重合指数产生不良影响。该方法被评为三。

使用空字符的第二种方法是在明文中插入一些特定的空字母序列。这些序列需要容易识别。我建议从一小部分中频字母（如 C、D 和 P）形成空序列。双字母组 CC、DD 和 PP 可以用来表示字母 C、D 和 P，这些字母的其他 6 个双字母组合将成为空字符。这种方法也被评为三。

6.3 中断密钥

使用空字符的更强大的方法是将空字符插入到密文中，以打破重复周期。这样做的简单方法首先是以正常方式使用多表密码加密消息。然后每次在密文中发生某些触发事件，例如某个选择的字母或双字母时，在其后插入一个空字符。空字符可以是任何字母，甚至是双字母。触发器的存在标记它为一个空字符。

这种空字符插入类型可能相当复杂。你可以插入一个空字符

• 在密文中每个 W 之后的 4 个字符，例如密文NPGWSOVKLEWPIDF可能变为NPGWSOVTKLEWPIDCF，

• 在密文中每第二个 H 之后，

• 在密文中每个跟随 Q 的第一个 A 之后，

• 第一个 V 之后的 1 个位置，然后下一个 B 之后的 2 个位置，下一个 L 之后的 3 个位置，然后重复 V、B、L、V、B、L、…，

• 在密文中每个双字母之后，或在连续 3 个元音之后，或在字母表中按升序或降序连续 4 个字母之后，

或者这些的组合。唯一的限制是你的想象力。只是不要让它变得太复杂，以至于桑德拉和里瓦无法快速准确地加密和解密。如果桑德拉应该在每第二个 K 之后插入一个空字符，以及每第三个 M 之后，而她错过了一个，或者在第四个 M 之后放置了空字符，那么里瓦可能无法解密消息。

这种插入空字符的方法使用标准字母评为四，使用混合字母评为五，前提是，如常，混合字母保密。

还有几种打破关键周期重复的方法。一种方法是在明文中发生某些触发器时重新启动关键。这比前一种方法更安全，因为触发器在密文中，艾米丽可以看到密文，但看不到明文。另一方面，对于合法的接收者来说更困难。当触发器在密文中时，里瓦只需扫描并通过眼睛删除空字符。当触发器在明文中时，里瓦必须逐个解密字符，注意触发器。

触发器可以类似于刚才提到的密文触发器，只不过在明文中，而不是在密文中。触发器发生后所采取的行动可能是

• 跳过关键中特定数量的字符，或

• 重复关键中特定数量的字符，或

• 从第一个字符重新启动关键，或

• 切换方向，通过关键向后走。

这里是使用关键 SAMPLE 和触发字母 A 的这 4 种类型的关键中断的示例：

这种形式的关键中断使用直接字母评为五，使用混合字母评为六。关键不应该经常重新启动，否则关键的第一个字符将被过度使用，而关键的最后一个字符可能会被忽略。

更强的关键中断形式是使用两个不同长度的密钥。当密钥长度互质时，此密码最强。当触发器发生时，您从一个密钥切换到另一个密钥。当混合字母表混合良好时，此方法评为六。这是一个使用密钥 FIRST 和 SECOND 以及触发器 A 的示例：

此密码会跟踪上次使用的密钥字母。当你切换到另一个字母表时，加密将继续使用密钥的下一个字母。例如，明文 MA 使用密钥字母 FI 进行加密，因此下一个密钥字母是 R。在使用第二个密钥 SECO 加密 RYHA 后，加密将在第一个密钥 RS 的密钥字母中继续。

这样，每个密钥中的所有字母大致相同的次数。

6.4 同音字替换

同音字替换，介绍在 4.2 节中，为了平坦化字母频率，为每个明文字母提供几个替代字。最常见的方法是扩大密文字母表以提供额外的替代字。由于经典的多字母密码使用固定的 26 个字母表，至少对于英语来说，它们通常不使用同音字替换。

对于使用 8 位字节的计算机实现，同音字替换很容易实现。一个字节有 256 个可能的值。26 个大写字母，26 个小写字母，10 个数字，以及可能的 32 个标点符号只使用了 256 个值中的 94 个。如果包括制表符、退格、换行和回车，就有 98 个。这样就留下了 158 个字符，可以用于空字符、双字母组合和三字母组合以及关键中断。

让我们看看如何使用纸和笔以及正常的 26×26 混合表进行同音字替换。如果您将一个字母保留为触发字母，那么该字母的频率将非常高，很容易被发现。同样，使用 2 个触发字母也是可能的。我建议使用 3 个触发字母，每个字母的频率都低于 4%。让我们称这个密码为Trig3。字母 BCDFGJKLMPQUVWXYZ 是合适的。假设您选择了 B、C 和 D。以这 3 个字母开头的双字母组合有 78 个，即 3×26。您不会使用包含高频字母 AEINORST 的双字母组合，因为那会增加它们的频率，这与平坦化字母频率的目标相悖。这样就留下了 54 个可以用作空字符、同音词和关键中断的双字母组合。这里是一组可能的双字母组合：

这里的**-**代表空字符，所以明文 BD、BL、CC 等都是空的。Codes +1、+2 和+3 是关键中断符，意思是跳过 1 个、跳过 2 个和跳过 3 个关键字母。同音词集包括 6 个双字母组合，AN、ER、IN、ON、RE 和 TH 以及单个字母。

保持平衡很重要。如果你过度使用这些替代字符，那么字母 B、C 和 D 的频率就会过高，很容易被发现作为触发器。如果你使用得太少，那么它们就不会有任何有用的影响。大约 10%是正确的，使用 B、C 和 D 的双字母组合频率大致相等，每个约为 3%。记住，使用这种密码时不能单独使用字母 B、C 和 D，必须使用它们的替代品 DM、CD 和 CG。

如果正确使用，使用混合得很好的键入字母表，Trig3 密码的评级为五。

6.4.1 密码 5858

在转向双字母组合替换之前，让我再介绍一个密码。我称之为Cipher 5858。这是一个使用 5 位字符的计算机密码。五位字符给出 32 个字符的字母表，足够 26 个字母、3 个空字符和 3 个同音字使用。（1）明文被写成一个混合字母的 5 位字符序列。（2）插入空字符和同音字，每个约占明文的 3%，总共占明文的 18%。最好是以随意的方式使用它们，而不是以系统化的方式。（3）明文被填充，使其长度成为 8 的倍数，如果需要，添加一个空字符，并最多添加 4 个随机位。（4）填充后的消息被视为 8 位字节的字符串，并进行混合替换。例如，如果消息包含 80 个 5 位字符，则将按顺序取 400 位，作为 50 个 8 位字节。（5）将消息再次视为 5 位字符的字符串。选择其中的三个字符作为键中断器+1、+2 和+3，就像 Trig3 密码一样。（6）使用一个通用的多表多字母密码和一个混合得很好的 32×32 的 5 位字符表对消息进行加密。（7）5 位字符的字符串然后重新分组成 8 位字节，并进行第二次 8 位替换。

总之，密码 5858 使用 4 个替换步骤，一个初始的 5 位替换，一个 8 位替换，一个带有键中断的 5 位通用多字母替换，以及最后一个 8 位替换。这个密码的评级为七。

6.5 双字母组合和三字母组合替换

防止 Emily 使用字母和联系频率破解您的密码的另一种方法是对双字母组合甚至三字母组合进行替换。最简单的方法是使用一个表格。对于双字母组合，您可以使用一个 26×26 的表格，其中每个条目都是一个双字母组合。以下是这样一个表格的开头：

AA 的替代品将是BL，AB 的替代品将是TC，依此类推。对于三字母组合替换，您可以使用一个小册子，其中包含 26 个这样的表格，每个表格对应三字母组合的第一个字母。

这种替换方法可以单独使用，也可以与另一种方法结合使用，例如多表替换。单独使用时，二元替换评为三，三元替换评为四。二元替换后跟着使用混合良好的秘密字母表的多表替换评为五，三元替换后跟着使用混合良好的秘密字母表的多表替换评为六。

*6.6 在图像中隐藏消息

一个有趣的想法，可以追溯到大约 1999 年，是将消息隐藏在计算机上各种类型的数据文件中。这是隐写术（第 2.2 节）的现代版本。让我们看看其中一种方法，将消息隐藏在位图或 BMP 文件中。位图是以像素为单位存储的图像。最常见的位图格式通过 3 个字节表示每个像素，指定图像上单个点的蓝色、绿色和红色色深度。 （这是微软位图图像标准中的设备无关顺序。如果你记不住顺序，注意蓝色、绿色和红色按字母顺序排列。）例如，0,0,0 表示没有颜色，因此是纯黑色，255,255,255 表示所有 3 种颜色的最大深度，因此是白色，255,0,0 将是纯蓝色。

像素通常用十六进制表示，因此纯蓝色将是 FF0000。在一些计算机语言中，这样写$FF0000 或 X’FF0000’甚至 0xFF0000，因为十进制 255 在十六进制中是 FF。在一些语言中，颜色组件的顺序是相反的。例如，在 HTML 中，纯蓝色将是#0000FF。

整个图像可能包含数百或数千行像素，每行包含数百或数千个像素。一个位图包含 3000 行，每行包含 4000 个像素并不罕见。这样的图像将有 12,000,000 个像素，并且需要 36,000,000 字节的存储空间，再加上 54 字节的头部信息。这就是为什么许多高分辨率图像会迅速填满计算机的内存。

诀窍是使用像素的每个组件中的低阶位来携带一位消息。这可能不会被察觉，因为 FF0000 和 FE0000 甚至 FE0101 之间的差异对肉眼几乎是不可察觉的。在大图像的单个像素中，这将在视觉上是不可察觉的。此外，一半的位不会改变值。在图像中隐藏消息时，关键是传输包含图像的文件时必须完全准确。图像不得放大、缩小、裁剪、旋转、倾斜、压缩或转换为另一种图像格式。

消息可以用任何方法加密。但是，如果 Emily 怀疑你是以这种方式隐藏消息，那么它不会增加任何额外的安全性。你将为每个消息位传输 8 位数据而不获得任何相应的好处。如果你简单地依次取每个像素的低阶位，评级将与你选择的加密方法相同。

从这种方案中获得额外安全性的一种方法是不使用所有位，而是以某种循环顺序从每个像素中选择特定位。为此，您可以使用一串八进制数字（请参阅第 3.1 节中的表）作为选择消息位的密钥，例如 1,3,7,4,6。这可以称为选择密钥。它有 5 个八进制数字，因此有 15 个选择位。从图像的第一个像素和选择密钥的第一个数字开始。如果该数字的第一个位为 1，则将消息的一位放入像素的蓝色分量的低阶位，否则将低阶位随机设置为 0 或 1。如果第二个密钥位为 1，则对绿色分量执行相同操作，如果第三位为 1，则对红色分量执行相同操作。然后对第二个像素和选择密钥的第二个数字重复此操作。依此类推。

有人可能会认为，当密钥位为 0 时，最好保持图像对应位不变。这样会导致图像失真较小，并且使得 Emily 更难检测到其中包含隐藏消息。没错，但如果 Emily 怀疑你在使用这种方法，那么就可能确定选择密钥。

假设情况如此。Emily 拦截了包含位图图像的消息。进一步假设 Emily 在互联网上进行了图像搜索，并找到了原始图像。Emily 可以逐像素和颜色分量地将两个图像进行匹配。这使得 Emily 能够制作出两个图像版本之间差异的地图。在低阶位匹配的地方，Emily 可以在地图中标记一个 X，而在不匹配的地方，Emily 可以标记一个 |。然后，Emily 可以尝试每个可能的选择密钥长度。当选择正确长度 L，并且标记以 L 像素间隔对齐时，那么每一列选择位为 0 的地方将包含所有的 X，而选择位为 1 的列将包含一半的 X 和一半的 |。例如，再次使用选择密钥 1,3,7,4,6，你可能会看到

对于每一列包含 | 的情况，选择密钥的对应位必须为 1。选择密钥的所有其他位可能为 0。随着差异图中行数的增加，概率会变得更高。

因此，无论选择位是 0 还是 1，颜色分量的低阶位都应该随机设置。使用循环选择密钥，隐藏消息的这种方法在底层密码的评级为 1 到 4 时添加 2，或者在评级为 5 到 8 时添加 1。

选择密钥也可以使用第 4.5 节的链式数字伪随机生成器生成，使用 7、9 或 10 位数的合格种子。使用从 0 到 7 生成的数字作为选择数字。如果生成的数字是 8 或 9，则丢弃它并生成下一个数字。这里不重要伪随机数字是否具有统计随机性。重要的性质是生成的数字序列比消息更长，以比特为单位衡量，这样艾米丽就不能匹配具有相同选择密钥的密文部分。

使用链式数字选择密钥，如果底层密码的评级为一到四，则此隐藏消息的方法添加 3，如果评级为五到七，则添加 2，如果评级为八，则添加 1。

6.7 添加空位

将消息的位与空位的这种混合思想也可以在不嵌入消息于图像或其他文件中的情况下实现，并且可以手工完成。首先使用简单替换法或您选择的任何方法对消息进行加密。将这个初步的密文写成二进制形式，比如 5 位二进制。简单替换和转换为二进制可以一步完成。您可以只是按一些混合顺序替换字母表的 26 个字母为 5 位二进制数，就像这样：

注意，除了字母表的 26 个字母外，还有 6 个十进制数字。省略了数字 0、1、2 和 5，以防止手写时与字母 O、I、Z 和 S 混淆。这给了您将 5 位数转换回符号以进行传输所需的 32 个字符。

现在，消息以位串的形式给出，可以添加空位了。选择密钥用于指定插入空位的位置。选择密钥的形式是 m1,n1,m2,n2,m3,n3,…，表示取 m[1] 位消息并插入 n1 个空位，再取 m2 位消息并添加 n2 个空位，再取 m3 位消息并添加 n3 个空位，依此类推。以下是使用选择密钥 2,1,3,1,4,2,3,2 的示例。

使用此方案，消息被加密为Q9JIF PGUFF F。四个空位（阴影部分）被附加以完成最后一组 5 位。这称为填充或空填充。

选择密钥也可以以二进制形式给出，比如 110111011110011100。密钥中的每个 1 位表示取下一个消息位，而每个 0 位表示插入一个空位。

当使用两个不同的字母表来将字母转换为比特和将比特转换回字母时，此方案更加强大。使用可变长度的替代品，如第 10.4 节中描述的哈夫曼编码，也可以提高强度。为此，代码的长度不需要与字母的频率相对应，但它们仍然必须具有前缀属性，以便里瓦能够解密消息。

你可以通过两种方式避免在第二次替换时添加额外字符，即从比特到字母的替换。 (1) 你可以每次取 4 个比特，并且只使用字母表的 16 个字母，或者使用 16 个十六进制数字，或者 (2) 你可以使用一个具有六个 4 比特代码组和二十个 5 比特代码组的可变长度编码。同样，这些代码组必须具有前缀属性。以下是一个示例：

注意，我为 6 个最高频率的字母使用了 4 比特的替代物。这将使这 6 个字母在密文中的频率大约是其他 20 个字母的两倍。这可能会使一个不警惕的对手认为这是一种完全不同类型的密码。

添加空位适用于许多类型的加密。由于空位和其他任何比特都无法区分，因此添加空位比添加空字符更强大。它可以使密码的评级提高高达三分。

让我们看一个具体的例子。称之为Cipher Null5。和之前一样，有 3 个步骤，将字母转换为比特，添加空位，然后将比特转换回字母。字母被转换为比特，使用从字母到 5 比特组的同音替换。为每个字母 E、T、A、O、I、N 提供了两个替代物。空位通过使用选择密钥插入，如第 6.6 节所示。比特通过类似于上表的 4 比特/5 比特替换转换回字母。

Cipher Null5 的评级为六。

6.8 合并多个消息

二进制形式的密钥也可以作为合并密钥来合并两个消息。也就是说，两个消息的比特会交错以形成单个消息。基数为 3 或 4 的合并密钥可以用来合并 3 或 4 个消息。基数为 4 的合并密钥同样可以合并 3 个消息加空位。

合并多个消息的两个优点是，你不会像使用空位一样增加太多额外长度，而且可以使用更简单、更快速的加密。如果你使用一个长的合并密钥交替四个消息，并且对每个消息使用不同的简单替换，那么单单这一步就能获得五分的评价。如果你对合并的消息再进行一次简单替换，评价就会提升到八分。

合并消息的密钥可以采用两种形式，一种是比特计数形式，一种是选择形式。在比特计数形式中，消息会轮流被取出。密钥的每一位指定了从每个连续消息中取出多少比特。在选择形式中，消息可以按任意顺序被取出，但每次只取出一个比特。密钥的每一位指定了从哪个消息中取出下一个比特。以下示例展示了如何通过比特计数方法使用密钥 123123 合并消息 010101111010001101011 和 11101010011011100110，以及如何通过选择方法使用密钥 12122112 合并消息。

合并多条消息时，如果这些消息长度不同可能会显得混乱。除了最长的消息外，其他消息都需要有一个消息结束标记。另一种处理长度不匹配的方法是平衡合并。首先，将所有消息依次写在一起，用某个预留的字符或字符序列分隔开。然后简单地将这个长字符串分成相等的部分。例如，如果消息长度分别为 50、60、70 和 80 个字符，总共是 260 个字符，再加上 3 个分隔符共 263 个字符。你可以将它分成 4 条长度分别为 66、66、66 和 65 个字符的子串。如果使用的是 8 位字节，你可以将 263×8 = 2104 位分成 4 条每条 526 位的子串。不需要在比特字符串上按照偶数字节边界进行分割，但是你应该选择从每条子串中取相等位数的密钥。

顺便说一下，消息数和子串数是独立的。可以只有一条消息，也可以有多条消息，子串数从 2 开始。例如，一条消息可以分成 3 个子串，也可以有 3 条消息分成 2 个子串。

平衡是解决方案的一半。另一半在合并过程接近尾声时出现。最终，你将会合并来自其中一条字符串的所有比特，而其他字符串还剩下一些比特。如果合并密钥指定了另一条没有剩余比特的字符串的另一个比特，则跳到下一个比特选择。

让我们把所有内容汇总成一个密码，称为 Merge8。Merge8 密码作用于一个或多个连接在一起的消息。在基于 26 进制的版本中，26 个字母使用类似于第 6.7 节中的 4 比特/5 比特编码转换为二进制。消息分隔符可以是一串字母，如 XXX 或 END。在基于 256 进制的版本中，对 ASCII 码应用混合良好的简单置换。生成的比特字符串被分成 8 个长度相等的比特串。使用 32 个八进制数字的密钥来合并这 8 条比特串。每个 8 进制值在密钥中出现 4 次，因此有 32!/(4!)⁸ = 2.39×10²⁴ 种可能的合并密钥。对生成的字符串执行第二个简单的置换。基于 26 进制和基于 256 进制的版本都使用 8 比特置换。Merge8 评级为六。

6.9 在文件中嵌入消息

当将消息隐藏在图片文件中时，每个消息比特至少有 7 个图像比特。这相当低效。如果不试图让它看起来像其他东西，你可以在文件中隐藏更多的消息比特。它是密文，就让它看起来像密文。有数十种方法可以在文件中隐藏明文消息。我将简单列举一些选项。与第 6.6 节一样，对于文件的每个字节，一定数量的明文比特被隐藏在其中的 8 比特中。

• 每次取固定数量的明文比特或可变数量的明文比特。

• 每个字节内的位可以放置在固定的位位置或可变的位位置。

• 位按顺序放置，或者重新排列。

• 明文位可以原样插入，也可以轻微加密，例如通过简单的替换。

• 密文位可以原样保留，也可以轻微加密，例如通过简单替换。

位的数量、位的位置和位的顺序可以由周期性密钥或某些随机序列控制。根据所选择的选项，这一类密码的评级可以从一到十不等。

这是一个这样密码的例子。 (1) 对消息执行混合良好的密钥简单替换。(2) 使用具有大内部状态的伪随机数生成器，在每个字节中选择 2 到 6 位位置。按顺序将消息的下一个 2 到 6 位放置到这些 2 到 6 位位置中。将剩余位位置设置为随机值。(3) 执行第二次混合良好的密钥简单替换。

这种称为EmbedBits的方法极其快速简单。缺点是密文长度约为明文的两倍。EmbedBits 被评为八分。要将评级提升到十分，可以将简单替换替换为双字母替换，例如 Two Square。

第七章：置换

本章涵盖

• 路径和列置换

• 随机数置换

• 密钥置换

• 多重变位词

在第五章和第六章，我们讨论了替换密码。秘密密钥加密方法的第二大类别是置换。置换意味着改变消息中元素的顺序。这些元素可以是单词、音节、字母或代表字母的个别数字或位。在本章中，我们将主要处理字母置换，但请记住，您可以使用相同的方法处理其他元素，例如第 7.2.2 节中的单词置换。本章将涵盖许多不同类型的置换密码。大多数这些置换密码只需用铅笔和纸就可以完成。

7.1 路径置换

路径 置换 是最简单、最古老的置换密码形式。没有涉及密钥。保密性来自路径或路径选择。

路径置换是让孩子们对密码学感兴趣的好方法。这是一个适合课堂、童子军团或其他俱乐部的活动。主要注意事项是孩子们必须以直立的列均匀地写字母，否则消息会混乱。可以通过使用间距较宽的方格纸来避免这种情况。

基本思想是将消息用一条路径写入矩形中，然后用另一条路径读出。例如，如果消息有 30 个字符，那么 5×6 的矩形最合适。如果消息有 29 个字符，只需添加一个空字符。用空字符填充消息，直到它适合合适大小的矩形。在开始填写之前，画出矩形的轮廓是有帮助的。如果消息很长，将其分成方便大小的块。例如，1000 个字符的消息可以分成二十个 5×10 的块。

我们已经在第 4.3 节看到了路径置换的一个示例。消息是水平地从左到右跨行写入 5×5 网格中，然后垂直地从上到下沿列读出。水平和垂直是两种路径。以下是更完整的列表。

• 水平方向，从左到右，从右到左，或交替左右

• 垂直方向，从上到下，从下到上，或交替上下

• 对角线方向，从左上到右下，从左下到右上，等等，或交替

• 螺旋，从任何一个角向内或从中心向外，顺时针或逆时针

你可以从矩形的任何一个角开始，使用任何路径写入消息，并使用任何其他路径读出消息。这里是一个花式路径的示例：

消息将按照数字指示的顺序写入网格中，并按列读出，即 1、36、37、39、42、2、6、38，…

对于路线置换，Emily 只需要猜测您用来读取消息的路线。在 Emily 将消息填入矩形之后，可以通过检查来读取。请注意，对于 Emily 来说，您是将消息水平写入 5×6 矩形还是垂直写入 6×5 矩形都无所谓。同样，您是从顶行向下工作还是从底行向上工作也无所谓。Emily 无法区分这两者之间的差异。

路线置换评为一级。

7.2 纵列置换

纵列 置换 是置换密码的主力军。自 17 世纪以来，它一直被军队、外交官和间谍使用。该方法首次在约翰·法尔科纳（John Falconer）于 1685 年撰写的《密信解密》（Cryptomenysis Patefacta）一书中描述。1688 年的光荣革命之后，约翰·法尔科纳跟随詹姆斯二世流亡到法国，在那里去世，而第二版于 1692 年以新标题《解释和解密各种秘密写作规则》（Rules for Explaining and Decyphering all Manner of Secret Writing）出版之前已经出版。

纵列置换使用的密钥可以是混合顺序的连续数字字符串，也可以是关键字或密语，通过将字母按字母表顺序编号来将其转换为数字字符串。考虑关键字 SAMPLE。字母 A 在字母表中最早，因此编号为 1。字母 E 在字母表中次序排在第二，编号为 2。然后是 L、M、P 和 S。因此 SAMPLE 转换为字符串 6,1,4,5,3,2。如果同一字母出现多次，则按从左到右的顺序编号。例如，ANACONDA 变为 1,6,2,4,8,7,5,3。

将消息从左到右水平写入网格。列数等于密钥的大小。如果密钥是 SAMPLE，则有 6 列。如果密钥是 ANACONDA，则有 8 列。像这样在网格上方写下数字密钥：

根据数字密钥从顶部到底部垂直读取消息，从编号为 1 的列开始，EKFHE，然后是列 2，ESRAT，列 3，NROW，直至列 8，YCYI，如图所示。

合法接收者 Riva 需要做一点算术才能阅读此消息。密钥长度为 8 个字母，消息长度为 35 个字母。35 除以 8 等于 4，余数为 3。这意味着数组将包含 4 行完整的 8 个字母，加上 3 个字母的短行。Riva 应该在开始填写列之前画出此数组的轮廓，以便将正确数量的字符放入其中。

艾米莉，敌人的任务有点困难。技巧是将每列的字母垂直写在一条纸条上，然后将这些条纸对齐以确定列的顺序。她寻找那些匹配字母形成常见双字母组合的条纸对。当她找到一个好的匹配时，她尝试在这两个条纸之前或之后添加第三个条纸。一旦正确匹配了 3 或 4 个条纸，短单词就开始出现，任务变得容易起来。

艾米莉不知道关键字的长度，所以她需要猜测。她可能从 5 开始并逐渐增加。假设她已经增加到 8，正确的长度。像丽娃一样，她将 35 除以 8。她知道有 5 个由 4 个字母组成的短列，和 3 个由 5 个字母组成的长列。艾米莉的问题是在哪里开始和结束每个条纸，以便至少包含一个完整的列。

第一条纸条从密文的第一个字符开始，如果第一列读出的数组是长列，则必须是 5 个字母长。第二条纸条从密文的第五个字母开始，如果第一列是短列，则在第十个字母结束。对于第三和第四条纸条也是如此。然后，艾米莉将对其他 4 条纸条做相反的操作，从密文的最后一个字母向中心反向工作。

然后，艾米莉将匹配这些条纸，将它们相互滑动以确定正确的对齐方式。所有这些都是凭眼睛完成的，所以艾米莉必须熟记最常见的双字母组合和三字母组合的频率。这也可以通过计算机以简单直接的方式完成。

针对这种匹配程序的最常见对策是，发送者桑德拉从上到下读出一些列，从下到上读出另一些列。这意味着艾米莉需要一套读取反向的第二套条纸。然后她将有两倍多的条纸来尝试匹配。

如果数组是矩形，则所有列向下读取时，列置换评为二，如果不是，则评为三。如果网格是矩形，或者列很长并且交替方向读取时，列置换评为三，否则为四。

列置换是一种为任何类型的替换密码增加强度的经过验证的方法。列置换与混合良好的简单替换相结合评为五。当与混合良好的一般多表密码相结合时，评为七。如果两个密钥的长度互质，则组合最强。

加强柱形置换的最常见技巧是使一些行的长度不同。这样会让艾米丽难以确定条带应该从哪里开始和结束。有四种这样的想法。其中，编号（4）是最强的，因为它在中间的一个不可预测的点破坏了条带，而不是在末端。更复杂的空白模式可能在某些列中有 2 个或更多的空白。

这些变种的柱形置换评分为四，前提是艾米丽不知道模式。如果密钥很长，并且列中有可变数量的空格，那么变种（4）的评分将提高到五。法国人在一战结束时使用了这样的系统。据信德国人能够读取其中至少一部分消息，主要是因为法国人多次重复使用了他们的密钥。

对数字（3）的两个进一步变种，楼梯，是（5）当你到达右边缘时从第一列开始，形成一个斜线模式，和（6）当你到达右边缘时反向，创建一个燕尾或之字形图案。这些模式的优点是每一行的字符数除了最后一行可能不同外，其他都相同，这样瑞娃很容易计算行数。以下是这两种变体的示例。

你也可以有两个或更多不同宽度的分开的楼梯，或者在对角线和反对角线方向上有楼梯 ** 和 /。

当你解密使用任何这些柱形置换变种发送的消息时，如果你有任何难以计算需要多少行，或者最后一行有多长的困难，这里有一个技巧。数一下消息中的字母，并从左到右用那么多的小点填写数组，按照桑德拉用来书写字母的相同模式。然后在点上填写字母。

例如，在变种（2）中，假设你已经同意你将始终从第一行开始使用 7 个字母。密文（2）有 38 个字母，所以你在第一行放置了 7 个点，第二行放置了 8 个点，直到你总共放置了 38 个点。然后你开始在它们的正确列中填写字母，像这样替换点：

使用有黑色方块的另一种方法是用空值填充它们。空值应该选择成为不常见的字母对，以使艾米丽更难匹配列。最好使用常见的字母而不是罕见的字母，这些字母可能很容易被识别为空值。这是一个例子。

有空格的柱形置换评为三。有固定的空格模式，评分为四。

7.2.1 Cysquare

历史趣闻：在第二次世界大战期间，英国使用了这个想法的一个变体，称为Cysquare，由约翰·H·蒂尔特曼准将于 1941 年发明。Cysquare 是一个具有大量涂黑的列置换密码。英国发行了 26×26 网格的填充物，大约 60%的方块以随机模式涂黑。每页有不同的模式。消息被写入横跨行的白方块中，然后以某种顺序垂直读出。网格是正方形的，因此可以以任何方向使用。

关键是填充物中的页码、方向以及网格内的起始和结束位置。密码员会在页面上画线标记消息区域。使用不同的区域可以让页面用于多条消息。

缺点在于需要分发如此多的填充物。为了最小化填充物的数量，英国人每天将每页用于可能多达 50 条消息。这意味着要写得很淡并且擦拭多次。页面变得难以阅读，最终密码员拒绝使用它们。Cysquare 在 1944 年被放弃了。

德国人在战争结束前从 1944 年开始使用这些填充物之一，连同说明书一起。他们开始自己使用这个系统，直到战争结束。他们称之为Rasterschlüssel，意思是网格密钥。然而，德国人在选择黑白方块时做得不好。他们使用了太多相邻的白方块，因此当他们将条带匹配时，英国人可以识别出二元组和三元组。这些消息成为英国情报的宝贵来源。Cysquare 评分为七分。Rasterschlüssel 评分为四分。

值得注意的是，在计算机时代，黑白方块可以作为比特模式传输，网格可以是任意大小，并且网格可以针对每条消息进行更改。我建议使用 65%到 75%的黑方块。这样做，cysquare 将被评为八分。

有一个简化版本的 cysquare 可供手动使用，不需要印刷网格，并且允许您使用数字密钥指定哪些方块被涂黑。这里有两种Blackout置换密码的变体，一种是左右交替版本，另一种是阶梯版本。两者都使用数字密钥 3174255 进行涂黑。涂黑密钥可以是重复的密钥，或者可以由伪随机数生成器生成。您将使用单独的密钥指定读取列的顺序。

加强列置换的另一种方法是将文本分成不规则大小的块。例如，如果消息长度为 150，您可以将其分成 37、71 和 42 个字母的块。这种方法被评为四分。如果您为每个块使用不同的密钥，评分将提高到五分。

将栏式置换与任何类型的替换密码结合在一起会极大增强其安全性。即使与简单的替换结合，等级也会提高到五级，因为匹配条变得更加困难。哪个先做都没有关系。将通用多表密码与至少 12 列的栏式置换结合会将等级提高到七级，即使多表密码的周期只有 3。这是因为您基本上消除了匹配条的可能性。

7.2.2 单词置换

Word transposition 是一个基于单词而不是字母的具有历史重要性的栏式置换。这是美国内战期间联邦军队使用的主要方法。这个想法来自安森·斯泰格（Anson Stager），一个后来创立了西联电报公司的联邦电报员。联邦军队的通信受到高传输错误率的影响。在许多情况下，指挥官们会放弃电报，而只是派遣步行或骑马的信使。斯泰格意识到，发送单词而不是单个字母将减少错误率，并减少重发消息的需要。

联邦密码员将消息逐字从左到右写成矩形数组，然后使用各种路线读出，例如交替上下读取列，或者交替从数组的左半部分和右半部分取列。空单词被大量使用。这里是一个例子。请注意第三行是空的。列按顺序读取为 1,3,5,2,4。

7.3 双栏式置换

如其名称所示，双栏式置换 意味着连续进行两次栏式置换，最好使用两个不同的密钥。这消除了匹配条的可能性。值得注意的是，1934 年，所罗门·库尔巴克（Solomon Kullback）找到了一个通用解决方案，并由信号情报局发布。这本 31 页的书在 1980 年解密，并由爱琴海公园出版社出版。爱琴海公园出版社多年来一直是密码学书籍的宝贵资源。在其创始人韦恩·G·巴克（Wayne G. Barker）去世后的 2001 年后不久，该公司停业，书籍不再可用。我很高兴地说，www.openlibrary.org 现在有这些书籍（2019 年 7 月访问）。

我不会在这里重复库尔巴克的分析，除了说它是基于确定每个明文字母在密文中出现的位置。相反，我将讨论 3 种打败库尔巴克解决方案的方法。（顺便说一句，库尔巴克和我父亲上了同一所高中，只是早了 6 年。）

一个简单的方法是通过涂黑几个方块来改变网格的形状。这些方块可以形成一个矩形，或者在一个角落，甚至在网格的中间形成其他形状。这里有一些例子：

黑掉的部分在两个置换步骤中可以具有不同的大小、形状或位置。黑掉的部分的大小、形状和位置可以附加到密钥中，以便为每个消息使用不同的黑掉。具有黑掉的双栏置换等级为 Five。

相反的方法称为NullBlock，也很有效。您可以将一块空字符块插入中间密文或最终密文，或两者都插入。将空块添加到明文中并不有助于加密。块的大小和位置可以由数字密钥指定。这些应该在消息之间变化。

将任何置换密码与任何替换密码结合使用会增强两者的安全性。双栏置换与简单替换的组合等级为 Six。双栏置换与通用多表替换的组合等级为 Eight。

7.4 循环栏置换

栏置换的另一种变体是循环栏置换。它有两种变体，水平循环和垂直循环。水平循环需要两个密钥，一个用于循环行，一个用于确定列顺序。首先，从左到右将消息写入矩形块的行。接下来，在行的左侧写入循环密钥。如果行数多于此密钥的长度，则根据需要重复使用该密钥。如果循环密钥是一个词或短语，请使用字母顺序将其转换为数字。

将循环密钥转换为数字形式后，将每行向左循环移动所指定的位置数。然后按列密钥指定的顺序垂直读出字母。以下是使用循环密钥 CYCLES 和列密钥 PAULREVERE 的示例。

解决栏置换所使用的匹配纸条方法也适用于循环栏置换。这只是稍微困难一点，因为每行的最后一个字母与第一个字母相邻，可能形成低频的二元组。这对 Emily 来说最多只是一个轻微的阻碍。具有水平循环的栏置换等级为 Three。

垂直循环类似。不是将块的行向左循环移动，而是将块的列向上循环移动。以下是使用关键字 CYCLE 来循环列和使用密钥短语 PAULREVERE 来选择列读取顺序的示例。

这种密码仍然可以通过匹配纸条来解决，就像普通的栏置换一样，但 Emily 需要为每个列使用两条纸条，一条用于顶部部分，一条用于底部部分。当每列循环时，某些字符从列的顶部移动到底部，并成为新的底部部分。剩下的字母向上移动，并成为新的顶部部分。在例子中，左列 ODYTEL 向上移动 1 个位置，所以 DYTEL 成为新的顶部部分，O 成为新的底部部分。这些部分需要放在不同的纸条上，因为 Emily 不知道这些字母是来自长列还是短列。这使得匹配过程变得相当困难。带有垂直循环的栏置换被评为 Four。

在这个区块上可以执行垂直和水平循环。这与双栏置换的强度相当。但请记住，你的密码越复杂，花费的时间就越长，而且正确地加密和解密也就越困难。双循环栏置换 被评为 Five。

7.5 随机数置换

让我们来看一个完全不同类型的置换。这种置换不涉及任何形式的数组或网格。相反，它只是随机对消息中的字母进行编号。

你可以使用任何随机数生成器。第十三章中介绍了几种随机数生成器。到目前为止，我只描述了第 4.5.1 节中的链式数字生成器，所以让我们使用那个生成器来说明。为消息的每个字母生成一个随机数字，像这样：

首先取所有从左到右编号为 1 的字母。这些是 C、V 和 I。

接下来取所有编号为 2 的字母。这些是 A、O 和 L。

然后取所有编号为 3 的字母，即 N、E、E 和 M。

持续这样做，直到所有的字母都被取走。

要解密这条消息，Riva 首先会生成随机数字。有三个 1，所以她会在三个 1 下面写下密文的前 3 个字母 CVI，像这样：

Riva 会将密文的下一个 3 个字母 AOL 写在 2 下面，像这样：

以此类推。

随机数置换被评为 Four。可以通过尝试所有可能的随机数生成器种子来破解它。

通过使用更长的种子或通过以 1、2、3、…以外的顺序选择明文中的字母来增强密码。 这相当于对随机数生成器的输出应用简单的替换。 例如，如果您想从标记为 4 的字母开始，那么您将把所有的 4 改为 1。 如果接下来想要取出所有标记为 7 的字母，那么您将把所有的 7 改为 2，依此类推。 然后按照描述的方式进行。 这将使可能的密钥数量增加到 10！，即 3,628,800。

通过这种改进，链式数字置换评级为五。 对于计算机版本，其中随机数生成器产生随机字节，该方法评级为七，因为重新排列 256 个不同字节的可能顺序太多。

7.6 选择器置换

由于我们正在研究随机数，让我们看看基于随机数的另一种置换密码，即选择器置换。 思路是将消息分成大致相等的部分，然后使用随机数序列合并这些部分。

假设明文有 100 个字符，你想将其分成 3 部分。 假设你有一个随机数生成器，以相等的概率产生数字 0、1 和 2，并且你已经选择了一个种子，它作为置换的密钥。 你需要知道如何将消息的每个部分做多大。 这很容易做到。 只需生成前 100 个随机数字，并计算产生的每个数字的数量。 假设有 36 个零，25 个一和 39 个二。 你将消息切成 3 部分，P0 有 36 个字母，P1 有 25 个字母，P2 有 39 个字母。

加密很容易。 每当生成器产生一个 0 时，从 P0 中取下一个字母。 每当生成器产生一个 1 时，从 P1 中取下一个字母。 每当生成器产生一个 2 时，从 P2 中取下一个字母。 解密甚至更容易，因为 Riva 不需要知道每个部分有多大。 每当她得到一个 0 时，她将下一个字母放入 P0 中。 每当她得到一个 1 时，她将下一个字母放入 P1 中。 每当她得到一个 2 时，她将下一个字母放入 P2 中。 然后她连接这 3 个部分，或者简单地忽略换行符读取消息。

当只用 2 部分完成时，Emily 可以轻松重构消息。 评级为一。 用 3 部分时稍微困难，评级为二。 用 20 个或更多部分时，评级为五。

7.7 密钥置换

有时，逐块移位消息是首选。用于置换块的最佳选择是 主要置换。在消息的字符上方写下数字密钥，然后将每个字符移动到其密钥编号指示的位置。在此示例中，块大小为 8，数字密钥为 41278563。第一个字母 R 的密钥编号为 4，因此将 R 移动到块中的第四个位置。第二个字母 U 的密钥编号为 1，因此将 U 移动到块中的第一个位置，依此类推。

主要置换可以用于明文、密文或两者。仅使用主要置换是弱的。根据块大小，主要置换的等级从一到三。

*****让我们深入了解置换。在数学中，置换被称为 排列。这里有一个例子。我用十六进制数字 A、B 和 C 来表示数字 10、11 和 12。在密码中，这些数字将代表被置换的位、字母或其他单元。

顶行是标准的。它表示置换之前的原始顺序。第二行是置换后的顺序。在本节的后面，第二行将用于描述置换。

在此置换中，位置 1 的数字移动到位置 4，位置 4 的数字移动到位置 7，位置 7 的数字移动到位置 12，位置 12 的数字移动到位置 3，位置 3 的数字移动到位置 1，完成循环 1➔4➔7➔C➔3➔1。循环可以表示为 (1,4,7,12,3)。

不在此循环中的第一个数字是 2。从位置 2 开始，我们找到循环 2➔A➔6➔9➔B➔8➔5➔2，可以表示为 (2,10,6,9,11,8,5)。整个置换可以表示为 (1,4,7,12,3) (2,10,6,9,11,8,5)。

这两个循环的周期分别为 5 和 7，因此此置换的周期为 35。也就是说，如果你将此置换一直应用到一个由 12 个字母组成的块上，它将产生 35 种不同的字母置换，而第 36 种置换将与原始明文相同。

假设你想要生成一个强大的块置换密码，其中每个块都有不同的置换。对于每个块分别应用先前的置换不足够，因为它每 35 个周期就重复一次。可以通过使用两个不同的置换并交替使用来解决这个问题。

让两个置换分别是 A 和 B。如果 A 和 B 被适当选择，那么你可以生成大量不同的置换 A、B、AA、AB、BA、BB、AAA、AAB、ABA，…。

理解排列的循环结构变得很重要。假设你选择了排列 (1,4,7,12,3) (2,10,6,9,11,8,5) 和 (1,4,3,12,7) (2,10,9,6,5,11,8)。这两个排列以相同的方式划分了 12 个单位的块，即 [1,3,4,7,12] 和 [2,5,6,8,9,10,11]。当你交替使用这两个排列时，[1,3,4,7,12] 的分区将与 [2,5,6,8,9,10,11] 的分区分别排列。也就是说，这两组数字之间没有相互作用。为了获得长周期，第二个排列的每个循环应尽可能与第一个排列的每个循环重叠。下面是一组适合的排列。

(1,4,7,12,3) (2,10,6,9,11,8,5)

(1,10,8) (4,6,5,12) (2,11,9,7,3)

这个转位密码被评为三。它可以通过尝试所有 12! 种可能的排列来简单解决第一个块。这只有 4.79×10⁸。对于为第一个块生成合理文本的每个排列，艾米莉可以尝试第二个块的 12! 种排列。实际上，这并不需要 (12!)² = 2.29×10¹⁷ 次尝试，因为仅查看块的前 3 或 4 个字符就可以消除许多不合理的组合。事实上，通过手工方法解决这个密码是可行的。随着块大小的增加，难度增加得很慢。

有几种增加密钥置换安全性的方法。一种方法是重叠块。例如，如果块大小为 16，则在消息中不是从位置 1、17、33、… 开始块，而是从位置 1、9、17、25、33、… 开始块。这样，每个块与前一个块重叠 8 个单位，并且与后一个块重叠 8 个单位。消息的最后 8 个单位可以与前 8 个单位组合成一个环绕块。这个密码被评为四。

重叠量可以是可变的。如果当前块从位置 P 开始，块长度为 L，则下一个块可以从位置 P+1 到位置 P+L 的任何位置开始。这个密码被评为五。如果使用两个不同的转位，并随机选择，评分将提高到七。

加强块置换密码的第二种方法是通过组合置换。如果 T 和 U 是转置，则 T 和 U 的组合，表示为 TU，是通过首先执行转置 U 然后执行 T 而形成的。结果的转置与使用 T 转置 U 然后使用结果的转置转置文本相同。让我们试试一个例子。假设 T 是419628573，U 是385917462*。由于 U 是一个包含 10 个字符的块，您可以使用 T 来转置 U，就像您使用 T 来转置一个 10 字母的单词一样。将 T 写在顶行上用作置换键，并将 U 写在第二行上作为被转置的文本。结果的第一个数字是键中数字 1 下面的数字，即8（见阴影）。结果的第二个数字是键中数字 2 下面的数字，即1，依此类推。使用 T 来排列 U 得到812349675。

通过这种方式组合转置，您可以生成一个转置序列，U，TU，TTU，TTTU，… 。此序列的周期与 T 的周期相同。对于块大小为 12，当循环的长度为 3、4 和 5 时，最长可能的周期为 3×4×5 = 60. 如果您的消息长于 60 个块，则可能需要更长的周期。这可以通过以某种重复或随机模式排列转置与 U 或 T 之一来完成，例如 U，TU，TTU，UTTU，UUTTU，… 这可以生成一个非常大的不同转置集合，前提是 T 和 U 各自具有较长的周期，并且 T 的循环重叠 U 的循环，如前文所述。

您可以使用累积测试来测试循环是否重叠足够。从 T 或 U 的任何一个循环开始。这形成一个只包含该循环的集合。将与其具有共同元素的 T 或 U 的任何其他循环添加到该集合中。现在将具有与您已选择的循环具有共同元素的 T 或 U 的任何其他循环添加到此较大的集合中。继续这样做，直到没有更多的共同元素为止。如果循环集现在包含 T 和 U 的所有循环，则具有很好的重叠。如果您决定使用超过两个转置，比如 T，U 和 V，则 T 和 U 应该重叠，T 和 V 应该重叠，U 和 V 也应该重叠。

这里有一个例子，使用本节早些时候的一些转置，T = (1,4,7,12,3) (2,10,6,9,11,8,5)，U = (1,10,8) (4,6,5,12) (2,11,9,7,3)。从循环(1,4,7,12,3)开始。

(1,4,7,12,3)

这个与循环 U 的(1,10,8)共有元素 1，因此将该循环添加到集合中。

(1,4,7,12,3) (1,10,8)

这个与循环 U 的(4,6,5,12)共有元素 4，因此将该循环添加到集合中。

(1,4,7,12,3) (1,10,8) (4,6,5,12)

依此类推。因为这将包括 T 和 U 的所有循环，它们是很好的重叠对，当它们组合时会产生非常庞大的转置家族。******

7.8 分半置换

分半 置换 是我发明的一种计算机技术，使用二进制密钥交换可能是位或字节，或者可能是十六进制数字的单元。IBM 在公司的发明披露公告中发布了这一技术，并考虑将其纳入数据加密标准（DES）中。分半置换作用于块的大小为 2 的某个幂次方，通常为 32 或 64 个单元。对于 n 个单元的块，密钥将有 n-1 位。

让我们以 16 个字符的块大小为例。明文是乔治·华盛顿。置换将使用一个 15 位的密钥。密钥的第一位确定了块的左右 8 单元半部分是否交换。0 表示不交换，1 表示交换两部分。接下来的 2 位密钥位确定了这些半部分的 4 单元是否交换。如果密钥的第 2 位是 1，则块的第一季度与第二季度交换。如果密钥的第 3 位是 1，则块的第三季度与第四季度交换。密钥的接下来的 4 位确定了这些季度的半部分是否交换。例如，如果密钥的第四位是 1，则块的第一八分之一与第二八分之一交换。最后的 8 位控制了块的 16 分之一是否交换。例如，如果密钥的最后一位是 1，则块的最后 2 个单元，第 15 和第 16 个单元，字母 O 和 N 被交换。

要解密这个置换，步骤必须按相反顺序进行。也就是说，首先应该交换单元，然后是对、四个一组等。

7.9 多次变位

解决置换密码的一般技术，适用于许多类型的置换，即使类型未知，也是多次变位。要使用这种技术，您需要拦截几条相同长度的消息。如果这些消息使用相同的密钥进行置换，那么每条消息的第一个字母将在所有密码文本中的相同位置，第二个字母将在所有密码文本中的相同位置，依此类推。

我们可以利用这一事实。用所有密码文本中的第一个字母制作纸条 1。用所有密码文本中的第二个字母制作纸条 2，依此类推。制作与每个密码文本长度相同的纸条。这些纸条可以像解决列置换时那样匹配。可用的消息越多，纸条就越长，成功的机会就越大。通常认为需要至少 3 条消息。

让我们看一个例子。假设我们有这 3 个密码消息：

消息长度为 12。右侧显示了 12 条条带。

消息（1）包含一个 K。可能在 K 之前的字母有 C 和 N。消息（1）各包含一个。消息（2）包含一个 D。在 D 之前可能的字母是 N。消息（2）包含一个 N。让我们检查这些是否是合理的选择。我们有

在消息（2）中，最有可能在ND之前的字母是A或E。这给出 3 种可能性：

将这 3 个选择与剩下的 9 条纸条进行匹配，最佳匹配是与第 4 条纸条。

这与我们之前已经组合的第 5 列和第 10 列非常匹配。

现在这 3 条消息很容易完成，（1）黎明时攻击，（2）发送更多弹药，和（3）立即见我。

第八章：杰斐逊轮式密码

本章包括

• 托马斯·杰斐逊的轮式密码

• 使用已知单词解密轮式密码

• 当不知道任何单词时解密轮式密码

托马斯·杰斐逊（Thomas Jefferson）在 1790 年至 1793 年间发明了杰斐逊轮式密码，当时他担任乔治·华盛顿（George Washington）的国务卿。该装置由直径为 1/8 至 1/4 英寸，长为 6 到 8 英寸的铁棒或纺锤和直径约为 2 英寸，厚约为 1/6 英寸的 36 个木制圆盘组成。每个圆盘在中心都有一个与棒相同大小的孔，以便所有圆盘都可以紧密地放在棒上，形成一个木制圆筒。圆盘的平面面对着彼此，外圆的圆边可见。棒的一端有一个类似钉头的头部。另一端有螺纹，以便螺母可以拧紧到棒上，将圆盘牢固地固定在位。

圆盘的平面侧编号为 1 到 36。外圆边被分为 26 个相等的部分。字母表的 26 个字母以某种混乱的顺序写入或刻在这些 26 个部分中的每一个中，每个圆盘的顺序都不同。棒上圆盘的顺序是密码的关键，这种密码现在被称为复用密码。

这是位于马里兰州福特米德（Fort Meade）的国家密码博物馆（National Cryptologic Museum）展示的一台 26 片杰斐逊密码轮的复制品。（照片由 Daderot 拍摄，根据知识共享 CC0 1.0 许可证发布。）

使用该装置对消息进行加密的方法是首先按照密钥指定的顺序将圆盘放在轴上。螺母松开，以便可以转动各个圆盘。消息的第一个字母在第一个圆盘上找到，然后转动第二个圆盘，使消息的第二个字母紧挨着第一个字母。然后转动第三个圆盘，使消息的第三个字母紧挨着第二个字母，依此类推，直到消息的前 36 个字母排成一行。然后拧紧螺母以固定它们的位置。

转动圆筒，还有其他 25 行字母，所有这些都是无意义的混乱。桑德拉可以选择其中任意一行作为密文。里瓦重复这个过程，在圆筒的一行上设置密文。很明显，其他 25 行中哪一行是预期的信息。

杰斐逊显然从未将这种密码投入使用。这个概念一直搁置，直到 19 世纪 90 年代初由Étienne Bazeries 重新发明。它于 1901 年被法国采用。Bazeries 的版本有两个改进。它有一个支架，这样设备可以放在桌子上进行双手操作，并且有一个导轨，帮助用户将字母对齐并选择用于读出密文的行。1914 年，上校帕克·希特发明了一种使用 25 个铝盘的密码版本，并于 1922 年被美国陆军采用为 M-94，于 1926 年被美国海军采用为 CSP-488。希特的版本只有 4.25 英寸长，足够小，可以放在口袋里，盘片的平面面上有凹槽和齿，使得它们在对齐后不会滑动。

这是国家密码博物馆展示的一张 CSP-488 的照片。

1916 年，Hitt 发明了密码的平面版本，并于 1935 年被军方采用，称为 M-138。这个版本是一个带有 25 个通道的平面铝板，上面放置着可以前后滑动的纸条，以模拟盘片的旋转。每个纸条上都有两份乱序的字母表。这个设备更加安全，因为纸条可以很容易地更换，甚至在必要时可以在野外手写。这很快被 M138A 或海军的 CSP-845 所取代，后者有 30 个纸条槽。设备附带 100 条纸条，用 2 位数字编号，因此任何消息使用了 100 条中的 30 条。这样可以产生 100!/70!=7.79×10⁵⁷种可能的密钥。

M-138A 中间有一个铰链，可以折叠以便携带。每半部分都有一个独立的导轨，用于对齐纸条并读出密码的 15 个字母。这些改进显著增强了密码的安全性。

军方在 1942 年或 1943 年左右放弃了这种带纸条的密码，但海军仍将其作为备用，以防止电力故障使得无法使用任何电子或电机式密码设备。

如果 Emily 没有设备的副本并且不知道字母表，解密多路复用密码是不可行的。如果 Emily 拥有设备，如果她知道一些可能的单词，解密就相对容易。当 Emily 拥有设备的副本并且知道一些可能的单词时，杰斐逊密码轮的评级为四到五。如果没有已知的可能单词，评级为六到七。Emily 拥有的密文越多，评级越低。相反，如果设备有很多额外的盘片，评级就会提高。例如，如果设备有 30 个盘片，用户可以从 100 个盘片中选择，评级可以达到八。对于非常短的消息，少于两倍盘片数量，除非 Emily 拦截使用相同密钥的多个消息，否则解密可能是不可能的。如果发件人每天只更改盘片的顺序一次，这种情况可能会发生。

8.1 已知单词解答

当你有足够的文本，并且知道至少部分消息时，可以解密使用杰斐逊密码轮加密的消息。通常，只要知道一个单词就足够了。假设你知道 Sandra 正在使用 M-94 设备，它有 25 个盘片，并且你拦截到了一条消息：

假设你还知道明文消息以 URGENT 开始。这已经被转换成了密文 CLPOXF。由于 URGENT 在一行上，而 CLPOXF 在另一行上，因此相应字母对之间的距离必须相同。让我们将带有 URGENT 的行称为第 1 行，假设带有 CLPOXF 的行是第 8 行。明文的第一个字母 U 和密文的第一个字母 C 分别来自第一个盘片的第 1 行和第 8 行。因此，在第一个盘片上，从 U 到 C 的距离必须为 7. 在第二个盘片上，从 R 到 L 的距离必须为 7. 在第三个盘片上，从 G 到 P 的距离必须为 7，E 到 O 也是，N 到 X 也是，T 到 F 也是。

搜索的最简单方法是依次尝试从 1 到 25 的每个可能的距离。从距离为 1 开始。找出所有距离 U 到 C 的距离为 1 的盘片。换句话说，U 的下一个字母是 C 的盘片。如果没有这样的盘片，那么你知道距离不是 1. 然后找出所有距离 R 到 L 的距离为 1 的盘片。同样，如果没有，那么距离也不能是 1。

假设你已经找到了 12 组盘片，其中字母对的距离都是 1. 现在你需要测试这 12 组盘片，看看它们中是否有任何一组是正确的。假设第一组盘片是 18-4-21-9-13-11. 从密文的第二块开始测试，字母从 26 到 50. 这个块以 ESIWVI 开头。将盘片 18 设置为字母 E，盘片 4 设置为字母 S，盘片 21 设置为字母 I，依此类推。现在看其他 25 行。如果它们都是无意义的，比如 HNSAEI 或 TFPGUW，那么你就知道 18-4-21-9-13-11 不是正确的盘片顺序。另一方面，如果你看到一些像 NCONDI 这样的合理文本，它可能是 UNCONDITIONAL 的一部分，那么 18-4-21-9-13-11 可能是正确的盘片顺序。再次测试，使用以 GAFOEM 开头的密文的第三块。如果第三和第四块都导致合理的文本片段，那么 18-4-21-9-13-11 可能是正确的…但继续搜索，因为你可能会找到更好的盘片顺序。

如果你没有看到任何可能的文本片段，那么尝试其他 11 组盘片顺序。如果这些都不起作用，尝试距离为 2、距离为 3，… 直到距离为 25. 可能会有几百种盘片顺序和距离的组合需要测试。这很乏味，但手工仍然可行。如果没有任何组合有效，请返回查找其中 2 个测试给出合理文本的盘片顺序。

一旦你确定了前 6 个盘的最有可能的序列以及相应的距离，然后尝试将其扩展到第 7 个盘。对于每个已知的盘的选择，你已经知道了从明文到密文的距离，因此扩展过程会相当快速。

*8.2 仅密文解决方案

当没有已知单词时，也可以解密多重密码。这被称为仅密文解决方案。我是第一个找到这种解决方案的人（“解密多重密码的计算机方法。” Cryptologia 2 (1978 年 4 月), pp. 152-160）。在原始的 1978 年论文中，我使用了二元频率，并逐步发展到三元组。如今的计算机速度更快，存储更多，所以我们可以跳过二元组步骤。该方法假设你有一张表，列出了英语中每个可能三元组的概率。你可以自己编制这样一张表，或者只需从互联网上下载一个三元组表。以下是该方法的要点。

假设与之前一样，艾米莉正在使用具有 25 个密码字母表的 M-94 设备，并且我们拦截了至少 3 个区块或 75 个字母的消息。我们知道关于消息的一切就是它是用英语写的。例如，假设我们拦截到了

首先尝试前 3 个盘的所有可能选择。有 25×24×23 = 13,800 种这样的选择。对于每个选择，将盘设置为密文每个区块的前 3 个字母，即CLP，ESI和GAF。对于这些三字母组中的每一个，查看其他 25 行。这些行包含与密文三字母组对应的可能的明文三字母组。由于每个 3 行有 25 种选择，所以总的可能性数为 13800×25³ = 215,625,000。这可以很容易地通过台式电脑或甚至笔记本电脑处理。

对于每个 3 个盘和 3 行的组合，该组合的概率是 3 个明文三字母组的概率的乘积。等价地，概率的对数是 3 个三字母组概率的对数之和。这个想法是只保留最有可能的组合并丢弃其余的。例如，你可以只保留前 1%，或者你可以保留一定数量的好组合，也许是最好的 1,000,000 个。假设你选择保留前 2,000,000 个。

一种方法是生成所有 215,625,000 个组合，然后按概率对它们进行排序，并且去掉最低的 99%。这需要大量的存储空间。有更好的方法来做这件事。首先分配一个比你想要的组合数大 10%到 25%的表，比如说 2,500,000 个组合。开始生成这些组合并将它们放入表中。当表满了之后，需要将其减少大约 20%。

通过对表格进行排序并删除底部 20%，可以实现这一点。也就是说，你按照概率降序排序，然后将表格条目数量设置为 2,000,000。对 2,500,000 个项目进行排序比对 215,625,000 个项目进行排序要快得多，但有更快的方法。从表格中随机选择 10 个项目。（如果你不知道如何随机选择，那么选择距离表格 1/11、2/11、…、10/11 处的项目。）将这 10 个项目按照从最不可能到最可能的顺序排序。将这些排序好的项目命名为 a、b、c、d、e、f、g、h、i、j。设 P 为项目 b 的概率。删除表格中概率小于 P 的每个项目。

继续生成组合，但不要向表中添加任何概率小于或等于 P 的项目。每当表填满时，重复抽样、对样本进行排序并重新设置截止概率 P 的过程。

在所有这些步骤结束后，你将获得约 2,000,000 种由 3 个磁盘和 3 行组成的组合。下一步是将此扩展到 4 个磁盘。尝试所有 22 种可能的选择来选择第 4 个磁盘。这将给你约 44,000,000 个组合。现在查看由磁盘 2、3 和 4 形成的三元组。对于每种组合，将磁盘 1、2、3 上的三元组的概率乘以磁盘 2、3、4 上的三元组的概率，以获得所有 4 个磁盘上的四元组的近似概率。将对应于 3 个密文三元组CLPO、ESIW和GAFO的明文四元组的概率相乘。

这将为你提供 4 个磁盘和 3 行的 44,000,000 种组合的概率。同样，你可以保留最佳的 1% 来给你 440,000 组四元组。使用与三元组相同的方法。

以此方式继续获取五元组、六元组、七元组等。每次添加一个磁盘时，你可以保留的组合比上一次少。当你的组合数量少于 100 时，你可以通过眼睛直接选择出正确的组合，并手动完成解决方案。

可能导致此过程失败的一个问题是：即使在普通文本中，也可能出现在你的三元组表中概率为 0 的三元组。如果 Emily 使用了空值，这种情况可能经常发生。这可能导致合法明文被拒绝。

一种解决方案是调整三元组概率，使得 0 概率永远不会出现。让 P(x) 表示字符串 x 的概率。如果一个三元组，比如 XYZ，的概率为零，你可以使用 P(X)P(YZ) 和 P(XY)P(Z) 中较大的那个。我建议将这个值除以 3，比如说，因为 XYZ 从未在你的三元组计数中出现过。如果 XYZ 的概率仍然为 0，则使用各个字母。例如，将 P(XYZ) 设置为 P(X)P(Y)P(Z)/10。

另一种解决方案是不要将概率相乘，而是使用其他函数将它们组合起来。例如，你可以将概率的平方和相加。这将强烈奖励常见的三元组，而大部分忽略罕见的三元组。

如果所有这些方法都失败了，那么就从密文中的另一个起始点再次尝试该过程。例如，从第五个磁盘开始。

第九章：分数化

本章涵盖

• Polybius 方阵

• 将一封信拆分成较小的部分，如比特或十六进制数字

• 混合和重新组合这些部分

密码学的前两个基本工具是替换和置换，这些内容涵盖在第 5 至 8 章。密码学的第三个基本元素是分数化。这意味着将语言的正常单位，即字母、音节和单词，拆分为较小的单位并对这些单位进行操作。较小的单位通常是比特、十进制数字、十六进制数字或其他进制的数字。本章涵盖了使用 2、3、5、6 和 16 进制的数字进行分数化，以及其他形式的分数化。

9.1 Polybius 方阵

可能是将字母表示为较小单位的最古老方法是Polybius 方阵，我们在第 4.4 节中看到过。在这里，每个字母由两个基数 5 位数字表示，共有 25 种可能的 2 位数字组合。（希腊人没有 0 的表示，因此他们的数字从 1 开始。）

这是第 4.4 节的 Polybius 方阵。每个字母都用方阵中的坐标表示，即通过其行号和列号表示。例如，字母 P 在第 2 行第 5 列，因此表示为 25。需要时，为了清晰起见，也可以写成 2,5。

Polybius 方阵本身可以产生多种不同的密码。例如，它可以通过用方阵中右边的字母（U 变成V）、下面的字母（U 变成Z）、下面和右边的字母（U 变成S）或左边的字母（U 变成P）等方式产生简单的替换。这个想法可以通过改变方向来扩展为多表密码，比如向右、向左、向下、向右、向左、向下等。你也可以走 2 个字母的距离或使用象棋中的骑士走法。

Polybius 方阵也可以用于生成Polybius Ripple密码。首先，将消息中的每个字母替换为其坐标，简单地写在一行中。从此列表中的第二个数字开始，将前一个数字加到当前数字上。如果总和超过 5，减去 5 以保持数字在 1 到 5 的范围内。然后再次使用 Polybius 方阵将这些数字转换回字母。

Polybius 涟漪密码评级为三。通过使用不同的 Polybius 方阵将坐标转换回字母，可以加强密码。

让我们看一下基于 Polybius 方阵的几种手写密码，涵盖在第 9.2 至 9.7 节。我在第 9.8 至 9.11 节中介绍了一些额外的手写方法。然后我在本章的其余部分讨论了一些计算机方法。

9.2 Playfair

普莱费尔密码是由查尔斯·维特斯通（发音为 WHIT-stun）于 1854 年发明的。维特斯通在电气工程师中以发明维特斯通电桥而闻名，该电桥用于测量电阻。维特斯通和威廉·库克在塞缪尔·摩尔斯发明他的键式电报几年前就发明了指针电报。库克在英格兰商业化了指针电报，比摩尔斯在美国成立电报公司早了几年。

维特斯通的密码被称为普莱费尔密码，因为维特斯通的长相类似的朋友利昂·普莱费尔男爵（两人都有红头发，身高约 5’2’'）主张使用它，并说服英国外交部在外交通信中使用该密码。

历史插曲

由于这个密码并不被称为维特斯通密码，这使得维特斯通的名字可以用于他大约在 1860 年发明并在 1867 年巴黎世界博览会上展示的第二个密码。维特斯通密码机看起来像一个大口袋手表，由两个固定的硬纸板同心圆环和两个可移动的时钟指针组成，通过简单的钟表机制连接。内环可擦拭，每条消息都可以更改。这个环上有乱序的 26 个字母表，而外环有标准的 26 个字母表加一个空格，共 27 个位置。您将长时钟指针移动到外环上的明文字母位置，短指针移动到内环上的密文字母位置。当长时钟指针完成 27 个位置的一次旋转时，短指针也会移动 27 个位置，即完成一次完整的旋转再加上 1 个额外的字母位置。因此，短指针在每次旋转时都从不同的位置开始。相当于具有可移动环而没有指针的设备于 1817 年由军械长德西厄斯·沃兹沃斯制造，该设备基于托马斯·杰斐逊于 1790 年制定的计划，但维特斯通的名字永远与这个概念联系在一起。

照片由拉尔夫·辛普森提供。铭文如下

“密码学。C.维特斯通 Inv^r。”

普莱费尔密码基于波利比奥斯方阵，每次加密两个字母。也就是说，它加密的是双字母组。方阵可以通过使用第 5.2 节中的任何方法混合字母来准备。为了使字母适应 5×5 方阵，会省略一个低频字母，如 J、Q 或 Z。（在法语中，J、Q 和 Z 很常见，所以省略 W。在德语中，省略 Q、X 或 Y。）当省略的字母出现在消息中时，会选择其他字母替换它。在我们的例子中，每个 J 都被I替换。

下一步是将信息分成二元素，例如 ME ET ME TO MO RR OW。如果一个二元素是双字母的，则应该将其分开，通常是通过在中间插入一个 X 来实现。（这是不应该从方块中省略 X 的一个很好的理由。）另外，如果消息包含奇数个字母，则在末尾添加一个 X。消息变为 ME ET ME TO MO RX RO WX。现在我们准备好加密它了。

普莱菲尔有 3 条规则：（1）如果两个字母位于同一行，则每个字母都被其右侧的字母替换；（2）如果字母位于同一列，则每个字母都被其下方的字母替换；（3）对于所有其他字母，每个字母都被二元素的另一个字母所在的同一行中的字母替换。理解方块环绕，因此在第 9.1 节的方块中，Y 的右侧字母是 U，Q 下方的字母是 W。

这些规则可以用坐标来重新表述。让我们要加密的二元素是 r1c1 r2c2，因此第一个字母在第 r1 行第 c1 列，第二个字母在第 r2 行第 c2 列。现在这 3 条规则变为

1. 如果 r1 = r2，那么将替换为 r1，c1+1 r2，c2+1。

2. 如果 c1 = c2，那么将替换为 r1+1，c1 r2+1，c2。

3. 否则替换为 r1，c2 r2，c1。

让我们对我们的样本信息 ME ET ME TO MO RX RO WX 进行加密，看看这些规则是如何起作用的。第一个二元素是 ME。M 和 E 位于不同的行和不同的列，因此适用规则 3。M 位于第 2 行第 4 列，E 位于第 3 行第 2 列。因此，M 被替换为同一行的字母，即第 2 行，与字母 E 相同的列，即第 2 列。第 2 行第 2 列的字母是 S，所以 M 被替换为S。同样，E 被替换为第 3 行第 4 列的字母，即C。

同样地，ET 被DO替换，第二个 ME 被SC替换。字母 T 和 O 位于同一行，因此适用规则 1。它们被替换为其右侧的字母。T 被N替换，O 被Q替换。所以 TO 被替换为NQ。

MO 按照规则 3 进行。它被替换为SR。R 和 X 位于同一列，因此适用规则 2。RX 被替换为XM。RO 和 WX 都使用规则 1，被替换为TQ和XY。因此整个消息变为SC DO SC NQ SR XM TQ XY，在重新分组后变为SCDOS CNQSR XMTQX Y。

这里有一些图表可以帮助你形象化地理解大二元素 LY、TO 和 RX 是如何被加密的。

普莱菲尔密码一直被军事和外交用途使用，至少持续到 1960 年。接下来，让我们简要地看一下普莱菲尔密码如何被解密。

9.2.1 解密普莱菲尔密码

请注意，每个字母只能由其所在行上的其他 4 个字母和其下方的字母替换。对于每个字母，在网格中有其他 24 个字母。其中，只有其所在列中的 4 个字母会导致该字母被其下方的字母替换。因此，被下方字母替换的概率为 4/24，或 1/6。因此，它被其所在行上的另一个字母替换的概率为 5/6。

由于方格中有 5 行，而英语字母中频率超过 5% 的有 9 个字母，因此至少有几行包含至少 2 个高频字母。如果这样的行少于 4 行，则必须至少有一行包含 3 个高频字母。这些行中的其他字母在密文中将比任何其他字母更频繁地出现。如果您有足够的密文，那么密文中出现频率最高的 3 到 5 个字母很可能在方格的同一行上。

如果我们去除包含这些字母的所有双字母组合，那么剩余双字母组合中出现频率最高的 3 到 5 个字母很可能在方格的同一行上。知道了 5 行中的 2 行上的高频字母就足以开始重建方格了。下一步是尝试放置一些可能的单词。

Playfair 密码的评级为三。有几种方法可以增强 Playfair 密码的强度。我就提几种。

9.2.2 强化 Playfair 密码

这里有几种更强的 Playfair 密码变体。

Nullfair 或 nofair

在密文中可以按照重复的间隔添加空值，就像这样：

Nullfair 的评级为五。

Playfair+1

这种超级简单的增强方式在 Playfair 密文中添加了重复的二进制密钥。在有 1 位的地方，使用字母表的下一个字母。如果二进制密钥的长度为奇数，则 Playfair+1 更强大。

Playfair+1 的评级为五。 Playfair+1 也可以用三进制数完成。加法密钥中的数字保持较小，因此可以在脑中进行加法，而不需要表格。

双 Playfair

Playfair 密码可以通过两次应用来加强。在第二轮中，成对字母应跨越第一轮创建的双字母组合。 (1) 使用 Playfair 密码对消息进行加密。 (2) 将第一个字母移到末尾，将最后一个字母移到开头，或在两端都添加一个空值。 (3) 应用另一轮 Playfair。如果第二个 Playfair 密码使用了不同的混合字母表，则这是最强的。双 Playfair 的评级为六。

Playfair 涟漪

这是双 Playfair 的一种变体，只需通过消息进行一次传递，而且只需要一个 Polybius 方块。让明文为 P[1]P[2]P[3]P[4] … 从左端开始，使用 Playfair 对明文二元组 P[1]P[2] 进行加密，产生密文二元组 C[1]C[2]。然后将 C[2]P[3] 作为第二个二元组进行加密，得到 D[2]C[3]。注意，D[2] 已经加密了两次。接下来，你将 C[3]P[4] 进行加密，得到 D[3]C[4]，依此类推，每一步向右移动一个字符。Playfair 波动被评为 Six。

由于密文的第一个字母 C[1] 和最后一个字母 C[n] 仅加密了一次，因此你可能希望将它们作为一个二元组加密以完成循环。

PolyPlayfair

使用两个不同的 Polybius 方块，并通过使用重复密钥在它们之间交替。例如，密钥为 11212 意味着在每个 5 个二元组的周期中，第一个、第二个和第四个二元组将使用方块 1 进行加密，而第三个和第五个二元组将使用方块 2 进行加密。这可以扩展到三个或更多方块，相应的设置时间会更长。使用两个方块和不超过 10 位数字的密钥，PolyPlayfair 的评级为 Five。如果密钥是由 Chained Digit 算法生成的，当数字为 0 到 4 时使用第一个方块，当数字为 5 到 9 时使用第二个方块，评级会增加到 Six。（注意：使用链式数字序列的奇偶性具有更短的周期，因此它更弱。）

转位

使用 Playfair 密码对明文进行加密后，可以对结果的密文进行转置。转置可以像第 7.2 节的栏转置那样复杂，也可以像第 4.6.1 节的 Bazeries 类型 4 密码那样简单。使用栏转置，Playfair 评为 Seven。使用分段反转，Playfair 评为 Five。

9.3 双方块

Two Square 密码，有时称为 双 Playfair，是 Playfair 密码的改进版本。它是由法国业余密码学家费利克斯·玛丽·德拉斯泰尔（Félix-Marie Delastelle）发明的，并在他的 1902 年著作 Traité Élémentaire de Cryptographie 中描述。顾名思义，它使用两个 Polybius 方块而不是一个，因此有两个混合字母表而不是一个。这两个方块可以水平并排放置，也可以垂直从底部到顶部放置。水平版本如图所示。在此示例中，使用关键词 FIRST 和 SECOND 混合了两个方块，并且省略了字母 Q 以适应 5×5 网格。

与 Playfair 一样，消息每次加密 2 个字母。也就是说，Two Square 加密双字母组。要加密双字母组 SO，我们在左方块中找到 S，在右方块中找到 O。S 的替代字母是右方块中与 S 同一行且与 O 同一列的字母，即T。O 的替代字母是左方块中与 O 同一行且与 S 同一列的字母，即K。因此，双字母组 SO 变成了TK。

与 Playfair 不同，不需要分开双字母。两个字母可以在两个方块的不同行上。例如，SS 变成MK。在大多数情况下，密文中的双��母不会对应于明文中的双字母。

这里是替换过程的可视化展示。

Two Square 密码的一个重要弱点是，当一个双字母组的两个字母在网格中的同一行时，替代字母就是这两个字母的反向。例如，ST 会变成TS。这种弱点被称为透明性，有时会导致整个单词泄露出来。例如，SU ND AY 会变成US DN YA。

为了防止这种情况，我提出了这个相同行规则：当两个字母在同一行上时，它们被它们下面的字母替换，必要时回到顶行。例如，ST 现在会变成DY，VI 会变成FP。

使用相同行规则，Two Square 评级为四。将这种变体称为Two Square B。

德国人字面上采用了“双 Playfair”这个名称。他们使用了 Two Square 密码对每个双字母组进行加密，然后再次使用相同的两个方块进行加密。结果基本上是一个通用的双字母替换（第 6.5 节）。

加强 Playfair 密码所使用的方法也可以用于加强 Two Square 密码，比如TwoSquare+1和Two Square Ripple，评级相同。这里是一个额外的变体。

Playfair TwoSquare

Two Square 密码使用了两个 Polybius 方块。这两个方块中的任何一个都可以用于 Playfair 密码。这提示了一种混合方法，将 Playfair 和 Two Square 结合起来。同样，我们将使用一个数字密钥来控制每个连续双字母组的加密。1 表示使用左方块中的 Playfair 加密双字母组，2 表示使用右方块中的 Playfair 加密双字母组，3 表示使用 Two Square 或 Two Square B 加密双字母组。最好是数字密钥至少包含每个数字。由于 Two Square 比 Playfair 更强大，3 应该比 1 或 2 在密钥中更频繁出现。大约 50% 是合适的。Playfair TwoSquare 评级为六。

9.4 三方块

Three Square 是我的独创想法。否则，它没有特别的优点。我在这里包括它只是因为我在为这本书做研究时阅读的一本书说 Two Square 不能扩展到超过两个方块。我喜欢挑战。

顾名思义，Three Square 使用三个 Polybius 方格。这些方格应该与独立的密钥混合得很好。Three Square 每次加密 3 个字母，也就是加密三字母组合。这比 Two Square 更强大。

基本思想是，每个字母都被其右侧方格中的一个字母替换。替换字母与原字母在同一行，但在下一个三字母组合中的列中。

假设我们希望加密三字母组合 THE。第一个字母是 T，第二个字母是 H，第三个字母是 E。我们使用第一个方格中的 T，第二个方格中的 H 和第三个方格中的 E 进行加密，就像这样。

T 的替代字母位于包含 T 的行，以及第二个方格中包含 H 的列，所以 T 被替换为V。H 的替代字母与第三个方格中包含 E 的列上的 H 在同一行，所以 H 被替换为R。E 的替代字母与第一个方格中包含 T 的列上的 E 在同一行，所以 E 被替换为Z。因此，THE 变成了VRZ。

这可以如下图所示：

解密是相反的过程。由于密文三字母组合VRZ的第一个字母来自第二个方格，我们从第二个方格开始解密，像这样：

Three Square 比 Two Square 更容易出现字母位于同一行的问题。在 XYZ 这样的三字母组合中，可能出现 X 和 Y 在同一行，Y 和 Z 在同一行，或者 Z 和 X 在同一行。这需要额外的两条规则来防止透明度，其中一个字母表示它自己。

规则 1： 如果三字母组合中连续的两个字母位于同一行，则这两个字母中的第一个被加密为第二个字母的右侧字母，如果需要则绕到左侧列。例如，在三字母组合 SUB 中，S 在第一个方格的顶行，而 U 在第二个方格的顶行。因此 S 被替换为V而不是U。类似地，在三字母组合 LET 中，T 在第三个方格的第三行，而 L 在第一个方格的第三行。所以 T 被替换为G而不是L。

这个图示说明了规则 1。没有规则 1，在三字母组合 SUB 中，S 将被U替换。相反，它被中间方格中 U 右侧的字母替换，即V。没有规则 1，在三字母组合 LET 中，T 将被L替换。相反，它被左方格中 L 右侧的字母替换。这从第 5 列绕到第 1 列，其中有字母G。

规则 2： 如果三元组中的所有三个字母都在同一行上，那么每个字母将被其下方的字母替换，如果需要，将回到顶行。因此，FUN 将被替换为AZV，而 WRE 将被替换为IXL。

根据这些规则，三方格被评为五。

Playfair ThreeSquare

三方格密码使用三个波利比斯方格。这些方格中的任何一个都可以用于 Playfair 密码。这表明了一种混合方法，将 Playfair 和三方格密码混合在一起。您可以使用数字密钥，例如 1,4,1,3,4,2,4 来控制每个连续的二元组或三元组的加密方式。1 表示使用第一个方格中的 Playfair 将下一个 2 个字母加密为二元组。2 表示使用第二个方格中的 Playfair 将下一个 2 个字母加密为二元组。3 表示使用第三个方格中的 Playfair 将下一个 2 个字母加密为二元组。4 表示使用三方格将下一个 3 个字母加密为三元组。最好是数字密钥至少包含每个数字。由于三方格比 Playfair 更强大，数字 4 应该比数字 1、2 或 3 更频繁地出现在数字密钥中。大约 50% 的频率是合适的。也就是说，4 应该与 1、2 和 3 的总和一样频繁出现。同样，生成从 1 到 6 的随机数，并使用 4、5 或 6 进行三方格加密。

由于 Playfair ThreeSquare 混合了二元组和三元组，大约一半的二元组和三分之二的三元组不会落在偶数边界上。这意味着强度的增加比 Playfair TwoSquare 的增加更大。Playfair ThreeSquare 被评为七。

可以将 Playfair、Two Square 和 Three Square 结合成一个更复杂的密码，毫无疑问具有更强的强度，但是 Playfair ThreeSquare 已经在推动人类代码员的极限。速度和准确性都会受到影响。

还有一种相反的方法，我称之为跨三方格。将明文分组成包含每行四个 3 个字符块的行。使用三方格密码对每个块进行加密。现在，取第一个块的最后一个字母和第二个块的第一个字母，并使用第一个波利比斯方格的 Playfair 密码对该二元组进行加密。取第二个块的最后一个字母和第三个块的第一个字母，并使用第二个波利比斯方格的 Playfair 密码对该二元组进行加密。取第三个块的最后一个字母和第四个块的第一个字母，并使用第三个波利比斯方格的 Playfair 密码对该二元组进行加密。这样可以提高三方格密码的强度，而不会增加太多复杂性或时间。始终使用相同行规则。

9.5 四方格

四方密码是由 Félix-Marie Delastelle 大约于 1890 年发明的，并在他于 1902 年去世后的 3 个月出版的书籍Traité Élémentaire de Cryptographie中描述。Delastelle 在四方密码之后发明了双方密码，作为简化且稍微不那么安全的版本。然而，使用第 9.3 节中描述的同行规则，可以认为这两种密码的强度相等。

如其名称所示，四方密码利用四个 Polybius 方块。其中两个方块包含标准字母表，另外两个方块包含使用独立密钥混合的字母表。消息以两个字母为一组进行加密，即四方加密二元组。

这是一个示例排列。

加密使用熟悉的矩形方案。您在标准字母表中定位两个明文字母，并将它们替换为矩形对角线上的字母，如下所示：

由于两个明文字母永远不可能在 10×10 网格的同一行或同一列中，因此无需特殊规则或分隔双字母。唯一需要空字符的情况是为了完成最后一个双字母组合。四方加密的评级为五。

循环方法

要获得更大的强度，您可以使用类似于第 4.6.1 节中的分段反转的简单换位。此换位使用重复的数字密钥，例如 1、3、1、4、2、6。将密文分成 7 个字符或任何其他奇数长度的块。在每个块的上方写下连续的密钥数字。然后将每个块左移其密钥数字指示的位置数。例如，如果密钥数字是 4，则将最左边的 4 位数字移动到块的右端。这是一个例子：

使用循环方法的四方加密的评级为六。

分半方法

加强四方加密的另一种方法是事先转置消息。假设消息是 AMBASSADOR WILKINS ASSASSINATED KABUL TODAY。这有 39 个字母。将 39 除以 2 并四舍五入得到 20。将消息写成两行，每行 20 个字母，并从垂直方向读取双字母组合。使用四方进行这些双字母组合的加密。

这些双字母组合不再具有正常的双字母组合频率或英语双字母组合的正常联系频率。使用分半方法的四方加密的评级为七。

9.6 双分

让我们再看一个基于 5×5 波利比乌斯方阵的历史手工密码。这是双重密码，也是在 19 世纪 90 年代由菲利克斯·玛丽·德拉斯特尔发明的。双重是一个 3 步密码，其中(1)字母被转换为它们的波利比乌斯坐标，(2)这些坐标被重新排列，(3)然后坐标被转换回字母。最初，德拉斯特尔将整个消息写出，坐标垂直写在每个字母下面，然后他将坐标对水平地读出，先横穿顶行，然后横穿底行。

现代方法是将消息分成固定大小的块。块大小应该是奇数，如 5、7 或 9。如果块大小是偶数，则艾米莉可以将块分成二元组。

第一步是将字母转换为波利比乌斯方阵中的坐标。假设块长度为 5。5 个明文字母可以表示为 X1、X2、X3、X4 和 X5。它们的行和列坐标可以表示为 R1C1、R2C2、R3C3、R4C4 和 R5C5。这些 R 和 C 符号各自是从 1 到 5 的数字，先是行坐标，然后是列坐标。这些坐标对是垂直地写在每个块的每个字母下面，像这样：

然后按照 R1R2、R3R4、R5C1、C2C3、C4C5 的顺序读取。这里是一个例子。使用关键词 SAMPLE 混合的波利比乌斯方阵对单词 MAJOR 进行了加密。

请注意，密文中的第三组字母坐标，R5C1，是一个行/列对。这意味着第三个密文字母将来自与第五个明文字母相同的行，R5，以及与第一个明文字母相同的列，C1。这个同时出现行坐标和列坐标的情况被称为自然。

由于方阵中每行有 5 个字母，每列有 5 个字母，所以第三个密文字母与第五个明文字母相同的概率为 1/5，第三个密文字母与第一个明文字母相同的概率也是 1/5。也就是说，R5C1与R5C5相同的概率是 20%，而R5C1与R1C1相同的概率也是 20%。在这个例子中，确实发生了这种情况。第五个明文字母是 R，第三个密文字母也是R。

现在看看第一个密文字母R1R2。这是一个行/行对，而不是一个行/列对。在这里，只有第一个坐标R1处于正确的位置，形成了一个行/列对。另一个坐标R2是列位置上的行坐标。这样的单一放置被称为半自然。它意味着第一个密文字母来自波利比奥斯方阵的与第一个明文字母相同的行。因此，第一个密文字母与第一个明文字母相同的机会为 20%。

第二、第四和第五个密文字母也是如此。它们中的每一个都落在明文字母的同一行或同一列中的一个。因此，它们每一个有 20%的机会与该明文字母相同。在这个例子中发生了这种情况，第二个密文字母J与第三个明文字母相同。

这是 bifid 密码的一个严重弱点，使得 Emily 能够猜测并放置可能的单词。另一方面，如果明文和密文字母不同，则知道它们位于同一行或列中。在本例中，第一个明文字母R1C1是 M，第一个密文字母R1R2是S。这意味着 M 和 S 必须在波利比奥斯方阵的同一行中。当 Emily 推断或猜测一个单词时，这提供了几个这样的等价物。这反过来又使得放置其他单词变得更容易。当积累了足够多的这些字母对时，Emily 可以重构方阵。

由于这些弱点，bifid 密码评分为三。

9.6.1 共轭矩阵 bifid

这些问题可以通过使用不同的 Polybius 方阵将坐标转换回字母来消除。例如，方阵 2 产生的密文是VBJEF。

两个单独的波利比奥斯方阵组成的双重 Polybius 方阵被称为共轭矩阵 Bifid。在这个上下文中，矩阵只是指一个字母或字符的矩形数组。共轭矩阵 bifid 密码评分为五。

有几种方法可以增强 bifid 密码的强度。一种方法是使用重复的数字密钥来改变块长度，例如 5、11、7。块长度将是该密钥的循环重复，即 5、11、7、5、11、7、5、… 如果您愿意，您可以通过使用链式数字生成器生成块长度，并将数字翻译为奇数块长度。一种可能性是

因此，如果生成器生成数字 3、6、2、7，…，那么块长度将为 11、7、9、9、…

使用短重复密钥和共轭矩阵的密码评分为六。使用长重复密钥或使用随机数生成器生成块长度的密码评分为七。

另一个类似的想法是从每个块的不同起点开始读出坐标。你可以使用一个数字密钥来指定起点的顺序。如果块的长度为 L，密钥中的每个数字可以是从 1 到 2L 的任何位置。从 1 到 L 的数字表示坐标顶行的起始位置，而从 L+1 到 2L 的数字表示底行的起始位置，就像这样：

坐标将成对地从左到右读取。这是使用数字密钥 4、9 读取坐标的顺序。起始位置 4 和 9 已经阴影化。

这种方法将评级提高到六。

加强双重栅栏密码的另一种方法是使用更强的置换来混合坐标。使用长度为 L 的标准双重栅栏将 2L 个坐标写入 2×L 块中。坐标被垂直写入块中，水平读出。我们将其识别为一个非常简单的路径置换，描述在第 7.1 节。在第七章中涵盖了几种更强的置换，尤其是列置换。这种密码的一个例子是由情报官尼布尔中尉发明并由德国人在第一次世界大战中使用的ADFGVX密码。在 ADFGVX 密码中，由字母 A、D、F、G、V、X 表示的坐标通过列置换混合，然后作为这些字母的字符串传输。这种密码的评级为五。

如果你使用更长的块，比如 20 个字符，那么将会得到 40 个坐标。（使用这种方法，块的长度可以是偶数也可以是奇数。）这足以有效地使用列置换来混合坐标。或者，你可以回到德拉斯泰尔的原始概念，并将整个消息的坐标作为单个块。无论哪种方式，使用共轭矩阵，此密码的评级为八。使用双列置换，密码的评级为十。假设有四个长的独立密钥和混合良好的字母表，这是一种无法破解的纸笔密码。称之为双列置换双重栅栏。

9.7 对角双重栅栏

对双重栅栏密码的变种是将波利比斯坐标垂直地写在每个字母下面，然后沿对角线从左下到右上（或从西南到东北）读取它们。这被称为左对角线或反对角线。（在纹章的冠上，它被称为邪恶的酒吧，并表示非婚生的出生。）对于最后一个字母，你会回到第一列（阴影部分的数字 1）。这样做的好处是没有自然数或半自然数可以帮助艾米莉猜测单词。这是一个例子。

对角 bifid 被评为 Four。与共轭矩阵一起，它被评为 Five。与共轭矩阵和定期变化的块大小一起，它被评为 Six。与古典 bifid 不同，对角 bifid 可以使用奇数和偶数块大小。

9.8 6×6 方阵

如果你的消息包含很多数字，使用 6×6 的 Polybius 方阵而不是 5×5 方阵可能会更有优势。6×6 方阵允许您使用完整的 26 个字母表以及从 0 到 9 的数字。不需要从字母表中省略 J 或 Q。如果你正在手动加密，这就需要额外小心地区分字母 O、I、Z、S 和 G 与数字 0、1、2、5 和 6。一些人采用特殊的惯例，例如在所有数字下划线。我觉得这样很麻烦且容易出错。我通常只是夸大区分这些字符与它们的同伴的特征，例如用额外宽的衬线写字母 I。

前面 5 节中的所有方法，即 Playfair、Two Square、Three Square、Four Square 和 Bifid，都可以与 6×6 方阵一起使用，以及它们的所有变体。

9.9 三重置

如果你喜欢方阵，那么立方体呢？另一种分数方法，也是在 1890 年代由 Félix-Marie Delastelle 发明的，是 Trifid 密码。与通过在基数 5（五进制数）中的两位数字来代表字母不同，每个字母由三位基数为 3 的数字（三进制数）表示。这给出了 3×3×3，或 3³，不同的 3 位数字组合。这足以表示字母表中的所有 26 个字母加上一个额外的字符。Delastelle 使用了一个 + 加号表示第 27 个字符。

额外的字符 + 可以用作标点符号的形式，或者它可能是一个信号，表示接下来的明文字母应该被解释为一个数字。对应关系 +A = 1, +B = 2, … , +J = 0 可以被使用。字母表的其余部分也可以被用作特殊字符。例如，+K 可以表示句号，+L 可以表示逗号，等等。

就像 2 位数字组合可以显示为 5×5 字母方阵一样，3 位数字组合可以显示为 3×3×3 字母立方体。每个三元组中的 3 位数字可以被解释为该字母位于的立方体中的坐标。这些坐标通常称为层、行和列。

这里是 27 个三元组合，按顺序排列，字母等效通过使用关键词 EXAMPLE 弱混合，并交替列。例如，字母 N 由三元组 102 表示，因此它将位于 3×3×3 字母立方体的第 1 层、第 0 行和第 2 列。

三方加密器的工作原理与双重加密器类似。明文按固定大小的块写入。大小可以是任何不是 3 的倍数的数字。将这 3 位数字垂直写在每个消息字母下面，然后水平分组读取。然后使用相同的等价关系将它们转换回字母。这里有一个明文为 SEND HELP，块大小为 4 的示例。

用于双重加密器的相同分析和技术也可以应用于 trifid，并且具有相同的评级。您可以使用两个单独的替换表将字母转换为数字，然后将数字转换回字母。您可以变化块的大小。您可以从每个块的不同位置开始读取数字。您可以使用强大的置换来混合三进制数字。

一个自然的问题是是否有与对角双重加密器类似的对角 trifid 加密器。对角双重加密器比原始双重加密器的优势在于，对角版本不会产生削弱原始版本的半自然数。在类似的对角 trifid 中，每组的中间数字将是第三自然数，因此失去了优势。然而，如果您使用两个不同的混合字母表，一个用于数字的书写，另一个用于读取它们，则自然问题会消失。带有两个字母表的对角 trifid 的评分为五。

9.10 三方加密器

当我在打前面关于 trifid 加密器的段落时，我意识到 3×3×3 的立方排列非常适合于描述第 9.3 节中描述的双重加密器的三维类比。在两个维度中很容易想象双重加密器，但在三个维度中很难想象一个立方体，因此我将仅根据坐标描述新的加密器。让我们将此加密器称为 三方加密器。

两方加密器一次加密两个字母，使用两个替换表，因此三方加密器会一次使用三个替换表加密三个字母。这里是使用关键字 COLUMBIA、STANFORD 和 HOPKINS 很好地混合了的三个表。这三个替换表分别标记为 S、T 和 U。这里的 S 表示替换（Substitution），T 表示表（Table），U 表示字母表中的下一个字母。

替换表对应字母表的 26 个字母和字符 + 与 27 个三元组。

与 trifid 类似，三方加密器首先将每个字母的 3 位数字三元组垂直写在其下方。第一个字母的 3 位数字来自替换表 S，第二个字母的 3 位数字来自表 T，第三个字母的 3 位数字来自 U。该模式在此处显示，并由三元组 FLY 进行说明。

然后从左到右读出数字，并将这些水平三元组转换回字母。使用表 S 转换顶行，表 T 转换中行，表 U 转换底行似乎很自然。然而，这会导致顶行与左列相同的概率为 9 分之 1，因此第一个明文字母将被自身替换。也就是说，S1S2S3 与 S1T1U1 相同的可能性为 9 分之 1。中行和底行也是如此。让我们将这种情况称为部分自然。

为此，第二行使用替换表 S，第三行使用表 T，顶行使用表 U。这样就消除了自然性。以下是模式。

由于手动加密时很难保持清晰，我建议在每个数字三元组上面写上替换表的选择。这类似于使用贝拉索密码（第 5.5 节）时在每个明文字母上写上密钥字母。以下是使用明文消息 FLY TO ROME 的三方块加密的示例。

三方块密码的评级为七。

有一种简单的方法可以加强三方块密码。不再像刚才那样使用三个替换表严格轮换地将三元组转换回字母，而是使用一个密钥来设置读出表的顺序。该密钥将由字母 S、T 和 U 以某种打乱的顺序组成，例如 SUTUTTUUSTS。这个密钥的长度不应该是 3 的倍数。我将这个变种称为三方块加密。以下是使用这个读出密钥对 FLY TO ROME 进行加密的方法。

使用三方块加密，大约有三分之一的字母会有部分自然性。也就是说，三个填写数字中的一个将与三个读出数字中的一个相同。然而，艾米丽不会知道哪些字母有这种缺陷，也无法利用它。

三方块加密的评级为九。

因此，你可能会说，是否可能将评级提高到十，而不使密码对手工使用过于复杂？感谢你的提问。首先，让我们将替换表的数量从 3 增加到 6。让我们称它们为 S、T、U、V、W 和 X。我们将不再使用严格的 STU、STU、STU…轮换写入三元组，而是使用另一个字母密钥，该密钥由这 6 个字母以某种打乱的顺序组成。填写密钥可以是 TWXUSTTVWV，读出密钥可以是 VWTXXSUSVTU。理想情况下，这些密钥的长度应该是互质的，并且两者的长度都不可被 3 整除。在这里，长度分别为 10 和 11。我们将这个密码称为三方块超级密码。这是一个使用明文 FLY TO NEW YORK 的三方块超级密码的示例。

三方块超级密码的评级为十。这是另一种不可破解的手工加密。

9.11 矩形网格

到目前为止，我们只讨论了字母的方形和立方体阵列。在密码学中，没有要求字母网格的所有维度都相同的限制。英文字母表有 26 个字母基本上是历史的偶然。如果我们使用 33 个字母的俄语字母表，我们可能会选择 4×8 或 5×7 的矩形。

如果我们想要所有 26 个字母的字母表，那么 3×9 或 4×7 的矩形可能更可取。这些给您提供了完整的 26 个字母的字母表，再加上一个或两个额外字符。我们之前已经讨论过这些额外字符的使用，例如用于在字母和数字之间切换。基于波利比奥斯方格的大多数密码与 5×5 方格一样适用于 3×9 或 4×7 的矩形，假设所有矩形都以相同的方向排列。这些是 Playfair、Two Square、Three Square、Four Square 和对角线 bifid 密码。

实际上，当与那些矩形一起使用时，这 5 种密码可能更强大，因为字母表中的每个字母都有更多可能的替代字符。使用 Playfair 或 Two Square 时的缺点是，两个字母在同一行的概率较高，因此它们将被其下方或右侧的字母替换。

下面是使用 3×9 矩形进行 Playfair 密码的示例：

9.12 十六进制分数

到目前为止，本章仅专注于手动方法。这意味着仅使用大写字母的小数组。对于计算机使用，通常希望使用完整的字母表，包括大写和小写字母、数字、标点符号、特殊符号、音标，以及可能是多个字母表。简而言之，您可能希望拥有计算机的完整文本功能。做到这一点的最简单方法是使用标准计算机代码之一，如 UTF-8 或 UTF-16，将每个字符表示为一个 8 位字节。

将 8 位字节分数化的一种自然方式是将其拆分为两个 4 位十六进制数字，或十六进制数字。所有基于波利比奥斯方格的分数化方法也适用于 16×16 方格，即 Playfair、Two Square、Three Square、Four Square 和 bifid。如果 16×16 方格使用大密钥混合得很好，那么这些方法比使用 5×5 方格的同一方法更强大。这是因为 256 个字符的排列方式远远多于 25 个字符的排列方式，即 8.58×10⁵⁰⁶与 1.55×10²⁵。

使用十六进制分数化的简单方法是：(1)通过使用混合得很好的密钥替换表将消息的字符转换为十六进制数字，(2)使用一些置换密码对这些数字进行混淆，然后(3)使用第二个混合得很好的密钥替换表将十六进制数字的对转换回字节。

最简单的转位法就是将第一个十六进制数字移到末尾，这样 12 34 56 78 就会变成 23 45 67 81。这可能被称为 Cycle Hex。它本质上是对角线的二重置位（第 9.7 节），只不过是在基数为 16 而不是基数为 5 下进行的。Cycle hex 评级为 Five。你也可以使用第 4.6.1 节描述的逐段反转置换来打乱字母顺序。这可能被称为 Piecewise Hex。它也评级为 Five。一种更强大的方法是使用列转位密码来打乱十六进制数字。这可以称为 Columnar Hex。它评级为 Seven。使用双列转位置换后，评级增至 Ten。

这些方法可以用于对任何计算机文件进行加密。但是，如果文件是纯文本，则可以进一步增强这些方法。纯文本通常会使用少于 256 个可能的字节值中的 100 个以下。其余的字符代码可以用于空值、双字母组、三字母组和第 6.4 节描述的其他用途。如果做得好，这会将 cycle hex 的评级提升至 Six，piecewise hex 的评级提升至 Six，columnar hex 的评级提升至 Eight。

9.13 位级分数化

分数化也可以用于表示消息中代表字符的各个位。长度为 N 的字符块将由 8N 位表示。这些可以以几种方式形成矩形，例如 2×4N、4×2N、8×N 和 N×8。例如，5 个字母的块将由 40 位表示，可以写成 2 行 20 位、4 行 10 位、8 行 5 位或 5 行 8 位。这对手工操作来说很麻烦，但在计算机上很容易实现。

这是一个示例，展示了如何将 5 个字符水平写入一个 5×8 的块中，然后垂直读出。此示例使用标准的 UTF-8 字符代码。例如，大写字母 A 表示为 01000001。明文是单词 DELTA。

位按列向下读取。由于每列只包含 5 位，因此每个密文字节必须跨越两列或更多列。第一个密文字节的 8 位位于列 1 和列 2 中，并用中等高亮度显示。第一列包含 00000，第二列的前 3 位为 111，因此密文的第一个字节为 00000111，或十六进制 07。这是控制字符 BELL，可以追溯到电传打字机时代，当时会发出退格铃声。它现在已经没有图形表示。我会用符号 ♪ 来代表铃声字符。

第二个密文字节来自跨越列 2、3 和 4 的较暗突出部分。第二列的最后 2 位是 11，第三列包含 00000，第四列的第一位是 0。结合这些，第二个密文字节为 11000000。这代表字符 À，是一个带重音符号的大写字母 A。

密文的第 3 和第 4 个字节是**“和x**，即双引号和小写字母 x。第五个字节来自第 7 和第 8 列，即 000 和 01001。字节 00001001 代表HTAB，或水平制表符，是看不见的。我将使用箭头头部►来表示它。因此密文是♪À“x►。

这看起来很神秘，但这种方法很弱，因为它在将明文转换为比特和将比特转换回字符时使用了标准字母表。它被评为一。如果这些步骤使用了两个独立的混合密钥字母表，则此密码只是共轭矩阵双字母变体（9.6.1 节）的二进制版本。这种方法可以称为Hex Rectangle。它与共轭矩阵双字母变体密码具有相同的评级，即五。

自然地将八个 8 位字节形成一个 8×8 比特方块。使用一个混合字母表将每个字符的 8 位写入方块中，并使用另一个混合字母表水平地读取它们。这只是十六进制矩形的一个 8×8 方块版本，评级为六。

9.13.1 循环 8×N

提高此密码的强度很容易。对于任何 N 个字符的块，垂直地将它们的 8 位表示写入 8×N 的矩形中。将每行循环地向左移动 0 到 N-1 位位置。例如，abcdefgh 循环左移 2 个位置将得到 cdefghab。然后垂直地读取每个 8 位列。这里有一个使用 8×8 比特方块的示例。每行都按其左侧指示的量向左循环。

这种密码已经达到了手工操作的极限。它需要 3 个密钥，即两个用于混合两个字母表的密钥，以及一个用于指定位移量的 8 位数字密钥。它可以称为Cyclic 8×N。当 N 为 6 或更大时，它被评为七。随着块大小 N 的增加，密码变得更强大。

当矩形是正方形时，你可以同时旋转行和列，得到一个Bicyclic 8×8密码。你应该交替方向进行。水平写入位，垂直循环位，水平循环位，然后垂直读取字符。Bicyclic 8×8 被评为八。

循环 8×N 密码可以重复以获得双循环 8×N密码。这需要 5 个密钥，即 3 个用于混合 3 个字母表的密钥，以及两个用于控制 2 轮移位的 8 位密钥。共有 5 个步骤。（1）使用第一个字母表进行简单替换。生成的 N 个字节被垂直地写入 8×N 位的矩形中。（2）使用第一个移位密钥循环移动行。（3）使用第二个字母表对 N 列执行简单替换。（4）使用第二个移位密钥循环移动行。（5）使用第三个字母表对垂直列执行最终的简单替换。注意，所有的移位都是水平的，所有的替换都是垂直的。双重循环 8×N 密码的评级为九。

如果需要，可以继续进行三重、四重等等。所有这些变化都可以通过周期性地或使用随机数发生器来变化块大小来进一步增强。

9.14 其他分数

在第 9.12 和 9.13 节中，我们看过将一个字节分成两个十六进制数字或分成八个单独的位。将 8 位分成许多其他方式，如 3,2,3。如果将每个字符的 3,2,3 位表示垂直地写下来，然后将 3 行按某个位置数循环向左移动，那么每一列仍然会有 3,2,3 位的分布，因此 8 位可以被转换回字节。这里是一个例子。每一行按左边显示的位置数循环左移，即分别为 1 个位置，3 个位置和 2 个位置。

这里明文 RETEAT 已经被转换成了密文**@w«θK_╝。我们称之为BitCycle Substitution。这种方法的评级为五。与第 9.13.1 节中的循环 8×N 密码一样，这可以加倍、三倍或更多，并且块大小可以变化。

这个基本思想可以以两种强大的方式进行增强。

首先，字节可以被分成几种不同的方式，例如 1,3,2,2 或 2,4,2。例如，你可以首先使用 3,2,3 的分割方式对块进行加密，然后使用 1,3,2,2 的分割方式重新加密，然后再使用 2,4,2 的分割方式重新加密。这将涉及 7 个密钥和 7 个步骤。（1）使用第一个替换产生消息的 3,2,3 位表示。（2）使用第一个移位密钥移动 3 行。（3）使用第二个替换产生字节的 1,3,2,2 位表示。（4）根据第二个移位密钥移动 4 行。（5）使用第三个替换产生字节的 2,4,2 位表示。（6）根据第三个移位密钥移动 3 行。（7）使用第四个替换产生最终的密文字节。

其次，消息区块可以以几种不同的方式划分。假设你使用长的明文区块，比如 32 个字符。对于前一种技术的第 2 步，你可以将 32 字节分成 6、14 和 12 字节的组。对于第 4 步，你可以将 32 字节分成 11、8 和 13 字节的组。对于第 6 步，你可以将 32 字节分成 8、17 和 7 字节的组。每个组都将独立移位。这种划分对每条消息可能是不同的。

或者，你可以采取更包容的方法。对于第 2 步，将整个消息划分为大小为 X 的区块。对于第 4 步，将消息划分为大小为 Y 的区块。对于第 6 步，将消息划分为大小为 Z 的区块。X、Y 和 Z 的长度可以是从 6 字节到整个消息长度的任意长度。

我不会评价所有 BitCycle 替换的变体。可以说，评级可能从五到十不等。在第十二章中，我将描述如何验证一个区块密码是否真正值得得到十分评级。

9.15 更强大的区块

本章描述的几种密码技术适用于明文区块。有几种方法可以对明文区块进行处理，使你的密码对艾米莉来说稍微困难一些。以下是一些想法的简短列表：

• 周期性或伪随机地改变区块长度。

• 反转每个区块的前几个字母，周期性或伪随机地。

• 反转每个区块的最后几个字母，周期性或伪随机地。

• 周期性或伪随机地将每个区块向左或向右循环。

• 将区块的最后 N 个字母与下一个区块的前 N 个字母交换。

但要警告一句：如果你手动加密和解密，请谨慎使用这些方法。如果你使你的密码变得如此复杂以至于无法准确加密和解密，那么它就变得毫无价值。