量子计算机真的可以破解任何密码吗?

据美国国安局前雇员斯诺登曝光的文件称,美国国安局(NSA)正在研发一种用于破解密码的量子计算机。一旦研究成功,美国将可以破解全世界任何密码和加密算法。

斯诺登曝美国安局正研发量子计算机 可破译任何密码

推荐  (0) | 11人关注关注
10个答案
87 0

方弦科学松鼠会成员,信息学硕士生

2014-01-06 18:22

一句话摘要:有影响,但是并非不可弥补。

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

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

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

那倒不一定。

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

4 0

eggcar古典吉他控,通信工程专业

2014-01-07 15:48

扶额......这也算新闻么......量子计算机的研究什么时候停过......
我要说中科院在这方面处于世界前沿是不是又有人跳出来骂TG了......
BTW求媒体和某些不够硬的科幻作家别再胡吹量子计算机了......就算是外行我也知道量子计算机只是在特定算法上具有优势,很多经典问题都很难找到量子算法,什么未来的超级计算机,快醒醒快醒醒......

0 0

yy2080Fringe科学博士

2016-08-16 19:30

量子计算机能不能破解量子密码?

0 0

量子计算机不只是矛,他也能当盾。

0 0

呃,量子计算机应该只是在速度上有优势。

还要有解密程序吧。



7 8

量子计算机真的造出来了,在破译密码方面当然有用,但是在生成密码方面一样也有出力。用量子计算机的强大计算能力生成的密码系统,估计量子计算机自己也够呛能解开。就像现在计算机的能力让以前的密码不再都那么可靠,但计算机同时也搞出了很多让自己解不开的密码方式。

0 1

额,这学期学了量子信息与量子计算这门课,简单的说一下吧。是否能破解所有的密码,在现在看来不太现实。
量子计算机知识基于量子力学运算的,区别于普通计算机主要就是相干态,另外纠缠对在其中起着很大作用。94年Shor提出了能用于破解RSA秘钥的算法,计算复杂度在对数量级,而RSA在经典计算机上几乎可以认为不可解。
但是这只是一个例子,毕竟用量子的方式来思考对于习惯了日常世界的我们来说不容易,设计算法并要求超越经典计算很难,但不代表没有。
总的来说,现在量子计算机还不具备破解所有密码的能力,也没人证明量子计算机会比经典计算机更有效,虽然在部分问题上确实有效。

0 2

量子计算机的特点在于,一个量子位它可以代表0的同时也代表1。

高位数的量子计算机的能力是,它代表000001,同时它也是48392,同时它还是XY2D3K,同时它还是LnM8K3…………在一瞬间,它可以代表你的任意密码组合。

相对于普通计算机一个一个尝试密码,量子计算机可以直接挑出正确的那个,就完成破解了。

唯一能给量子计算机增加难度的地方就是,让它挑出正确的密码后,仍然无法快速验证那个密码就是正确的。

这点就是最WTF的地方。如何让计算机在获得正确密码的前提下,很难验证,同时又不对用户造成困扰。

现在有好多算法(包括google最新资助的防量子算法)说能抵抗量子计算机解密,但都说是增加难度,而没有人在数学上证明XX算法是量子计算机无法计算的。

13 21

positron理论物理、天文爱好者

2014-01-06 17:06

密码的破解一般都是理论上可行,而实际上不可能。意思是,理论上,你可以破解某个密码,但是,即使使用当前最强大的超级计算机,也需要(n>2)年的计算时间。

所以,如果能发明一种计算机,其计算效率是当前计算机的倍甚至更多,那么自然可以破解密码。

查看更多

添加回答

登录 后回答问题,你也可以用以下帐号直接登录

相关问答

关于我们 加入果壳 媒体报道 帮助中心 果壳活动 家长监控 免责声明 联系我们 移动版 移动应用

©果壳网    京ICP证100430号    京网文[2018] 6282-492号    新出发京零字东150005号     京公网安备11010502007133号

违法和不良信息举报邮箱:jubao@guokr.com    举报电话:18612934101    网上有害信息举报专区    儿童色情信息举报专区