密码，亦可传情

为2.14情人节，应项目方要求而作的密码学科普。

2.14西方情人节是一个幸福的节日，情侣们会在这天互送礼物、表示爱意。你知道密码学也可以用来表达爱意么？来看看今天的故事。

五层摩尔斯密码的爱情故事

2009年中国的互联网世界演绎了一段费尽周折的浪漫爱情猜谜传奇。一男生向一女生表白，女生却给了他一段摩尔斯密码，以及很少的提示，并表示破译了这段密码，才答应和他约会。男生绞尽脑汁也不得其解，于是便在百度贴吧里将密码贴出，求助于广大网友。在网友的集思广益下，这段密码最终被破解。

这是一个五层加密的密码，也就是说要破解五层密码才是正确答案。

爱情摩尔斯密码的原样：“****—****—*————***——**———/—********—/”

在最开始，先是网友贴出了摩尔斯密码对照表，然后发现相应密码对应的数字组合和英文字母组合分别是“4194418141634192622374”和“daiddahadafcdaibfbbcgd”。

在贴吧的第40楼，网友“Killing_ill”提示道：“手机键盘吧。”

网友“ybaba”在115楼“哈哈”大笑后留下了这么一段话：“4194418141634192622374，大家注意下这组数字，最大的数字范围是1至9。手机上一共有10个数字按键，其中0和1不对应任何字母，所以不存在0。而为何会有1呢？

再仔细看一下，如果将数字从左到右编序号，1、2、3、4、5直到22，有没有发现奇数编号对应的数字没有1呢？所以奇数编号的数字应该是对应有字母的手机按键，而所有偶数编号对应的数字都是1、2、3、4。为什么只有1、2、3、4？大家再看看手机，所有有字母的按键，最多只有4个字母，所以偶数编号的字母对应的是按键上的第几个字母。”

“ybaba”在作了没有给出答案的推敲之后，又留下了下面这段话：“按照这个方法，我们来看看这串数字××94×××××××74，这是仅有的两个偶数编号的4，相对应9和7。你们再看看手机，只有按键9和7才对应4个字母，其他的都只对应3个。”

网友“片羿天使”在第158楼出现，表示自己已经完全解出来了。在网友的跟贴催促下，在第207楼再次出现，道出了爱情摩尔斯密码的答案，而且给出了解答的步骤。

“片羿天使”从摩尔斯密码推到数字，再从数字推到手机键盘和电脑键盘，然后再重新排序排列，最后再倒换，答案便水落石出了。

首先，“片羿天使”将摩尔斯密码对应的数字“4194418141634192622374”转换成了手机键盘字母。以“41”为例，它对应的就是传统手机键盘上的“4”的第1个字母，“94”则是“9”的第4个字母。这样，“片羿天使”便得到了第二步的答案“GZGTGOGXNCS”。

接着，“片羿天使”又将这些英文字母转换成用电脑键盘打出来的字母。“片羿天使”说：“因为QWE格式（即QWERTY电脑键盘布局）是被世人所认可的，所以也就可能成为密码的码表。这段密码的码表为‘QWE=ABC’，以此类推。”按照这样的次序，上面的来自于手机键盘的字母，就转换到了第三步答案“OTOEOIOUYVL”。

在第四步中，“片羿天使”用了包括凯撒密码、乘法等方法，对第三步的几乎已经可以看出来的答案进行了进一步的解码，最后发现只有用栅栏密码才能读的通。“片羿天使”便将这组字母分成了“OTOEOI”和“OUYVL”两排，然后对插重组，得到第四步的字母排列“OOTUOYEVOLI”。

于是，第五步变得更为简单起来。那便是将“OOTUOYEVOLI”倒序排列，即“I LOVE YOU TOO”。“片羿天使”还肯定楼主有一个非触摸屏手机，而且手机键盘应该是标准格式；并且，他推断楼主还有一台笔记本，或是经常接触电脑。“片羿天使”还说，楼主和给出这段摩尔斯密码的女孩的关系应该是认识很久的那种，而不是一见钟情。

如果你愿意一层一层解开我的密码，你会发现，其实我也爱你。

摩尔斯密码知识点

1838年1月8日，Alfred Vail展示了一种使用点和划的电报码，这是摩尔斯电码前身。

作为一种信息编码标准，摩尔斯电码拥有其他编码方案无法超越的长久的生命。摩尔斯电码在海事通讯中被作为国际标准一直使用到1999年。1997年，当法国海军停止使用摩尔斯电码时，发送的最后一条消息是：“所有人注意，这是我们在永远沉寂之前最后的一声吶喊”！

做为一种实际上已经绝迹的电码，美式摩尔斯电码使用不太一样的点、划和独特地间隔来表示数字、字符和特殊符号。这种摩尔斯电码的设计主要是针对地面报务员通过电报电线传输的，而非通过无线电波。

这种古老的、交错的电码是为了配合报务员接听方式而设计的。不象现在可以从扬声器或者耳机中听到电码的音调，你只能从这些最早期的电报机的一个机械发生装置听到嗒嗒的声音，甚至是从发送电键接听：这种电键在不发送信号时被设置为从动模式，负责发声。

这些报务员大多是为铁路或以后的西联电传等服务。象那时的许多年轻人一样，十几岁的爱迪生就是这样一名话务员。

在今天，国际摩尔斯电码依然被使用着，虽然这几乎完全成为了业余无线电爱好者的专利。直到2003年，国际电信联盟(ITU)管理着世界各地的摩尔斯电码熟练者取得业余无线电执照的工作。在一些国家，业余无线电的一些波段仍然只为发送摩尔斯电码信号而预留。

因为摩尔斯只依靠一个平稳的不变调的无线电信号，所以它的无线电通讯设备比起其它方式的更简单，并且它能在高噪声、低信号的环境中使用。同时，它只需要很窄的带宽，并且还可以帮助两个母语不同、在话务通讯时会遇到巨大困难的操作者之间进行沟通。它也是QRP中最常使用的方式。

在美国，直到1991年，为了获得FCC颁发的允许使用高频波段的业余无线电证书，必须通过每分钟五个单词(WPM)的摩尔斯码发送和接收测试。1999年以前，达到20WPM的熟练水平才能获得最高级别的业余无线电证书(额外类)；1999年12月13日，FCC把额外类的这项要求降低到13WPM。

2003年世界无线电通信大会（WRC03，ITU主办的频率分配专门会议，两年一度）做出决定，允许各国在业余无线电执照管理中自己任选是否对摩尔斯电码进行要求。虽然在美国和加拿大还有书面上的要求，但在一些其他国家正准备彻底去除这个要求。

熟练的爱好者和军事报务员常常可以接收（抄报）40WPM以上速度的摩尔斯码。虽然传统发报电键仍有许多爱好者在使用，但半自动和全自动的电子电键在今天使用越来越广泛。计算机软件也经常被用来生成和解码摩尔斯码电波信号。

凯撒密码和代换密码

凯撒密码是一种代换密码。据说凯撒是率先使用加密函的古代将领之一，因此这种加密方法被称为凯撒密码。

凯撒密码作为一种最为古老的对称加密体制，在古罗马的时候都已经很流行，他的基本思想是通过把字母移动一定的位数来实现加密和解密。明文中的所有字母都在字母表上向后（或向前）按照一个固定数目进行偏移后被替换成密文。例如，当偏移量是3的时候，所有的字母A将被替换成D，B变成E，以此类推X将变成A，Y变成B，Z变成C。由此可见，位数就是凯撒密码加密和解密的密钥。

在上一个五层摩尔斯爱情密码故事中，在将摩尔斯码转换为数字和字母，以及由数字转换为键盘位置所代表的字母，由字母的电脑键盘位置转换为所代替的字母中，都用到了代换密码。

栅栏密码

所谓栅栏密码，就是把要加密的明文分成N个一组，然后把每组的第i个字连起来，形成一段无规律的话。一般比较常见的是2栏的棚栏密码。
比如明文：THERE IS A CIPHER
去掉空格后变为：THEREISACIPHER
两个一组，得到：TH ER EI SA CI PH ER
先取出第一个字母：TEESCPE
再取出第二个字母：HRIAIHR
连在一起就是：TEESCPEHRIAIHR
这样就得到我们需要的密码了！
而解密的时候，我们先吧密文从中间分开，变为两行：T E E S C P EH R I A I H R
再按上下上下的顺序组合起来：THEREISACIPHER
分出空格，就可以得到原文了：THERE IS A CIPHER
但是有些人就偏不把密码作出2栏，比如：明文：THERE IS A CIPHER
七个一组：THEREIS ACIPHER
抽取字母：TA HC EI RP EH IE SR
组合得到密码：TAHCEIRPEHIESR
那么这时候就无法再按照2栏的方法来解了...

古典密码

以上所用的密码技术，都属于古典密码范畴。古典密码编码方法归根结底主要有两种，即置换和代换。

置换密码

把明文中的字母重新排列，字母本身不变，但其位置改变了，这样编成的密码称为置换密码。最简单的置换密码是把明文中的字母顺序倒过来，然后截成固定长度的字母组作为密文。

代换密码则是将明文中的字符替代成其他字符。代换密码又分为列置换和周期置换两种。

列置换是在加密时将明文按固定长m分组，即每行m个字母，在密钥控制下按某一顺序交换列，最后按列优先的顺序依次读出，即产生了密文。解密的过程就是加密过程的逆过程。

周期置换在很大程度上与列置换相同，只不过加、解密时，在列交换后是按行优先的顺序向下进行。

代换密码

代换密码分为单表代换和多表代换两种。

（1）单表代换密码

①加法密码A和B是有 n个字母的字母表。定义一个由A到B的映射：f:A→Bf(ai )= bi=ajj=i+k mod n加法密码是用明文字母在字母表中后面第k个字母来代替。K=3 时是著名的凯撒密码。

②乘法密码乘法密码是简单代替密码的一种。它需要预先知道消息元素的个数，加密的过程其实是相当于对明文消息所组成的数组下标进行加密，然后用明文消息中加密后位置所对应的明文字符代替。

设明文消息元素个数为n，密钥为k。密钥k在选取的时候应满足两个条件：a：0<k<nb：k与n互素设明文消息为M，消息元素为m;则密文消息为C，密文元素为c=m*k mod n;

其解密过程如下：首先要得到解密密钥，就是要求得加密密钥k模n的逆元 ；
具体求法为k * mod n=1;
然后计算m=c * mod n即可得到明文消息M。

举例说明如下：
英文字母有26个，即n=26;
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
M=m[26]={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 };
我们选取密钥k=5;
现在我们对hello进行加密，hello所对应的数组为[8,5,12,12 15]；
由于8*5(mod 26) =40(mod)26=14；依次类推，可得到加密后的数组为[ 14 , 25,8,8, 23 ]；
对应的密文消息就是nyhhw。
现在我们开始对nyhhw解密，首先要求得解密密钥。
由于5*21(mod 26)=105(mod26)=1;所以 =21；
nyhhw所对应的数组为[ 14 , 25,8,8, 23 ]；
由于14*21(mod26)=294(mod26)=8;依次类推，可得到解密后的数组为[8,5,12,12 15];
对应的明文消息就是hello。

③密钥词组代替密码随机选一个词语，去掉其中的重复字母，写到矩阵的第一行，从明文字母表中去掉这第一行的字母，其余字母顺序写入矩阵。然后按列取出字母构成密文字母表

（2）多表代换密码

单表代替密码的安全性不高，一个原因是一个明文字母只由一个密文字母代替。可以利用频率分析来破译。故产生了更为安全的多表代换密码，即构造多个密文字母表，在密钥的控制下用以一系列代换表依次对明文消息的字母序列进行代换。著名的多表代替密码有Vigenere密码等。

① Vernam密码明文、密文、密钥都表示为二进制位:明文：M=m1,m2,… ,mn 密文：K =k1,k2,… ,kn 密钥：C =c1,c2,… ,cn

②Playfair密码用密钥控制生成矩阵，然后每两个字母为单位进行代换。

③Hill密码(乘积密码)建立在矩阵相乘的基础上，但不能抵抗已知明文攻击。

01密码分析的历史

尽管密码分析这个概念的提出十分晚近（1920年由William Friedman确立），但破解密码和密码机的方法却已经存在很久了。

世界上最早的破解密码方法的文字记录可以追溯到九世纪阿拉伯通才AlKindi所著《破解密码信息》，这篇文章论述了一个频率分析的方法。

频率分析是破解经典密码的一个基本方法。在自然语言里，字母表里的有些字母比其它的字母出现得更频繁。例如，在英语里，字母E很有可能是在任何文字样本里出现频率都最高的字母。同样的，TH这两个字母连起来是最有可能出现的字母对。

频率分析法假设密码没有隐藏这样的统计信息。例如，在简单的替换密码中，每个字母只是简单地被替换成另一个字母，那么在密文中出现频率最高的字母就最有可能是E。

频率分析法除了需要用到统计学外，也需要用到语言学。但随着密码算法的日渐复杂，密码分析也渐渐变得主要依赖数学方法。这个改变在第二次世界大战时最为明显。那时，为了破解轴心国的密码，需要发展更加复杂的数学方法。而且，自动计算也头一次被应用到密码分析中，如密码炸弹（Bomba）以及最早的计算机之一，巨人计算机（Colossus）。

尽管第二次世界大战时计算机的运用使得密码分析更加容易，这同时也使得新的密码学方案的复杂程度上升了好几个数量级。总体来说，破解密码在现代比起只用纸和笔的年代来说要困难得多了。现在看来，似乎密码学对纯密码分析来说已经占了上风。

美国历史学家卡恩这样说道：“今天，由数百个商家提供的很多密码系统都不能被已知的密码分析方法来破解。确实，在这样的密码系统中，即使用选择明文攻击，也就是攻击者可以选择明文并比对相应的密文，也不能找出可以用来解开其它加密信息的钥匙。从某种意义上来说，密码分析已经死了。

故事到这并没有结束。密码分析也许死了，但打个不恰当的比方，其实条条大道通罗马。”（2002年11月1日在美国国家安全局50周年纪念会上的讲话）。卡恩接着又提到，其它的攻击方式的可能性增加了，例如拦截攻击，窃听，边信道攻击，以及用量子计算机来代替传统计算机做密码分析。

卡恩对于密码分析所作的论断也许还为时过早。不安全的密码并没有绝迹，美国国家情报机构的密码分析方法也没有公开过。在学术界，新的密码在不断地被设计出来，也经常地被破解。

1984年，Madryga分组密码被一种唯密文攻击破解。1998年，原本提出来要取代DES标准加密算法的分组密码FEAL-4，也因为被学术界发现了很多类似而且实际可行的攻击而消亡。

在工业界，很多密码也被发现有漏洞。例如，在手机中使用的A5/1，A5/2以及CMEA算法，用一般的计算工具可以在几小时，几分钟内，甚至是实时地被破解。2001年，用来保护无线Wi-Fi网络的有线等效加密协议（或称无线加密协议，即WEP）也可以用相关钥匙攻击来破解。

02密码分析的重要性

成功的密码分析影响了历史的进程。能够看懂别人本以为是秘密的想法或计划，这种能力可以成为决定性的优势，在战争期间尤其如此。

在第一次世界大战中，破解齐默尔曼电报促使了美国参战。在第二次世界大战中，对德国密码的成功破解，包括恩尼格玛密码机（Enigma）和洛仑兹密码机（Lorenz Cipher），其后果从使欧洲战场早几个月结束，到对整个战争起决定性作用，各种说法都有（参见ULTRA）。美国也从对日本的PURPLE密码的密码分析中受益（参见MAGIC）。

一些国家的政府很早就已经意识到了密码分析对于情报收集的重要性，不管是对于军事还是外交都一样。

这些国家还建立了专门破解密码的机构，如英国政府通讯总部（GCHQ），以及美国国家安全局（NSA）。这些机构在当今都非常活跃。2004年，有报道说美国成功破解了伊朗的密码。但这是纯粹的密码分析还是有其它因素，目前还不清楚。

对于密码分析的结果来说，其有用的程度也各有不同。密码学家Lars Knudsen于1998年将对于分组密码的攻击按照获得的秘密信息的不同分为以下几类：

完全破解-攻击者获得秘密钥匙。全局演绎-攻击者获得一个和加密和解密相当的算法，尽管可能并不知道钥匙。

实例（局部）演绎-攻击者获得了一些攻击之前并不知道的明文（或密文）。

信息演绎--攻击者获得了一些以前不知道的关于明文或密文的香农信息。

分辨算法--攻击者能够区别加密算法和随机排列。对于其它类型的密码学算法，也可以做出类似的分类。

03密码分析的分类

可将密码分析分为以下五种情形。

（1）惟密文攻击（Cipher text only）对于这种形式的密码分析，破译者已知的东西只有两样：加密算法、待破译的密文。

（2）已知明文攻击（Known plain text）在已知明文攻击中，破译者已知的东西包括：加密算法和经密钥加密形成的一个或多个明文—密文对，即知道一定数量的密文和对应的明文。

（3）选择明文攻击（Chosen plain text）选择明文攻击的破译者除了知道加密算法外，他还可以选定明文消息，并可以知道对应的加密得到的密文，即知道选择的明文和对应的密文。例如，公钥密码体制中，攻击者可以利用公钥加密他任意选定的明文，这种攻击就是选择明文攻击。

（4）选择密文攻击(Chosen cipher text)与选择明文攻击相对应，破译者除了知道加密算法外，还包括他自己选定的密文和对应的、已解密的原文，即知道选择的密文和对应的明文。

（5）选择文本攻击（Chosen text）选择文本攻击是选择明文攻击与选择密文攻击的结合。破译者已知的东西包括：加密算法、由密码破译者选择的明文消息和它对应的密文，以及由密码破译者选择的猜测性密文和它对应的已破译的明文。

很明显，惟密文攻击是最困难的，因为分析者可供利用的信息最少。上述攻击的强度是递增的。一个密码体制是安全的，通常是指在前三种攻击下的安全性，即攻击者一般容易具备进行前三种攻击的条件。