【讲 义】单字母替换密码及实例

通过把信息隐藏起来的这种秘密通信称为Staganography(隐文术)，由希腊词Steganos(意为“覆盖”)和Graphein(意为“写”)派生而来。从希罗多德以后2000多年，各种形式的隐文术被使用。例如，中国古代将信息写在小块丝绸上，塞进一个小球里，再用蜡给封上，然后让信使吞下这个蜡球。16世纪，意大利科学家乔瓦尼·波塔描述了如何将信息埋藏在一个煮熟的鸡蛋里：他把少许明矾和一点醋混在一起制作成一种墨水，再用这种墨水将信息写在鸡蛋壳表面。墨水溶液就会经蛋壳上的微孔渗透进去，在已凝固的鸡蛋白表面留下印记，这样只能剥去蛋壳后才能读取。隐文术也包括用隐形墨水来写信息，早在公元一世纪普林尼就解释了体液如何用作隐形墨水。用这种液体写的字干后即变得透明，但轻轻地加热就能把液体烤焦，从而字体就以棕色显现出来。许多有机流体都有这样的性质，因为它们富含碳因而变得很容易被烤焦。事实上，即使是现在间谍也很少知道在标准配备的隐形墨水用完之后还可以用自己的尿来临时代替。
隐文术的长久使用表明它确实起到了一定保密作用，但它也有一个根本的弱点。如果信使被搜查，信息被发现，那么秘密通信的内容也立即暴露无遗。一旦信息被截获，所有的安全性也就随之荡然无存。一个严格的士兵会例行地搜查每一个过境人，包括刮一刮所有上蜡的刻写板，给所有空白纸张加加热，剥开煮熟的鸡蛋，剃光人们的头发等等，难免会有发现隐藏信息的时刻。
因此，在隐文术发展的同时，还有另一种方法也在演化，那就是Cryprography(密码术)，从希腊词Kryptos(意为隐藏)派生而来。密码术的目的不是隐藏密码本身，而是要隐藏它的意思，也就是一种和加密的过程。为了使信息无法被外人理解，将信息按照事先在发送者和接收者之间规定好的某种特别规则打乱。那么接受者可以将打乱的信息恢复原样，信息就可以被理解。密码术的优势在于即使敌人截住了一条加密的信息，也无法读懂它。不知道扰乱的规则，敌方将很难(也并非不可能)重现密文的原始含义。
虽然隐文术和密码术是各自独立的，但完全可以将一条信息既混乱又隐藏以取得一个最安全的效果。例如，二战期间流行的微粒照片是一种隐文术。德军在拉丁美洲的间谍将一页文件缩小在直径不到1毫米的微型照片上，看上去就是一个点，再将这个点状照片贴在看似无关紧要的一封信中的某个句号上面。这种微型照片在1941年第一次被美国联邦调查局发现，紧接着美军就有所警觉，查看信中有无微弱的光点，它可能就是反滑的胶片反射出来的光。从那以后，美军美军能读懂大多数被截住的微型照片的内容，除非德军间谍有所防范，在缩小之前，将照片中的信息混乱。这样，密码术融进了隐文术中，美军即使有时截获了通信，但却无法获得关于德间谍活动的任何新的信息。在秘密通讯的上述两种分支中，密码术是更加有效的，因为它能防止确切的信息落到敌军手中。
同样，密码术也会被分为两种，即易位和替换。在易位中，组成信息的字母被简单地重排，形成互相颠倒的一组字母序列(我们暂称之为易位句)。对于特别短的信息，例如一个单词，这种方法相对不可靠，因为只有有限的几种方法来重组这个句子。以三个字母COW为例，仅有六种结果：COW，OCW，CWO，OWC，WCO，WOC。然而，随着字母逐渐增多，重组的可能结果也急剧膨胀，从而不可能再复原到原来的信息，除非知道具体混乱的规则。例如有下面一条信息：For example, consider this short sentence。其中只含有35个字母，然而却有5×10的31次方种不同的排列结果。如果一人每秒能检查一条，世界上所有的人日夜工作的话，那么宇宙泯灭轮回1000次，才能查完所有这些结果。
即使是很短的信息，地方拦截员要复原出其原意也是不切实际的，因而，字母的随机排列似乎提供了一种很高的安全性。但也有个缺点。易位虽然有效地形成一个极其难的易位句，但是，如果字母既不是按照某种韵律也不是按照其他什么逻辑而是随机地被混乱，那么复原一个易位句对于一个联络好的接收人或对于一个敌方拦截人员一样是不可能的。为了使易位行之有效，字母的排列需要遵循一种直接的规律，当然这种规律实现只有发送信息的人和接受人共同知道，并对敌方是保密的。例如，在学校里，学生有时用一种叫“栅栏”的易位方法来传递信息，信息中的字母被交替地写成上下两行，再将下面一行文字附加在上面一行的后面，从而形成一段加密后的信息。例如：

THE SECRET IS THY PRISONER; IF THOU LET IT GO, THOU ARE A PRISONER TO IT
T Y E R T S H P I O E I T O L T T O H U R A R S N R O T
H S C E I T Y R S N R F H U E I G T O A T P I O E T I
→THYSECRETISTHYPRISONERIFTHOULETITGOTHOUAREAPRISONERTOIT

接收者只需简单地将上述过程反过来记得到信息。已有许多程序化的易位方法，包括三线栅栏密码，它是先将信息写成三行字母而不是两行，也可以选择再交换每一对字母，使第一和第二行字母交换位置，第三和第四交换位置，以此类推。
另一种易位形式第一次被做成了军用密码装置，那是斯巴达的一种装置，早在公元前五世纪就出现了。这种外观是一根菱形木棍，外面缠绕着一条皮革或羊皮纸。发送人先沿着木棍纵向在皮带上写上信息，然后再解开皮带，那么从皮带上就看到一些无意义的字母，信息已被混乱了，信使就可以带着这条皮带，如果再来点隐文术的手段，他可以将其伪装成腰带系在身上，而信息却写在反面。复原信息时，接收者只需简单地把皮带绕在一根木棍上，其直径应和发送者使用的一般大。公元前404年，斯巴达的莱桑德接见了一位满身血污、憔悴不堪的信使，他从波斯来，本来是五个人，现在只有他在艰难的旅途中存活下来。这位信使把他的皮带递给莱桑德，莱桑德将皮带缠绕在密码装置上，得知波斯法拿巴兹正计划进攻斯巴达。正是因为这个密码装置，莱桑德才有所准备，并进行了有力还击。
与易位并列的密码术是替换。关于替换加密的最早描述出现在《爱经》中，这是由婆罗门学者写于公元四世纪的一篇文章，但根据手迹来看，可追溯到公元前四世纪。《爱经》建议女人应学会64种技术，如做饭、穿衣、按摩和制备香水，还包括一些如咒语、象棋、装订和木工之类的不太常见的技术。第45种是密文术。其中介绍的一种方法就是先随机地将字母两两配对，然后将原始信息中的每一个字母用它的配对者来代替。以罗马字母为例，我们可以进行如下配对：

A D H I K M O R S U W Y Z
V X B G J C Q L N E F P T

那么，对于句子：meet at midnight，发送者将写成：CUUZ VZ CGXSGIBZ。这种形式的密文叫做替换密码，因为原文中的每一个字母都被换成一个不同的字母，所以可以作为易位的一种辅助方法。在易位中字母不变，位置改变；替换中字母改变，位置不变。
将替换密码用于军事用途的第一个文件记载是凯撒著的《高卢记》。凯撒描述了他如何将迷信送到正处在被围困、濒临投降的西塞罗。其中罗马字母被替换成希腊字母使得敌人根本无法看懂信息。关于这次奇妙的传送，凯撒是这样写的：
信使受到指示，如果他不能接近被围困的军营，他就将信件绑在一根矛上，然后将矛投到被围困的军营内。
可是掷出的矛碰巧插进了一个防塔里，连接两天没有被人发现，第三天一个士兵看见了，取下来交给西塞罗。西塞罗看完之后在全军面前复述了这个信息，大家都倍受鼓舞。
凯撒频繁地使用密文，对此瓦莱利厄斯·普罗布斯做过详细地描述，但不幸失传了。然而有幸的是苏托尼厄斯在公元二世纪写下《凯撒传》，书中对凯撒用过的其中一种替换密码作了详细的描写。凯撒只是简后第三个字母代替。密码学家通常将用来书写原始信息的有关字母称为明码字母表，这里简称明码表；而把用来替换明码字母的有关字母称为密码字母表，这里简称密码表。当把明码表放在密码表的上面时，很明显密码字母表和明码字母表相比后移了3个位置。因而这种形式的替换通常叫做凯撒移位密码，或简单说，凯撒密码。这里我们可以给密码下一个定义：一个密码是指任何形式的一种隐秘的替换，其中每个字母都被另一个字母或符号代替。

明码表 a b c d e f g h i j k l m n o p q r s t u v w x y z
密码表 D E F G H I J K L M N O P Q R S T U V W X Y Z A B C
明文 v e n i, v i d i , v i c i
密文 Y H Q L. Y L G L. Y L F L

尽管苏托尼厄斯仅提到三个位置的凯移位，但显然从1到25个位置的移位我们都可以使用，从而对每个字母我们都能构建25种不同的密码字母来代替它。实际上，如果我们对移位不加限制，即允许密码字母表是明码字母表的任一种重排，那么我们能得到更大数目的密码字母表。有超过4×10的27次方种这样的重组，因而存在有同样数目的密码字母表。
每个不同的密码都代表着一种加密方法，包括算法和密钥两元素，这两个元素描述了每种加密的精确细节。在上述例子中，将信息中每个明码字母用密码字母来代替就代表一种算法，而密码字母表可以是明码字母表的任一种重排。密钥则明确了某特定加密过程中所用的密码字母表。
一个敌人在研究一段被截获的信息时，或许能猜到其所用的算法，却无法得知其所用的特定密钥。例如，他们可能深深地怀疑原始文件中的每一个字母都根据某种密码表被另一个不同的字母代替，但他们不可能知道哪个密码表被使用了。加入密码表，即密钥，只是发送者和接收者之间严守的一个秘密，那么敌人就不能对截住的信息进行解密。和算法相对立，密钥的重要性是密码术中永久的一项原则。对此，1883年，荷兰语言学家奥古斯特在其所著《密码学》一书中作了权威性的陈述：一个密码系统的安全性不在于对加密算法进行保密，而仅在于对密钥的保密。
除了对密钥保密外，一个安全的密码系统也必须有一个大范围的可供选择的密钥。例如，如果发送者用凯撒转移密码来加密一段信息，那么这种加密相对就较弱，因为只有25种可能的密钥。从敌人来说，如果他们截住了这信息并怀疑其使用的是凯撒移位算法，那么他们只需简单地检查这25种可能性即可破解。然而，如果发送者使用更为综合的替换算法，也就是允许密码表是明码表的任一种随意排列，那么检查所有可能的密钥将是一件可怕的任务。如果一个地方间谍每秒能检查4×10的27次方种可能密钥中的一条，检查完所有这些密钥并破解了信息将花费宇宙轮回10亿次所经历的时间。
这种密码很实用，因为它在很容易实施的同时提供了很高的安全性。发送者很容易定一个密钥，只需说明一下重排后得到的密码表中26个字母的顺序，就有效地防止敌人通过所谓蛮力筛选的方法检验所有可能的密钥，密钥的简单性是重要的，因为密钥是发送者和接收者所共知的，密钥越简单，误解的机会就越小。
事实上，如果发送者可以接受密钥数目的稍微减少，密钥甚至可以更简单。发送者可以不通过随机地重排明码字母表来得到密码表，而是选择一个关键词或关键词组。例如，用JULIUS CAESAR作为一个关键词组，先将其中的空格和重复字母去掉(JULISCAER)，然后将其作为密码表的前部分密码字母，至于后部分，先将明码字母表中在关键词组中出现过的字母去掉，再按顺序接在其后。因而，所得到的密码表就是：

明码表 a b c d e f g h i j k l m n o p q r s t u v w x y z
密码表 JU L I S C A E R T V W X Y Z B D F G H K M N O P Q

用这种方法建立一个密码表的优点在于关键词或关键词组容易被记住，因而密码表也一样。这一点很重要，因为如果发送者将密码表写在一张纸上，敌人可能会截获这张纸，从而发现密钥并能读取用该密钥加密的通信。但是，如果密钥仅存留在记忆中，就不太可能落入地方手中。显然用关键词组产生的密码表数目比那种明码表随机排列产生的数目少得多，但也很大，对敌人也是不可能通过测试所有可能关键词来复原截获的信息。
替换密码的简单有效使其在公元前一个千年里在密文技术领域占尽了优势。密码编码者已经建成了一个系统能够保证安全的通讯，因此如果没有必要，就不必进一步发展，也就无需更深入研究。因而任务就落在了密码破解者的身上，他们要不断地尝试破解替换密码。究竟有没有方法能使敌方拦截者重复一段被加密的信息呢？许多古代学者认为替换密码是无法破解的，庞大数目的可能密钥的存在，使得几个世纪来都被认为是可靠的。但是，密码破解者最终发现了一种捷径来穷搜索有可能的密钥。不用花费数亿年的时间来破解一个密码，通过捷径复原一条信息也就十几分钟的事情。这项突破首先发生在东方，是一次语言学、统计学和宗教信仰之间的卓越的联合。


阿尔-金迪的革命性的密码破译系统可压缩在两段话中：
如果我们知道一条加密信息所使用的语言，那么破译这条加密信息的方法就是找出用同样的语言写的一篇其他文章，大约一页纸长，然后我们计算其中每个字母的出现频率。我们将频率最高的字母标为1号，频率排第2的标为2号，第三标为3号，以此类推，直至数完样品文章中的所有字母。
然后我们观察需要破译的密文，同样分类出所有的字母，找出频率最高的字母，并全部用样本文章中最高频率的字母替换。第二高频的字母用样文中2号替换，第三则用3号替换，直到密文中所有字母均已被样文中的字母替换。

表：此相对频率是从报纸和小说中记录下来的。共调查100362个字母表惯例，由H.克和F.皮波刊登在《密码系统——通信保护》上。

A-8.2
B-1.5
C-2.8
D-4.3
E-12.7
F-2.2
G-2.0
H-6.1
I-7.0
J-0.2
K-0.8
L-4.0
M-2.4
N-6.7
O-7.5
P-1.9
Q-0.1
R-6.0
S-6.3
T-9.1
U-2.8
V-1.0
W-2.4
X-0.2
Y-2.0
Z-0.1

然而我们不能无条件地应用阿尔-金迪的方法来破译密码。例如有一篇短句讨论空气对非洲带斑纹的四足动物运动的影响：“From Zanzibar to Zambia and Zaire, zones make zebras run zany zigzags.”大意是从桑给巴尔到赞比亚和扎伊尔，这些空气新鲜的地带使得斑马以滑稽的姿态弯弯曲曲地向前奔跑。对这个句子直接做频度分析就没有什么意义。通常，短文可能较明显地偏离标准频率。加入文章少于100个字母，那么用来解密就会很困难。而另一方面，较长的文章会更可能地接近标准频率，尽管并不总是这样。1969年法国作家乔治斯·佩雷克写了一本200页的小说《逃亡》，其中没有一个含有e的单词。更令人称道的是英国小说和评论家吉尔伯特·阿代尔成功地将《逃亡》翻译成英文，而其中居然也没有一个e字母。阿代尔将这本译著取名为《真空》，令人惊叹，值得一读。由于英文字母中最常见的字母完全没有出现，因而如果将这本书根据单字母替换密码而进行加密的话，那么天真地试图去解密它将会受到极大阻碍。

实例——破译一条密文

PCQ VMJYPD LBYK LYSO KBXBJXWXV BXV ZCJPO EYPD KBXBJYUXJ LBJOO KCPK. CP LBO LBCMKXPV XPV IYJKL PYDBL, QBOP KBO BXV OPVOV LBO LXRO CI SX’XJMI, KBO JCKO XPV EYKKOV LBO DJCMPV ZOICJO BYS, KXUYPD: “DJOKL EYPD, ICJ X LBCMKXPV XPV CPO PYDBLK Y BXNO ZOOP JOACMPLYPD LC UCM LBO IXZROK CI FXKL XDOK XPV LBO RODOPVK CI XPAYOPL EYPDK. SXU Y SXEO KC ZCRV XK LV AJXNO X IXNCMJ CI UCMJ SXGOKLU?”
OFYRCDMO, LXROK IJCS LBO LBCMKXPV XPV CPO PYDBLK

已知：此段密文根据单字母替换密码进行了加密，书写语言为英语，可通过频度分析破解。

解：
1..密文频度分析
字母 出现次数 百分比 字母 出现次数 百分比
A 3 0.9 N 3 0.9
B 25 7.4 O 38 11.2
C 27 8.0 P 31 9.2
D 14 4.1 Q 2 0.6
E 5 1.5 R 6 1.8
F 2 0.6 S 7 2.1
G 1 0.3 T 0 0.0
H 0 0.0 U 6 1.8
I 11 3.3 V 18 5.3
J 18 5.3 W 1 0.3
K 26 7.7 X 34 10.1
L 25 7.4 Y 19 5.6
M 11 5.3 Z 5 1.5
2.由于密文较短，先将注意力放在密文中出现超过30次的三个字母上，即O、X和P。
参考标准频度表，尝试替换：
O=e、t或a； X=e、t或a； P=e、t或a。
此外需要对频度分析做一些细微的改进。除了简单地计算三个字母的频率外，还可以注意周围其他字母出现的情况。例如，字母O的前后有其他字母吗？或者，字母O是否倾向于仅有几个特定的字母做邻居？回答这些问题将会很好地表明O代表一个原因，那它可出现在其他大多数字母的前后，而如果代表一个辅音，则会避开大多数的字母。例如，字母e能够与其他的几乎每一个字母组合，而字母j却几乎不会出现在字母b d g j k m q和v的两边。
下表取密文中最常见的O、X和P三字母，列出每个字母与其他字母相邻的次数。例如O出现在A前一次，出现在A后零次，因此表中第一个总数为1。字母O能与大多数的字母相邻，仅与7个字母完全不靠，因O行有7个0。字母X同样活跃，因为它除了8个字母以外的其他所有字母的两旁都有它的踪迹。然而字母P却没有那么多的朋友，它一般只潜伏在几个字母的两边，与15个字母没有接触。这些情况表明，O和X代表元音，而P代表一个辅音。
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
O 1 9 0 3 1 1 1 0 1 4 6 0 1 2 2 8 0 4 1 0 0 3 0 1 1 2
X 0 7 0 1 1 1 1 0 2 4 6 3 0 3 1 9 0 2 4 0 3 3 2 0 0 1
P 1 0 5 6 0 0 0 0 0 1 1 2 2 0 8 0 0 0 0 0 0 11 0 9 9 0
究竟是O=e和X=a呢还是O=a和X=e呢？密文中有个有趣的现象是OO组合出现了两次，而XX组合却没有。由于在一般英文文章中ee出现的频率比aa高，因此一个可能结论是O=e，X=a。
在此基础上，辨认出密文中的两个字母。我们的结论是X=a，事实依据是X在密文中以单字形式出现过，而英文中仅有两个单词有单字组成，其中一个就是a。密文中另一个以单字形式存在的字母是Y，它非常有可能代表英文中的另一个单字母词i。从一个单字母着手是标准的密码破译方式。这种特殊的技巧也只有当密文单词间还留有空格时才有效。通常，密码的作者会移去所有的空格，以便使敌方拦截者更难还原信息。
虽然单词之间有空格，但我们仍需使用下面的技巧，这种技巧对已连成一串字符的密文同样有效。一旦我们已经辨认出字母e，使用这个技巧能使我们标出字母h。在英文中，字母h经常出现在e的前面(如then，they)，却很少位于其后。下面显示了密文中的字符O(我们已经认定它代表e)出现在其他字母前后的频率，该表暗示密文中字母B代表h，因为它出现在O前面9次，却没有一次位于其后。表中没有其他字母像B这样有着与O一样如此不对称的关系。
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
O前 1 0 0 1 0 1 0 0 1 0 4 0 0 0 2 5 0 0 0 0 0 2 0 1 0 0
O后 0 9 0 2 1 0 1 0 0 4 2 0 1 2 2 3 0 4 1 0 0 1 0 0 1 2
我们现在已经明确了4个字母，O=e，X=a，Y=i，B=h，我们可以开始将密文中的一些字母替换成明文中的字母。这一步虽然简单，但可以帮助我们确定其他几个字母，因为我们可从密文中猜出一些单词来。例如，英语中最常见的三个字母单词是the和and，因而可较容易认出密文中出现6次Lhe和出现5次的aPV。那么，L可能代表t，P可能代表n，V可能代表d。我们现在把密文中的这些字母换回其原来的真是面目。
PCQ VMJiPD LhiK LiSe KhahJaWaV haV ZCJPe EiPD KhahJiUaJ LhJee KCPK. CP Lhe LhCMKaPV aPV IiJKL PiDhL, QheP Khe haV ePVeV Lhe LaRe CI Sa’aJMI, Khe JCKe aPV EiKKeV Lhe DJCMPV ZeICJe hiS, KaUiPD: “DJeKL EiPD, ICJ a LhCMKaPV aPV CPe PiDhLK i haNe ZeeP JeACMPLiPD LC UCM Lhe IaZReK CI FaKL aDeK aPV Lhe ReDePVK CI aPAiePL EiPDK. SaU i SaEe KC ZCRV aK LV AJaNe a IaNCMJ CI UCMJ SaGeKLU?”
eFiRCDMe, LaReK IJCS Lhe LhCMKaPV aPV CPe PiDhLK

nCQ dMJinD thiK tiSe KhahJaWad had ZCJne EinD KhahJiUaJ thJee KCnK. Cn the thCMKand and IiJKt niDht, Qhen Khe had ended the taRe CI Sa’aJMI, Khe JCKe and EiKKed the DJCMnd ZeICJe hiS, KaUinD: “DJeKt EinD, ICJ a thCMKand and Cne niDhtK i haNe Zeen JeACMntinD tC UCM the IaZReK CI FaKt aDeK and the ReDendK CI anAient EinDK. SaU i SaEe KC ZCRd aK td AJaNe a IaNCMJ CI UCMJ SaGeKtU?”
eFiRCDMe, taReK IJCS the thCMKand and Cne niDhtK

一旦确定了一定数量的字母，密码破译的进展也就会很快。例如，第二句开头单词是Cn，由于每个单词都至少含有一个元音，因此C一定是元音。我们只剩下两个元音有待辨认，即u和o，u不符合，因而C一定代表o。我们还有单词Khe，说明K代表的不是t就是s。但我们已知道L=t，因此显然K=s。确认了这两个字母后，我们再将它带入密文中，出现了词组thoMsand and one niDhts。凭感觉就能猜到是thousand and one night。最后一行文字似乎告诉我们这短信息来自《Tales from the Thousand and One Night》。这意味着M=u，I=f，D=g，R=l，S=m。
通过继续猜测其他的单词，我们可以确认出其他的字母。但是先来看看对于明码字母表和密码字母表我们得到了什么。这两个表形成了密钥，密码作者即用它来进行替换从而加密信息。通过确认密文中字母的真实值，我们已经有效地得到密码字母表中的一些具体细节。到目前为止，我们的收获可概括在以下的原初字母表和密码字母表中。
明码表 a b c d e f g h i j k l m n o p q r s t u v w x y z
密码表 X - - V O I D B Y - - R S P C - - J K L M - - - - -
通过检查部分的密码字母表，我们能够完成密码的破译。密码表中的序列VOIDBY表明密码作者已经选了一个关键词组来作为密钥的骨架。稍微猜一下就能知道该关键词组可能是AVOID BY GEORGES PEREC，除去其中空格和重复的字母后得到AVOIDBYGERSPC。跟随其后的密码表中的字母按照字母表的顺序继续下去，并略过关键词组中出现过的字母。但这个例子有些特殊，该密码作者并没有像通常那样将关键词组放在密码字母表的最前方，而是从第三个字母开始。这可能是因为关键词组是以A开头，密码作者想避免将a加密成A。最后，命去了密码字母表中的所有字母后，我们就能揭开整篇的密文，密码破译就此大功告成。
明码表 a b c d e f g h i j k l m n o p q r s t u v w x y z
密码表 X Z A V O I D B Y G E R S P C F H J K L M N Q T U W

now during this time shahrazad had borne king shahriyar three sons. on the thousand and first night, when she had ended the tale of ma’aruf, she rose and kissed the ground before him, saying: “grest king, for a thousand and one nights i have been recounting to you the fables of past ages and the legends of ancient kings. may i make so bold as td crave a favour of your majesty?”
epilogue, tales from the thousand and one nights