密码的发展1

原创
04/15 16:57
阅读数 54

码书笔记

隐私权是所有人的一项根本权利,可是如何防止自己的信息被其他人窃取呢?想让信息不被拦截在互联网时代已经不可能了,我们要做的是让其他人即使拦截到了信息也不明白它传达了什么,这就是密码的作用。

隐匿法

密码不是一步到位的,到现在还一直在发展中。在最开始,人们想到的很朴素的保守秘密办法就是不让其他人看到秘密。在战争期间,信差会打扮成各种各样的人来瞒过敌方的侦查,以便将情报传递出去。希罗多德记录了一个信差先将自己的头发剃光,然后将信息写在头皮上,等头发长出来后再去传递这则消息。侦探剧里的隐形墨水也是一种,将信息用隐形墨水写到纸上,干了之后字迹隐去,肉眼不可见,等到送到目的地,用火烤一烤字迹就显形了,如果隐形墨水用光了,甚至可以使用尿液来应急。

密码法

隐匿法虽然可以隐藏信息,但是一旦被发现信息就直接泄露了,因为隐匿法的保密方式是将信息本体隐藏起来。与之相对的,密码法追求的是隐藏信息的意义,即使信息被发现了,敌方也看不懂,这样也实现了信息的保密。

密码法通过发信人和收信人约定好的规则将把信息转译成不可理解的文字或符号,这就是我们熟知的加密。 由于密码法比隐匿法有更强的保密性,所以几千年来密码法有了长足进步,不过隐匿法和密码法并不是二选一的,可以将两者结合使用,先将信息混淆然后在秘密的送达出去。

密码法实际上又分为两类:移位法和替代法。

移位法密码

移位密码是将字母重新排列一下,而不更改字母的表示。最简单的二排篱笆法就是将奇数位字母写在一排,偶数位字母写在一排,然后连接起来。

譬如我们要加密明文hello world, 我们可以如下进行(密码学里明文使用小写,密文使用大写)

明文: hello world

H   L  O  O  L
  E   L  W  R  D

密文: HLOOLELWRD

收信人只要逆向执行这个过程就可以复原信息。移位法本质就是对信息的重新排列,也可以使用三排篱笆法,四排篱笆法等。

凯撒挪移密码法

移位法只是使用明文信息的重新排列,虽然文本长了之后排列方式有非常多种,但是发信人和收信人之间需要约定好一种排列方式,不便于记忆。凯撒挪移密码法是凯撒大帝发明的,方式是将密文字母向前挪移几位来替代明文。如下是一种挪移了三位的密码:

a b c d e f g .. x y z
D E F G H I J .. A B C

挪移位数可以是1-25。

一般替代密码法

凯撒挪移式密码只有25种,但如果我们随意指定字母间的对应关系,这样就可以产生26! 种密码,这就是一般替代密码。

每种密码法都可以视为某种一般加密法--称为算法加上密钥的组合。密钥是用来指定特定加密算法的演算细节。算法是公开的,密钥是保密的。密钥的重要性远高于算法,这是密码学上颠扑不破的真理。

凯撒挪移密码的密钥就是挪移位数,对于一般替代法,密钥可以是任意单词或词组,剩下的字母按顺序排列到后面即可,而不用全部字母随机重排。譬如我们选用密钥 hello world,先将重复字母去掉,然后排列就得到下面的密码集:

明文 a b c d e f g h .... x y z
密文 H E L O W R D A .... X Y Z

这个密钥不好,因为后面的三位重复对应了。

除了要保密密钥之外,安全的密码法还必须有庞大的可以密钥。像凯撒挪移密码只有25种,如果其他人猜测你加密使用的这种形式,最多需要测试25次就可以找到答案了。一般替代法却有 26! = 4 * 10^26 种可能,绝对不可能通过暴力枚举来破解,因此一般替代法的安全性很高。

替代式密法的破解

有秘密自然就有人会想要窥探秘密。编码者已经有了简单又强大的密码法可用,难题到了解码者手中。

最先找到破解方法的是阿拉伯的密码分析家肯迪,他发现,在正常的文章中其实各个字母的出现次数并不是均等的,譬如在英文中出现次数最多的是e,其次是t,a.. 因此跟不需要检查所有的可能密钥,只要分析一下密文里各个符号出现的频率,然后与明文字母对应起来,就可以揭开加密信息的内容了。这种方法称为频率分析法

替代式密码的变种

一般替代法被破解之后,人们想出了很多种方式来增强替代法的强度。譬如加入虚元,可以理解为噪音,频率分析法是基于每个字母出现的频率来分析的,虚元的目的就是让每个字母出现的频率基本一致,这样就无法通过简单的频率替换来破解了。

另一种方式是故意拼错字,这样也可以扭曲正常字母的频率分布。还有一种是改变对应方式,现在是一个字母对应一个字母,我们可以使用一个或多个符号来代替一个单词,不过这样的方式得编写一本密码簿,很不方便。

维吉尼亚密码法

前面提到的密码法都是一个字母对应一个字母,因此称为单套密码法。虽然有多种变种,但是这种加密方法已经被密码分析家们完全的破解了,这种加密法的缺点就是明文字母只对应密文的一个字母,因此很容易被人使用频率分析法攻破。

维吉尼亚发明了维吉尼亚密码法,它的本质是使用多套密码来加密明文信息。它的加密方式是使用26套字母,叫维吉尼亚方格:

明文 a b c d e .... x y z
1    B C D E F .... Y Z A
2    C D E F G .... Z A B
...
25   Z A B C D .... W X Y
26   A B C D E .... X Y Z

每一套字母就是简单的凯撒挪移式密码,当加密时,双方先约定好使用的密钥,譬如用 zac,然后加密 deez,我们就去维吉尼亚方格中查找密钥开头的字母。d 使用 Z 开头的密文字母对应为 C,e 使用 A 开头的密文字母对应为 E,第二个e 使用 C 开头的密文字母对应为 G,z 从头使用密钥对应为 Y,因此 deez 加密为 CEGY

维吉尼亚密码法的优点是对于明文中的同一个字母会加密为密文中的不同字母,上面 e 就对应了两个字母 E 和 G,因此使用上面的频率分析法就无法破解这个维吉尼亚密码。

维吉尼亚密码的密钥数量也是庞大的,因此不可能被暴力枚举破解。

巴贝奇破解维吉尼亚密码法

巴贝奇就是发明了差分机二号,号称最早的计算机。他也破解了这个当时称为无法破解的密码维吉尼亚密码。

巴贝奇提出的解决办法很简单(事后诸葛亮的角度),我们可以再观察一下上面的加密过程,我们用一个极端的例子来说明巴贝奇的破解方法。

假设我们要加密的是 eeeeee, 按照维吉尼亚方格我们得到加密后的密文是 DEGDEG, 巴贝奇发现,虽然维吉尼亚密码会将同一个明文字母加密为不同的密文字母,但是由于密钥的长度是有限的,因此在加密同一个字母(单词)时,当明文超过密钥的长度后,维吉尼亚加密的密文开始出现循环,巴贝奇破解维吉尼亚密码的第一步就是寻找密码里的重复字符串来判断密钥的长度,譬如例子中有重复串DEG我们可以判定密钥长度为3。

得到密钥的长度后,就可以使用频率分析法来破解了,换句话说,维吉尼亚这种多套字母密码法本质上是多(N)个单套字母密码法组成的,像 上面例子就是 3 个,每一个单套密码法负责加密整个信息的 1/N, 我们将信息分成 N 份,每份使用单独的频率分析法就可以将密文解密为明文。

单次密钥簿密码法

巴贝奇的破解方法是建立在大量明文使用同一个密钥的基础上,如果密文的数量不够大,没有重复字符串出现,那么就无法应用巴贝奇方法来破解。

美军的一位少校提出了随机密钥的概念,密钥不再是可辨识的单词而是一串随机的字母。首先编订出一本随机密钥簿,每一页包含有一个密钥,加密信息时,发信人使用第一页的密钥来加密信息,收信人也使用第一页的密钥来解密信息,当信息被正确的收到之后,就将此页的密钥销毁,下次再发送信息就使用下一页的随机密钥,用完即毁,每把密钥只使用一次,这个系统就称为单次密钥簿法。

单次密钥簿法的关键在于密钥的随机性,而使得密码分析人员无法通过可辨识的单词来猜测密钥,编订这样一本密钥簿其实是很难的。另一个就是密钥簿使用一次就丢弃掉使得发信人与收信人之间要频繁交换密钥簿,一旦密钥簿泄露,所有的秘密也都暴露在敌人眼前。

密码机械

科技的发展为了使人们不必再费劲的人工加密而发展除了机械加密方式。 最早的密码机械是密码盘,分内外两层,分别刻有26个字母,内层圆盘可转动,外层字母是明文,内层是密文,这样就可以实现一个简单的凯撒挪移式密码。

为了增强密码强度,可以使用多个密码盘,每个密码盘使用不同的设定,这样就是多套字母集密码,如果使用某个密钥来作为设定,然后循环加密信息的话,就是使用了维吉尼亚密码法。

密码机械最有名是德国在二战时使用的雪毕伍斯设计的奇谜,不过后来被波兰和英国的密码分析家们破解了,具体不再详述。

待续

一直以来发信人和收信人都必须事先约定好加解密的密钥然后才能开始秘密通信,但真的必须提前约定好密钥吗?

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
OSCHINA
登录后可查看更多优质内容
返回顶部
顶部