揭开密码学的面纱

The Da Vinci Code

本来是研究区块链来着,遇到一些密码学的知识不甚了解, 影响到了整体的学习效果,所以决定恶补一下密码学,不求深入,但求浅出。

提起密码学,大部分人会想起谍战,像电影《风声》,想起谜题,像电影《达芬奇密码》。只要不想起用户名,咱们就能继续往下聊。普通人认识的密码学基本都属于古典密码学的范畴,相对于古典密码学就必然有现代密码学,那么他们到底是怎么回事呢?不用说普通人,就算是搞计算机的,如果不专门研究一下,也不一定说的清楚。

古典密码学


简单的说,古典密码学就是研究如何用别人不懂的方式进行沟通的一种科学,主要着眼于将普通信息(明文)转换成难以理解的数据(密文)的过程及其逆向过程,即加密和解密。在这里我们定义三种角色,信息发送者负责信息加密,信息接受者负责信息解密, 窃听者负责信息破译,后面用Alice、Bob和Eve代替。为什么这么取名?请参考 Alice 和 Bob 的故事

举个例子,Alice、Bob和Eve都是英国人,Alice和Bob懂法语,Eve不懂法语。那么Alice和Bob有啥小秘密直接用法语交流就行了。Alice将英语(明文)转换为法语(密文)的过程就是加密,Bob将法语(密文)转换成英语(明文)的过程就是解密,Eve不懂法语所以不知道他俩说的啥。这里我们不考虑Alice和Bob如何传递密文,以及Eve如何获取密文,那些都是谍战剧的任务,总之Eve总是能获得密文的。但是如果Eve学习了法语或者找到个懂法语的人帮忙,那么Eve就能够很简单的将法语翻译成英文,即破译密文。法语知道的人有点多,换种小众的语言吧,非洲的斯瓦斯里语?魔戒的精灵语?无论多么小众的语言只要是公开的就没有意义,总能找到会的人。

必须找到一种只有Alice和Bob两个人知道的方法,用找到可能不是特别恰当,应该用发明,只有这样才能保证只有他们两个知道,并且这种方法必须让Eve难以破译。凯撒密码,将明文的每一个字母在字母表上向后或向前按照一个固定数目进行偏移后被替换成密文,比如每个字母用下一个字母替换,ni hao -> oj ibp。转置式密码,将明文的每一个字母按照一定的规则变换位置形成密文,比如每两个相邻的字母交换位置,ni hao -> in aho。替换式密码,将明文按照一定的规则(密码本)替换成密文,比如ni hao -> ■ ◆。这些方法都很巧妙,如果不知道规则,无法第一时间破译。但是道高一尺魔高一丈,只要花些时间,窃听者Eve总会找到办法。对于凯撒密码和转置式密码,可以用暴力破解来破译,将所有可能的位移都尝试一遍,将所有可能的位置变换都尝试一遍。对于替换式密码,可以进行频率分析来破译,将密文每个符号的出现频率和一篇正常文章中字母出现的频率进行对比破译。

古典密码学,主要以语言学为基础,无论是发明还是破译都依靠于人类的智慧技巧与创造力。到了现代,由于计算机的飞速发展,计算能力成几何倍数的增长,古典密码学已经不再适用,其破解成本在计算机面前显得微不足道。拥有强大计算能力的计算机淘汰了古典密码学,与此同时又催生了现代密码学。

现代密码学


不同于古典密码学主要考虑语言学上的模式,现代密码学是以数学为基础的,借助计算机强大的计算能力已经无法被人力所破解。除了机密性,在数据完整性、身份认证和不可抵赖性等方面均有很好的表现,突破了古典密码学的局限性,拥有更广阔的空间。

密钥

古典密码学关注于算法本身,如果算法的细节泄露了,算法也就失效了。而现代密码学则不同,一般算法的细节都是公开的,通过不同的输入参数来进行加密和解密,这个参数就被称作密钥。相同的明文和相同的算法配上不同的密钥,加密得出的密文是完全不同的。同样,解密时也必须使用与加密密钥相对应的解密密钥才能得出正确的明文。加密密钥和解密密钥是成对出现的,在有的算法中他们是相同的,有的则不同。

对称密钥

用相同的密钥进行加密和解密,称之为对称密钥。信息发送者和接受者保有相同的密钥,所以又叫共享密钥。1977年美国标准与技术研究院(NIST)将DES定为国家标准,密钥长64位,除去8位用来奇偶校验,实际只有56位。随着计算机的发展,56位密钥的强度日益减弱。1999年NIST将3DES定为过渡加密标准,从字面上可以猜出,3DES是用3条56位密钥对数据进行3次DES操作,以弥补56位密钥的强度不足的情况。但这三次操作并不是简单的三次加密配三次解密,而是加密解密加密配上解密加密解密的组合,详情见维基百科。2002年NIST制定了新的高级加密标准AES,有兴趣可以研究一下Rijndael算法。

这里有一个有趣的悖论,对称密钥算法的密钥是如何传播的,如何保证其安全性。如果密钥有其他方法可以保证安全传播,那么直接用那个方法就好了,还要这个算法干嘛?如果密钥无法保证安全传播,那么这个算法也就毫无意义了!

非对称密钥

用不同的密钥进行加密和解密,称之为非对称密钥,其中一个是公开的叫做公钥,一个是私密的叫做私钥,所以又叫公开密钥。在加密的场景下,公钥加密私钥解密。在数字签名的场景下,私钥加密公钥验证。

大名鼎鼎的RSA就不多说了,网上有的是资料,这里推荐阮一峰老师写的科普文章。
RSA算法原理(一)
RSA算法原理(二)

数字摘要

数字摘要是将任意长度的数据处理为固定长度的数据,不同的输入数据产生不同的输出数据,相同的输入数据产生相同的输出数据,并且该过程不可逆。这样的一个函数,我们称之为单向散列函数或Hash函数,通过明文生成的密文,我们称之为数字摘要或数字指纹。就如同指纹可以代表一个人一样,数字指纹也可以代表明文。数字摘要技术可以用来验证数据的完整性,如文件下载通常会提供原文件的数字指纹,下载后只需要比较数字指纹就可以知道下载的文件是否正确。目前使用的比较广泛的散列函数,MD5和SHA-1。

数字签名

顾名思义数字签名就是用数字的方式达到在纸上签名的效果,用来证明信息发送者的身份,主要利用了非对称密钥和数字摘要两项技术。

通常,Alice将信息生成数字摘要,然后将数字摘要用私钥加密,将信息和密文(数字摘要密文)一起传给Bob。Bob用同样的Hash函数将收到的信息生成Bob的数字摘要,然后用公钥将密文解密得出Alice的数字摘要,验证两个数字摘要是否一致,即可验证发信人的身份是否为Alice。

DSA同样是非对称密钥,但常常与RSA混淆,特别做一下区分。DSA是数字签名算法,只能用作数字签名,不能用作加密。因为DSA算法用私钥生成数字签名,用公钥验证,验证的过程不会将签名还原成原文。RSA既可以用作数字签名,也可以用作加密。因为RSA算法的公钥和私钥都可以用来加密和解密,可以产生数字签名的效果。

ECDSA就是比特币里面用的签名算法,协议框架和DSA基本一致,只不过ECDSA使用的椭圆函数域,而DSA使用普通乘法域。

混合秘钥系统

非对称密钥算法比对称密钥算法慢,对称密钥算法的密钥管理又存在问题,所以常常将他们混合起来应用。非对称密钥用来保护和分发会话密钥,会话密钥用在对称密钥算法中,对通信消息进行保密。整个通讯过程既安全又高效。

例,Bob将他的公开密钥发给Alice。Alice产生随机会话密钥K,用Bob的公开密钥加密,并把加密的密钥EB(K)送给Bob。Bob用他的私人密钥解密Alice的消息,恢复出会话密钥:DB(EB(K))=K。他们两人用同一个会话密钥对他们的通信消息进行加密。

图解密码技术 第3版

最后,本文勉强算是科普文章,只是说要解开面纱,并没有要深入剖析,所以算法的细节一概没提。精力有限,期待有缘人吧。推荐一本书,《图解密码技术 第三版》,豆瓣评分很高,虽然只看过目录,应该有助于进一步学习。