立即打开
人类要如何面对数字安全的终极威胁者——量子计算机

人类要如何面对数字安全的终极威胁者——量子计算机

Jeremy Khan 2020年09月16日
使用量子物理编译信息的机器在未来的某一天将变得足够强大,能够破解当前使用最广泛的编译系统,并导致几乎所有的数字通讯手段失去其安全性。

在过去10年的很长一段时间中,网络安全专家一直在警告一个正在逼近的威胁:量子计算机的面世。

这些使用量子物理来编译信息的机器在未来的某一天将变得足够强大,继而破解当前使用最广泛的编译系统,并导致几乎所有的数字通讯手段失去其安全性。

人们一直在问,这一天什么时候才能到来。最常见的数字加密技术RSA诞生于1977年,它基于两个大素数之商。其中的一个破解办法就是弄清楚这两个大素数到底是多少。1994年,数学家皮特•肖尔发明了一种算法,如果将其交由算力足够强大的量子计算机来运算,则可以轻易破译这两个素数。然而在当时,量子计算机依然停留在纯理论阶段。

第一台能够工作的量子计算机诞生于十多年前。然而,大多数量子计算机要么在设计之初便并非用于运行肖尔的算法,要么就是没有足够的算力来计算异常庞大的素数对。网络安全专家担忧的量子计算机黑客时代还远未到来,有人估计至少还得等25年,而且当时还存在着更加紧迫的威胁。

然而好景不再。去年,谷歌称自己已经实现了所谓的“量子霸权”里程碑,打造了一台量子计算机,它可以执行传统计算机无法开展的计算,并运行相当长的一段时间。

谷歌的这台机器依然无法破解RSA。然而,量子硬件制造的快速进步,再加上算法方面些许高明的调整,意味着肖尔的算法迫使RSA退出历史舞台的时代已经大幅提前。专家称,如果幸运的话,我们可能还有十几年的时间为数据隐私保护工作添砖加瓦。然而,一些人认为最多还有五年的时间,甚至可能更短。

2016年,美国国家安全局(U.S. National Security Agency)发布了一则严重警告:政府机构和公司必须“立即采取行动”,开始转而使用能够防范量子计算机攻击的新加密标准。唯一的问题?没有人知道这个加密标准到底长什么样。

正是基于这个原因,全美标准与技术研究所(NIST)在大约三年前便开始举行比赛,以选出一种可以抵御量子计算机攻击的新加密技术。该研究所隶属于美国商务部(U.S. Department of Commerce),负责向政府和企业推荐其常用标准。

这些新“后量子”加密和数字签名方法将有可能成为美国各政府部门以及众多与政府做生意的企业必须强制采取的标准,尤其是国防和情报部门。有鉴于美国市场的规模,它们很有可能成为一种新的全球安全标准。NIST如今很快将选出获胜的加密算法,并借此迈入网络安全新时代。

今年7月,这家负责标准的机构宣布,经筛选,候选者清单从最初的82个缩减至依然较长的15个,在主要决赛选手中,有4名来自于加密学,3名来自于数字签名领域,它们均使用密码来验证电子信息和文件的真实性。(8名候补选手也将参加决赛轮。)NIST称,它将在未来18个月之内宣布最终获胜者,并将其作为新加密标准。

因此,NIST的这个长篇候选清单描述了一个什么样的网络安全未来?其实,它很有可能涉及人们所称的基于格的密码技术。竞赛中四分之三的决赛选手都采用了这个门类的算法。

基于格的密码技术依靠的是栅格化等间隔点的独特数学特性,又称格密码。由于这些点的间隔相等,事实在于,人们只需要栅格的两个坐标便能够计算出同一格子中所有的点。然而,如果格子存在数千个维度,而且如果格子中各点之间的角度与直角偏差过大,那么弄清楚任何特定点是否都处于格子中将是一件十分困难的事情。人们已经制定了一系列加密机制,以利用这些特性来打造可以共同协作的公钥和私钥,因为它们都基于同样的格子。不过在这一领域,以公钥为模板来制作私钥是极其困难的事情。

然而,一些网络安全专家对于NIST如此倚重这类后量子加密技术的事实感到十分惊讶。这是因为,尽管这种基于格子的问题在数学层面上十分难解,而且与RSA不同的是,它并不容易被肖尔的算法破解,但并没有证据表明,这类技术从数学层面来讲就能够彻底防范基于量子计算机的攻击。英格兰约克大学的网络安全教授德拉拉姆•卡罗贝伊说:“虽说现在的量子算法还无法破解它们,但说不定明天就会有人拿出用于破解的量子算法。”

卡罗贝伊称,令她感到失望的是,来自于其他门类的潜在后量子算法并未进入公钥加密竞赛的决选名单。这其中包括多变量加密,它取决于解答复杂二次方程式系统的难度(还记得高中算术中那些方程式吗?);以及卡罗贝伊自己的研究领域——基于群的密码学。这种密码学基于另一种数学,涉及通过结合要素来转化一组数字,通常按照精心制作的几何样式,例如编织形状。一位来自于多变量加密门类的候选者开发了名为Rainbow的算法,而且的确进入了竞赛数字签名部分的决选名单,另一个名为GeMSS的算法在该竞赛中被选为候补算法。

NIST决选名单中唯一非格子后量子加密候选者来自于称之为基于代码算法的密码学门类。这类算法设计会在数据中添加某些错误信息,例如在经典的加密方式中人们会将字母向后移动两位进行加密,也就是A变成C,B变成D,以此类推。然后在解密这个信息的过程中会将这种错误纠正过来。NIST选择的后量子算法称之为Classic McEliece,它取名于上个世纪70年代末由数学家罗伯特•麦克阿里斯发明的纠错代码算法。它会随机向每一条加密信息添加错误信息,从理论上来讲,如果不知道秘钥的话是无法破解的。

Post-Quantum Group的联合创始人兼首席执行官安德森•程说:“麦克阿里斯的系统已经存在了41年,而且一直遭到密码界的攻击,但未发现任何漏洞。” Post-Quantum Group是一家总部位于伦敦的网络安全公司,其合作方为芝加哥伊利诺伊大学的知名密码学专家丹尼尔•伯恩斯坦领导的团队。在NIST的长篇决选名单中,Classic McEliece算法便是二者合作的成果。

2019年,德国联邦信息安全办公室(German Federal Office for Information Security)担心NIST在这个流程中花的时间过长,因此推荐Classic McEliece作为候选的两个后量子加密标准之一。(另一个来自于NIST候补名单,采用的是格密码方法。)安德森•程称,他怀疑NIST与德国政府一样,最终会批准两套标准,即Classic McEliece和其中一种格密码方法。

安德森说,McEliece算法唯一的缺点在于,该方法使用的秘钥相对较长,而且算法计算十分复杂,意味着与其竞争对手网格化方法相比,计算机需要更多的时间来加密、解密信息。安德森还说:“速度会慢几毫秒。”但他说,在交换公钥时(这也是算法的主要用途),这个方法实际上依然要比RSA快。

尽管像IBM、英特尔和芯片制造商ARM这样的知名科技公司的研究人员也参加了比赛,寻找防范量子破解的加密算法,但值得一提的是,参加NIST竞赛的网络安全公司相对来说较少。Post-Quantum是参加竞赛的多家初创企业之一,这些初创公司将受益于迈向新一代加密技术的举措。

卡罗贝伊称,她预计市场上将涌现一大批新公司,帮助实现后量子加密的商业化,就像RSA成为过去30年网络安全领域的主导者一样。RSA成立于1982年,旨在实现RSA算法的商业化。

安德森说,Post-Quantum Group成立于2009年,曾几何时,要让首要银行和企业的首席信息安全官和首席信息官严肃对待量子计算机的威胁对于公司来说是一件很难的事情。然而他说,NIST竞赛引发了其迟来的关注。他说:“如今他们意识到自己得在18个月的时间内采取行动,而且也开始发出疑问:‘自己能做什么?’”(财富中文网)

译者:冯丰

审校:夏林

在过去10年的很长一段时间中,网络安全专家一直在警告一个正在逼近的威胁:量子计算机的面世。

这些使用量子物理来编译信息的机器在未来的某一天将变得足够强大,继而破解当前使用最广泛的编译系统,并导致几乎所有的数字通讯手段失去其安全性。

人们一直在问,这一天什么时候才能到来。最常见的数字加密技术RSA诞生于1977年,它基于两个大素数之商。其中的一个破解办法就是弄清楚这两个大素数到底是多少。1994年,数学家皮特•肖尔发明了一种算法,如果将其交由算力足够强大的量子计算机来运算,则可以轻易破译这两个素数。然而在当时,量子计算机依然停留在纯理论阶段。

第一台能够工作的量子计算机诞生于十多年前。然而,大多数量子计算机要么在设计之初便并非用于运行肖尔的算法,要么就是没有足够的算力来计算异常庞大的素数对。网络安全专家担忧的量子计算机黑客时代还远未到来,有人估计至少还得等25年,而且当时还存在着更加紧迫的威胁。

然而好景不再。去年,谷歌称自己已经实现了所谓的“量子霸权”里程碑,打造了一台量子计算机,它可以执行传统计算机无法开展的计算,并运行相当长的一段时间。

谷歌的这台机器依然无法破解RSA。然而,量子硬件制造的快速进步,再加上算法方面些许高明的调整,意味着肖尔的算法迫使RSA退出历史舞台的时代已经大幅提前。专家称,如果幸运的话,我们可能还有十几年的时间为数据隐私保护工作添砖加瓦。然而,一些人认为最多还有五年的时间,甚至可能更短。

2016年,美国国家安全局(U.S. National Security Agency)发布了一则严重警告:政府机构和公司必须“立即采取行动”,开始转而使用能够防范量子计算机攻击的新加密标准。唯一的问题?没有人知道这个加密标准到底长什么样。

正是基于这个原因,全美标准与技术研究所(NIST)在大约三年前便开始举行比赛,以选出一种可以抵御量子计算机攻击的新加密技术。该研究所隶属于美国商务部(U.S. Department of Commerce),负责向政府和企业推荐其常用标准。

这些新“后量子”加密和数字签名方法将有可能成为美国各政府部门以及众多与政府做生意的企业必须强制采取的标准,尤其是国防和情报部门。有鉴于美国市场的规模,它们很有可能成为一种新的全球安全标准。NIST如今很快将选出获胜的加密算法,并借此迈入网络安全新时代。

今年7月,这家负责标准的机构宣布,经筛选,候选者清单从最初的82个缩减至依然较长的15个,在主要决赛选手中,有4名来自于加密学,3名来自于数字签名领域,它们均使用密码来验证电子信息和文件的真实性。(8名候补选手也将参加决赛轮。)NIST称,它将在未来18个月之内宣布最终获胜者,并将其作为新加密标准。

因此,NIST的这个长篇候选清单描述了一个什么样的网络安全未来?其实,它很有可能涉及人们所称的基于格的密码技术。竞赛中四分之三的决赛选手都采用了这个门类的算法。

基于格的密码技术依靠的是栅格化等间隔点的独特数学特性,又称格密码。由于这些点的间隔相等,事实在于,人们只需要栅格的两个坐标便能够计算出同一格子中所有的点。然而,如果格子存在数千个维度,而且如果格子中各点之间的角度与直角偏差过大,那么弄清楚任何特定点是否都处于格子中将是一件十分困难的事情。人们已经制定了一系列加密机制,以利用这些特性来打造可以共同协作的公钥和私钥,因为它们都基于同样的格子。不过在这一领域,以公钥为模板来制作私钥是极其困难的事情。

然而,一些网络安全专家对于NIST如此倚重这类后量子加密技术的事实感到十分惊讶。这是因为,尽管这种基于格子的问题在数学层面上十分难解,而且与RSA不同的是,它并不容易被肖尔的算法破解,但并没有证据表明,这类技术从数学层面来讲就能够彻底防范基于量子计算机的攻击。英格兰约克大学的网络安全教授德拉拉姆•卡罗贝伊说:“虽说现在的量子算法还无法破解它们,但说不定明天就会有人拿出用于破解的量子算法。”

卡罗贝伊称,令她感到失望的是,来自于其他门类的潜在后量子算法并未进入公钥加密竞赛的决选名单。这其中包括多变量加密,它取决于解答复杂二次方程式系统的难度(还记得高中算术中那些方程式吗?);以及卡罗贝伊自己的研究领域——基于群的密码学。这种密码学基于另一种数学,涉及通过结合要素来转化一组数字,通常按照精心制作的几何样式,例如编织形状。一位来自于多变量加密门类的候选者开发了名为Rainbow的算法,而且的确进入了竞赛数字签名部分的决选名单,另一个名为GeMSS的算法在该竞赛中被选为候补算法。

NIST决选名单中唯一非格子后量子加密候选者来自于称之为基于代码算法的密码学门类。这类算法设计会在数据中添加某些错误信息,例如在经典的加密方式中人们会将字母向后移动两位进行加密,也就是A变成C,B变成D,以此类推。然后在解密这个信息的过程中会将这种错误纠正过来。NIST选择的后量子算法称之为Classic McEliece,它取名于上个世纪70年代末由数学家罗伯特•麦克阿里斯发明的纠错代码算法。它会随机向每一条加密信息添加错误信息,从理论上来讲,如果不知道秘钥的话是无法破解的。

Post-Quantum Group的联合创始人兼首席执行官安德森•程说:“麦克阿里斯的系统已经存在了41年,而且一直遭到密码界的攻击,但未发现任何漏洞。” Post-Quantum Group是一家总部位于伦敦的网络安全公司,其合作方为芝加哥伊利诺伊大学的知名密码学专家丹尼尔•伯恩斯坦领导的团队。在NIST的长篇决选名单中,Classic McEliece算法便是二者合作的成果。

2019年,德国联邦信息安全办公室(German Federal Office for Information Security)担心NIST在这个流程中花的时间过长,因此推荐Classic McEliece作为候选的两个后量子加密标准之一。(另一个来自于NIST候补名单,采用的是格密码方法。)安德森•程称,他怀疑NIST与德国政府一样,最终会批准两套标准,即Classic McEliece和其中一种格密码方法。

安德森说,McEliece算法唯一的缺点在于,该方法使用的秘钥相对较长,而且算法计算十分复杂,意味着与其竞争对手网格化方法相比,计算机需要更多的时间来加密、解密信息。安德森还说:“速度会慢几毫秒。”但他说,在交换公钥时(这也是算法的主要用途),这个方法实际上依然要比RSA快。

尽管像IBM、英特尔和芯片制造商ARM这样的知名科技公司的研究人员也参加了比赛,寻找防范量子破解的加密算法,但值得一提的是,参加NIST竞赛的网络安全公司相对来说较少。Post-Quantum是参加竞赛的多家初创企业之一,这些初创公司将受益于迈向新一代加密技术的举措。

卡罗贝伊称,她预计市场上将涌现一大批新公司,帮助实现后量子加密的商业化,就像RSA成为过去30年网络安全领域的主导者一样。RSA成立于1982年,旨在实现RSA算法的商业化。

安德森说,Post-Quantum Group成立于2009年,曾几何时,要让首要银行和企业的首席信息安全官和首席信息官严肃对待量子计算机的威胁对于公司来说是一件很难的事情。然而他说,NIST竞赛引发了其迟来的关注。他说:“如今他们意识到自己得在18个月的时间内采取行动,而且也开始发出疑问:‘自己能做什么?’”(财富中文网)

译者:冯丰

审校:夏林

For much of the past decade, cybersecurity experts have been warning of a looming threat: the advent of quantum computers.

These machines, which use principles of quantum physics to represent information, will one day be powerful enough to crack the most widely used encryption systems, rendering almost all digital communication insecure.

The question has always been exactly when that day would arrive. The most common digital encryption technique, RSA, which was invented in 1977, is based on multiplying two large prime numbers. One way to break it is to figure out what those two large primes were. In 1994, mathematician Peter Shor invented an algorithm, that if run on a sufficiently powerful quantum computer, would easily find these two primes. But at the time, quantum computers were still purely theoretical machines.

The first working quantum computers were built over a decade ago. But most were either not designed in a way that would allow them to run Shor’s algorithm. Others were simply not powerful enough to do so for a very large prime multiple. The moment when cybersecurity experts would have to worry about quantum computer-equipped hackers seemed a long way off—at least a quarter century by some estimates—and there were far more pressing threats.

But not anymore. Last year, Google claimed it had achieved a milestone known as “quantum supremacy,” having built a quantum computer capable of performing a calculation that could not be done on a traditional computer in a reasonable length of time.

Google’s machine is still unable to break RSA. But the rapid progress in building quantum hardware along with some clever advancements in algorithms mean the timeline for Shor’s algorithm rendering RSA obsolete have been moved up considerably. If lucky, we may have more than decade of data privacy protection left, experts say. But some think we have at best five years—maybe less.

In 2016, the U.S. National Security Agency issued a stark warning that government agencies and companies "must act now" to begin moving to a new encryption standard that is safe from quantum computer-based attacks. The only problem? No one was sure exactly what that encryption standard should be.

That’s why the National Institute of Standards and Technology (NIST), an agency with the U.S. Department of Commerce that is responsible for recommending standards that are often adopted by both government and business, began a competition almost three years ago to select new encryption techniques that would be resistant to attacks from quantum computers.

These new “post-quantum” encryption and digital signature methods will likely become mandatory for all U.S. government departments and for many companies that do business with the government, especially in defense and intelligence. Because of the size of the U.S. market, they are also likely to become the new global security standard. NIST is now on the verge of picking the winning encryption algorithms—and ushering in a new era in cybersecurity.

In July, the standards agency announced that it had winnowed an initial group of 82 candidates down to a long-list of 15, including four main finalists for encryption and three for digital signatures, which use cryptography to verify whether electronic messages and documents are authentic. (Eight alternates will advance to the final round as well.) NIST has said it will announce its final endorsements for a new encryption standard within the next 18 months.

So what does the NIST long-list tell us about the future of cybersecurity? Well, there’s a good chance that it will involve something called lattice-based cryptography. Three of the four encryption finalists come from this family of algorithms.

Lattice-based cryptography is based on the unique mathematical properties of grids of evenly-spaced points, or lattices. Because the points are evenly spaced, it turns out that from just two coordinates of the grid it is possible to compute all the points within the same lattice. But figuring out whether any given point is in the lattice can be difficult if the lattice is in many thousands of dimensions and if the angles between points in the grid are far from perpendicular. A number of encryption schemes have been created that use these properties to create a public key and a private key that work together—because they are calculated from the same lattice—but in which it is extremely difficult to derive the private key from the public key alone.

But some cybersecurity experts are surprised that NIST has leaned so heavily towards this kind of post-quantum encryption. That’s because while lattice-based problems are mathematically difficult and, unlike RSA, are not susceptible to Shor’s algorithm, they have not been mathematically proven to be impervious to a quantum computer-based attack. “We say that quantum algorithms cannot break them yet,” Delaram Kahrobaei, a professor of cybersecurity at the University of York, in England, says. “But tomorrow someone comes up with another quantum algorithm that might break them.”

Kahrobaei says she is disappointed to see that candidates from other families of potential post-quantum algorithms did not make it onto the final list for the public key encryption competition. This includes multivariate cryptography, which is based on the difficulty of solving systems of complex quadratic equations (remember those from high school algebra?), and group-based cryptography, which is the area that Kahrobaei herself works on. It is based on yet another area of mathematics involving transforming a set of numbers by combining elements, often according to elaborate geometric patterns, such as braids. One candidate from the multivariate cryptography family, an algorithm called Rainbow, did make onto the list of finalists in the digital signature portion of the competition, and another, called GeMSS, was selected as an alternate in that contest.

The only non-lattice post-quantum encryption candidate among the NIST finalists comes from a cryptographic family known as code-based algorithms. These all involve adding some sort of error to data—like a classic code where you shift the alphabet over two letters so that A is encoded as C and B as D, and so on. This error is then corrected to decrypt the message. The post-quantum algorithm NIST has chosen is called Classic McEliece, named for an error-correcting code algorithm invented by mathematician Robert McEliece in the late 1970s. It applies a different random error to each piece of information that’s encoded—which in theory makes it impossible to break without knowing the key.

“McEliece’s system has been around for 41 years and been attacked by the crypto community for all that time without finding a vulnerability,” Andersen Cheng, the co-founder and chief executive officer of Post-Quantum Group, a London-based cybersecurity company that joined forces with another team, led by Daniel Bernstein, a noted cryptographer at the University of Illinois in Chicago, to work on the Classic McEliece submission that made it to the long list of NIST finalists.

In 2019, the German Federal Office for Information Security (BSI), concerned that the NIST process was taking too long, recommended the Classic McEliece as one of its two recommended post-quantum encryption standards. (The other was a lattice-based method that is among NIST’s alternate candidates.) Cheng says he suspects that NIST, like the German government, will ultimately endorse two standards—Classic McEliece and one of the lattice methods.

The only drawback of the McEliece algorithm, Cheng says, is that the relatively lengthy keys the method uses, and the computational complexity of the algorithm, means it takes more time for a computer to encrypt and decrypt information than with its lattice-based competitors. “It’s slower by a few milliseconds,” Cheng says. But he says that for exchanging public encryption keys—which is mostly what the algorithm would be used for—the method is still actually faster than RSA.

While there are researchers from established tech companies, such as IBM, Intel, and the chipmaker ARM, involved in the race to find quantum-secure encryption algorithms, what’s notable is how relatively few established cybersecurity firms are contenders in the NIST contest. Post-Quantum is among several startups that entered the competition—and which are poised to profit from the move to a new generation of encryption.

Kahrobaei says she expects a host of new companies to spring up to help commercialize post-quantum encryption, just as RSA Security—the company that was founded in 1982 to commercialize the RSA algorithm—became a dominant player in the cybersecurity space for the past three decades.

Cheng says that Post-Quantum Group, which was founded in 2009, once struggled to get chief information security officers and chief information officers at major banks and corporations to take the threat of quantum computers seriously. But, he says, the NIST process has belatedly focused their attention. “Now they know they have to do something in 18 months-time and they are starting to ask questions, ‘what can they do?’ ” he says.

最新:
  • 热读文章
  • 热门视频
活动
扫码打开财富Plus App