数学圈丛书:密码的数学

**章 密码和替换密码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）[ 据说这是凯撒遇刺时的*后一句话，因莎士比亚剧作《尤利乌斯·凯撒》而家喻户晓，也在英语世界中广泛运用，表示来自好友的始料未及的背叛。——译者注]”这条信息就变成了：明文：a n d y o u t o o b r u t u s密文：D Q G B R X W R R E U X W X V这就是爱丽丝要发给鲍勃的信息了。“绕回去”这种思路，实际上你从小时候起就已经在用了。一点之后再过三小时是几点？四点钟。两点之后再过三小时是五点钟。十点之后再过三小时又是几点呢？一点钟。你看，绕回去啦。1.2 关键问题：凯撒密码的一般化在凯撒看来，他的密码够安全了，毕竟能截获他的消息的人多半大字不识一个，就更不用说还能分析密码了。但是从现代密码学的角度来看，凯撒密码有很大的缺点：你一旦搞清楚人家用的是凯撒密码，就能对整个系统都一览无余。没有密钥或别的只言片语的信息能让你对密码做出变化。这看起来糟糕得很。停下来想一会儿吧。多大个事儿呢？你的密码要么是个秘密要么不是，对吧？这就是凯撒那个时代的看法，在那之后好多好多年也还是如此。但到了1883年，奥古斯特·柯克霍夫（Auguste Kerckhoffs）发表了一篇划时代的文章，文中宣称：“系统必须不需要保密，而且就算被敌方窃取，也不会带来麻烦。”太神了！怎样才能让你的系统就算被窃取也不带来麻烦呢？柯克霍夫接着指出，窃听者伊芙要发现艾丽丝和鲍勃用的是什么系统可太轻而易举了。跟凯撒那个时候一样，在柯克霍夫的年代密码学还是主要用于军事和政府，因此柯克霍夫想的是，敌人可能通过贿赂或是抓获爱丽丝或鲍勃的一名工作人员来获取信息。就算到了今天，在很多情况下这些问题也仍然值得关注，我们还可以添进去诸如伊芙窃听电话、在电脑上安装间谍软件和纯靠运气瞎猜的可能性。不过在另一种情况下，如果爱丽丝和鲍勃有一个需要密钥来进行加密和解密的系统，事情就没有那么糟糕了。就算伊芙发现了正在使用的通用系统是什么，她也还是不能轻易读取任何信息。试着在没有密钥的情况下读取信息，以及／或确定用于一段信息的密钥是什么，就叫做密码分析，或是密码运算，或者再通俗一点，叫做破解。而就算伊芙设法找到了爱丽丝和鲍勃的密码，那也不算大势已去。要是爱丽丝和鲍勃够聪明，他们就会时常倒换密钥。因为基本系统还是一样的，倒换密钥也不会很难，而就算伊芙拿到了其中一些信息的密钥，她也还是没办法读取所有信息。所以我们得找个办法来对凯撒密码做一点点改动，这取决于一些密钥的值。合情合理的出发点是，问一下为什么爱丽丝是将她的明文移动了3个位置，而不是别的数字？并没有特别的理由，也许凯撒只是对数字3情有独钟罢了。他的继任者奥古斯都（Augustus）用的是跟他相似的系统，但每个字母只向右移动了一位。“回转13位”密码将每个字母移动了13位，走到头的时候又绕回到起点。这种密码经常在网络上用到，用来隐藏笑话的包袱，或是有可能会冒犯到某些人的内容。移动k个字母（或者说加k模26）的一般思路就叫做以k为密钥的移位式密码，或是加法密码。比如说，假设有个以21为密钥的移位式密码，那凯撒的消息就会变成：明文: a n d y o u t o o b r u t u s数字: 1 14 4 25 15 21 20 15 15 2 18 21 20 21 19加21: 22 9 25 20 10 16 15 10 10 23 13 16 15 16 14密文: V I Y T J P O J J W M P O P N那一共会有多少个不同的密钥呢？移动0个字母恐怕不是个好主意，但你也可以这么干。移动26个字母又跟移动0个字母是一样的——要不换个说法，以26为模数，26就和0是一样的。移动27个字母也跟移动1个字母殊途同归，等等。所以，一共有26种移动方法能实际带来不一样的结果，也就是说有26个密钥。记住这里面也有0，那个“没头脑密钥”，实际上对信息没有做任何处理。加密时什么都没干，术语就叫做无用密码。假设爱丽丝用移位式密码给鲍勃发了一条信息，而且被伊芙截获了。就算伊芙设法知道了爱丽丝和鲍勃用的是移位式密码，她也还是要试26次不同的密钥来解密信息。这不是个大数目，但总比凯撒密码强一点。