Permalink
Switch branches/tags
Nothing to show
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
158 lines (92 sloc) 14.2 KB
title tags categories date
密码学科普
信息安全
密码学
科普
信息安全
2016-04-08 14:06:15 -0700

(这是一篇很早以前写的文章了,因为确实还比较满意,所以大概改了改发出来)

密码学是做什么的呢?绝不仅仅是研究“怎样加密信息”这么简单。事实上经过多年发展,密码学已经可以漂亮地解决、或正在努力解决以下问题:怎样防止窃听?怎样防止篡改?怎样防止发信人不承认他发过信?怎样防止收信人不承认他读过信?怎样防止冒充身份?怎样用同一个密码接收不同人发来的加密消息?怎样一次发加密消息给很多人?怎样无需见面或通过安全通道交流就实现以上要求?这篇文章会在避免涉及复杂细节的前提下,介绍一些密码学中最重要的工具和概念,并一一回答上述问题。


一、何谓信息

生活中的信息常常很复杂,比如一张图片、一篇文章、一首歌,或者一个概念、一个数字。它们看似形式不同,但共同点是都可以被“编码”成一串数字,这串数字能通过“解码”过程,分毫不差地还原成原来的信息。

你的手机或电脑里存储的短信、音乐、图片、视频,都是编码成数字,存储在存储卡或硬盘上的,所以“信息”这个概念各位应该不难理解吧。一切你想要加密、解密、发送的东西,归根到底是一串数字。

接下来的讨论就不关注信息的内容了,只关心这串数字要怎样处理。


二、摘要

摘要的产生,是因为人们有这样的需求:检查两个文件是否相同。

如果你想要确认,你朋友手中的一个1G大小的文件内容是否和你手中的相同。那么你可以要求他花费1G流量和成小时的时间把文件发给你,然后你把这两串超长的数据进行比较看是否相等。这是容易想到的做法。

但还有没有高效一些的做法呢?于是人们构造了一些数学函数,叫作摘要函数。这些函数都有以下特点:

  1. 它可以把任意长度的任意原始数据转换成一定长度的数据,称为原始数据的摘要。
  2. 原始数据改变一点点,摘要就变化很大,几乎完全不同于改变前的摘要。
  3. 摘要很像随机数,以至于除了“暴力”尝试,没办法从摘要逆推出原始数据。
  4. 摘要较长又很随机,所以很难找出两个不同的原始数据,他们的摘要相同。这种情况叫作“碰撞”。碰撞显然是存在的,但很难找出,基本可以保证你一生中见到的所有数据,他们的摘要都各不相同。

这样一来,你可以要求朋友计算出文件的摘要,发给你,如果和你的文件的摘要相同,就可以认为你们俩手中拿着的是相同的文件。摘要比文件短多了,很省流量和时间。而且即使有坏人恶意篡改你的文件,他也不可能逃避摘要的检查(除非这个坏人运气很好,篡改后的文件摘要与篡改前相同,就可以骗过检查。但这种情况发生概率低得很)

摘要的另一个用途是存储密码。比如说你设定电脑密码后,电脑其实没有保存你的密码,否则,密码明晃晃地放在电脑里,太危险。实际上电脑把你的密码的摘要保存了。前文说到过,没法从摘要逆推出原始数据,所以即使摘要泄露也没事。登录电脑时,电脑会将你这次输入的密码的摘要计算出来。如果密码错误,摘要必然与存储的值大不相同。只有正确的密码才能计算出和曾经保存的相同的摘要,你就会登录成功。

这也就是为什么我们常发现“可以重新设置密码,但没法知道曾经设置的密码是什么”。不是电脑不想告诉你,是它自己也不知道你的密码。它只知道摘要。

有些网站,点击“找回密码”后,你的邮箱会收到一个重新设置密码的链接,或者告诉你“暂时帮您把密码改成了xxx,请登录并修改”。这些网站是好网站,他们没保存你的密码,只保存了摘要,无论是黑客还是网站管理员都没法知道你的密码。如果“找回密码”时你的邮箱收到了你曾经亲手设置的密码,说明这网站很不重视安全。


三、对称加密

有了摘要函数,我们就可以通过检查摘要来确保文件没有被篡改了。但怎样保密呢?对称加密就是最简单的一种加密方法。注意:简单并不意味着它有安全漏洞。

你把“love”的每个字母变成之后的第3个字母,也就是“oryh”,发给朋友。另外通过安全渠道(比如见面)告诉他“3”这个数字。这就实现了一次对称加密。事实上,字母向后移动这种做法很容易被破解,但目前广泛使用的对称加密方法很安全。成熟的对称加密方法的特点是:

  1. 加密和解密都使用同一个“钥匙”(也就是这个3)。
  2. 你和每一个朋友的交流,都需要一把专门的钥匙。
  3. 这把钥匙必须通过安全渠道发给对方。
  4. 加密后的消息和原文一样长,不过变得很随机,即使原文是“aaaaa”,加密后也是杂乱无章的。

特点4是“成熟的加密方法”必须具备的要点。如果不这样,就会出现很多漏洞,比如:知道了“o”对应“l”,就能破解出“oryh”对应“love”。

特点2和3是缺点,如果你要和100个朋友交流,就要分别和他们见面,弄出100个“密码钥匙”(下文称为“密钥”),全都保管好。如果你要加密下载美国网站上的文件,难道你还要跑去面见站长?这不科学,因此……


四、非对称加密

为了解决“怎样不用见面就能安全地把密钥发给别人”这个问题,出现了非对称加密法。这种加密法很特殊,它有两把钥匙,分别叫“公开钥匙”和“私密钥匙”。顾名思义,公开钥匙要公开发布,私密钥匙要小心藏好。

要解释这种加密方法不太容易。假想一下,假如这个世界上没有人会算除法,也没有人会求倒数。有一种方法可以一次性制造出互为倒数的两个数字(比如5和0.2),但如果只知道5,就算不出0.2这个数。

在这个世界中,你就可以制造出一对倒数,比如4和0.25。你把0.25藏起来,作为私密钥匙。把4公开发布。如果别人要写信给你(假设信件内容是数字“15”),他可以把信件内容和4相乘,把乘积(60)发给你。因为不会算除法,所以没有人能从4和60解出原文“15”。只有你可以用60乘以0.25,把信件解密。

这是一个比喻。实际上,非对称加密利用了一种逆运算特别难算的数学计算,来实现上面这个构思。这下理解了吗?

现在,你就可以制造出一对公开钥匙和私密钥匙。假如有100个人要写信给你,他们都可以用公开钥匙加密,然后发给你。(注意:如果发信人在加密后弄丢了原文,那么这世上就只有你能用私密钥匙解密了,连发信人都不能得到信件内容)

如果你想回信,你就要先得到发信人的公开钥匙,然后加密发给他。他会用他自己的私密钥匙解密。

这个加密方法的优缺点是:

  1. 可以把加密用的密钥随便公开,不用悄悄发给对方了。
  2. 每个人只需要记住一个密钥就够了。
  3. 虽然加密运算的逆运算很难算,但加密运算本身也很慢,所以加密大文件要很久。

缺点3怎么克服呢?假如你要写信给张三,以下是方法:

你先制造出一个对称加密用的密钥,然后取得张三的公开钥匙,把对称加密密钥用张三的公开钥匙加密,传给张三。对称加密密钥很短,所以这是很快的。这之后,你和张三就可以用这个临时性的对称加密密钥来交流了。非对称加密技术其实只被使用了一小下。这个对称加密密钥是临时性的,用完就销毁,下次联系时再重复以上步骤即可。


五、剩下的问题

我们再来回顾一下最初提出的问题,看看哪些已经被解决了。

  • 怎样防止窃听?用加密。
  • 怎样防止篡改?用摘要或者加密都行。
  • 怎样防止发信人不承认他发过信?不知道。
  • 怎样防止收信人不承认他读过信?不知道。
  • 怎样防止冒充身份?不知道。
  • 怎样用同一个密码接收不同人发来的加密消息?用非对称加密。
  • 怎样一次发加密消息给很多人?不知道。
  • 怎样无需见面或通过安全通道交流就实现以上要求?用非对称加密。

接下来补充一个非对称加密方法的特殊用途,可以再解决一些问题。


六、数字签名

生活中的签名的目的是证明签名者承认一些东西,防止他日后耍赖反悔。密码学当然也要解决这个问题。

非对称加密有一个特点,就是用公开钥匙加密的东西,可以用私密钥匙解密。用私密密钥也可以加密东西,这时只有公开密钥能够解密。就好比15(原文)和0.25(私密钥匙)的乘积,也可以乘上4(公开钥匙)来还原成15。这个特点很重要。

如果李四欠了我1块钱,我可以让李四把“我欠了1块”这句话用他的私密钥匙加密发给我。(这不会导致他的私密钥匙泄露,因为不会除法的人是不能通过15和15x0.25这两个数逆推出0.25这个数的)以后在法庭上,我就可以用李四的公开钥匙把这句话解密给法官看。“法官大人,我刚刚用李四的公开钥匙解密出了这句话。除了李四本人外,还有谁能加密这个呢?”显然证明了这是李四亲手加密的,因为别人不可能知道李四的私密钥匙啊!

以上,就叫作“防抵赖”技术,是把非对称加密技术“反过来”使用的。简单地说,用私密钥匙加密一句话就意味着你承认这句话,不会被伪造,不能抵赖。

非对称加密很慢,因此让李四加密“我欠了1块”可能要很久。为了更快,在实际使用时,我会让李四加密“我欠了1块”这句话的摘要。摘要很短,加密会很快。现在相当于李四承认了这个摘要。别忘了,几乎不可能找出另一句话,摘要和这相同。“我欠了10块”的摘要与“我欠了1块”的摘要截然不同。因此,李四承认了那个摘要,也就相当于承认了他欠我1块。加密速度提高了,防抵赖的效果没有损失。

以上这个过程,被称作“李四在“我欠了1块”这句话上留下了数字签名”。

数字签名的另一个用途是认证。比如微软公司如果认为一个软件没有病毒,就可以给这个软件进行数字签名。你拿到软件后,一检查,发现微软的签名真实有效,就可以知道微软信任这个软件。这对于软件来说是一种权威认证,或者说一种荣誉。

你有没有想过,如果我写信给张三时,网上可能有个坏人冒充张三,把自己的公开钥匙说成是张三的公开钥匙。这会导致我的信件泄密给坏人。这个问题也可以通过数字签名解决:

张三造出了自己的非对称密钥,在把公开钥匙发布在网上之前,他先和一个权威认证中心取得联系(我们的电脑里都预装了这家权威认证中心的公开钥匙,所以没人能冒充认证中心)。他向认证中心证明了自己的身份是张三,然后请认证中心对这句话进行数字签名:“张三的公开钥匙的确是xxxx”。

这样一来,当我写信给张三时,我可以取得这句话,以及认证中心在这句话上的签名。这签名让我明白,这个公开钥匙肯定是张三的。如果有人想冒充张三,他搞不到认证中心的签名,就骗不了我。


七、尾声

虽然有了优秀的加密算法,但加密技术与攻击技术一直道高一尺魔高一丈。我国的王小云博士及其团队发现了一种快速制造出摘要碰撞的方法,应对策略是采用混合摘要。无数大型电脑在日以继夜地计算常见密码的摘要值并以亿为单位出售,以便黑客根据摘要逆推密码,应对策略是使用加盐摘要。物理攻击法发展迅猛,已经可以根据电脑加密时所发出的噪音或者电脑外壳上的微弱电压破解出密钥,应对策略是涉密设备与外界物理隔离……

另一方面,新式攻击方法也层出不穷,比如“重放攻击”,就是指网上付款后,拦截和付款有关的数据,虽然无法解密或篡改,但可以不断重发,试图增加付款额。应对策略是为每条消息编个号,收到号码相同的消息的话只处理一次。类似的不解密不篡改数据就能实现的攻击也颇受关注。

无论权力部门愿不愿意承认,密码学的成果早已走入平民生活。你的浏览器中就内置了与ATM机加密系统,或者美国军用密码系统安全程度不相上下的密码工具。当你在淘宝购物时,这些技术就在为你提供顶级保护。如果你有需求,也可以十分方便地下载到更加尖端和更加可靠的密码学工具。信息无国界,技术无国界,密码无国界。在这个时代,没有知识就意味着落后于人,更容易上当受骗。

之前,使用数字签名技术,我们又新解决了两个问题:

  • 怎样防止发信人不承认他发过信?让他在信件上数字签名。
  • 怎样防止冒充身份?检查权威认证机构的认证。

目前还剩下两个问题:

  • 怎样防止收信人不承认他读过信?不知道。
  • 怎样一次发加密消息给很多人?不知道。

很遗憾,这是未解难题,前一个貌似有望用量子计算机的新式加密算法解决(量子计算实现加密的知识这篇文章不打算涉及),后一个也有一些很初步的设想了。信息科学发展日新月异,未来还有无限可能!

(补充:一次发加密消息给很多人并不难实现:首先生成一个对称加密的密钥,用该密钥加密信息。然后用所有收件人的公钥分别加密该对称密钥,把信息的密文和对称密钥的所有密文合并成一封邮件即可。当时写这篇文章的时候我怎么就没想到呢!)