前言
序言
从秘密解码环到政府政策声明，隐藏和发现信息的挑战长期以来一直吸引着智慧。密码学是一个引人入胜的主题，几乎每个学童都有一些实践经验。然而，出于良好的原因，它是一个被深度保密包裹的学科，并被政府用来保护其最敏感的武器。密码学在军事和外交事务中的作用一直非常严肃。毫不夸张地说，密码学的成功和失败塑造了战争的结局和历史的进程；而且毫不夸张地说，密码学的成功和失败正在制定我们当前的历史进程。
回想一下美国南北战争中的安提塔姆战役，发生在 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 整除时。
- 假设 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’的高效方法。
- 如果 a 和 N 有一个大于 1 的公因数 d，则 a 在模 N 下没有乘法逆元。就是说不存在一个 a’使得 aa’≡1 (mod N)。如果 b 不能被 d 整除，则同余方程 ax≡b (mod N)没有解。例如，4x≡5 (mod 12)没有解。
- 假设 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 的重复很容易发现。 混合哈夫曼评为三级。
密钥密码学（一）（2）https://developer.aliyun.com/article/1508650
