• 欢迎访问举个栗子网站
  • 小说APP下载 xsz.tw 不带广告的小说站

举个栗子:美国国家安全局的“量子计算机”什么密码都能破?

日报 举个栗子 2年前 (2017-11-16) 268次浏览 0个评论 扫描二维码

举个栗子:美国国家安全局的“量子计算机”什么密码都能破?

流言说:斯诺登泄漏的文件显示,美国国家安全局(NSA)正在开发一个“量子计算机”,可以破解几乎任何类型的加密, 该项目是其总额为 7970 万美元的“穿透硬目标”项目的一部分,项目在马里兰大学帕克实验室运作。这种“量子计算机”能够帮助美国国安局破解任何类型的加密,包括银行、医疗、商业以及政府的密码。

回答:

假。量子计算机并不相当于一台能够做高速运算的经典的超级计算机。它的出现会威胁到当前的密码体系,同时我们也有足够的技术储备来维持我们的隐私,维护目前的秩序。

论证:

什么是量子计算机?量子计算机并不相当于一台能够做高速运算的经典的超级计算机。量子计算机能以高速度解决某些特定的问题,但却对别的问题无能为力。目前人们找到的高速度的量子算法大体有两类,一类是解决隐含子群问题的,比如因子分解问题、离散对数问题等,量子计算机在这些问题上有指数级的加速;另一类是 量子随机游走相关的,比如说 Grover 算法(在 O(sqrt(n))时间内搜索大小为 n 的数据库)等,量子计算机在这些问题上有多项式级的加速。还有一些比较奇怪的就不说了。在这些特定的问题上,量子计算机能迅速解决问题,但出了这个范围,目前它跟经典计算机没什么区别。

会威胁到当前的密码体系,但并非无所不能

量子计算机能解决的问题,是否会威胁到当前的密码体系呢?答案是的确会。目前的密码体系大体有两种:对称密码与非对称密码。AES 是前一种的例子,RSA 是后一种的例子。对称密码的话,Grover 算法能进行不小的加速,比如说 AES-128 的密钥空间是 2^128,通过构造适当的可以量子化的数据库黑盒子,Grover 算法能在大约 2^64 的时间内找到密钥,而经典计算机则需要大概 2^128 的时间。不过这个问题并不特别大,换用更长的密钥就可以了。问题在于非对称密码,量子计算机在很短的时间内破解。而偏偏这些算法特别重要,无论是银行转账、身份识别、在线浏览,很多都需要非对称算法来进行密钥分发与身份验证。举个例子,上 Gmail 时候会自动 SSL 加密,这个东西就是用 RSA 来做密钥分发的。

那么,一旦量子计算机做出来之后,是不是隐私就无处遁形呢?那倒不一定。

学界早就关注这个现象了,也提出了一些能解决这个问题的非对称密码体系,比如说基于格(lattice)的体系(比如 NTRU)、基于纠错码的体系(McEliece),还有基于多变量的体系。这些体系都不依赖于隐含子群问题,所以对量子计算机造成的威胁是免疫的。不过,这些体系各有各不太实用的地方,也有些弱点,所以目前没有很多人采用。不过一旦足够规模的量子计算机造出来了,我们也有足够的技术储备来维持我们的隐私,维护目前的秩序。


举个栗子 , 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权
转载请注明原文链接:举个栗子:美国国家安全局的“量子计算机”什么密码都能破?
喜欢 (0)
举个栗子
关于作者:
建筑工地上施工员,闲暇时弄个博客打发时间,
发表我的评论
取消评论
表情 贴图 加粗 删除线 居中 斜体 签到

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址