量子安全加密的崎岖之路（上）

RSA 不对称加密和 Diffie-Hellman 密钥交换是互联网的安全之盾，但在 Shor 揭示了量子计算强大的分解能力之后，安全主宰的未来地位似乎岌岌可危，密码学家开始争相研究量子计算无法破解的加密算法。Quanta 的这篇文章讲述了现代版的猫捉老鼠游戏简史。

8月11日，NSA 网站发布了一份措辞含糊的声明，称将更换政府和军事数据的加密方式以抵御尚未明确的量子计算机攻击。

“现在很清楚了，当前的互联网安全手段及其背后的加密方式无法抵御量子计算机所带来的新的计算能力的攻击，” NSA 发言人在邮件中确认了网站的这一变动：“NSA 保护关键的国家安全系统的使命要求我们要预料到这样的进展。”

大家的普遍预测是，一度被视为遥不可及、仅具备理论可能性的量子计算机将在 5 到 30年 内实现。这种设备可利用量子物理的概率论破解包括 NSA 秘密、银行记录、邮箱密码在内的全球大部分的 “安全” 数据。意识到这一威胁的密码学家正在争相开发既高效又可 “抵御量子攻击” 的加密方法。

基于晶格数学—即多维的重复点阵的那些被认为是其中最有希望的一种。信息隐藏在具有数百维度的晶格背后，要想破解，必须知道秘密的路由。

不过去年10月，英国的电子监管机构政府通讯总部（GCHQ）在网上发表了一篇神秘的论文，质疑了某些晶格类加密法的安全性。论文暗示，在长达 10年 的不断追求加密效率的道路上，已经有一些漏洞暴露出来。由于加密者简化了作为基础的晶格，导致加密模式更容易受到攻击。

根据 GCHQ 的声明，去年两个团队的破译专家花了 1年 的时间去确定哪些晶格加密方法是可以被量子计算机破解的，哪些是安全的。

荷兰莱顿大学的 Ronald Cramer 把这称为是加解密者之间现代版的猫捉老鼠游戏。解密者没有动静的时候，为了提高效率，加密者会适当放宽一些安全基础。但是一旦宽松稍微过度，解密者就有机可乘，现在就是这种情况。

公开的秘密

每次访问以 “HTTPS” 开头的网站时，你收发的都是加密过的数据。安全互联网交易正是由 1970年 代的革命性发明—公钥加密促成的。在此之前，密码术结伴上就是政府和间谍之间的游戏；交换信息的双方（如间谍和接头人）必须事先约定好密钥（key）才能进行通信（比如简单的 “凯撒密码” 就是把字母按照双方约定进行统一移位）。而公钥加密（不对称加密）让每个人都可以向别人发送只有接接收者才能破解的加密信息，这个过程中双方无需事先协定任何东西，且不惧监听。

公钥加密的特点是加密容易解密难。比方说，计算机计算两个素数的乘积是很容易的，如 34,141 x 81,749 = 2,790,992,609，但是反过来要把 2,790,992,609 这样的大数分解成原来的那两个素数却要花很长的时间。密码学家因此就利用这两个素数做出了公钥加密法，生成一对密钥，其中一个作为 “公钥” 发布给别人，后者利用这个 “公钥” 对信息进行加密；另一把则是前者自己持有的 “私钥”—公钥加密的信息只有私钥才能解密。

1970年 代末诞生的两种有效的加密方法至今仍用得最为广泛：一个是基于素因子问题的 RSA（用发明者 Ron Rivest、Adi Shamir 与 Leonard Adleman 的名字命名），以及基于离散对数问题的 Diffie-Hellman 密钥交换。尽管这两种算法在合理时间范围内不可能有解尚未经过实际证明，但至今无人想出有效的计算办法。

“随着时间的流逝，大家开始树立起对某些问题的难度的信心，因为那么多人绞尽脑汁想要破解都失败了，” 布朗大学的数学家和密码学家 Jill Pipher 这样评价。

现有的这些算法下，要想计算出典型长度的公钥素因子往往需要数年的时间。因此，RSA 和 Diffie-Hellman 密钥交换成为了互联网之盾，给人以安全主宰的味道。

不过结果证明，这种安全性也有保鲜期。

Shor 算法

1994年，有关计算机难以破解部分数学问题的假设被打破，AT&T 一位名叫 Peter Shor 的研究人员发现了量子计算机的理论解密能力。

在一般计算机里，信息通常是用位（要么是 0 或 1 两种状态）来存储的，而计算机的计算能力与位数成正比。然而量子计算机里面信息的存储单位是量子比特（qubit），它的特点是 0 态和 1 态可以同时并存（比方说量子比特可以是亚原子粒子的形式，它可以同时进行顺时针或逆时针旋转）。由于带有许多量子比特的系统可以任何可能的独立状态的所有可能组合形式存在，因此量子计算机的计算能力会随着量子比特的数量而指数增长。

加密黑箱的新设计

这似乎让量子计算机成为比传统计算机更加强大的问题解决者。然而，要想真正挖掘量子计算的潜能，需要找到一个算法来捕捉到它的并发状态，这样与正确答案相对应的系统状态才会最终出现。这件事实现起来没那么简单，自 1980年 代量子计算机构思出现以来的 10 多年时间里，尚未出现过有希望的算法，这个领域也慢慢失去了活力。“实际上没人关注，” MIT 的量子计算理论家 Seth Lloyd 说。

不过 1994年 一切都有了改观—Shor（现在 MIT）发明了足以有效计算素因子和离散对数的量子计算机算法，在理论上 RSA 加密和 Diffie-Hellman 密钥交换同时变得弱不禁风。Lloyd 说，在量子计算有了一个杀手应用（可称之为 quapp）之后，对量子计算的兴趣开始爆发。

在 Shor 算法揭示了量子计算的超级计算能力之后，全球的研究者开始争相开发量子计算机。与此同时，密码学家也在争分夺秒设计量子计算无法破解的加密方法。“很长一段时间我们都没有头绪，” Georgia Institute of Technology 的密码学家 Chris Peikert 说：“不过晶格似乎是一个很好的基础。”

未完待续......

本文编译自：quantamagazine.org

“看完这篇还不够？如果你也在创业，并且希望自己的项目被报道，请戳这里告诉我们！”