量子安全加密的崎岖之路（上）
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说：“不过晶格似乎是一个很好的基础。”
