作者：伊恩·斯图尔特
出版社：人民邮电出版社图灵新知
出版时间：2019年8月
说起密码，我们马上会想到詹姆斯·邦德或者《柏林谍影》。但是，几乎所有人都会在日常生活中用密码进行一些完全正常、合法的活动，比如使用网上银行的密码。我们和银行之间的通信是加密的，信息被编写成密码，因此犯罪分子无法读取，也不能接触到我们的钱——至少不那么容易。
在英语字母表里有26 个字母，实际的密码也经会常用到26。例如，德国人在第二次世界大战时使用的恩尼格玛密码机，这种机器采用的转子有 26 个档位，档位和字母相对应。所以，这个数为密码学提供了一个合理的切入点。不过，26 在密码领域中并没有特殊的数学性质，类似的原理也可以用于其他数。
一、凯撒密码
密码的历史至少可以上溯到公元前1900 年左右的古埃及。尤利乌斯·凯撒在秘密信函里也使用过一种简单的密码，被用于传递军事机密。凯撒的传记作者苏埃托尼乌斯写道：“如果他有什么秘密要说，就会把它写成密码。他会更改字母表上的字母顺序，令人无法看出它是哪个单词。如果有人想破译它们并得到本意，就必须把字母表上的第4 个字母给换掉，那么 A 对应的就是 D，其他字母也类似。”
在凯撒生活的那个时代，字母表里没有字母J、U 和 W。但我们仍使用现代字母表来解释，因为我们更熟悉它。凯撒的思路是，先按常规顺序把字母表写下来，然后在它下面写一个移位的字母表，有可能如下所示：
现在，你可以把每个常规字母表上的字母对应到移位字母表上相同位置的字母，从而加密消息。也就是说，A 变成F，B 变成G，J变成O，U变成Z......以此类推。就像下图这样（第一行与第二行对照看）：
想要破译消息，你只需看一下字母表之间的反向对应关系：
为了制作一种将字母绕在环上的实用机械装置，我们把字母放置在一个圆环或圆筒上（图1）。
图1：绕在环上的实用装置
凯撒密码过于简单，因此并不安全，后面会解释其中的原因。但它包含了一些对所有密码（编码系统）都通用的基本概念（图2）。
明文：原始信息。
密文：原始信息加密后的版本。
加密算法：用来把明文转换成密文的方法。
解密算法：用来把密文转换成明文的方法。
密钥：加密和解密文本所需的秘密信息。
在凯撒密码里，密钥就是字母表移位的步数。加密算法是“用密钥将字母表移位”。解密算法是“用密钥将字母表反向移位”，也就是减去相同方向的移位步数。
图2：密码系统的一般特征
在这个密码系统里，加密密钥和解密密钥之间关系密切——一个是另一个的负数，也就是说，它们的移位步数相同，只不过方向相反。在这种情况下，知道了加密密钥实际上就知道了解密密钥。这类系统被称为对称密钥密码。凯撒显然使用了更复杂的密码——幸好他是这么做的。
1. 数学公式化
利用模运算，我们可以通过数学表示凯撒密码。在这里， 模数等于26，即字母表上字母的个数。计算和平时一样，但需要加上一条：任何26 的倍数都可以替换成0。这正是我们需要的，让移位的字母表“绕一圈”后从头开始。现在，用数字0~25 代表字母A~Z，即A=0、B=1、C=2，以此类推， 直至 Z=25。把 A（位置 0）移动到 F（位置 5）的加密过程就是数学规则：
n → n 5 mod 26
请注意，U（位置20）成了20 5=25 mod 26，它代表Z，而V（位置21）成了：
21 5=26=0 mod 26
它代表A。这说明了数学公式是如何确保字母表正确地绕圈的。
解密过程也有类似的规则：
n → n-5 mod 26
因为 n 5-5=n mod 26，所以解密把加密还原了。更一般地，当密钥为k时，意味着“向右移动k步”，于是加密过程的规则成了：
n → n k mod 26
而解密的规则是：
n → n-k mod 26
把密码转换成数学语言的优点在于，我们可以用一种精确的方式来描述密码，并分析它们的性质，同时还不必考虑字母本身，一切都是用数字表示的。我们也可以考虑其他符号，如小写字母a、b、c……，以及标点符号，还有数字。只要把26 换成某个更大的数，然后一次性确定如何分配这些数就行了。
2. 破解凯撒密码
凯撒密码非常不安全。如前所述，它只有26种可能性，因此你可以穷尽所有可能，直到某个解密消息看起来有含义。
还有一种名叫替换码的变体也很脆弱，虽然这种编码会打乱字母表，而不只是移动。这样一来，就产生了26种编码，这个数非常大。然而，利用简单方法就可以破解所有这类编码。对某种给定的语言来说，某些字母会比另一些更常见（图 3）。
图3：在典型的英语文本里，字母出现的频率
在英语里，最常见的字母是E，它大约占全部出现频率的13% ；接下来是T，大约是9% ；再往下是A，大约是8%，等等。如果你截取了一段很长的密文，并猜测它是通过打乱字母表的方法生成的，那么就能计算所有字母的频率。由于文本各式各样，因此它们或许并不能和理论值精确地吻合。
但是，比方说，如果在密文里的字母Q出现得比其他字母更频繁， 那么你可以试着用E代替Q。如果接下来最常见的字母是M，那么试试看用T代替M结果会怎样，以此类推。当然，你还可以微调它们的顺序。即便如此，你需要尝试的可能性也会少很多。
例如，假设部分密文如下：
X J M N Q X J M A B W
你发现在整个密文里，频率最高的3个字母依次分别是Q、M 和 J。用E代替 Q、T 代替 M、A 代替 J，并把其他地方留白后得到：
- A T - E - A T - -
不难猜测这条消息实际上是（数学运算）：
M A T H E M A T I C S
如果有更多密文，你很快就会发现它的含义，因为你已经可以猜测X 解码为M、N 解码为H、A 解码为I、B 解码为C，而W 解码为S。如果另一段密文是：
W B A Q R B Q H A B M A L R
那么你可以试着把它解密成：
S C I E - C E - I C T I -
进而猜它应该是（科幻）：
S C I E N C E F I C T I O N
出现两次的N 更加有助于确认你的猜测。现在，你知道N、F 和 O 分别是由什么字母加密的了。整个过程很快，甚至通过人工处理也能快速破解编码，编码方式有成千上万种。破解编码的过程就是在不知道算法或密钥的情况下，找到如何解密消息的方法，这一过程依赖于编码本身。
在现实中，一些编码方法破解起来非常困难，因为密码学家们在拥有足够的信息进而尝试破解编码之前，密钥会保持不断变化。
第二次世界大战期间，人们使用“单次密本”来实现这一点：从根本上说，它需要一本有许多复杂密钥的记事本，每个密钥只用于一条短消息，随后便马上被销毁。这类方法的最大问题是，间谍们必须带着密码本到处跑——如今某些电子小配件也有相同的功能，而密码本可能会在他们的私人物品中被发现。
二、恩妮格玛密码机
在第二次世界大战期间，德军使用的恩尼格玛密码机是最著名的密码系统之一。在英国布莱切利庄园工作的数学家和电子工程师们破解了恩尼格玛的编码，而这些人中最出名的就是计算机科学先驱——艾伦·图灵。
他们得到了一台可以使用的恩尼格玛密码机，为完成破解任务带来了极大的帮助。它是由一组波兰密码学家在1939 年提供的，当时，这些波兰专家已在破译恩尼格玛编码方面取得了重大进展。德国人还有一些别的编码也被破解过，其中包括更复杂的洛伦兹密码，但破解这个编码时并没有用到实体设备。
当时，在拉尔夫·特斯特的领导下，一个密码分析小组从设备发送的消息里推测出了洛伦兹密码的可能结构。接着，威廉·图特灵光一闪，向破解编码走出了第一步：他推测出与设备运行方式有关的重要信息，此后，这项工作的进展大大加速。
实际上，破解这种编码用到了一台电子设备，它就是由托马斯·弗劳尔斯领导的团 队设计和建造的“巨人”计算机（Colossus）。事实上，“巨人”计算机是为某项特定任务而设计的早期电子计算机之一。
恩尼格玛密码机包括一个用于输入明文的键盘和一系列转子，每个转子都有26个档位，档位和字母表上的字母相对应（图4）。早期的密码机有3个转子，后来被扩展成一组5个德国海军甚至用到了8个，但使用者每天只选用其中的3个。转子的作用是，在每输入一个新字母时，打乱明文字母的方式就会改变。确切的方法很复杂，这里就不细说了。
图4：恩格斯密码机
粗略地讲，整个过程大致是这样的。密码机根据转子所处的档位决定移位情况，转子就像凯撒密码一样把字母表打乱。当一个字母被传递到第一个转子时，产生的移位结果就会传给第二个转子，同时产生新的移位。
而这一结果又会传给第三个转子，并产生第三个移位（图5）。此时产生的信号会到达一面反射镜。这面反射镜实际是一组把字母连成对的13根线，它把结果字母与相连的另一个字母做交换。最后，结果再次返回到3个转子，从而生成与给定输入相对应的最终编码结果。
密文可以从识别灯盘上得到，灯盘上有26 盏灯，每个字母背后都有一盏，每当灯亮起时，就说明这个密文字母与刚刚输入的明文相对应。
这种密码机最具独创性的地方在于，在每次连续击键时，明文字母和产生的密文字母之间的对应关系会以独特方式发生变化。在键盘上每敲击一个新字母，转子都会转到下一个位置，因此转子会以不同方式打乱字母表。右侧的转子每次都向前移动一格；当右侧的转子从Z 回到A 时，中间的转子才会移动一格；左侧的转子相对于中间的转子，也是这样的。
图 5：一组 3 个转子
因此，转子的运作很像汽车里（被电子化之前）的里程计。里程计的“个”位数码从0到9，再回归0，每次动一格。“十”位数码也一样，但只有从个位得到“进位”信号时才会动，这时，个位从9 回归到0，类似地， 只有从十位得到“进位”信号时，“百”位数码才会加1。
因此，这3个数位从000到999，每次加 1，最终再恢复到000。然而，恩尼格玛密码机的转子从A到Z共有26个“数位”，它比10 更多。并且转子的开始状态是可以任意设置的，一共有26×26×26=17576种位置。在实际使用中，起始位置是在一天开始的时候设置的，并在使用24小时后被重新设置。
我是按照左、中、右的顺序来介绍转子的步进过程的，但实际上，密码机可以使用转子的所有6种排列顺序。将初始化的可能性乘以6，于是一共有105456种可能性。
在军事用途中，插接板为设备额外提高了一个安全等级：按不同方式在字母间插连接线，可以成对地交换字母（图6）。这种连接线超过10根， 因此提供了 150 738 274 937 250 种A可能性。同样，插接板的设置也是每天变化的。
对使用者而言，这个系统在实用性方面有一个很大的优点：它是对称的。相同的机器可以用作解密消息。给定日期的初始化设置必须传达给所有使用者，因此德国人使用一种单次密本。
图 6：插了两根连接线的插接板
1. 破解恩尼格玛编码
但是，整个过程也导致了一些缺陷。其中最明显的就是，如果敌军（在这里指盟军）能推算出设置，那么当天发送的所有消息都能被解密。还有一些别的弱点，尤其是，如果连续两天使用了相同的设置——这是偶尔发生的错误，那么编码就会被破解。
通过利用这些漏洞，布莱切利庄园的研究团队于1940 年1月首次成功破解了恩尼格玛编码。他们的工作依赖于一个波兰密码团队取得的知识和思路。波兰团队的领导人是马里安·雷耶夫斯基，自从1932 年以来，他就一直在尝试破解恩尼格玛。
通过研究把当天的设置传递给使用者的方式，波兰团队发现了一个缺陷，有效地把需要考虑的设置数量从一亿亿种降低到大约十万种。将这些设置进行编目，波兰人可以很快地算出哪天用的是什么设置。他们发明了一种名叫记转器的设备来帮助破解。他们还花了大约一年时间准备编目，不过当编目大功告成后，推断当天的设置和破解编码就只需要 15 分钟。
德国人在1937 年升级了系统，于是波兰团队必须从头开始。他们发展了几种方法，并用其中最强大的方法制造了一种名叫密码逻辑炸弹（bomba kryptologiczna）的设备。每台设备都具备强大的分析能力，旨在推断由3个转子形成的17576种初始化设置，以及每种设置因转子的不同排列而得到6种可能。
1939 年，图灵刚到布莱切利庄园不久就发明了英国人自己的“炸弹”，它被称为“炸弹机”。同样，该设备的功能也是推断初始转子的设置，以及所有转子的顺序。截至1941 年 6 月，已有5台炸弹机投入使用。而在1945年战争结束时，设备数量达到了210 台。
当德国海军改用4个转子的设备时，改进的炸弹机也随之诞生。当德国人将系统升级以提高安全时，破解密码的英国专家们也找到了使升级失效的方法。到1945 年，盟军已经可以破解几乎全部的德军消息了，但德军最高统帅部仍然相信，所有通信是绝对安全的，他们的密码学家们还沉浸在安全的假象中，丝毫没有怀疑别人可能会花费极大的力气来破解编码。盟军虽然取得了极大的优势，但他们必须小心使用，以免暴露自己具有破解消息的能力。
三、非对称密钥密码
在密码学领域，最了不起的概念大概要算非对称密钥了。在非对称密钥里，加密密钥和解密密钥是不同的，因此，即使你知道加密密钥，也不可能真的计算出解密密钥。这似乎是不可能的，因为一个过程的逆过程就是另一个过程，但一些方法可以实现这一点，从而终结“反推加密方法”。RAS编码就是其中一例，它基于模运算里的质数性质。
在这样的系统里，可以公开加密算法、解密算法和加密密钥——即便如此，人们也不可能推断出解密密钥。不过，合法的接收者是可以知道解密方法的， 因为他们还有一个私钥，可以告诉接收者如何解密消息，像现在很火的区块链就是运用了非对称性加密。
【钛媒体作者介绍：本文来自《不可思议的数》作者，伊恩·斯图尔特。他是英国皇家学会会员，曾获英国皇家学会“法拉第奖章”和英国伦敦数学学会与英国数学及应用研究院颁发的“塞曼奖章”。他著有多部优秀畅销数字科普作品，如《数学万花筒》系列、《改变世界的十七个方程》和《迷人的图形》等。】
《不可思议的数》将会纳入钛媒体Pro版书库，敬请大家关注前沿书库的上新动态~每位Pro专业用户一年可以在书库中任意选择三本书，由钛媒体免费赠送哦～点击链接、登录，进入“前沿书库”选书：http://www.tmtpost.com/pro
- 人工智能相关好书：http://www.tmtpost.com/3122712.html
- 创业事项相关好书：http://www.tmtpost.com/2788508.html
- 培养领导力相关好书：http://www.tmtpost.com/2678549.html
更多精彩内容，关注钛媒体微信号（ID：taimeiti），或者下载钛媒体App
,
