第 2 章 历史上的密码——写一篇别人看不懂的文章

第 2 章 历史上的密码——写一篇别人看不懂的文章

我在看完这些内容之后,一脸茫然,只好对勒格朗说:“这些都是什么意思啊?我是一点儿都看不懂这上面的内容是什么啊!假如只有破解这封密码信才能得到金银财宝,那我只能说,自己根本没有得到金银财宝的命了!”

——爱伦·坡《金甲虫》

2.1 本章学习的内容

本章我们将介绍历史上几种著名的密码。

  • 恺撒密码
  • 简单替换密码
  • Enigma

此外,我们还将介绍两种破译密码的方法(即合法接收者以外的人试图由密文还原出明文的方法)。

  • 暴力攻击
  • 频率分析

在本章最后我们还将思考密码算法与密钥之间的关系。

本章所介绍的密码在现代都已经不再使用了,但在寻找密码弱点的方法、破译密码的思路以及密码算法与密钥的关系等方面,这些密码与现代的密码技术依然是相通的。

2.2 恺撒密码

首先,我们来介绍一种最简单的密码——恺撒密码。

2.2.1 什么是恺撒密码

恺撒密码(Caesar cipher)是一种相传尤利乌斯·恺撒曾使用过的密码。恺撒于公元前 100 年左右诞生于古罗马,是一位著名的军事统帅。

恺撒密码是通过将明文中所使用的字母表按照一定的字数“平移”来进行加密的。在日语(例如平假名)或者汉语(例如汉语拼音)中也可以用同样的思路来实现恺撒密码,但为了简化内容,在这里我们只使用英文字母。

本章中,为了讲解方便,我们用小写字母(a, b, c, ...)来表示明文,用大写字母(A, B, C, ...)来表示密文。

现在我们将字母表平移 3 个字母,于是,明文中的 a 在加密后就变成了与其相隔 3 个字母的 D,以此类推,b 变成 Ec 变成 Fd 变成 G……v 变成 Yw 变成 Z,而 x 则会回到字母表的开头而变成 A,相应地,y 变成 Bz 变成 C。通过图 2-1 我们可以很容易地理解“平移”的具体工作方式。

图 2-1 恺撒密码中将字母表“平移”

2.2.2 恺撒密码的加密

这里,我们假设要保密的信息为 yoshiko 这个女性的名字。我们暂且不管这个名字到底代表一位真实的女性,还是只是一种暗号,只考虑将它在保密的状态下发送给接收者。

此时,明文包含下列 7 个字母。

yoshiko

接下来我们将明文中的字母逐一进行加密。

y → B
o → R
s → V
h → K
i → L
k → N
o → R

这样,明文 yoshiko 就被转换成了密文 BRVKLNRyoshiko 这个词我们能够看懂,但 BRVKLNR 就看不懂了。

恺撒密码中,将字母表中的字母平移这个操作就是密码的算法,而平移的字母数量则相当于密钥。在上面的例子中,密钥为 3(图 2-2)。

图 2-2 用恺撒密码进行加密(密钥为 3)

2.2.3 恺撒密码的解密

现在,假设接收者已经收到了密文 BRVKLNR,由于密文本身是看不懂的,因此必须将它解密成明文。

恺撒密码的解密过程是使用与加密时相同的密钥进行反向的平移操作。用刚才的例子来说,只要反向平移 3 个字母就可以解密了。

B → y
R → o
V → s
K → h
L →i
N → k
R → o

这样我们就得到了明文 yoshiko

在这个场景中,密钥 3 必须由发送者和接收者事先约定好。

图 2-3 用恺撒密码进行解密(密钥为 3)

2.2.4 用暴力破解来破译密码

通过上面的讲解,我们知道对于发送者用恺撒密码加密过的密文,接收者是能够进行解密的,因此发送者可以向接收者成功发送 yoshiko 这条消息。

那么,接收者以外的人(即不知道密钥 3 的人)在看到密文 BRVKLNR 后,是否能够猜测到明文 yoshiko 呢?也就是说,恺撒密码能够被破译吗?

在恺撒密码中,密钥就是字母表平移的字数。由于字母表只有 26 个字母,因此加密用的密钥只有 0 到 25 共 26 种(平移 0 个字母实际上相当于没有加密,但在这里我们也将这种情况考虑进去)。

下面我们按顺序将这 26 种密钥都尝试一遍。

BRVKLNR → 用密钥 0 解密 → brvklnr
BRVKLNR → 用密钥 1 解密 → aqujkmq
BRVKLNR → 用密钥 2 解密 → zptijlp
BRVKLNR → 用密钥 3 解密 → yoshiko
BRVKLNR → 用密钥 4 解密 → xnrghjn
BRVKLNR → 用密钥 5 解密 → wmqfgim
BRVKLNR → 用密钥 6 解密 → vlpefhl
BRVKLNR → 用密钥 7 解密 → ukodegk
BRVKLNR → 用密钥 8 解密 → tjncdfj
BRVKLNR → 用密钥 9 解密 → simbcei
BRVKLNR → 用密钥10 解密 → rhlabdh
BRVKLNR → 用密钥11 解密 → qgkzacg
BRVKLNR → 用密钥12 解密 → pfjyzbf
BRVKLNR → 用密钥13 解密 → oeixyae
BRVKLNR → 用密钥14 解密 → ndhwxzd
BRVKLNR → 用密钥15 解密 → mcgvwyc
BRVKLNR → 用密钥16 解密 → lbfuvxb
BRVKLNR → 用密钥17 解密 → kaetuwa
BRVKLNR → 用密钥18 解密 → jzdstvz
BRVKLNR → 用密钥19 解密 → iycrsuy
BRVKLNR → 用密钥20 解密 → hxbqrtx
BRVKLNR → 用密钥21 解密 → gwapqsw
BRVKLNR → 用密钥22 解密 → fvzoprv
BRVKLNR → 用密钥23 解密 → euynoqu
BRVKLNR → 用密钥24 解密 → dtxmnpt
BRVKLNR → 用密钥25 解密 → cswlmos

尝试一遍之后,我们就会发现当密钥为 3 时,可以解密出有意义的字符串 yoshiko。这就意味着我们仅仅根据密文就推测出了密钥和明文,这样的密码有什么用呢?恺撒密码实在是太脆弱了,无法保护重要的秘密。

上面介绍的这种密码破译方法,就是将所有可能的密钥全部尝试一遍,这种方法称为暴力破解(brute-force attack)。由于这种方法的本质是从所有的密钥中找出正确的密钥,因此又称为穷举搜索(exhaustive search)。

小测验 1 破译恺撒密码      (答案见2.7 节)

假设你收到了以下用恺撒密码加密过的密文,但你不知道密钥(平移的字母数),请破译这段密文。

PELCGBTENCUL

2.3 简单替换密码

2.3.1 什么是简单替换密码

恺撒密码是通过将明文中所使用的字母表平移来生成密文的。但是,如果我们将字母表中的 26 个字母,分别与这 26 个字母本身建立一对一的对应关系,那么无论哪一种对应关系就都可以作为密码来使用。这种将明文中所使用的字母表替换为另一套字母表的密码称为简单替换密码(simple substitution cipher)。恺撒密码也可以说是简单替换密码的一种。

例如,图 2-4 就是一个简单替换密码的对应表(替换表)。

图 2-4 简单替换密码的替换表(例)

2.3.2 简单替换密码的加密

简单替换密码的加密过程是依次将明文中的每一个字母按照替换表替换成另一个字母。

例如,我们可以用图 2-4 中的替换表,对刚才恺撒密码例子中的明文 yoshiko 进行加密。参照图 2-4,依次对每个字母进行替换。

y → K
o → B
s → L
h → T
i → J
k → S
o → B

就可以得到密文 KBLTJSB

2.3.3 简单替换密码的解密

只要使用加密时所使用的替换表进行反向替换,就可以对简单替换密码进行解密了。

由于在简单替换密码的解密中,需要用到加密时所使用的替换表,因此发送者和接收者必须事先同时拥有该替换表,而这份替换表也就相当于简单替换密码的密钥。

2.3.4 简单替换密码的密钥空间

yoshiko 用恺撒密码(密钥为 3)加密后的密文是 BRVKLNR,而用简单替换密码(密钥为图 2-4)加密后的密文则是 KBLTJSB。无论是 BRVKLNR 还是 KBLTJSB 都是无法看懂的字符串,在这一点上它们是相似的。单从密文上来看,我们无法判断出恺撒密码和简单替换密码到底哪一种更难破解。

恺撒密码可以通过暴力破解来破译,但简单替换密码很难通过暴力破解来破译。这是因为简单替换密码中可以使用的密钥数量,比恺撒密码要多得多。

为了确认这一点,我们来计算一下简单替换密码中可以使用的密钥总数吧。一种密码能够使用的“所有密钥的集合”称为密钥空间(keyspace),所有可用密钥的总数就是密钥空间的大小。密钥空间越大,暴力破解就越困难。

简单替换密码中,明文字母表中的 a 可以对应 A, B, C, ..., Z 这 26 个字母中的任意一个(26 种),b 可以对应除了 a 所对应的字母以外的剩余 25 个字母中的任意一个(25 种)。以此类推,我们可以计算出简单替换密码的密钥总数为:

26×25×24×23×… × 1 = 403291461126605635584000000

这个数字相当于 4 兆的约 100 兆倍 1,密钥的数量如此巨大,用暴力破解进行穷举就会非常困难。因为即便每秒能够遍历 10 亿个密钥,要遍历完所有的密钥也需要花费超过 120 亿年的时间。

11 兆等于 1 万亿,即 1012,这里所计算的简单替换密码的密钥总数约为 4×1026,或者约为 288。——译者注

如果密码破译者的运气足够好,也许在第一次尝试时就能够找到正确的密钥,但反过来说,如果运气特别差,也许尝试到最后一次才能找到正确的密钥。因此平均来说,要找到正确的密钥也需要花费约 60 亿年的时间。

2.3.5 用频率分析来破译密码

虽然用暴力破解很难破译简单替换密码,但使用被称为频率分析的密码破译方法,就能够破译简单替换密码

频率分析利用了明文中的字母的出现频率与密文中的字母的出现频率一致这一特性。尽管篇幅较长,但为了让大家体会到破译密码的感觉,我们还是来实际尝试破译一段密文吧。

假设你得到了下面一段密文,已知明文是用英语写的,并且是通过简单替换密码进行的加密,但是你不知道作为密钥的替换表。下面就让我们来破译这段密文。

MEYLGVIWAMEYOPINYZGWYEGMZRUUYPZAIXILGVSIZZMPGKKDWOMEPGROEIWGPCEIPAMDKKEYCIUYMGIF
RWCEGLOPINYZHRZMPDNYWDWOGWITDWYSEDCEEIAFYYWMPIDWYAGTYPIKGLMXFPIWCEHRZMMEYMEDWOMG
QRYWCEUXMEDPZMQRGMEEYAPISDWOFICJILYSNICYZEYMGGJIPRWIWAIHRUNIWAHRZMUDZZYAMEYFRWCE
MRPWDWOPGRWAIOIDWSDMEIGWYMSGMEPYYEYHRUNYARNFRMSDMEWGOPYIMYPZRCCYZZIOIDWIWAIOIDWE
YMPDYAILMYPMEYMYUNMDWOUGPZYKFRMIMKIZMEIAMGODTYDMRNIWASIKJYAISIXSDMEEDZWGZYDWMEYI
DPZIXDWODIUZRPYMEYXIPYZGRPDMDZYIZXMGAYZNDZYSEIMXGRCIWWGMOYM

首先,我们来统计一下这段密文中每个字母出现的频率。也就是说,我们要数一下每个字母各出现了多少次。结果如表 2-1 所示。

表 2-1 密文中各字母出现的频率表

{%}

为了找到破译的线索,我们再来看一看英语文章中所使用的字母的频率。例如,将爱伦·坡的《金甲虫》中出现的英文字母按照出现频率排序的结果是:e, t, a, o, i, n, s, h, r, d, l, u, c, m, f, w, g, y, p, b, v, k, j, q, z。这个顺序根据所统计的文章的不同会有所变化,但一般的英语文章中出现频率最高的字母是 e,这一点基本上是不会错的。

表 2-1 中出现频率最高的两个字母是 IY,我们假设它们中的其中一个是 e。当假设 Ye 时,我们将密文中的 Y 全部替换成 e,替换后的密文如下。

MEeLGVIWAMEeOPINeZGWeEGMZRUUePZAIXILGVSIZZMPGKKDWOMEPGROEIWGPCEIPAMDKKEeCIUeMGIF
RWCEGLOPINeZHRZMPDNeWDWOGWITDWeSEDCEEIAFeeWMPIDWeAGTePIKGLMXFPIWCEHRZMMEeMEDWOMG
QReWCEUXMEDPZMQRGMEEeAPISDWOFICJILeSNICeZEeMGGJIPRWIWAIHRUNIWAHRZMUDZZeAMEeFRWCE
MRPWDWOPGRWAIOIDWSDMEIGWeMSGMEPeeEeHRUNeARNFRMSDMEWGOPeIMePZRCCeZZIOIDWIWAIOIDWE
eMPDeAILMePMEeMeUNMDWOUGPZeKFRMIMKIZMEIAMGODTeDMRNIWASIKJeAISIXSDMEEDZWGZeDWMEeI
DPZIXDWODIUZRPeMEeXIPeZGRPDMDZeIZXMGAeZNDZeSEIMXGRCIWWGMOeM

英语中出现最多的单词是 the,因此我们可以寻找一下以 e 结尾的 3 个字母的组合,结果我们发现 MEe 这 3 个字母的组合是最常出现的,而且 MEe 出现在密文的开头,因此 MEe 很有可能就是 the

于是,我们再假设 MtEh

theLGVIWAtheOPINeZGWehGtZRUUePZAIXILGVSIZZtPGKKDWOthPGROhIWGPChIPAtDKKheCIUetGIF
RWChGLOPINeZHRZtPDNeWDWOGWITDWeShDChhIAFeeWtPIDWeAGTePIKGLtXFPIWChHRZtthethDWOtG
QReWChUXthDPZtQRGthheAPISDWOFICJILeSNICeZhetGGJIPRWIWAIHRUNIWAHRZtUDZZeAtheFRWCh
tRPWDWOPGRWAIOIDWSDthIGWetSGthPeeheHRUNeARNFRtSDthWGOPeItePZRCCeZZIOIDWIWAIOIDWh
etPDeAILtePtheteUNtDWOUGPZeKFRtItKIZthIAtGODTeDtRNIWASIKJeAISIXSDthhDZWGZeDWtheI
DPZIXDWODIUZRPetheXIPeZGRPDtDZeIZXtGAeZNDZeShItXGRCIWWGtOet

让我们动员自己所有的英语词汇,在上面的文字中继续寻找可能的组合。我们发现中间有一个词 thPee 比较可疑,这个词不会就是 three 吧(Pr)?

theLGVIWAtheOrINeZGWehGtZRUUerZAIXILGVSIZZtrGKKDWOthrGROhIWGrChIrAtDKKheCIUetGIF
RWChGLOrINeZHRZtrDNeWDWOGWITDWeShDChhIAFeeWtrIDWeAGTerIKGLtXFrIWChHRZtthethDWOtG
QReWChUXthDrZtQRGthheArISDWOFICJILeSNICeZhetGGJIrRWIWAIHRUNIWAHRZtUDZZeAtheFRWCh
tRrWDWOrGRWAIOIDWSDthIGWetSGthreeheHRUNeARNFRtSDthWGOreIterZRCCeZZIOIDWIWAIOIDWh
etrDeAILtertheteUNtDWOUGrZeKFRtItKIZthIAtGODTeDtRNIWASIKJeAISIXSDthhDZWGZeDWtheI
DrZIXDWODIUZRretheXIreZGRrDtDZeIZXtGAeZNDZeShItXGRCIWWGtOet

通观上面的文字,我们可以发现很多类似 herereter 这样的很像是英语的拼写,通过这些碎片信息,我们可以断定 Pr 的对应关系应该是正确的。

接下来我们来看密文的末尾,末尾出现的单词 Oet 到底是 betgetletset... 这些组合中的哪一种呢?我们先假设它是最常见的单词 getOg)。

下面我们逐一列出所找到的组合以及假设的对应关系。

thethDWg 这个组合,有可能是 the thingDiWn)。

grINe 这个组合,翻一下字典可以找到很多可能的单词,如 gracegradegrapegrategravegripegrofe、...,这可有点为难。我们先假设 Ia,然后我们可以找到 greater 这样的组合,因此 Ia 应该是正确的。但如果假设 Nc,则会出现 tricening 这样的组合,这个单词怎么看也不像是英语,看来 Nc 是错误的。

英语中出现频率较高的字母中,只有 o 还没有出现在我们的假设中。相对地,密文中出现频率较高的字母中,还没有找到对应关系的有 GZ。我们先假设 Go

使用上面所有的假设重新替换一下密文。

theLoVanAthegraceZonehotZRUUerZAaXaLoVSaZZtroKKingthroRghanorCharAtiKKheCaUetoaF
RnChoLgraceZHRZtriceningonaTineShiChhaAFeentraineAoTeraKoLtXFranChHRZtthethingto
QRenChUXthirZtQRothheAraSingFaCJaLeScaCeZhetooJarRnanAaHRUcanAHRZtUiZZeAtheFRnCh
tRrningroRnAagainSithaonetSothreeheHRUceARcFRtSithnogreaterZRCCeZZagainanAagainh
etrieAaLtertheteUctingUorZeKFRtatKaZthaAtogiTeitRcanASaKJeAaSaXSithhiZnoZeinthea
irZaXingiaUZRretheXareZoRritiZeaZXtoAeZciZeShatXoRCannotget

噢噢,这回在末尾出现了 Cannotget 这样的组合,那么 Cc 应该是没错了。既然 Cc,那么刚才我们的假设 Nc 就是错误的了。

Shich 这个组合,大概是 which 吧(Sw)。

除了高频字母以外,密文中的低频字母 Q 也可以找到一些相关的组合。

例如 thethingtoQRench 这个组合,应该是 the thing to QRench。查字典发现有 quench 这样一个单词(QqRu)。quench 是“解渴”的意思,大概文章讲的是关于喝水的话题吧。

接下来会发现 hotZuUUer 这个组合,大概是 hot summer 吧(ZsUm)。U 连续出现了两次,这是一个关键性的线索,而且和“解渴”的上下文也比较符合。

successagainanAagain 很明显应该是 success again and againAd)。

triedaLter 应该是 tried afterLf)。

whatXoucannotget 应该是 what you cannot getXy)。

thefoVandthegraNesonehotsummersday 应该是 the fox and the grapes one hot summers dayVxNp)。

用上面的假设重新替换密文后,我们发现小写字母的比例大幅增加,这说明我们已经基本上完成了破译工作。

thefoxandthegrapesonehotsummersdayafoxwasstroKKingthroughanorchardtiKKhecametoaF
unchofgrapesHustripeningonaTinewhichhadFeentrainedoTeraKoftyFranchHustthethingto
quenchmythirstquothhedrawingFacJafewpaceshetooJarunandaHumpandHustmissedtheFunch
turningroundagainwithaonetwothreeheHumpedupFutwithnogreatersuccessagainandagainh
etriedafterthetemptingmorseKFutatKasthadtogiTeitupandwaKJedawaywithhisnoseinthea
irsayingiamsuretheyaresouritiseasytodespisewhatyoucannotget

接下来我们再列举一些线索。

foxwasstroKKing
fox was strolling
(K → l)

hetooJarunandaHumpandHustmissed
he took a run and a jump and just missed
(H → j)
(J → k)

hejumpedupFutwithnogreatersuccess
he jumped up but with no greater success
(F → b)

butatlasthadtogiTeitup
but at last had to give it up
(T → v)

没有使用到的最后一个字母

(B → z)

这样我们就全部破译出来了!密钥(替换表)如下。

明文如下。

thefoxandthegrapesonehotsummersdayafoxwasstrollingthroughanorchardtillhecametoab
unchofgrapesjustripeningonavinewhichhadbeentrainedoveraloftybranchjustthethingto
quenchmythirstquothhedrawingbackafewpaceshetookarunandajumpandjustmissedthebunch
turningroundagainwithaonetwothreehejumpedupbutwithnogreatersuccessagainandagainh
etriedafterthetemptingmorselbutatlasthadtogiveitupandwalkedawaywithhisnoseinthea
irsayingiamsuretheyaresouritiseasytodespisewhatyoucannotget

补上空格和标点符号之后,文章就变得非常易读了。

"The Fox and the Grapes"
One hot summer's day, a Fox was strolling through an orchard till he came to
a bunch of grapes just ripening on a vine which had been trained over a lofty
branch.  "Just the thing to quench my thirst," quoth he.  Drawing back a few
paces, he took a run and a jump, and just missed the bunch.  Turning round
again with a one, two, three, he jumped up, but with no greater success.  Again
and again he tried after the tempting morsel, but at last had to give it up,
and walked away with his nose in the air, saying: "I am sure they are sour."
It is easy to despise what you cannot get.

原来这段文章就是《伊索寓言》中《狐狸和葡萄》的故事 2

2这里引用的是互联网上的免费文本。

通过上面的破解过程,我们可以总结出下列结论。

  • 除了高频字母以外,低频字母也能够成为线索
  • 搞清开头和结尾能够成为线索,搞清单词之间的分隔也能够成为线索
  • 密文越长越容易破译
  • 同一个字母连续出现能够成为线索(这是因为在简单替换密码中,某个字母在替换表中所对应的另一个字母是固定的
  • 破译的速度会越来越快。

我们仅仅尝试了一次破译,就获得了这么多的知识,可想而知如果是专业破译者,他们的知识和经验一定是相当丰富的。

实际尝试一次就可以看出,用频率分析来破译简单替换密码对于新手来说也并不是很困难。

从公元前开始,简单替换密码在几百年的时间里一直被用于秘密通信。然而在阿拉伯学者发明频率分析法之后,这种密码很容易就被破译了。

在本章开头,我们引用了爱伦·坡的小说《金甲虫》中出现的一段密文,这也是一种简单替换密码。小说中还描写了使用频率分析进行破译的情景。

小测验 2 简单替换密码的“改良”      (答案见2.7 节)

在上面的例子中,我们发现存在如 cCqQ 这样,明文中的字母被替换成了相同字母的密文的情况。于是 Alice 就想:如果替换表中不出现这种被替换为相同字母的情况,那么密文应该会更难被破译吧?请问 Alice 的想法正确吗?

2.4 Enigma

下面我们来讲解一下第二次世界大战中德国使用的一种名为“Enigma”的密码机。

2.4.1 什么是 Enigma

Enigma 是由德国人阿瑟·谢尔比乌斯( Arthur Sherbius)于 20 世纪初发明的一种能够进行加密和解密操作的机器。Enigma 这个名字在德语里是“谜”的意思。谢尔比乌斯使用能够转动的圆盘和电路,创造出了人类手工所无法实现的高强度密码。在刚刚发明之际,Enigma 被用在了商业领域,后来到了纳粹时期,德国国防军采用了 Enigma,并将其改良后用于军事用途。

2.4.2 用 Enigma 进行加密通信

Enigma 是一种由键盘、齿轮、电池和灯泡所组成的机器,通过这一台机器就可以完成加密和解密两种操作。

发送者和接收者各自拥有一台 Enigma。发送者用 Enigma 将明文加密,将生成的密文通过无线电发送给接收者。接收者将接收到的密文用自己的 Enigma 解密,从而得到明文。

由于发送者和接收者必须使用相同的密钥才能够完成加密通信,因此发送者和接收者会事先收到一份叫作国防军密码本的册子。国防军密码本中记载了发送者和接收者所使用的每日密码,发送者和接收者需要分别按照册子的指示来设置 Enigma。

用 Enigma 进行加密通信的过程如图 2-5 所示。

图 2-5 用 Enigma 进行加密通信的流程

2.4.3 Enigma 的构造

Enigma 的构造如图 2-6 所示。Enigma 能够对字母表中的 26 个字母进行加密和解密操作,但由于图示复杂,这里将字母的数量简化为 4 个。

按下输入键盘上的一个后,电信号就会通过复杂的电路,最终点亮输出用的灯泡。图 2-6 中描绘了按下 \boxed{{\rm a}} 键点亮 \textcircled{\rm D} 灯泡的情形。

图 2-6 Enigma 的构造(只有 4 个字母的情况)

每当按下 Enigma 上的一个键,就会点亮一个灯泡。操作 Enigma 的人可以在按键的同时读出灯泡所对应的字母,然后将这个字母写在纸上。这个操作在发送者一侧是加密,在接收者一侧则是解密。只要将键和灯泡的读法互换一下,在 Enigma 上就可以用完全相同的方法来完成加密和解密两种操作了。大家在图 2-6 中沿着粗线反向走一遍就可以理解这个原理了。

接线板(plugboard)是一种通过改变接线方式来改变字母对应关系的部件。接线板上的接线方式是根据国防军密码本的每日密码来决定的,在一天之中不会改变。

在电路中,我们还看到有 3 个称为转子(rotor)的部件。转子是一个圆盘状的装置,其两侧的接触点之间通过电线相连。尽管每个转子内部的接线方式是无法改变的,但转子可以在每输入一个字母时自动旋转。当输入一个字母时,转子 1 就旋转 1/4 圈(当字母表中只有 4 个字母时)。转子 1 每旋转 1 圈,转子 2 就旋转 1/4 圈,而转子 2 每旋转 1 圈,转子 3 就旋转 1/4 圈。这 3 个转子都是可以拆卸的,在对 Enigma 进行设置时可以选择转子的顺序以及它们的初始位置。

图 2-7 显示了一个转子的放大示意图。

图 2-7 转子

这些装置组合起来使得 Enigma 看起来很像是一个能够动态变化的“鬼脚图”3

3鬼脚图(ghost leg),日本称“阿弥陀签”,是一种基于数学原理的简易决策游戏,其基本原理是将一个序列映射到元素相同但顺序不同的另一个序列,具体请参见维基百科。——译者注

2.4.4 Enigma 的加密

下面我们来详细讲解一下 Enigma 的加密步骤。图 2-8 展示了发送者将一个包含 5 个字母的德语单词 nacht(夜晚)进行加密并发送的过程。

{%}

图 2-8 用 Enigma 加密 nacht

在进行通信之前,发送者和接收者双方都需要持有国防军密码本,国防军密码本中记载了发送者和接收者需要使用的每日密码。

(1) 设置 Enigma

发送者查阅国防军密码本,找到当天的每日密码,并按照该密码来设置 Enigma。具体来说,就是在接线板上接线,并将 3 个转子进行排列。

(2) 加密通信密码

接下来,发送者需要想出 3 个字母,并将其加密。这 3 个字母称为通信密码

通信密码的加密也是通过 Enigma 完成的。假设发送者选择的通信密码为 psv,则发送者需要在Enigma 的键盘上输入两次该通信密码,也就是说需要输入 psvpsv 这 6 个字母。

发送者每输入一个字母,转子就会旋转,同时灯泡亮起,发送者记下亮起的灯泡所对应的字母。输入全部 6 个字母之后,发送者就记下了它们所对应的密文,在这里我们假设密文是 ATCDVT(密文用大写字母来表示)。

(3) 重新设置 Enigma

接下来,发送者根据通信密码重新设置 Enigma。

通信密码中的 3 个字母实际上代表了 3 个转子的初始位置。每一个转子的上面都印有字母,可以根据字母来设置转子的初始位置。通信密码 psv 就表示需要将转子 1、2、3 分别转到 psv 所对应的位置。

(4) 加密消息

接下来,发送者对消息进行加密。

发送者将消息(明文)逐字从键盘输入,然后从灯泡中读取所对应的字母并记录下来。这里是输入 nacht5 个字母,并记录下所对应的 5 个字母(如 KXNWP)。

(5) 拼接

接下来,发送者将“加密后的通信密码”ATCDVT 与“加密后的消息”KXNWP 进行拼接, ATCDVTKXNWP 作为电文通过无线电发送出去。

上面就是用 Enigma 进行加密的操作步骤,看来还真是挺麻烦的。

2.4.5 每日密码与通信密码

大家应该注意到了,在 Enigma 中出现了“每日密码”和“通信密码”这两种不同的密钥。

每日密码不是用来加密消息的,而是用来加密通信密码的。也就是说,每日密码是一种用来加密密钥的密钥。这样的密钥,一般称为密钥加密密钥(Key Encrypting Key,KEK)。KEK 在现代依然很常用,在第 6 章的混合密码系统中也会出现这一概念。

之所以要采用两重加密,即用通信密码来加密消息,用每日密码来加密通信密码,是因为用同一个密钥所加密的密文越多,破译的线索也会越多,被破译的危险性也会相应增加。

2.4.6 避免通信错误

在通信密码的加密中,我们需要将通信密码 psv 连续输入两次,即 psvpsv。这是因为在使用 Enigma 的时代,无线电的质量很差,可能会发生通信错误。如果通信密码没有被正确传送,接收者也就无法解密通信内容。而通过连续输入两次通信密码(psvpsv),接收者就可以对通信密码进行校验,也就是检查一下解密后得到的通信密码是不是 3 个字母重复两次这样的形式。

2.4.7 Enigma 的解密

下面我们来看看 Enigma 是如何解密的(图 2-9)。

{%}

图 2-9 用 Enigma 解密

解密的操作步骤如下。

(1) 分解

接收者将接收到的电文分解成两个部分,即开头的 6 个字母 ATCDVT 和剩下的字母 KXNWP

(2) 设置 Enigma

接收者查阅国防军密码本中的每日密码,并按照该密码设置 Enigma,这一步和发送者进行的操作是相同的。

(3) 解密通信密码

接下来,接收者将加密后的通信密码 ATCDVT 进行解密。接收者在 Enigma 的键盘上输入 ATCDVT 这 6 个字母,然后将亮起的灯泡对应的字母 psvpsv 记下来。因为 psvpsvpsv 重复两次的形式,所以接收者可以判断在通信过程中没有发生错误。

(4) 重新设置 Enigma

接下来,接收者根据通信密码 psv 重新设置 Enigma。

(5) 解密消息

接下来,接收者对消息进行解密。

接收者将电文的剩余部分 KXNWP 逐一用键盘输入,然后从灯泡读取结果并记下来,这样接收者就得到了 nacht 这 5 个字母,也就是完成了对发送者发送的消息进行解密的过程。

上面就是解密的操作步骤。

2.4.8 Enigma 的弱点

上文中我们讲解了 Enigma 的构造以及加密和解密的过程。通过这些信息,我们应该已经可以找到 Enigma 的一些弱点了。

Enigma 可以在每次输入时,通过 3 个转子的旋转来改变电路。然而,在加密通信密码这一重要步骤(最开始的 6 次输入)中,实际上只有转子 1 会旋转,这就是 Enigma 的弱点之一。

将通信密码连续输入两次并加密也是一个弱点,因为密码破译者可以知道,密文开头的 6 个字母被解密之后的明文一定是 3 个字母重复两次的形式。

通信密码是人为选定的也是一个弱点,因为通信密码必须不能被密码破译者推测出来。然而现实中的发送者却有可能使用 aaabbb 这样简单的密码,也经常有人用自己女朋友的名字当作密码,不知道是因为怕麻烦,还是因为过于相信 Enigma 的安全性,或者是没有充分理解通信密码的重要性。密码系统中使用的密钥不能是人为选定的,而应该使用无法预测的随机数来生成。关于随机数,我们将在第 12 章详细探讨。

必须派发国防军密码本也可以说是一个弱点。如果没有国防军密码本,就无法使用 Enigma 进行通信,但如果国防军密码本落到敌人手里,就会带来大麻烦。如果现在所使用的国防军密码本被敌人得到,哪怕只泄露了一本,也必须重新制作新的密码本并发放到全军。“必须配送密钥”这个问题,在广泛使用计算机进行的现代密码通信中也是非常重要的。关于这个话题,我们将在第 5 章的密钥配送问题中详细探讨。

2.4.9 Enigma 的破译

当时,Enigma 被认为是一种无法破译的密码机,为了破译 Enigma,欧洲各国的密码破译者们付出了巨大的努力。

首先,法国和英国的密码破译者通过间谍活动得到了德军使用的 Enigma 的构造。然而,即便知道了 Enigma 的构造,也还是无法破解 Enigma 的密码,这是因为 Enigma 的设计并不依赖于“隐蔽式安全性”(security by obscurity)。即使密码破译者得到了 Enigma 密码机(相当于密码算法),只要不知道 Enigma 的设置(相当于密钥),就无法破译密码。

为 Enigma 破译打开新局面的是波兰的密码破译专家雷耶夫斯基(Marian Rejewski)。雷耶夫斯基得到了法国提供的信息支援,并在此基础上提出了通过密文找到每日密码的方法。

由于每日密码在一天之中是不会改变的,因此密码破译者一天内所截获的所有通信,都是用同一个密码进行加密的。而且,这些密文都有一个共同的特点,那就是通信密码都会重复两次。以 ATCDVT 为例,我们可以知道第 1 个字母和第 4 个字母(AD),第 2 个字母和第 5 个字母(TV),第 3 个字母和第 6 个字母(CT)都是由相同的明文字母加密得到的。此外,我们还知道,在第 1 个字母和第 4 个字母的加密过程中,转子 1 旋转了 3/26 圈。通过上述事实以及大量的密文,雷耶夫斯基对密文字母的排列组合进行了深入的研究。

3 个转子的顺序共有 3×2×1=6 种可能,3 个转子的旋转位置共有 26×26×26=17576 种组合。雷耶夫斯基制作了 6 台机器,分别对这 17576 种组合进行检查。通过使用这些机器,他在大约两小时内通过大量的密文找到了每日密码。

由于担心希特勒进攻波兰导致 Enigma 破译的线索付之一炬,波兰决定将这些情报提供给英国和法国。于是,Enigma 破译的接力棒,就从波兰传给了英法。此后不久,第二次世界大战就全面爆发了。

英国的密码专家们在布莱切利园集中进行了 Enigma 的破译工作,其中,现代计算机之父阿兰·图灵(Alan Turing)也是破译团队的一员。图灵根据之前所获得的情报继续研究,终于在 1940 年研制出了用于破译 Enigma 的机器。Enigma 这一机器创造出了难以破译的密码,但最终战胜 Enigma 的却是另一台机器。

Enigma 的破译过程十分冗长和复杂,在这里无法详细介绍。对此感兴趣的读者请参阅《密码故事:人类智力的另类较量》(The Code Book: The Science of Secrecy from Ancient Egypt to Quantum Cryptography)[Singh] 以及《艾伦· 图灵传:如谜的解谜者》(Alan Turing: The Enigma)[Hodges]。

小测验 3 没有 L 的密文      (答案见2.7 节)

第二次世界大战中,英军的密码破译者截获了一段 Enigma 的密文,他们发现在密文中字母 L 一次都没有出现。据说密码破译者根据没有 L 这一事实推测出了明文,那么明文到底是什么呢?

(本小测验是根据 Rudolf Kippenhahn 所著的 Code Breaking: A History and Exploration 一书中的记载改编而来的)

2.5 思考

为什么要将密码算法和密钥分开呢

我们在介绍密码系统时,经常会说“密码算法是○○,密钥是△△”,也就是说,我们有意识地对密码算法和密钥进行了区分。下面我们来思考一下,将密码算法和密钥分开到底有什么意义呢?

我们来列举一下本章介绍过的密码系统的“密码算法”和“密钥”。

恺撒密码

密码算法:将明文中的各个字母按照指定的字母数平移

密钥:平移的字母数量

简单替换密码

密码算法:按照替换表对字母表进行替换

密钥:替换表

Enigma(通信密码的加密)

密码算法:使用 Enigma 密码机,通过接线板的接线方式、3 个转子的顺序、每个转子的旋转位置对字母进行替换

密钥(每日密码):接线板的接线方式、3 个转子的顺序、每个转子的旋转位置

Enigma(通信电文的加密)

密码算法:使用接线板的接线方式和 3 个转子的顺序固定的 Enigma 密码机,按照每个转子的旋转位置对字母进行替换

密钥(通信密码):每个转子的旋转位置

仔细研究一下每一对密码算法和密钥的组合就会发现,在密码算法中必然存在可变部分,而这些可变部分就相当于密钥。当密码算法和密钥都确定时,加密的方法也就确定了。

如果每次加密都必须产生一个新的密码算法,那真是太诡异了。对于已经开发出的一种密码算法,我们总是希望能够重复使用。

将密码算法和密钥分开的意义正在于此。密码算法是需要重复使用的,但在重复使用同一种算法的过程中,该算法被破译的可能性也在逐渐增大。因此,我们就在密码算法中准备了一些可变部分,并在每次通信时都对这部分内容进行改变,而这一可变部分就是密钥。

将密码算法和密钥分开考虑,就解决了希望重复使用,但重复使用会增加风险这个难题。

图 2-10 将密码算法和密钥分开考虑

本章中,我们介绍了历史上一些有名的密码技术。虽然这些密码技术现在都已经不再使用了,但是“希望重复使用,但重复使用会增加风险”这个难题却依然存在。

现在的密码算法中都有一部分标准化的技术。你也许会想,密码这种需要机密性的领域怎么可能会标准化呢?其实这并不奇怪,请大家回想一下我们之前讲过的那条常识——不要使用保密的密码算法(1.7.1 节)。标准化的推进,使得密码算法能够作为公有财产被开发、研究和利用。即便经过标准化,密文的机密性也丝毫没有降低,这是因为密码算法和密钥是分开的。

密钥才是秘密的精华。因此,在密码技术中,如何管理密钥是一个重要的课题。关于密钥管理,我们将在第 11 章详细讲解。

每个人都可以拥有相同品牌的锁,但每个人都有不同的钥匙。锁的设计是公开的——锁匠都有带有详细图的书,而且绝大多数好的设计方案都在公开专利中进行了描述——但是钥匙是秘密的。

——布鲁斯·施奈尔:《网络信息安全的真相》(Schneier, 2000,p.117)4

4本段引文摘自《网络信息安全的真相》简体中文版第 51 页,吴世忠、马芳译,机械工业出版社出版。——译者注

2.6 本章小结

本章中我们介绍了历史上一些著名的密码系统:恺撒密码、简单替换密码以及 Enigma。关于密码破译技术,我们也尝试了暴力破解和字母频率分析两种方法。此外,我们还对密码算法与密钥的关系进行了思考。

为了破译 Enigma,密码专家们制造出了能够高速进行复杂运算的机器,而这一努力为现代计算机的诞生做出了巨大的贡献。

从下一章起,我们将开始介绍使用计算机来实现的密码技术。

2.7 小测验的答案

小测验 1 的答案:恺撒密码的破译      (2.2.4 节)

可以用暴力破解法来破译,从密钥 0 到 25 逐一进行尝试。

PELCGBTENCUL → 用密钥 0 解密 → pelcgbtencul
PELCGBTENCUL → 用密钥 1 解密 → odkbfasdmbtk
PELCGBTENCUL → 用密钥 2 解密 → ncjaezrclasj
PELCGBTENCUL → 用密钥 3 解密 → mbizdyqbkzri
PELCGBTENCUL → 用密钥 4 解密 → lahycxpajyqh
PELCGBTENCUL → 用密钥 5 解密 → kzgxbwozixpg
PELCGBTENCUL → 用密钥 6 解密 → jyfwavnyhwof
PELCGBTENCUL → 用密钥 7 解密 → ixevzumxgvne
PELCGBTENCUL → 用密钥 8 解密 → hwduytlwfumd
PELCGBTENCUL → 用密钥 9 解密 → gvctxskvetlc
PELCGBTENCUL → 用密钥10 解密 → fubswrjudskb
PELCGBTENCUL → 用密钥11 解密 → etarvqitcrja
PELCGBTENCUL → 用密钥12 解密 → dszquphsbqiz
PELCGBTENCUL → 用密钥13 解密 → cryptography
PELCGBTENCUL → 用密钥14 解密 → bqxosnfqzogx
PELCGBTENCUL → 用密钥15 解密 → apwnrmepynfw
PELCGBTENCUL → 用密钥16 解密 → zovmqldoxmev
PELCGBTENCUL → 用密钥17 解密 → ynulpkcnwldu
PELCGBTENCUL → 用密钥18 解密 → xmtkojbmvkct
PELCGBTENCUL → 用密钥19 解密 → wlsjnialujbs
PELCGBTENCUL → 用密钥20 解密 → vkrimhzktiar
PELCGBTENCUL → 用密钥21 解密 → ujqhlgyjshzq
PELCGBTENCUL → 用密钥22 解密 → tipgkfxirgyp
PELCGBTENCUL → 用密钥23 解密 → shofjewhqfxo
PELCGBTENCUL → 用密钥24 解密 → rgneidvgpewn
PELCGBTENCUL → 用密钥25 解密 → qfmdhcufodvm

密钥为 13,明文(加密前的消息)如下:

cryptography

也就是“密码”这个词。

小测验 2 的答案:简单替换密码的“改良”      (2.3.5 节)

不正确。相反,Alice 的“改良”让密码变得更容易破译了。

密码破译者需要推测密文中的某个字母(如 A)应该解密为哪个字母。这时,如果没有 Alice 的“改良”,其可能性应该有 26 种。然而,经过 Alice 的“改良”后,由于 A 是不可能对应 a 的,因此破译者从一开始就可以将 a 排除掉,而只要考虑剩下的 25 种可能性就可以了。这等于是给了破译者一条用于破译的线索。

像这个例子一样,对密码进行“少许改良”,很可能反而会让安全性变得更差。

小测验 3 的答案:没有 L 的密文      (2.4.9 节)

明文是一段只有字母 l 的文字,即 llllll……。发送者的目的是将毫无意义的明文加密发送以干扰密码破译者。

然而密码破译者知道 Enigma 的构造,即无论接线板如何接线,3 个转子的顺序和每个转子的旋转位置如何改变,输入的字母都绝对不可能被替换成该字母本身。通过密文中没有 L 这一事实,密码破译者就能够推测出其明文可能是一串 l

此外,密码破译者还能够根据密文的排列组合继续进行破译,从而得到推测 Enigma 的接线板和转子状态的线索。

发送者本想干扰密码破译者,却反而为破译者提供了线索。顺便提一下,破解这一谜题的破译者名叫 Mavis Lever,是一位女性。

目录

  • 译者序
  • 前言
  • 第 1 部分 密码
  • 第 1 章 环游密码世界
  • 第 2 章 历史上的密码——写一篇别人看不懂的文章
  • 第 3 章 对称密码(共享密钥密码)——用相同的密钥进行加密和解密
  • 第 4 章 分组密码的模式——分组密码是如何迭代的
  • 第 5 章 公钥密码——用公钥加密,用私钥解密
  • 第 6 章 混合密码系统——用对称密码提高速度,用公钥密码保护会话密钥
  • 第 2 部分 认证
  • 第 7 章 单向散列函数——获取消息的“指纹”
  • 第 8 章 消息认证码——消息被正确传送了吗
  • 第 9 章 数字签名——消息到底是谁写的
  • 第 10 章 证书——为公钥加上数字签名
  • 第 3 部分 密钥、随机数与应用技术
  • 第 11 章 密钥——秘密的精华
  • 第 12 章 随机数——不可预测性的源泉
  • 第 13 章 PGP ——密码技术的完美组合
  • 第 14 章 SSL/TLS ——为了更安全的通信
  • 第 15 章 密码技术与现实社会——我们生活在不完美的安全中
  • 附录 椭圆曲线密码——密码技术综合测验
  • 附录 A 椭圆曲线密码
  • 附录 B 密码技术综合测验
  • 参考文献