译|密码学简短入门

这是一篇译文,原文地址:https://cmdli.github.io/crypto/

电脑能帮我们做的最有用、最有趣的事情之一就是加密。通过加密,我们可以隐藏信息,验证身份,乃至于构建一个完全去信任的分布式系统。加密技术不仅定义着当代世界,也影响着我们构建未来的方式。 ​

不过,不花费数年读个密码学博士,大多数人要了解加密原理还是很困难的。加密过程充满陷阱,任何人想要从头构建加密技术都只能自取其辱,为什么呢?

我认为,这是由其历史决定的。现代密码学是在过去许多世纪的设计、攻破、重新设计的过程中形成的。大多数密码学教程只关注是什么:要这么做,不要那么做,应该遵循哪些原则。却跳过了为什么:为什么要这么做,为什么不能那么做?

要理解为什么,还得回到历史中去。因此,不妨把电脑先放一边,看看经典密码学的世界。


1. 最早的加密技术:凯撒密码

凯撒密码是最古老,也是最简单的加密技术,原理极为简单:将每个字母沿字母表前移或后移一定距离。例如,前移三位就是把 A 变成 D,G 变成 J,M 变成 P。解密时,只需往回移动同样距离即可。密文和原文看上去完全不同。毫无压力,不是吗?

从这最简单的技术中,我们还是可以看出密码学的基本要素:原始信息,或者说明文;混淆后的信息,或者说密文;以及移动的数值,或者说密钥image.png 现在,让我们看看如何破解它。假设我们拿到一段密文,比方说 KJQNSJ,怎么才能知道明文呢?因为字母表中只有 26 个字母,也就是说,只有 26 种移动方式,显然,只要尝试 26 次,就可以得到原始信息了。

这告诉我们,有效加密技术的第一个条件就是:必须拥有足够大的有效密钥空间。26 种移动方式作为密钥空间来说显然是太小了,完全可以手动破解。那么,如何将密钥空间扩大到攻击者无法逐个尝试呢?


2. 最新技术(16世纪):维吉尼亚密码

维吉尼亚密码以 Blase de Vigenère 的名字命名,实际发明者是 Giovan Battista Bellaso。自 1533 年该技术发明以来,300 年内无人破解。其实,它对凯撒密码的改进并不复杂。 ​

凯撒密码中,每个字母都移动相同距离,那么,可不可以每个字母移动不同距离呢?要是移动距离不一样,就不可能在不知道密码的情况下破解密文了。 image.png

每个字母移动不同距离

不过,这个想法实现起来有点困难。毕竟,我们还得告诉收消息的人每个字母移动的距离是多少,传递这个信息也就等于传递明文了。因此,维吉尼亚密码采用了一种简化的办法:设定一组移动值,然后不断重复,从而通过一个相对小的密钥加密整个信息

这组移动值用一个简单好记的单词表示,单词中的每个字母在字母表中的位置就代表它的移动值。例如,A 代表前移 0 位(也就是不移动),D 代表移动 3 位等等。 image.png

不同字母代表不同移动值

如果密钥是 LEMON,也就意味着明文的第一个字母要移动 11 位,第二个字母要移动 4 位,第三个字母移动 12 位,以此类推。要点在于,我们可以重复这种模式,完成所有明文的加密。我们会在后文中讨论这种加密方式的问题,不过,和每个字母移动不同数值相比,它极大地简化了加解密的过程。 image.png

维吉尼亚密码加密后的信息

这种加密技术极大地扩展了密钥空间,不过整个加解密过程还是可以手动完成。大多时候,会用一个叫做 Tabula Recta 的表格作为辅助。 image.png 怎么破解呢?要完成解密,必须知道密钥中的每个字母。以 LEMON 为例,密钥空间的规模已经扩大到 26 的 5 次方,手动破解已经完全没有可能。这也是维吉尼亚密码在几个世纪内都没被破解的原因。

还有什么其它办法吗?既然暴力破解已经不可能了,我们就得考虑一些聪明点的办法来推导密钥。这里,我们引入词频分析技术。


3. 更准确的猜测:词频分析技术

首先,让我们回头看看凯撒密码。如果不用暴力法,还有什么其它方式可以破解密码吗?我们能从密文中获取什么信息呢?

由于明文中的每个字母都移动了同样的距离(比方说,A 移动到 F),不同字母在文本中的出现频率实际上是保持不变的。 ​

image.png

英语中不同字母的出现频率

在大多数语言中,不同字母的出现频率其实是相当稳定的。英语中的字母出现频率如上图所示。如果我们有足够多的密文,就可以计算密文中不同字母的出现频率,并将它与普通文本中的出现频率相比较,从而很有把握地推断字母间的对应关系。 image.png 在上图中,我用凯撒密码加密了苹果公司的维基百科信息,再计算字母出现频率。根据频率分析,我们大概会推测,J 应该代表 E,而 F 代表 A,那么,凯撒密码的移动值应该是 5。

词频分析对维吉尼亚密码有效吗?初看起来,好像是无效的,因为字母移动的距离不固定,也就隐藏了原文中的频率信息。这里,我以 LEMON 为密钥加密了苹果公司的维基百科信息,从下图可以看到,字母频率与一般英语文本中的频率已经不一样了: image.png 然而,维吉尼亚密码有一个致命缺陷:移动值重复。还是以 LEMON 密钥为例,明文中的第一、第六、第十一个字母都用 L 加密,每 5 个字母使用相同的移动值。也就是说,我们可以将它看作 5 次凯撒加密。

如果我们知道密钥长度,就可以很容易地拆分密文,重新进行频率分析。把每次分析的移动值汇总起来,就得到我们想要的密码了。还是上面的例子,我们来看第一组字母,可以看到,字母 P 出现的评率最高,它也正是 E 移动 L 后的值。 image.png 这种方法的前提是知道密钥长度,相应的,我们也有获取密钥长度的分析方法,也就是 Kasiski 测试(以 Friedrich Kasiski 命名,他是第一个公开破解维吉尼亚密码的人)。

原文中的相同部分,有一定概率会被密钥的相同部分加密,使密文中也出现重复部分。而重复部分之间的间隔,一定是密钥长度的公倍数。 image.png

文本中的重复部分

以上图为例,重复部分间的间隔是 32 位,那么密钥长度一定是 1、2、4、8、16 或 32 位。文本中的不同重复会提示不同的信息,帮助我们更好地确定密钥长度。 ​

当然,所有这些方法并不能保证我们一定能破解密码。重复部分可能只是巧合,我们获取的密文可能数量不足,频率分析也就无从谈起。

不过,破解加密数据并不要求一步成功。从密文中获取的关于原文或密钥的部分信息,可以帮助我们作出概率更高的推断,从而使暴力破解更为容易。


4. 如何应对频率分析

我们之所以能使用频率分析技术的核心原因在于,密文中的每个字母都依赖于明文中的一个字母与密钥中的一个字母,从而使我们可以取出密文中的部分文本,并且这部分文本的字母出现频率必然与明文一致。

用密码学术语来说,维吉尼亚密码在混淆(confusion)与扩散(diffusion)方面都没有做好。简单地说,混淆就是使输出的每个字母都依赖于密钥中的多个部分,而扩散就是使输出的每个字母都依赖明文中的多个部分

具体要怎么做呢?经典做法是通过一个代换-置换网络(Substitution-Permutation Network),以确定的方式“混合”输入的字母。 image.png

来自维基百科的图示

代换-置换网络多次执行维吉尼亚密码,每次执行时都通过代换操作和置换操作混合数据。

代换操作将每个文本块替换为一个新的文本块,这个过程中,文本块中任意字母的变动都会导致新文本块中的多个字母发生变化。之后,置换操作会交换输入文本中不同块的位置,使密钥的下一次执行可以作用于文本的不同部分。 ​

代换-置换网络满足了混淆与扩散两方面的需求。代换操作使输出的每个字母都依赖于输入的多个字母,而置换操作使输出的每个字母都依赖于密钥的不同部分。混淆与扩散使密文与原文和密码的关系变得模糊,从而可以有效应对频率分析及其它形式的攻击。 ​

代换-置换操作具体如何实现呢?置换操作的一种方式是使用栅栏密码(Rail Fence cipher),以 Z 字形的方式将信息写到不同行,再按行读取。这种方式很好理解,也延续了古典密码学的传统,可以手动实现,虽然破解起来并不困难,但我们不会单独使用这种操作。 image.png

栅栏密码

一种简单的代换操作是,让每个字母按它之后的字母进行移动。因而,代换操作输出的每一个字母,都依赖于两个输入字母。鉴于代换操作会多次执行,也就意味着最终输出的每个字母都依赖于多个输入字母。单独应用这种代换操作的加密强度也很弱,但好处是可以手动计算。 image.png

简单的代换操作

将维吉尼亚密码与上面的代换操作与置换操作整合,就可以得到一个比它们三者单独应用的强度高得多的加密算法。维吉尼亚密码负责转换文本,而代换-置换操作负责混淆密文与原文和密钥间的关系。 image.png

重复执行不同加密操作

image.png 如上图所示,密文的字母频率曲线变得相当平坦,其中隐藏的信息大大减少。通过更优秀的代换-置换网络,远胜维吉尼亚密码的加密方法,以及越来越长的密钥,我们可以让这个曲线变得更加均匀,不过,这些工作就留给计算机去做了。


5. 结论:我们该使用上面的加密算法吗?

当然不行!前文所有这些内容要告诉我们的一个关键信息就是,对加密算法的攻击来自未来,预防这些攻击的最佳方式就是采用著名的、安全的,由深入研究现代攻击技术及其防御手段的专家们仔细设计的加密算法。 ​

通过前文讨论的这些简单加密技术,我们了解了常见的攻击思路与预防手段。不过,这样简单的讨论也忽略了加密攻防中的许多细节。 ​

本文介绍了现代密码学的由来,以及更重要的,它之所以如此工作的原因。希望你也和我一样,对此有了更多的理解。 ​ 欢迎关注我的公众号:ReadingPython


发表评论

评论列表,共 0 条评论