凯尔茜·休斯敦-爱德华兹

《光明日报》( 2024年11月07日 14版)

未来量子计算机的问世将威胁所有经典加密信息的安全,密码学家正争分夺秒地开发能难倒量子计算机的加密算法。

快速发展的量子计算机

全世界的数字安全专家都把目光投向了量子年时钟(Y2Q clock)。这台时钟不断计时着,终点是人们预测量子计算机能破解现代某种重要加密算法的时间点。这种加密算法非常精妙,它可以用公开的密钥为信息加密,因而被称为公钥加密算法。尽管信息加密算法听上去有些陌生,但对于时常用互联网传递信息的我们,它无处不在。在上网购物时,它能确保我们的信用卡号码安全;当我们更新手机软件的时候,它能确保更新来自手机公司而非黑客。举报人需要用信息加密的途径联系记者,企业也需要安全的途径发送机密文件。

但量子计算机会让标准的公钥加密算法失效。“这是非常严峻的情形”,云端安全联盟量子安全防护工作组的联合主席布鲁诺·赫特纳说道,“如果量子计算机明天就能建成,我们从此将没有任何办法进行安全的通话。”

赫特纳是量子年时钟的创建者之一。Y2Q这个名字模仿了20世纪90年代末的“千年虫”Y2K危机。20世纪很多软件使用两位数表示年份,这意味着2000年与1900年,在计算机中都表示为“00”。当时人们预计使用这种日期表示法的程序会在新千年到来之际出现故障,这可能会导致大量系统崩溃。但最终,没有哪家银行在跨年时崩溃,没有电网断电,也没有飞机从天上坠落。计算机程序的世纪交替,过渡得很平滑,主要是因为企业和政府都抓紧时间修复了Y2K问题。

量子计算机究竟会在何时发展到足以碾压密码学的程度?没有人能确切知道。当前量子年时钟的倒计时终点是2030年4月14日,这只是一个猜测。但大多数研究者都相信这一变革会在未来几十年内发生。“对信息安全的威胁正在逼近”,赫特纳说,而量子年时钟是一个警示,“把日期贴上去,可以帮助人们保持警醒。”

不过,对于需要长期保密的政府等机构,真正的截止日期还要早得多。如果今天发送的加密数据被长期储存起来,那未来的量子计算机就可以解码今天的加密信息。“如果你想保密20年,而你认为可以破解密码的量子计算机在20年内就会出现,那你今天就需要着手解决问题了。”美国密歇根大学的计算机科学家克里斯·派克特说。

美国国家标准与技术研究院预见到这一威胁,于2016年举办了一场公开比赛,征集“后量子”或者“抗量子”的加密算法——也就是可以在当前的计算机上执行,但加密强度高到量子计算机也没办法破解的算法。为了强调时间紧迫,美国国会于2022年12月通过了《量子计算网络安全防范法案》,要求政府机构制定过渡到后量子加密算法的计划。

美国国家标准与技术研究院的比赛进行了四轮。第一轮允许参赛者提交方案,每轮评审之后晋级的组可以调整方案并提交下一轮的版本,新一轮评审将更为严格。最终,研究院选择了一个叫CRYSTALS-Kyber的方案作为公钥加密组的优胜方案。数字签名组则选出了三个优胜方案,其中数字签名可用来安全地识别信息发送者。研究院正在和研究者合作,将获胜的算法写成标准,以便程序员开始将这些算法纳入当前的加密系统中,奠定后量子保密的基础。

但有些令人担忧的是,选中的四个算法中有三个(包括CRYSTALS-Kyber)都是基于“格”的——格是指高维空间中周期排列的点阵,关于它有一些难解的数学问题。专家都相信这类问题很难解,但没人能确保未来的研究不会破解这些算法。

加密算法的更迭

纵观密码学的发展,已知最早的一种加密算法就是把字母替换成别的符号。在凯撒写的信中,他会把每个字母替换成罗马字母表往后三位的字母。用英语举例的话,就是把“a”换成“d”,“b”换成“e”,以此类推。如果要解开凯撒写的密文,你只需要反过来,把字母往前移三位就好。

凯撒的替换加密算法有无数种原理相同的变体——在课堂上传纸条的小朋友也可以自己做一套,比如把“a”换成心形,“b”换成星形,等等——但这些都很容易破解。没收纸条的老师可能会注意到,文字中有不少单独出现的三角,表示某个单字母的单词,由此就能推断出三角代表“I”或者“a”。一般来说,通过比较不同符号的频率,并与常见英语文本中字母的出现频率进行对照,破译密码的人可以解出更复杂的替换方案。

现代密码学的黄金标准——高级加密标准(AES),就是凯撒做法的超级升级版。它会对信息进行多次替换并像洗牌一样打乱顺序。在乱序和替换足够多次之后,重构原始信息非常困难。

要想解密原始信息,需要反向执行每一步乱序和替换操作。如果是一副实体扑克牌,这几乎不可能做到——决定洗牌顺序的是看不到的细微运动。但若是计算机根据一套精确的指令打乱信息——比如说,“把第二条目放到第五位”,那恢复原始顺序会变得很轻松。计算机只需要反过来操作,“把第五条放回第二位”。

和凯撒密码一样,AES也采用对称的加密和解密过程。它会分别将相同的过程正向和反向执行,就像正反拧门钥匙一样。事实上,在20世纪70年代之前,密码学里就只有对称加密算法(又称对称密钥加密算法)。但这类加密算法的局限性很强:发送者和接收者必须在交换信息之前约定好加密和解密的方法,要么当面约定,要么采用另外一条可信任的交流渠道。

很难想象有对称加密算法能摆脱这种限制。1974年,美国加利福尼亚大学伯克利分校的本科生拉尔夫·默克尔在课堂作业里提出了一个项目,探讨“两人无需提前约定便可安全通信”的方法。当时他预料到这个题目听起来有多离谱,还补充道:“不,我没在开玩笑。”默克尔想象了一个系统,其中两个人可以完全公开地交换信息,假设永远有人在偷听。通过公开交流,他们可以构建起一套编码和解码的方案,然后用来发送秘密信息。即使有其他人在偷听这些信息,也没办法猜到解码方案,并破解秘密信息。默克尔的提案被一名专家否决了,因为“工作假设不切实际”。

不过,令人惊叹的是,在仅仅数年后便有几篇数学论文实现了默克尔的想法。其中提出的两种算法,Diffie-Hellman和RSA(是三名作者姓氏Rivest、Shamir和Adleman的首字母缩写)在现代通信中获得了广泛应用。事实上,早在默克尔的课堂作业之前,英国情报机构的研究人员就已经发现了这类编码方案——公钥加密算法——但没有公开。

当你在网上检查银行账户的时候,计算机和银行服务器就在进行通信:你发送自己的密码,银行发回你的余额信息。当这些信息通过互联网传输时,其他人可能会读取。因此,这些信息必须加密。

大多数消息都是通过对称加密算法加密的,比如AES,它可以快速高效地混淆信息。但首先,你的计算机和对面的服务器必须约定好具体的混淆手段。不过这种约定不能直接写下来,因为所有的交流方式都可能被窃听者记录。他们必须使用公钥加密算法加密。

要想理解公钥加密算法的过程,我们可以想象有两位朋友,艾丽斯和鲍勃,他们共同开了一家面包店,有一个非常机密的布朗尼蛋糕食谱,机密到就连艾丽斯和鲍勃都不知道完整的食谱。他们会各自加一道只有自己知道的神秘配料。在制作布朗尼蛋糕时,艾丽斯和鲍勃会交替选择一个人开始。有时候艾丽斯会负责混合基础材料,并加入自己的机密配料,然后把混好的面糊交给鲍勃,由他加入自己的配料,最后烘焙。有时候鲍勃会负责混合基础材料并加入他的配料,然后交给艾丽斯,由她加入自己的秘密配料并烘焙。

最终,艾丽斯和鲍勃总是会得到相同的布朗尼蛋糕——但他们从来不用对任何人分享完整的食谱,就连他们自己都不知道。即使是给他们运货的狡猾司机伊芙,也没办法猜出完整的食谱。(在密码学里,经常会用艾丽斯和鲍勃表示交换信息的两人,即A和B;而伊芙则是“偷听者”的谐音。)伊芙不可能推断出秘密配料,因为当她运送面糊时,这些配料永远和基本配料混合在一起——不可能分离开来。

当然,计算机不会烘烤布朗尼,而是对数字执行数学运算。在真正的公钥密码学里,其目标是得到一个双方共享的秘密数字——类似授予私人对话访问权限的一个临时密码。接下来,两台计算机就可以用对称加密算法(比如AES)进行加密通话。

不同的公钥加密算法会用不同的方式制作和共享临时密码。艾丽斯和鲍勃为了不让伊芙知道他们的布朗尼配方,会在寄出前先把配料混合进面糊里。实现公钥加密的人则会使用数学函数来混合秘密数字。

我们可以将函数粗略地理解为一种机器,它在接收数字输入后,执行一些操作,再输出一个新的数字。公钥加密用到的函数非常特别,它既需要轻松地混合数字,又需要保证这些数字很难拆开。这样,即使伊芙看到了函数的输出,也没办法猜到输入的秘密数字是什么。

例如,RSA加密算法是基于乘法函数和它的反函数(即因数分解)进行的。将数字乘起来作为混合手段对计算机来说很简单,就算数字很大也没问题。但是反过来,如果是一个大数,因数分解将变得很困难。因数分解问题问的是:哪些数字相乘能得到输入的数字。例如,对21做因数分解,会得到3和7。要解码RSA创建的密码,就要对大数做因数分解。其中最好的办法也需要筛选很多数字才能找到特定的组合——对计算机而言,这需要花很长时间。

美国哈佛大学的计算机科学家博阿兹·巴拉克说道:“我们并没有试图让加密算法变得越来越复杂,而是改用了原理非常非常简单的加密算法,比如人们已经研究了好几千年的因数分解。”

利剑高悬

1994年,当时还在美国贝尔实验室做研究员的应用数学家彼得·肖尔提出了一种方法,可以让量子计算机解开任何通过RSA或Diffie-Hellman算法加密的密文。肖尔告诉我,他当时参加了一个讲座,讲如何使用量子计算机求解具有周期性结构的数学问题。这让他想到了“离散对数”问题。对数函数是指数函数的反函数。求对数通常很简单,但离散对数是在同余意义下进行的“算术”运算中的“对数”变体,类似于在时钟上进行3+10=1的算术。比如,在模为21的空间下,求Ind5(16),这需要5x除以21余16,虽然最终可以求得x为4,但计算机求解这一问题的过程并不容易。就像RSA基于因数分解一样,Diffie-Hellman算法则基于离散对数问题。计算机科学家普遍认为,用传统计算机没办法快速算出离散对数,但是肖尔发现了一种算法,能在量子计算机上快速完成。接下来他用类似的逻辑说明如何用量子计算机快速找到大数的因数。这些解决方案被统称为肖尔算法。

肖尔想的并不是如何在真正的量子计算机上编程——他只是在黑板上列出了数学公式。“当时量子计算机似乎还遥不可及”,肖尔说,“所以我主要想的是,这是一个非常好的数学定理。”但他的算法对公钥加密算法的影响非常大,因为量子计算机可以用它破解几乎所有现在正在使用的加密体系。

经典计算机处理的数据是被称为比特(bit)的长串“0”和“1”,但量子计算机使用量子比特(qubit),其中“qu-”是“quantum”(意为量子)一词的前两个字母。量子比特可以处于叠加态——同时处于“0”态和“1”态的神奇组合。当量子比特处于叠加态时,量子计算机可以在某些问题上获得比经典计算机更快的运算速度。然而量子计算机很挑剔。量子比特必须在算法运行时一直处于叠加态,但它们却很容易“坍缩”成一串“0”态和“1”态。

量子计算机看起来很厉害——就像天花板上悬吊着的巨型黄金吊灯,但现在还没有很强。科学家至今只使用过少量量子比特进行过运算,而他们在量子计算机上用肖尔算法分解过的最大数字是21。2012年,英国布里斯托尔大学的研究人员用量子计算机计算出21=3×7。

很多专家相信,足以破解RSA和Diffie-Hellman加密算法的强大量子计算机会在接下来几十年内出现,但他们也很快承认,这一时间线并不确定。对于密码学家而言,他们必须比量子计算机更快想出解决方案才行,这种不确定性很令人担忧。每个行业都有一部分工作非常重要,这些信息需要严格保密。比如,医疗保健公司必须确保医学研究使用数据的安全性;电力公司必须保证电网不被黑客破坏。最可怕的情况是:如果发生什么糟糕的事情,它们会完全无力应急。

会永远安全吗

每种公钥加密算法都基于一个难解的数学问题。为了保证在未来量子时代还能保密,研究人员需要找到非常难解的问题,困难到连量子计算机都没办法在合理时间内求解。而研究院寻找的正是这样的公钥加密算法,它应该可以广泛地应用于标准计算机,并能很好地替代RSA和Diffie-Hellman算法。人们所使用的各种互相连接的系统和设备都能“用这种新的加密算法和其他设备对话”,数学家莉莉·陈说。

在2017年的截止日期之前,研究人员提交了82种不同的后量子密码学提案。“量子密码学”和“后量子密码学”听起来很相似,却是完全不一样的概念。量子密码学指的是把量子现象用作加密体系一部分的做法。在接下来的几年里,研究人员测试了这些算法,而后美国国家标准与技术研究院的专家选择了26个算法进入下一轮。

公众反馈是比赛中很重要的一部分。密码学系统并不保证安全,因此研究人员要试着破坏它们,找寻其中的漏洞。其中一个候选算法使用了基于同源(isogeny)的加密算法,它被研究了好几十年,似乎前景颇为乐观。但两名研究员注意到,一个25年前的数学定理可以用来破解那个算法。他们用普通的笔记本电脑只花了一个小时,便破解了该算法。

专家最终选出了几个进入决赛的算法,多数都基于格问题。“格是一个很自然的选择”,CRYSTALS-Kyber的作者之一,IBM的瓦季姆·柳巴舍夫斯基说道,“人们已经用各种方式研究它二十多年了。”

格是指一组周期性的点阵。最简单的格可以被想象成一个钉板——从正方形网格的顶点排列出的点阵。数学家认为这组点阵是由两条基础线组成的结构:一根水平线和一根等长的垂直线。想象在纸的中心画一个点,再从中心沿着水平线或垂直线走几步,把最后的落点记下来。如果你遍历所有走法,会发现最后这些点形成了一个方格。不同的初始线组会生成不同的格。两条线的长度可以不一样,也可以不走横平竖直而是有一定角度。用这种线组重复走许多步,同样会得到周期性的点阵,但是行和列会错开,或是高度不同。

一些以格为背景的数学问题看似简单,实际上非常棘手。假设我在纸上画了两条线,告诉你这就是构成格的基础单元。然后我在纸上某处随便画一个点。你能找到离那个点最近的格点吗?

你大概会从那两条线开始画格点,最终找到最近的一个。但这种方法可行,完全是因为纸面只有二维。我们的空间想象力通常局限于三维或更低维,但数学家却可以描述几百维的格。在这样的情况下,想找到最近的格点变得非常困难。

研究人员使用巨大的格来构造加密系统。例如,从一个1000维的格开始。从这个点阵海中,选择一个点。这个点的具体位置就表示需要加密的信息。然后从那个点出发,找到一个稍微偏离格一些的新点。接下来你可以公开那个新点的位置,而无需暴露原始的秘密点是哪个——找到最近的格点是个非常难的数学问题。就好像混合配料可以保护布朗尼蛋糕配方的秘密一样,从秘密点出发,偏离一点也可以隐藏它的准确位置。

计算机科学家已经研究这类问题几十年了,他们有理由相信这些问题非常难解。但是在设计新的算法时,密码学家还需要在安全性和很多其他问题之间进行权衡,比如两台计算机之间需要交换的信息量,以及加密和解密的计算难度。在这方面,基于格的密码学很出色。“格恰好落在了各方面都很合理的一个位置上——各方面都不算太糟,各方面也没有过好。”派克特说。

问题在于,没有人能保证基于格的加密算法会永远安全。为了防止某一天数学研究上的突破解决了加密算法底层的问题——并据此破解密码——密码学家必须有多种算法备用。但美国国家标准与技术研究院最终选出的四种算法里有三种是基于格的。而选作通用公钥加密算法进行标准化的只有CRYSTALS-Kyber。

比赛还有一个组别是数字签名算法,这种算法能确保发送信息的人为真,以及信息未被修改。美国海军研究院的密码学家布里塔·黑尔解释说,加密算法回答的问题是“我能确保其他人不会读到这条信息吗?”而数字签名回答的问题是“我能信任这些数据没被修改过吗?”现在使用的数字签名算法同样会被肖尔算法破解。三个数字签名算法进行标准化,其中两个基于格。如此依赖单一类型的数学问题,风险很大。没有人能保证,数学家不会在哪天破解这个问题。用户也没有太多选择上的自由度——可能另外一种加密算法更符合他们的具体需要。因为这些原因,研究院拓宽了两个组别的标准化过程,以研究那些非基于格的算法。

而就算是选作标准的算法,也需要进行调整。在第一轮提交过后,研究人员注意到CRYSTALS-Kyber有一个小问题,而作者也解决了。在之后的一轮提交过程中,他们找到一个办法稍微改进了算法。“我们改变了参数,增加了几比特的安全性。”德国马克斯·普朗克安全与隐私研究所的彼得·施瓦贝说,他是CRYSTALS-Kyber的作者之一。其中,密码学中一个算法的安全等级可以用“比特”衡量,安全度为n比特表示需要2n次运算才能破解。

研究院现在正在敲定标准,其中需要详细规范程序员应当如何实现这些算法。“互联网上的所有东西都必须有非常精确、非常无聊的标准,其中包括每个小细节。否则计算机就没法互相对话了”,柳巴舍夫斯基说。在标准确立之后,每台计算机系统都需要切换到后量子加密算法。这不是所有人同时按个开关就能实现的事。每个软件公司都必须升级协议,政府需要修改需求,甚至需要更换物理硬件。

完全转换到后量子加密算法可能需要花很多年,甚至几十年。在那之前,所有使用旧方法加密的信息都可能被未来的量子计算机破译。如果你想保密很长时间,那该着急的时间点可能已经过了。就像黑尔说的那样:“在密码学领域,每个人都盯着表说‘你已经过时限了’。”

(作者:凯尔茜·休斯敦-爱德华兹)

本版图文由《环球科学》杂志社供稿