量子时代要如何拯救密码?

密码在信息社会

密码与战争有着密不可分的关系,通常战争的输赢取决于对信息的保密情况。战争中的一方将自己所传的信息伪装起来,即使被敌军截获或窃听,信息也不会泄露。密码术有着和社会文明一样悠长的历史,并且一直有着非常重要的影响。在20世纪70年代之前,密码术的主要用户是政府及军队,而在今天的信息社会,密码技术的服务对象也扩展到了公司和个人。随着网络技术和电子商务的发展,大量的个人以及企业信息的踪迹存留在网络上,为了保障这些信息的安全,密码技术举足轻重。

加密技术是利用物理或数学的手段,将重要的数据(信息)加以伪装,只有特定的对象可以将数据还原,获知真正的机密信息。需要被隐藏的信息通常称为明文,将它伪装起来的操作叫做加密,加了密的明文叫做密文(或密码文)。将明文信息加密所使用的一套规则称为加密算法。通常这种算法的操作依赖于密钥,密钥是与信息一起被输入算法的。

为了使接收者能够从密文中得到信息,需要有解密算法,当它和适当的解密密钥一起使用时,就能从密文中还原出明文。依据加密算法的不同,加密密钥与解密密钥有时是相同的,有时是不同的。目前,最广泛使用的数字加密体制或密码系统基于数学“陷门”:一种易于计算的函数,但是如果没有密钥,这个函数几乎不可能反向计算。

网络时代的非对称加密系统

1949年,信息理论的先驱者——香农发表了《保密系统的通信理论》,标志着现代密码学的诞生。在这篇论文中,香农首次从信息论的角度讨论密码学,为对称加密体制建立了理论基础。所谓对称加密体制,即加密和解密密钥是相同的或容易从加密密钥导出解密密钥的密码体制。例如在明文中加入一些干扰信号,此时的干扰信号是发送者有意加进的,且可由发送者进行设计和控制的。在未经发送者允许时,信息的截获者不能将加了干扰信号的密文恢复成明文,因为第三方截获者不知道将哪些干扰信号去除。加入的干扰信号就是密钥,此时的加密和解密密钥是相同的,密钥不能简单地在不安全的通信通道中传送。对于这样的密码系统,我们称它为常规的或对称的密码系统。

但密钥不能通过网络传送带来了对称加密系统不能适用于大型网络和更大的用户群的问题,于是公开密钥加密系统即非对称加密系统应运而生。1976年,两位计算机专家怀特菲尔德·迪菲和马丁·海尔曼发表了《密码学的新方向》,这篇文章引入了一种完全不同的看待密码学的方式,同时使人们迈出了将密码学引出秘密领域、推入公开领域的第一步。在先前所述的对称加密系统中,密钥不能够公开。但是迪菲和海尔曼观察到世界上存在一种天然的不对称:某些很容易完成但是反过来却不容易完成的行为。比如打碎花瓶很容易,但是想要将碎片再还原花瓶却十分困难。非对称加密系统的关键在于加密很容易,但除了指定接收者以外,其他人解密都很困难。在非对称加密系统中,加密密钥称为公钥,任何人都可以知道公钥,解密密钥称为私钥,只有接收者能知道私钥。

以RSA密码系统为例,我们依靠它来保护大量数据,从信用卡详细信息到国家机密,它基于一个被称为因子分解的陷门(加密算法)。这个算法涉及到两个素数(素数保密)和这两个素数的乘积(乘积是公开的)。任何人都可以使用公开的大数(即乘积)来发出秘密消息,但是只有知道那两个素数的人才能阅读消息。如果不知道两个素数,打破此加密的唯一方法是选择一对数字,将它们相乘,看看结果是否与目标匹配。如果没有,选择另一对并再试一次,再一次,再一次……由于计算量非常大,这个试数的过程非常费力,这保证了RSA系统的安全性。

另一个目前正在使用的陷门体制——椭圆曲线代码会稍稍有些抽象。你将从一个方程等式开始,该等式在图表上绘制时将创建特定类型的曲线。一系列简单的操作描述了曲线上点之间的运动轨迹,该方法的加密能力来源于此。如果你只知道起点和终点,你将很难搞清楚两点之间的运动轨迹。

量子时代如何拯救密码?

量子计算机是一类遵循量子力学规律进行高速数学和逻辑运算、存储及处理量子信息的物理装置。经典计算机中一比特只能处于1或0的两种二进制状态之一,且经典计算机的时序逻辑是线性不可逆的。而基于量子力学规律的量子计算机基本存储单位是量子比特,量子比特可以利用量子的叠加特性,同时拥有1和0两种状态,并且量子逻辑门是可逆的,可以知道之前的逻辑状态。在量子比特具有相干性的前提下,每增加一比特(或量子比特),经典计算机只增加一个状态,而量子计算机增加一倍的状态,这使得计算机的计算处理能力得到了极大的提高。

因子分解和椭圆曲线是目前最为常用的加密算法,而且也一直表现得不错。但是当我们构建出基于量子物理学定律的计算机时,计算机的处理能力会出现指数型的飞跃,问题就会出现。虽然第一台量子计算机还没有正式启动和运行,但近年来的进展为我们敲响了警钟,我们不能只满足于现在的加密算法了。麻省理工学院数学家彼得·绍尔创造了一种以他的名字命名的新算法,该算法可以使量子计算机发挥它在解决因子分解问题上的能力,从而破解传统的网络加密算法。

没有人知道我们还要多久才能看到计算机有足够的量子比特来使用绍尔算法。加拿大滑铁卢量子计算研究所的米歇尔·莫斯卡估计了这种可能性,他认为到2027年有1/6的概率,量子计算机将有能力破坏RSA和椭圆曲线密码系统,并且到2031年将有1/2的机会发生这种情况。这些都促使我们“必须立即采取行动”!

但是我们该怎么做呢?在还没有一台功能完整的量子计算来测试算法的时候,我们怎么设计出可以抵抗量子计算机的加密系统?我们已经对量子计算机的功能有了一个很好的了解,因此解决方案很简单:建立一个非常复杂的数学算法,来保证量子计算机甚至一台顶级量子计算机都无法破解它。

美国国家标准技术研究院的后量子密码小组举办了一次新加密算法竞赛,参与竞赛的团队在向后量子加密小组提交了自己的设计后,便想方设法地破解其他团队的密码,以证明自己的设计是最安全的。如果我们找到一种能够避开所有攻击的算法,那么它将成为21世纪最完美的“科技锁”。但对于所有的参与竞赛的人来说,他们心中都有着这样的质疑:自己的算法是否真的有可能超越量子计算机?