问：据美国国安局前雇员斯诺登曝光的文件称，美国国安局（NSA）正在研发一种用于破解密码的量子计算机。一旦研究成功，美国将可以破解全世界任何密码和加密算法。http://news.xinhuanet.com/world/2014-01/06/c_125961809.htm
2 L- L* d) h% S' X答：一句话摘要：& l1 q1 S- i! F2 [$ t
有影响，但是并非不可弥补。
2 o. X2 @. w- q8 H$ U6 A首先，量子计算机并不相当于一台能够做高速运算的经典的超级计算机。量子计算机能以高速度解决某些特定的问题，但却对别的问题无能为力。目前人们找到的高速度的量子算法大体有两类，一类是解决隐含子群问题的，比如因子分解问题、离散对数问题等，量子计算机在这些问题上有指数级的加速；另一类是 量子随机游走相关的，比如说Grover算法（在O(sqrt(n))时间内搜索大小为n的数据库）等，量子计算机在这些问题上有多项式级的加速。还有一些比较奇怪的就不说了。在这些特定的问题上，量子计算机能迅速解决问题，但出了这个范围，目前它跟经典计算机没什么区别。2 T6 t1 z" W7 Y5 s
然后，量子计算机能解决的问题，是否会威胁到当前的密码体系呢？答案是的确会。目前的密码体系大体有两种：对称密码与非对称密码。AES是前一种的例子，RSA是后一种的例子。对称密码的话，Grover算法能进行不小的加速，比如说AES-128的密钥空间是2^128，通过构造适当的可以量子化的数据库黑盒子，Grover算法能在大约2^64的时间内找到密钥，而经典计算机则需要大概2^128的时间。不过这个问题并不特别大，换用更长的密钥就可以了。问题在于非对称密码，无论是基于因子分解问题的RSA，还是基于椭圆曲线上离散对数的ElGamal，都可以用量子计算机在很短的时间内破解。而偏偏这些算法特别重要，无论是银行转账、身份识别、在线浏览，很多都需要非对称算法来进行密钥分发与身份验证。举个例子，上Gmail时候会自动SSL加密，这个东西就是用RSA来做密钥分发的。+ g+ U) z8 f9 t. Q. ]. ^4 G3 l
那么，一旦量子计算机做出来之后，是不是隐私就无处遁形呢？
/ s& t0 ]% A5 t! _6 }! G那倒不一定。7 l- M' B6 s5 r5 ^- r2 r
学界早就关注这个现象了，也提出了一些能解决这个问题的非对称密码体系，比如说基于格（lattice）的体系（比如NTRU）、基于纠错码的体系（McEliece），还有基于多变量的体系。这些体系都不依赖于隐含子群问题，所以对量子计算机造成的威胁是免疫的。不过，这些体系各有各不太实用的地方，也有些弱点，所以目前没有很多人采用。不过一旦足够规模的量子计算机造出来了，我们也有足够的技术储备来维持我们的隐私，维护目前的秩序。8 d8 e0 {5 Y* y+ _& E9 h
转载自 http://www.guokr.com/question/530973/ | 
|手机版|Archiver|
( 桂ICP备12001440号-3 )|网站地图
发表于 2025-5-17 08:53:54