加密算法与量子核算的赛跑

liukang20242个月前 (05-03)998吃瓜705

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

未来量子核算机的面世将要挟一切经典加密信息的安全，暗码学家正分秒必争地开发能难倒量子核算机的加密算法。

快速开展的量子核算机

全世界的数字安全专家都把目光投向了量子年时钟（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次运算才干破解。

研讨院现在正在敲定规范，其间需求具体规范程序员应当怎么完结这些算法。“互联网上的一切东西都有必要有十分准确、十分无聊的规范，其间包含每个小细节。不然核算机就无法相互对话了”，柳巴舍夫斯基说。在规范建立之后，每台核算机体系都需求切换到后量子加密算法。这不是一切人一起按个开关就能完结的事。每个软件公司都有必要晋级协议，政府需求修正需求，乃至需求替换物理硬件。

彻底转换到后量子加密算法或许需求花许多年，乃至几十年。在那之前，一切运用旧办法加密的信息都或许被未来的量子核算机破译。假如你想保密很长时刻，那该着急的时刻点或许现已过了。就像黑尔说的那样：“在暗码学范畴，每个人都盯着表说‘你现已过时限了’。”

本版图文由《举世科学》杂志社供稿

《光明日报》（2024年11月07日 14版）

来历：光明网-《光明日报》

告发/反应