矛盾相争:密码学史

密码学是现代电子信息社会的基石。随着技术和计算能力的不断进步,民众能够将越来越多的数据迁移到数字领域,这带来了速度,可访问性和便利性。同时,密码学竭力保护数字数据,以使其不被用于非法目的。

密码学的重要性可以概括为:它是用户在数字世界中保护其私有数据的唯一工具,随着数字世界中用户的不断增长,密码学也变得越来越重要。

密码学进入商用,并作为一门科学(或艺术)进行系统的学习研究,只有100个春秋。但在此之前,作为人类文明史的一条暗线,加密与解密的博弈已经走过了几千年。


凯撒与高卢战争

密码学史可以分为三个阶段:

  • 古典密码学
  • 近代密码学
  • 现代密码学

“密码学”(cryptography)这个词衍生自希腊语中的”krypto”和”graphein”,它们的意思分别是”隐藏”和“书写”。

古典密码学最著名的应用是凯撒密码。在公元前60-50年左右,高卢战争期间,凯撒采用单表替换加密与自己的将军们联系。凯撒密码的操作其实很简单:

定一个固定步数,比如向右移动3位,那么明文abc就变为了密文def。

单表替换加密的也有其它变种,比如移位密码(将字符与数字按ASCII表进行移位),埃特巴什码(逆序替换),简单替换(以打乱顺序的字母替换明文字母),仿射密码(按方程计算)。但单表替换加密的共性就是明密文一一对应。

所以要破解单表替换加密有两种方法:

  1. 采用暴力破解方式。换句话说,也就是代入所有字母一个个去试。不过这种方法只适用于在密钥空间较小,即明文与密文对应可能性不太多的情况。这里需要说明的是,与凯撒交战的高卢部落识字率很低,这本身就可以过滤掉大部分的潜在破解者了。而且当你拿到一份密文本时,需要找到加密方法和步数才能破解,对于当时的高卢部落来说,推算破解基本不可能。
  2. 密钥空间较大时,就需要用到第二种方法了。这种方法直到公元800年前后,由阿拉伯数学家肯迪提出——频率分析。

在英文中,“e”是出现频率最高的字母。

在所有语言中,不同字母或元素的出现频率是不同的,所以最大的切入口就是按频率分布进行对应,加密方法和步数便可水落石出。

由此,频率分析成为了系统破解加密的方法,这也成为此后一千多年里,人类最基础的解密方法。

这是加密与解密的第一次系统性对抗。


技术突变

加密方法的下一个重大突破出现在公元1467年,由文艺复兴时期的通才莱昂·巴蒂斯塔·阿尔伯蒂开启。他提出对消息的不同部分使用不同的代码,这也是多字符加密法的开端。为了实现这套方法,他发明了密码盘,可以实现加密与解码。

阿尔伯蒂发明的密码盘

多字符加密最典型的案例是维吉尼亚加密法,由同为意大利人的吉奥万·巴蒂斯塔·贝拉索在1553年提出,他引入了密钥的概念,即所有字母皆可用密钥进行加密。加密与解码都需要用到密钥。

后法国外交官维吉尼亚在1583年在《论密码》一书中提出,他吸取了当时贝拉索的密钥概念,以一个共同约定的字母为起始密钥,以之对第一个密文脱密,得到第一个明文,以第一个明文为密钥对第二个密文脱密,以此类推。

贝拉索在《吉奥万·巴蒂斯塔·贝拉索先生的密码》中提出的密码表

密钥的问世,无异于在密码学圈中掀起惊涛骇浪,这对密码学造成了重大转变(从隐藏系统转变成隐藏密钥)。这意味着系统可以是公共的,并且在不掌握密钥的前提下,无法读取对应的消息。这攻克了整个系统被直接的频率分析而暴露的顽疾。

在19世纪期间,第一次使用转轮机(rotor cipher machine)进行加密 。20世纪问世的Enigma的发明是一个技术里程碑,被誉为最难攻破的密码之一,Enigma应用的巅峰是在二战期间的德国。

当时德军的各支部队都部署了Enigma,所有机器的转子的排列顺序统一,起始位置和接线板的连线也必须相同,这些设置都记录在密码本中,每天在使用前统一设置。这套方案在不清楚线路设置的情况,密码的可能性为10^114种,可以说是绝不可能被破解。当时希特勒正是利用这套加密机制,成功实现闪电战攻占了欧洲大陆。

二战也成为了盟军与轴心国之间加密与解密的拉锯战,当时双方最顶尖的数学家、密码学家、计算机专家相继投入战场。盟军曾苦于德军的加密机制,出击总是慢一拍。1941年英国海军捕获德国U-110潜艇,得到密码机和密码本,这成为了盟军破译德军密码的转机。

Enigma 机器

在计算上,第一次提出完整破解维吉尼亚加密的方法,是在1863年,由弗里德里希·卡西斯基提出,这套方法也被成为卡西斯基试验。维吉尼亚加密的目的是在于打乱字母分布的频率,使密文的分布更趋于随机性,所以直接的频率分析会失效。但纯粹的随机是极难达到的,意味着肯定有些特别的密文内容会成为其弱点。卡西斯基试验正是基于这个思路。

而Enigma加密是在1932年,波兰密码学家们根据其运作原理破译,并由波兰政府在1939年告知英国,因此盟军才得以根据截获的密码本与密码机进行解密。

这便是加密与解密在近代密码学中的交锋。


算力之争

二战结束后,密码学大范围额进入商业应用领域。IBM是第一家系统开发加密组的公司,二十世纪七十年代早期,IBM开发出了DES加密方法。1977年,这成为了美国第一个加密标准。但它只是昙花一现,因为它能被简单但非常强大的方法所攻破,即“暴力破解”。

这涉及到在一个“计算密集”的过程中简单地尝试所有可能的组合,这也为在之后计算能力的提高而选择增加私钥的复杂性埋下伏笔。

如今,为了满足与不受信任的各方进行通信的需要,”公钥加密”与“非对称加密”声名鹊起。这种加密方法依赖于发送者用来加密信息的公钥和接收者拥有的私钥(用于解密消息)。这个过程是单向的,意味着没有其他人可以解密消息。

现在密码学的交锋已成为加密密钥的复杂性和可用计算能力之间的追逐游戏,从原则上来说,任何密钥都容易受到暴力攻击;密钥越复杂,这种攻击破解就越耗时。当今密码学的目标是创建算法,使其在计算上无法获取私钥。


密码学重新定义信任

由于计算时间的限制,最先进的加密协议几乎不可破解,交锋暂时成为加密的一枝独秀,密码学也衍生出了新的应用方向——隐私交易。

随着计算能力和密码学的进步,信任已经成为关注隐私的群体的新目标。密码学家认为,如果可以加密并有效地隐藏数据,使其对无关的人不可见,那么也许有一种方法可以在不显示数据的情况下与其进行交易。

诚然,在二十世纪八十年代,零知识证明和加密数据计算等工具的问世,通过将数学转换应用于基础数据,这些工具使人能够与数据进行交互并验证加密数据,从而有效地在密码学领域掀起另一场风暴。

现在,数据交换可以是私密的,甚至在直接交易的各方之间。

时间来到2012年,来自IBM和微软的Pinocchio在零知识证明的计算需求上得到突破,它可用于隐藏双方之间的数据,并且仍允许它们进行交易。

更重要的是,它的速度足够快——零知识证明使计算需求减少20倍,将验证的需求减少了50倍,这意味着它能使相关的个人和商业应用程序成为现实。

同样的,在尖端的隐私保护技术方面,新的实施方案如雨后春笋般层出不穷,包括:

  1. 安全的私人在线投票;
  2. 提供加密资产证明,而无需透露一个账户中可用的资金;
  3. 包含数据提供商和买方的市场,企业能够在决定购买数据之前尝试数据,同时保持数据隐藏;
  4. 在不公开数据或模型的情况下,可以演示模型对新数据的预测能力。

未来战场

那么密码学的未来蓝图又是怎么样呢?

  • 同态加密

如今在数据通过互联网传输时,以及在存储设备上处于静态时,用户可对数据进行加密,但是用户必须解密数据才能使用或分析它,从而产生潜在的安全漏洞。

同态加密是一种解决该问题的新思想,允许用户在不解密的情况下处理数据。通过同态加密,用户处理加密数据并生成加密结果。

  • 量子计算

量子计算也许是密码学的一系列前沿发现所蕴含着的一个令人兴奋的未来。

基于粒子叠加属性的量子计算能够以指数方式增加可用的计算能力。这意味着目前在硅芯片上运行效率低下的加密转换可以在量子芯片上高效运行。

但之前所说的“追逐游戏”仍在上演,量子计算的进步带来了量子加密,它利用量子粒子的特性来确保不可破解的加密,不过量子计算的算力提升,也增加了加密方法被暴力破解的风险。

加密与解密的交锋不会结束,正如人类互相博弈的历史从未中断过。但我相信,在一个“信息是最有价值的资产”的世界中,值得探索和应用密码学的新技术来守护它。

Leave a Reply

Your email address will not be published.