密码学家找到了免遭量子攻击的算法

编译 魏刘伟

量子计算机可以破解现在维护互联网安全的公钥加密方案

成熟的量子计算机仍然需要数年乃至数十年时间才会出现。但开发人员始终认为，其杀手级应用程序能在互联网和其他地方解码加密信息，无论是国家机密还是个人信息。这种可能性激励了密码学家。最近在加州圣巴巴拉举行的一次会议上，他们将讨论20多个加密信息的方案，即使量子计算机也无法将其破解。

此次研讨会是美国国家标准与技术研究所（NIST）推动制定所谓后量子密码学标准的一个努力。这多年的努力听起来可能为时过早和极端，因为这样的量子计算机可能永远不会出现。但密码学家表示，现在是做好准备的时候了，尤其是因为现在任何人都可以记录敏感通信，然后再对它们进行解密。荷兰艾恩德霍芬科技大学的密码学家坦贾·兰格（Tanja Lange）说：“如果等到量子计算机出现就太迟了，没有后量子密码学的每一天都会遭受数据泄露。”

高达数千亿美元的电子商务都依赖于被称为公钥加密术的这种易受攻击的方案。它们是基于“陷阱门”来计算的，之所以称之为陷阱门，是因为它们更易于正向计算而非逆向。接收者Alice提供数字公钥和秘方，发送者Bob用它来对消息进行加密。窃听者Eve不可能轻易逆转Bob的计算来发现这条信息。然而，Alice还生成了秘密私钥，它在数学上与公共密钥相关，这有助于她通过像Bob那样的计算来解读信息。

例如，在一个名为RSA的流行公钥方案中，Bob通过将数字信息本身乘以Alice指定的数字来倍增该数字信息。他将结果除以公钥（这是由两个素数相乘而产生的巨大数字）并将余数发送给Alice。为了重建消息，Alice将余数乘以不同的数字——该数字是她的私钥——并除以公钥。就这样！Bob的原始信息出现了。这就好像Alice告诉Bob如何模糊密码锁的设置：通过将刻度盘向前转许多次，知道如何将刻度盘向前转以恢复原来的设置。Eve只能努力弄清楚要把拨号盘拨回去多远。

RSA还说明了量子计算机构成的威胁。如果Eve能够将公钥分解为其素数组成，她就可以窃取私钥并破解密码。计算大量数字对于传统计算机来说很难，但对于量子计算机来说会更容易，正如麻省理工学院数学家彼得·肖尔（Peter Shor）在1994年所展示的那样。运行肖氏算法的量子计算机也可以击败新的公钥方案，因为它擅长于在重复的除法和取余数的操作中找到模式。

为了应对这一风险，密码专家正在开发不易受攻击的陷阱门算法。许多人依赖于被称为格的几何结构，即类似于晶体中重复的三维原子图案的点阵，但它们有数百或数千个维度。格由一组箭头或向量定义，这些箭头或向量以不同的组合进行添加而形成模式。对于相同的格，其起初可以由短的、几乎垂直的、易于处理的矢量组成，也可以由长的、几乎平行的、很难处理的矢量组成。这些方案中，Alice的私钥是简单的格基础，而她的公

在钥是定义相同模式的混乱密钥。为了将每个信息比特传递给Alice，Bob可以向她发送多维空间中点的坐标，该坐标在接近格的点来表示0，在距格点较远的地方表示1。通过使用杂乱无章的公钥，即使是量子计算机也无法帮助Eve搞清楚这个点离格有多近。然而，Alice可以很容易做到这一点，因为她持有简单的私钥。“格密码学是非常活跃的领域，因为它是如此的多功能。”德国达姆施塔特技术大学的计算机科学家尼娜·宾德尔（Nina Bindel）说。

一些研究人员正在研究更古老的算法。假设您想要在互联网上传输一串字符，但是担心一些0和1可能会在不经意间翻转。您可以通过使用有冗余的较长字符串来防止这一点，而这些冗余可以用来更正错误。这样的纠错码可以用由0和1组成的网格或矩阵来表示，在20世纪70年代，密码学家证明了它们可以加密信息。

在这种方案中，Alice的私钥是纠错矩阵，而她的公钥是它的加扰版本。Bob的信息是比特字符串，他将公共矩阵应用于该字符串以获得不同的字符串。他翻转几个随机的比特以获得好的度量，并将结果发送给Alice。即使Eve知道Bob的杂乱无章的矩阵，也无法撤销他的动作。但是，有了更清晰的矩阵（为了纠正翻转部分而设计），Alice就能做到。兰格说，纠错方案已经进行了比格更多的测试，即使Eve有一台量子计算机，他也可以应对。多数后量子算法比现有标准需要更大的密钥或更多的

大计算时间。荷兰拉德堡德大学的密码学家西蒙娜·萨马德吉斯卡（Simona Samardjiska）和他的同事正在开发一种基于二次方程的灵活的小密钥方案，它可能更适合于数字签名而不是发送秘密信息。

就像任何公开密钥系统一样，没有证据表明后量子方案是不可破解的，甚至在传统的计算机上也是如此。因此，微软公司的密码学家布莱恩·拉麦克奇亚（Brian LaMacchia）表示，新算法不会取代现有的算法，而是很可能与它们一起运行

NIST的数学家达斯汀·穆迪（Dustin Moody）说，最快于2022年，NIST就可以将加密和数字签名的两种或三种算法标准化。他表示，该机构希望有选择。穆迪说：“如果发现一些新的攻击破坏了所有的格，我们仍有一些东西可以依靠。” NIST为联邦政府设定了标准，但“世界上很多国家都使用NIST标准化的加密技术。”CloudFlare是加州旧金山的一家互联网安全和性能公司，为2 000万的企业及客户提供服务。该公司已经开始在网络浏览器中试用其中的一些算法。但Cloudflare的应用密码学家尼克·沙利文（Nick Sullivan）说，对其全面的采用将需要数年时间。

拉麦克奇亚说，在过去的30年里，他在密码学方面经历了4到5次重大变化，包括10年前从RSA转向与数学相关但更安全的接任者。“这个在性质上是不同的，这要复杂得多。”通过难以察觉的方式，加密用户——也就是说几乎每个人——将会知道这一变化进展顺利。