若想世界不崩塌，先开发后量子时代加密算法

作者 | 蒋宝尚

2020年，世界上产生的数据量预计有40ZB，如果一个硬盘的存储量是1T，那么一个ZB相当于10亿个硬盘。

如果用传统的储存方法，根据香飘飘奶茶广告词中的计量方式：“香飘飘奶茶,一年卖出三亿多杯，杯子连起来可绕地球一圈。”那么，世界一年产生的数据所需的1T硬盘，至少也能绕地球一圈。

而面对巨量的数据，未来量子存储设备则只需要指甲盖大小就能存储人类几百年的信息。

除了上述量子计算带来的好处，它打破传统计算机二进制基础之后带来的威力也是一种威胁。毕竟，量子计算机在0和1之间有无数种可能，一台真正的量子计算机运算能力可能超过现在世界上所有计算机运算能力之和。

这就意味着量子计算机一旦被率先突破，那么现在所有的加密算法都会被马上破解，全世界的信息将没有安全可言。换句话说，首台量子计算机诞生，它足以破解当代绝大多数的加密标准。

因此，我们就需要新一代的加密算法来应对这类量子计算的威胁。在介绍后量子时代加密算法之前，我们先介绍公钥密码。

1

公钥密码与天敌

当前，公钥密码已经广为使用，无论去线下银行、还是在网上银行办业务，都要证明个人身份以避免被人冒用，访问电商网站或使用手机支付时，其数据也需加密。

除民用用途之外，公钥密码算法在海陆空通信方面也有着特定用途，设备间的通信都需要数据加密和身份验证。比如，对面过来一架飞机，远处看到一艘船，往往需要判断对方到底是友是敌，这时也需要用公钥密码算法来保护传输数据。

随着量子计算能力的提高，目前已经从数学上证明，经典公钥密码算法肯定会被量子计算机所攻破。当前，整个互联网系统安全和网络安全，都会用到密码技术，而目前最不可被取代的正是公钥密码模块。

公钥密码算法一旦被量子计算机攻破，整个互联网将“轰然倒塌”，那时我们将没法去银行，也没法用电，甚至没法坐飞机和高铁。整个互联网系统会因为失去安全而瘫痪，各种网络攻击事件将不断出现。

可以说，全人类都面临着量子攻击的风险。因此，学术界正在研究能替换经典公钥密码算法的算法，即后量子密码算法，以有效应对量子计算机技术进步带来的严峻挑战。

2

后量子密码算法分类与进程

能有效抵御量子计算机攻击的密码算法，统称为后量子密码 (Post-Quantum Cryptography) 或抗量子攻击密码 (Quantum-Resistant Cryptography)。后量子，主要是指针对量子计算机时代的安全威胁，所发展出的密码算法体系。

后量子密码算法分五大类：第一类是基于格的，第二类是基于编码的，第三类是基于多变量的，第四类是基于哈希的，第五类是基于超奇异同源的。

其中，第一类基于格的后量子密码算法由于其计算的相对高效性和通用性，成为最主流的候选算法种类。

业界的一些产业巨头已经在后量子密码算法的应用方面进行了一些探索。谷歌于 2016 年在其实验版浏览器中实现了后量子密钥交换算法 NewHope，虽然可以证明其对量子攻击防护的一定有效性，但其执行效率限制了其进一步推广应用。

微软研究院已推出后量子密码算法 Picnic 算法和后量子 VPN 算法，亚马逊公司目前也在其 AWS 密钥管理系统中的传输层安全（Transport layer security, TLS）网络加密协议中提供后量子密钥交换支持。

目前，全球尚未就后量子密码算法形成统一的标准。美国国家标准与技术研究院（National Institute of Standards and Technology，下称 NIST）正在开展后量子密码算法的标准化工作，目前已经推进到第三轮。

对于征集到的每个候选算法，NIST 及密码领域的研究人员都会对其进行安全评估、数学评估、以及实现性能评估（包括软件实现和硬件实现）。最终通过评估的算法，将会成为 NIST 的推荐标准。

NIST 的后量子标准化是影响力最大，同时进展最快的，其从第一轮征集到的 69 个候选算法，到目前第三轮仅剩下 15 个算法，预计至 2021 年底还会淘汰大半，仅选出不到五个算法，直到最后沉淀出的算法成为 NIST 推荐的国际标准。

由于后量子密码算法要抵抗未来的量子攻击和当前的经典计算攻击，因此需考虑未来数年计算机的发展。更重要的是，后量子密码算法的布局一定要先于量子计算机进入应用。

同时，公钥密码的应用广泛，不计其数的软硬件主体和企业都在使用公钥密码，替换它们将是一个超大系统工程，需提前三至五年布局。

具体的后量子密码算法：英特尔-BIKE

英特尔团队开发出了一款应对量子计算的升级版加密算法，可以有效运用于物联网下的智能家居与工业设备。

这个算法的名字叫作：BIKE（Bit-flipping Key Encapsulation）。

BIKE提供了一种创建共享密钥的方法。这个共享密钥能够对在两个设备之间交换的敏感信息进行加密。

加密过程要求计算层面的复杂操作，涉及到数学问题，可能会给许多物联网设备硬件带来压力。

针对这个问题，英特尔的研究人员开发了一个硬件加速器，使BIKE软件能够在功能较弱的硬件上高效运行。

当BIKE软件在物联网设备（尤其是轻量级设备中）上执行时，会造成密集的延迟与功耗，而他们所开发的BIKE硬件加速器能够在一定程度上解决这个问题。

英特尔一直在与其他公司合作，希望推动BIKE发展成为一种能够对抗量子计算威胁的加密算法。今年10月13日，英特尔团队将这个技术拓展为一篇论文，发表在了IEEE国际会议量子计算与工程会议（IEEE International Conference on Quantum Computing and Engineering）上。

论文地址：https://eprint.iacr.org/2020/117.pdf

2020年10月13日在IEEE量子计算与工程国际会议上，论文主要是由英特尔团队开发的最新版本的BIKE。

“在这三个步骤中，BIKE解码是计算量最大的操作，” Ghosh解释说。

据该论文的共同作者兼英特尔研究科学家Santosh Ghosh介绍，BIKE通过三个步骤，创建了一个安全性较高的共享密钥。

第一步：主机设备先创建一个“公钥-私钥”对，并将公钥发送至一个客户；

第二步：该客户使用公钥向主机发送一条加密消息；

第三步：主机使用私钥，通过BIKE解码过程对加密的消息进行解码。

在这三个步骤中，BIKE解码要用到的计算量最大。

BIKE的升级版本很好地利用了对算力要求较小的新型解码器。测试表明，这个新型解码器在Intel Arria 10 FPGA上，可以在12毫秒内以110 MHz的频率在130万个周期内执行单个BIKE解码操作的计算。

BIKE不仅适合安装在用于封装的物联网设备上，还能充当主机的角色，生成密钥并解除封装。

这也是适用于5级密钥和密文的BIKE的第一个硬件实现，其中5级为美国国家标准技术研究院（NIST）定义的最高安全级别。安全级别越高，所要求的密钥与密文就越大，对计算密集型操作的要求也越多。

英特尔团队先前便专注研究适用于安全级别为1和3的BIKE实现。

BIKE最新的硬件实现将安全级别提高了两个等级。

级别5提供了与AES-256相当的安全性，而BIKE解码器支持用于级别5的密钥和密文。这意味着，量子计算机需要进行2^128次的操作才能破解BIKE。

BIKE硬件加速器的最新版本设计先进，能够抵抗边信道攻击，阻止攻击者掠夺功率消耗或软件进程时间的信息，提高安全性。比方说，差分功耗攻击可以追踪用于运行某些计算任务的功耗模式，暴露一些隐藏计算。

从理论上讲，针对BIKE的此类攻击可能会试图针对两个设备之间的一小块秘密。密码块的大小取决于在隐藏子操作中一同工作的秘密位数量。由于1个BIKE块的大小为1位，因此1次处理1个秘密位的BIKE硬件设计极易受到差分功耗分析攻击的攻击。

新的BIKE硬件加速器可以并行处理128位秘密的计算，使得与各个计算相关的功耗模式难以被找到，因此可以有效抵御此类攻击。

BIKE硬件加速器还可以阻止定时攻击，因为其解码器始终运行着固定的回合，每个回合与定时的时间相同。

BIKE曾被NIST选为替代现代密码学标准的方案之一。

参考资料：

https://spectrum.ieee.org/tech-talk/computing/hardware/how-to-protect-the-internet-of-things-in-the-quantum-computing-era

https://mp.weixin.qq.com/s/ey73dnhsFz1CPBW_ZCWwmg