密码复杂度排行(酷到让人望而生畏密码学)(1)

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

——爱伦·坡《金甲虫》

一提到“密码”,我们第一反应可能是,我们平时登录淘宝或者QQ 时需要输入的那个密码,或者刷信用卡或者在ATM 上取钱时输入的密码。但是,上面这种“密码”跟我们本文要探讨的“密码”几乎是完全不同的两码事。

无论是上淘宝还是刷卡时输入的密码,都只是一种身份验证的凭据,换句话说,也就是向系统证明你才是这个账号或银行卡的主人的一种证据——跟“天王盖地虎!”“宝塔镇河妖!”差不多是一回事。严格来说,这种“密码”应该叫作“口令”(对应英文中的password、passcode 或者pin)。

我们要说的“密码”是什么呢?简单来说,密码(对应英文中的cryptography)是一个非常庞大而复杂的信息处理体系,涉及信息的机密性、完整性、认证等许多方面,由此衍生出的技术无时无刻不在保卫着我们生活中的各种信息的安全。

举例来说,比如战争剧里用来加密解密通信消息的技术。在战争剧里,总能看到这样的一幕:战事特别紧张,好多人紧锣密鼓地研究如何破译敌方密码......

密码复杂度排行(酷到让人望而生畏密码学)(2)

《模仿游戏》剧照

这密密麻麻的数字和字母,真的让人望而生畏,但下面这篇文章却让我对密码学有了新的认识:只要解释得当,密码技术也可以变得很简单。

下面我们就将介绍历史上几种著名的密码:

● 恺撒密码

● 简单替换密码

● Enigma

以及两种破译密码的方法(即合法接收者以外的人试图由密文还原出明文的方法)。

● 暴力攻击

● 频率分析

来一起跨过密码技术的大门!

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

恺撒密码

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

一、什么是恺撒密码

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

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

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

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

密码复杂度排行(酷到让人望而生畏密码学)(3)

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

二、恺撒密码的加密

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

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

yoshiko

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

y → B

o → R

s → V

h → K

i → L

k → N

o → R

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

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

密码复杂度排行(酷到让人望而生畏密码学)(4)

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

三、恺撒密码的解密

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

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

B → y

R → o

V → s

K → h

L →i

N → k

R → o

这样我们就得到了明文yoshiko。

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

密码复杂度排行(酷到让人望而生畏密码学)(5)

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

四、用暴力破解来破译密码

通过上面的讲解,我们知道对于发送者用恺撒密码加密过的密文,接收者是能够进行解密的,因此发送者可以向接收者成功发送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 破译恺撒密码

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

简单替换密码

一、什么是简单替换密码

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

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

密码复杂度排行(酷到让人望而生畏密码学)(6)

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

二、简单替换密码的加密

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

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

y → K

o → B

s → L

h → T

i → J

k → S

o → B

就可以得到密文KBLTJSB。

三、简单替换密码的解密

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

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

四、简单替换密码的密钥空间

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

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

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

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

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

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

1 兆等于 1 万亿,即 10的12次方,这里所计算的简单替换密码的密钥总数约为 4×10的26次方,或者约为 2的88次方。

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

五、用频率分析来破译密码

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

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

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

MEYLGVIWAMEYOPINYZGWYEGMZRUUYPZAIXILGVSIZZMPGKKDWOMEPGROEIWGPCEIPAMDKKEYCIUYMGIFRWCEGLOPINYZHRZMPDNYWDWOGWITDWYSEDCEEIAFYYWMPIDWYAGTYPIKGLMXFPIWCEHRZMMEYMEDWOMGQRYWCEUXMEDPZMQRGMEEYAPISDWOFICJILYSNICYZEYMGGJIPRWIWAIHRUNIWAHRZMUDZZYAMEYFRWCEMRPWDWOPGRWAIOIDWSDMEIGWYMSGMEPYYEYHRUNYARNFRMSDMEWGOPYIMYPZRCCYZZIOIDWIWAIOIDWEYMPDYAILMYPMEYMYUNMDWOUGPZYKFRMIMKIZMEIAMGODTYDMRNIWASIKJYAISIXSDMEEDZWGZYDWMEYIDPZIXDWODIUZRPYMEYXIPYZGRPDMDZYIZXMGAYZNDZYSEIMXGRCIWWGMOYM

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

密码复杂度排行(酷到让人望而生畏密码学)(7)

表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,这一点基本上是不会错的。

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

MEeLGVIWAMEeOPINeZGWeEGMZRUUePZAIXILGVSIZZMPGKKDWOMEPGROEIWGPCEIPAMDKKEeCIUeMGIFRWCEGLOPINeZHRZMPDNeWDWOGWITDWeSEDCEEIAFeeWMPIDWeAGTePIKGLMXFPIWCEHRZMMEeMEDWOMGQReWCEUXMEDPZMQRGMEEeAPISDWOFICJILeSNICeZEeMGGJIPRWIWAIHRUNIWAHRZMUDZZeAMEeFRWCEMRPWDWOPGRWAIOIDWSDMEIGWeMSGMEPeeEeHRUNeARNFRMSDMEWGOPeIMePZRCCeZZIOIDWIWAIOIDWEeMPDeAILMePMEeMeUNMDWOUGPZeKFRMIMKIZMEIAMGODTeDMRNIWASIKJeAISIXSDMEEDZWGZeDWMEeIDPZIXDWODIUZRPeMEeXIPeZGRPDMDZeIZXMGAeZNDZeSEIMXGRCIWWGMOeM

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

于是,我们再假设M → t,E → h。

密码复杂度排行(酷到让人望而生畏密码学)(8)

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

theLGVIWAtheOrINeZGWehGtZRUUerZAIXILGVSIZZtrGKKDWOthrGROhIWGrChIrAtDKKheCIUetGIFRWChGLOrINeZHRZtrDNeWDWOGWITDWeShDChhIAFeeWtrIDWeAGTerIKGLtXFrIWChHRZtthethDWOtGQReWChUXthDrZtQRGthheArISDWOFICJILeSNICeZhetGGJIrRWIWAIHRUNIWAHRZtUDZZeAtheFRWChtRrWDWOrGRWAIOIDWSDthIGWetSGthreeheHRUNeARNFRtSDthWGOreIterZRCCeZZIOIDWIWAIOIDWhetrDeAILtertheteUNtDWOUGrZeKFRtItKIZthIAtGODTeDtRNIWASIKJeAISIXSDthhDZWGZeDWtheIDrZIXDWODIUZRretheXIreZGRrDtDZeIZXtGAeZNDZeShItXGRCIWWGtOet

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

接下来我们来看密文的末尾,末尾出现的单词Oet 到底是bet、get、let、set、... 这些组合中的哪一种呢?我们先假设它是最常见的单词get(O → g)。

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

thethDWg 这个组合,有可能是the thing(D → i,W → n)。

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

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

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

密码复杂度排行(酷到让人望而生畏密码学)(9)

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

Shich 这个组合,大概是which 吧(S → w)。

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

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

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

successagainanAagain 很明显应该是success again and again(A → d)。

triedaLter 应该是tried after(L → f)。

whatXoucannotget 应该是what you cannot get(X → y)。

thefoVandthegraNesonehotsummersday 应该是the fox and the grapes one hot summers day(V → x,N → p)。

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

thefoxandthegrapesonehotsummersdayafoxwasstroKKingthroughanorchardtiKKhecametoaFunchofgrapesHustripeningonaTinewhichhadFeentrainedoTeraKoftyFranchHustthethingtoquenchmythirstquothhedrawingFacJafewpaceshetooJarunandaHumpandHustmissedtheFunchturningroundagainwithaonetwothreeheHumpedupFutwithnogreatersuccessagainandagainhetriedafterthetemptingmorseKFutatKasthadtogiTeitupandwaKJedawaywithhisnoseintheairsayingiamsuretheyaresouritiseasytodespisewhatyoucannotget

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

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)

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

密码复杂度排行(酷到让人望而生畏密码学)(10)

明文如下。

thefoxandthegrapesonehotsummersdayafoxwasstrollingthroughanorchardtillhecametoabunchofgrapesjustripeningonavinewhichhadbeentrainedoveraloftybranchjustthethingtoquenchmythirstquothhedrawingbackafewpaceshetookarunandajumpandjustmissedthebunchturningroundagainwithaonetwothreehejumpedupbutwithnogreatersuccessagainandagainhetriedafterthetemptingmorselbutatlasthadtogiveitupandwalkedawaywithhisnoseintheairsayingiamsuretheyaresouritiseasytodespisewhatyoucannotget

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

"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 简单替换密码的“改良”

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

Enigma

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

一、什么是Enigma

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

二、用Enigma 进行加密通信

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

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

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

密码复杂度排行(酷到让人望而生畏密码学)(11)

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

三、Enigma 的构造

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

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

密码复杂度排行(酷到让人望而生畏密码学)(12)

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

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

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

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

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

密码复杂度排行(酷到让人望而生畏密码学)(13)

图7 转子

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

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

四、Enigma 的加密

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

密码复杂度排行(酷到让人望而生畏密码学)(14)

图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 分别转到p、s、v 所对应的位置。

(4) 加密消息

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

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

(5) 拼接

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

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

五、每日密码与通信密码

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

每日密码不是用来加密消息的,而是用来加密通信密码的。也就是说,每日密码是一种用来加密密钥的密钥。这样的密钥,一般称为密钥加密密钥( Key Encrypting Key,KEK)。KEK在现代依然很常用。

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

六、避免通信错误

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

七、Enigma 的解密

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

密码复杂度排行(酷到让人望而生畏密码学)(15)

图9 用Enigma 解密

解密的操作步骤如下。

(1) 分解

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

(2) 设置Enigma

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

(3) 解密通信密码

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

(4) 重新设置Enigma

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

(5) 解密消息

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

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

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

八、Enigma 的弱点

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

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

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

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

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

九、Enigma 的破译

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

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

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

由于每日密码在一天之中是不会改变的,因此密码破译者一天内所截获的所有通信,都是用同一个密码进行加密的。而且,这些密文都有一个共同的特点,那就是通信密码都会重复两次。以ATCDVT 为例,我们可以知道第1 个字母和第4 个字母(A 和D),第2 个字母和第5 个字母(T 和V),第3 个字母和第6 个字母(C 和T)都是由相同的明文字母加密得到的。此外,我们还知道,在第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 的密文

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

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

思考

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

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

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

恺撒密码

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

密钥:平移的字母数量

简单替换密码

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

密钥:替换表

Enigma(通信密码的加密)

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

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

Enigma(通信电文的加密)

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

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

——

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

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

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

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

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

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

密钥才是秘密的精华。因此,在密码技术中,如何管理密钥是一个重要的课题。

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

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

本文节选自史上最好懂的密码学——《图解密码技术(第3版)》。

密码复杂度排行(酷到让人望而生畏密码学)(16)

图解密码技术(第3版)

  • 史上最好懂密码学,豆瓣评分9.5
  • 日本数学协会出版奖得主、《程序员的数学》《数学女孩》作者结城浩重磅力作

本书以图配文的形式,详细讲解了6种非常重要的密码技术:对称密码、公钥密码、单向散列函数、消息认证码、数字签名和伪随机数生成器。

第1部分讲述了密码技术的历史沿革、对称密码、分组密码模式(包括ECB、CBC、CFB、OFB、CTR)、公钥、混合密码系统。第2部分重点介绍了认证方面的内容,涉及单向散列函数、消息认证码、数字签名、证书等。第3部分讲述了密钥、随机数、PGP、SSL/TLS以及密码技术在现实生活中的应用。

小测验的答案

小测验 1 的答案:恺撒密码的破译

可以用暴力破解法来破译,从密钥 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 的答案:简单替换密码的“改良”

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

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

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

小测验 3 的答案:没有 L 的密文

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

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

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

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

,