数学圈丛书：《密码的数学》
和乐数学”关注我们，查看更多历史⽂章。设为星标，快速读到最新⽂章。
▲加密货币很⾼深吗？⼈类可以创造出⼈类⾃⾝⽆法破解的密码吗？致敬历史上和未来的密码精英！普通⼈读懂密码学，这本就够了！
1.1 爱丽丝与鲍勃与卡尔与尤利乌斯：术语与凯撒密码
⼏乎从书写的诞⽣开始，⼈们就在试图隐藏书⾯信息的内容了，也由此发展出了很多不同的⽅法来实现这⼀点。也⼏乎就从⼈们试着隐藏信息开始，学者也开始对这些⽅法进⾏分类和描述。不好玩的地⽅在于，这样⼀来我就不得不直接扔给你们⼀⼤堆专门术语。更糟糕的是，有很多我们⽇常会话中会⽤到的可以互换的词，在这个领域的专家眼⾥却有着特殊的含义。不过要找到窍门摸清楚到底什么是什么，倒也不是真的那么难。
我要举的第⼀个例⼦是，研究秘密信息的⼈经常⽤术语代码（code）和密码（cipher）来指代两个不同的东西。⼤卫·卡恩（David Kahn）写过⼀本密码学的历史，也许算得上是终极论述，他对此说得不能再好了：“代码由成千上万的单词、短语、字母、⾳节组成，带有可代替明⽂组分的代码编码或代码编号，……⾄于说密码，其基本单位是字母，有时候是字母对……⼤串字母的情况很少见。”发送秘密信息
的第三种⽅法是隐写术，包括隐藏已经存在的信息，⽐如说⽤看不见的墨⽔来书写。在本书中我们将集中精⼒考察密码，这是因为从数学上来看，密码通常是其中最有意思的，不过其它⽅法的例⼦也会时不时地刷刷存在感。
在我们开始之前，再学⼏个别的术语会⼤有帮助。研究如何⽤代码和密码发送秘密信息的学问叫做密码学（cryptography），⽽研究如何擅⾃读取这些秘密信息的学问叫做密码分析（cryptanalysis），或是密码破译（codebreaking）。这两个领域合在⼀起就组成了密码编码学（cryptology）。（有时候“密码学”⼀词也会⽤来表⽰这两个领域的集合，但我们会努⼒把这些术语都区分开。）当我们谈论密码学时，我们会说到爱丽丝想发送信息给鲍勃，这已经成为约定俗成的习惯了。但跟这⼉我打算从尤利乌斯说起。这就是尤利乌斯·凯撒（Julius Caesar），他不只是罗马“千秋万代的独裁者”，也是军事天才、作家，以及……密码⼯作者。
我们今天叫做“凯撒密码”的这玩意，很可能最开始并不是凯撒发明的，但肯定是因为他才变得这么有名。罗马历史学家苏埃托尼乌斯（Suetonius）这样描述凯撒密码：他（凯撒）除了写给西塞罗（Cicero）的信，还有就私⼈事务写给⾄交好友的。在私⼈信件中，他要是想说⼀些机密的事情，就会写成密码，也就是改变字母表中字母的顺序，写出来就字不成字了。要是有⼈想破译这些⽂字知道它们都是什么意思，他就得把字母表中的第四个字母，也就是 D 替换成 A，并对其它字母也以此类推。
换句话说，当爱丽丝想要发送信息时，她先得写出明⽂（plaintext），也就是把信息⽤正常的语⾔写出来的⽂本。接着她得把这条信息译成密码（encipher），也就是⽤密码将其写成秘密形式，得到的结果就是这条信息的密⽂（ciphertext）。要把信息变成代码的话，就得对其进⾏编码（encode），或者⽤加密（encrypt）这个术语也可以。对明⽂中的每⼀个 a，爱丽丝在密⽂中将其替换成 D，再将每⼀个 b 都替换成 E，以此类推。每⼀个字母都在字母表中往后移动了三位。这可真是太简单了。但是当爱丽丝⼀直进⾏到字母表的最后，把字母都⽤完了的时候，好玩的地⽅就出现了。字母 w 变成了 Z，那字母 x 该去哪⼉？它绕了⼀圈回到开头，变成了 A！于是字母 y 变成 B，⽽ z 变成了 C。举个例⼦：“你也有份吗布鲁图（and you too, Brutus） ”这条信息就变成了：
这就是爱丽丝要发给鲍勃的信息了。
“绕回去”这种思路，实际上你从⼩时候起就已经在⽤了。⼀点之后再过三⼩时是⼏点？四点钟。两点之后再过三⼩时是五点钟。⼗点之后再过三⼩时⼜是⼏点呢？⼀点钟。你看，绕回去啦。
1.2 关键问题：凯撒密码的⼀般化
在凯撒看来，他的密码够安全了，毕竟能截获他的消息的⼈多半⼤字不识⼀个，就更不⽤说还能分析密码了。但是从现代密码学的⾓度来看，凯撒密码有很⼤的缺点：你⼀旦搞清楚⼈家⽤的是凯撒密码，就能对整个系统都⼀览⽆余。没有密钥或别的只⾔⽚语的信息能让你对密码做出变化。这看起来糟糕得很。
停下来想⼀会⼉吧。多⼤个事⼉呢？你的密码要么是个秘密要么不是，对吧？这就是凯撒那个时代的看法，在那之后好多好多年也还是如此。但到了 1883 年，奥古斯特·柯克霍夫（Auguste Kerckhoffs）发表了⼀篇划时代的⽂章，⽂中宣称：“系统必须不需要保密，⽽且就算被敌⽅窃取，也
不会带来⿇烦。”太神了！怎样才能让你的系统就算被窃取也不带来⿇烦呢？
柯克霍夫接着指出，窃听者伊芙要发现艾丽丝和鲍勃⽤的是什么系统可太轻⽽易举了。跟凯撒那个时候⼀样，在柯克霍夫的年代密码学还是主要⽤于军事和政府，因此柯克霍夫想的是，敌⼈可能通过贿赂或是抓获爱丽丝或鲍勃的⼀名⼯作⼈员来获取信息。就算到了今天，在很多情况下这些问题也仍然值得关注，我们还可以添进去诸如伊芙窃听电话、在电脑上安装间谍软件和纯靠运⽓瞎猜的可能性。
不过在另⼀种情况下，如果爱丽丝和鲍勃有⼀个需要密钥来进⾏加密和解密的系统，事情就没有那么糟糕了。就算伊芙发现了正在使⽤的通⽤系统是什么，她也还是不能轻易读取任何信息。试着在没有密钥的情况下读取信息，以及／或确定⽤于⼀段信息的密钥是什么，就叫做密码分析，或是密码运算，或者再通俗⼀点，叫做破解。⽽就算伊芙设法找到了爱丽丝和鲍勃的密码，那也不算⼤势已去。要是爱丽丝和鲍勃够聪明，他们就会时常倒换密钥。因为基本系统还是⼀样的，倒换密钥也不会很难，⽽就算伊芙拿到了其中⼀些信息的密钥，她也还是没办法读取所有信息。
所以我们得找个办法来对凯撒密码做⼀点点改动，这取决于⼀些密钥的值。合情合理的出发点是，问⼀下为什么爱丽丝是将她的明⽂移动了个位置，⽽不是别的数字？并没有特别的理由，也许凯撒只是对数字情有独钟罢了。他的继任者奥古斯都（Augustus）⽤的是跟他相似的系统，但每个字母只向右移动了⼀位。“回转位”密码将每个字母移动了位，⾛到头的时候⼜绕回到起点。这种密码经常在⽹络
上⽤到，⽤来隐藏笑话的包袱，或是有可能会冒犯到某些⼈的内容。移动个字母（或者说加模）的⼀般思路就叫做以为密钥的移位式密码，或是加法密码。⽐如说，假设有个以为密钥的移位式密码，那凯撒的消息就会变成：
那⼀共会有多少个不同的密钥呢？移动个字母恐怕不是个好主意，但你也可以这么⼲。移动个字母⼜跟移动个字母是⼀样的——要不换个说法，以为模数，就和是⼀样的。移动个字母也跟移动个字母殊途同归，等等。所以，⼀共有种移动⽅法能实际带来不⼀样的结果，也就是说有个密钥。记住这⾥⾯也有，那个“没头脑密钥”，实际上对信息没有做任何处理。加密时什么都没⼲，术语就叫做⽆⽤密码。假设爱丽丝⽤移位式密码给鲍勃发了⼀条信息，⽽且被伊芙截获了。就算伊芙设法知道了爱丽丝和鲍勃⽤的是移位式密码，她也还是要试次不同的密钥来解密信息。这不是个⼤数⽬，但总⽐凯撒密码强⼀点。
上⽂节选⾃湖南科学技术出版社数学圈丛书《密码的数学》。
向上滑动阅览本书⽬录
⽬录：企业福利
前⾔
致谢
第⼀章密码和替换密码
最新马桶垫编织>牛黄解毒片的禁忌1.1 爱丽丝与鲍勃与卡尔与尤利乌斯：术语与凯撒密码1.2 关键问题：凯撒密码的⼀般化
1.3 乘法密码
1.4 仿射密码
1.5 破晓攻击：简单替换密码的密码分析
1.6 刚好登上这座⼭：多字替换密码
1.7 已知明⽂攻击
1.8 展望
第⼆章多表替换密码
2.1 同⾳密码
2.2 纯属巧合还是处⼼积虑？
2.3 阿尔伯蒂密码
2.4 我好⽅：表格法，⼜称维吉尼亚⽅阵密码
2.5 多少才算多？确定字母表数量
2.6 超⼈留下吃晚餐：叠置与还原
2.7 多表密码的乘积
2.8 转轮机和转⼦机
2.9 展望
第三章换位密码
3.1 这就是斯巴达！密码棒
3.2 栅栏与路径：⼏何换位密码
3.3 排列与排列密码
3.4 排列乘积
3.5 带密钥的纵⾏换位密码
补充阅读3.1 实⽤虚⽆主义
3.6 决定矩形的宽度
3.7 拼字游戏
补充阅读3.2 然⽽⼀说到搅乱
3.8 展望
第四章密码与计算机
4.1 ⾟苦娘⼦磨⾖腐：多项密码与⼆进制数字
4.2 分馏密码
4.3 如何设计数字密码：SP⽹络与法伊斯特尔⽹络
补充阅读4.1 明⽂数字化
4.4 数据加密标准
4.5 ⾼级加密标准
4.6 展望
第五章序列密码
5.1 流动密钥密码
补充阅读5.1 原来你也在这⾥
5.2 ⼀次性密码本
5.3 带着你的妹妹带着你的嫁妆赶着那马车来：⾃动密钥密码5.4 线性反馈移位寄存器
5.5 向LFSR添加⾮线性
5.6 展望
第六章带指数的密码
6.1 ⽤指数加密
6.2 费马⼩定理
6.3 ⽤指数解密
6.4 离散对数问题
6.5 合数为模
6.6 欧拉函数
6.6 欧拉函数
6.7 以合数为模时的解密
补充阅读6.1 哼哼哈兮
6.8 展望
第七章公钥密码
7.1 公钥密码的思路：完全公开
英语之声
7.2 迪菲-赫尔曼密钥协议
7.3 ⾮对称密码学
7.4 RSA
7.5 注⽔启动：素数检验
7.6 为什么说RSA是（好的）公钥系统？
活着的意义是什么7.7 RSA的密码分析
7.8 展望
附录⼀公钥密码学的隐秘历史
昭媛第⼋章其它公钥系统
8.1 三次传递协议
8.2 贾迈勒（ElGamal）
8.3 椭圆曲线密码学
8.4 数字签名
蒸香肠的做法
8.5 展望
第九章密码学的未来
9.1 量⼦计算
怎么锻炼肺活量
9.2 后量⼦密码学
9.3 量⼦密码学
9.4 展望
内容推荐：
从古⾄今，密码激发了设计者的智慧和破解者的聪明才智。密码学，也就是发送秘密信息的学问，背后的数学是怎样的？约书亚·霍尔登同时聚焦于编码和解码，通过解读历史上最简单⼜最为知名的凯撒密码，阐述了⼤部分为⼈熟知的古代和现代密码背后关键的数学理念。本书还探讨了多字母替换密码、换位密码（其中⼀种是由斯巴达⼈发明的）、序列
