the biggest threat to modern encryption
在前面的里我们讲到，在加密与解密的大战中，RSA加密法取得了暂时的胜利。那它有没有破解法呢？
坦率的说，现在还没有，但理论上存在破解的可能。那就是量子计算机。
具体来说，要破解RSA加密法，需要量子计算机和配套的量子算法，也就是硬件、软件两部分都要有。
现在我们已经有了软件，硬件还远不成熟。
1
功能齐备的量子计算机到底有多强，我们可以和传统计算机对比来看。
不论哪种计算机都是对存储单元中的数据进行操作，比如这个存储单元可以存放N位数据，又因为每个数据都只能是0和1，所以N位数据的存储单元里，数据一共有2^N种可能。
传统计算机里，任何一个时刻只能对这么多种可能性中的一个进行操作，当N比较小的时候，工作量还是可以应付的；当N是几千的时候，完成这个工作量需要的时间，就可能会超过全宇宙的历史。
量子计算机中，存储的数据总是处于0和1的叠加态，你可以理解成所有出现0和1的可能性融汇在一起，所以一个量子存储单位在某一时刻，是可以同时存储2^N个数据的。
比如说这个存储单元有300位，那么存储的数据就是2^300比特，这个数字就比全宇宙的原子数还多了。
传统计算机要对这么多可能性一个一个操作，而量子计算机运算一次，就是同时对2^300个状态进行操作。所以它的一次运算的效果相当2^300台传统计算机，算力大大增加。
而RSA加密法我们之前也说过，它之所以坚固就是因为要分解一个大数N的因子，这个问题的计算量随N的增加以指数形式增加。
但量子计算机一次操作就相当于传统计算机很多次操作，所以如果能设计出一些连续的操作来分解质数的话，即使是一个超大数，用量子计算机也能很快的找出他的因数。
这样，RSA加密法就被破解了。
2
那这种操作设计出来了吗？
已经设计出来了，叫做“Shor算法”。它是1994年设计出来的，专门用来分解因数。
一共有7个步骤，其中计算量最大的第4步，是必须在量子计算机中运行的。其他步骤，可以在传统计算机中操作。
Shor 算法：
1. 选择任意数字a＜N
2. 计算gcd（a, N）。这一步是求a和N的最大公约数。
3. 若gcd(a,N) ≠ 1，则我们找到了因数，运算结束。
4. 否则，找到最小的r，使ax(mod N) = ax+r (mod N)，这一步就是需要在量子计算机里实现的步骤。（mod是模运算，根据欧拉定理r一定存在）
5. 若r是奇数，回到第一步。
6. 若ar /2 ≡ -1 (mod N)，回到第一步。
7. gcd(ar/2+1,N)和gcd(ar/2-1,N) 分別是N的因数。
任务完成。
这是一个专门针对量子计算机设计的算法，它的功能就是专门用来分解因数。
Shor算法的作者休尔当年在贝尔实验室做出这个成果后，大致估量了一下算力，他说速度至少可以比传统计算机快百万倍。
其实这个差距，是和N的大小选取密切相关的。
以当前传统计算机做过的分解因数中最大的数为例，这个数是768位的，传统计算机和量子计算机要计算它，大约是100万年和1秒的差距。
在休尔之后，还是贝尔实验室，洛夫·格鲁夫（Lov Grover）又设计出一种新算法，也是利用量子计算机。专门针对美国国家标准的加密法DES，结果在当前典型的应用级别下，4分钟就把所有可能的钥匙试遍，密码随之告破。
3
听起来量子计算机好像很强大，很多谈到量子计算机的新闻都会把它夸张到无以复加的程度，好像传统密码遇到它马上碎成渣。
但我要告诉你，这种观点是不对的。
量子计算机做到的只是大幅削减计算量，其实它还是要花时间计算的，量子计算机很强，但并不是任意一种密码遇到它都秒破。
具体来说，针对计算机一个任务所需的时间，有一个评估方法。我找了一张描述不同任务下随着数字n增加，计算时间随之增加的趋势对比图。
通过这张图能够看到——
传统计算机里，n稍稍增大，计算量的增加的曲线几乎是垂直上升的；而量子计算机里，计算总量增加的趋势虽然平缓很多，但还是一个陡峭的斜坡。
所以我们现在不用那么担心量子计算机出现后，当前的密码保护会瞬间碎成渣渣。不会这样的。
只要我们愿意把那个大数n再加长很多，比如从300位增加到3000位，保密强度还是足够应付初期量子计算机破解的。
4
刚刚说的一切都是软件方面，下面说说硬件。
其实这才是最大的障碍，因为到现在为止，还没有一个通用的量子计算机出现，可靠的专用量子计算机也没有。
有人听说过D-Wave这个机器，而且也可能知道武器商洛克希德·马丁2011年就订购过一台128个量子位的量子计算机，但实际上那台D-Wave虽然确实利用量子理论计算，但它只能运行一种特殊的算法，叫做“量子退火算法”。
所以说，D-WAVE只能算一个实验性质的计算器，洛克希德·马丁买它更多是一种尝试。
后来D-Wave还开发出了二代，谷歌和NASA都买过一台，这台改进多了，是512位的，甚至可以进行一部分传统运算。但是运算速度大约跟1998年前的计算机的速度差不多，只是在进行特定的量子算法时才比传统电脑快很多倍。
在媒体宣传中，这个很多倍甚至被夸张到1亿倍。但实际情况，远没有这么乐观。
为什么这么多顶级公司都搞不定量子计算机呢？
主要原因就是，量子实在太容易变了。我们现在还没有特别好的手段，能控制量子按照算法的步骤运转。
最经典的例子，就是“光的双缝干涉实验”。
这个实验是这样的：
一个光源射向一堵障碍物，障碍物上有两道缝可以透光。当尺寸合适的时候，你会发现在两道缝后面的幕布上看到一道明一道暗、一道明一道暗的条纹。
但是，请注意我下面这段话——当人们好奇心大增，想弄清从光源发出来的光的每一个光子，到底通过了哪个缝才射到了幕布的话，我们可以在缝前安放一个侦测光子的设备。
但如果我们这么做了，在双缝后面的幕布上明暗条纹就消失了，取而代之的是两道集中的光斑。
其实这就反映了一个结果——我们的测量行为，会影响到量子的状态。
我们一旦在缝隙前设置了装置，去判断入射光到底通过了哪道缝，本应该保持的明暗条纹状态就消失了。
如果那些明暗条纹代表着量子计算机运算到某一时刻的量子位的正确状态的话，那设计者要尽最大可能维持住这种状态。但实际上，这种状态会被很多因素干扰。
在宏观世界里，任何一种物质都有可能和量子发生互动改变他们的状态，比如说温度。所以那些量子计算机，都需要在零下200多摄氏度的极低温才能正常工作。
6
有人还担心，手中的密码什么时候会受到量子计算机的威胁？
简单回答：至少10年之内不用担心。
在2016年，美国国家科技委员会曾经发布过《发展量子信息科学》的报告，量子计算机部分的规划是这样的：
未来5年会有几十个量子位的原型机诞生……，通用量子计算机是一项长期的挑战，至少需要10年。因为它的硬件、算法、编程语言、编译器都严重缺失，每一项都是巨大的困难。
但有人认为：总有一天量子计算机会成熟吧，那时候我们现在的密码不就都完了吗？要不要设置一些规定，限制量子计算机的研究，或者限制交易这类计算机？
这个问题的答案是——
由新技术导致的问题，最好的解决方案不是禁令，而是更新技术。因为新老技术的较量，可以让人们在应不应该禁用这个问题上，达到自然平衡。
什么意思呢？
比如哪天真的出现了一种新技术可以破解RSA加密法，政府部门也真的可以利用它监听消息。但新技术刚刚诞生的时候，天然就有各种各样的问题，比如使用不便、成本极高……
这些困难自然就约束了想使用它的人，所以这种破解法即使管用，也只能在那些确实非常重要的案件上用，而没法用来监控全体人民上。所以技术门槛高，就天然约束了政府的行为。
那你说，万一哪天这项技术成熟了，政府滥用了怎么办？比如说，通用量子计算机只有几十万块钱一台的时候，那怎么办？
答案是，还可以用更新的技术解决这个问题，让双方达到平衡。
因为当这项技术已经廉价到普及的地步，其实也就意味着下一代对抗上一代的更新的技术，马上就要诞生了。你看，问题就是这样靠新技术解决的。整个过程，客观上一直在刺激人们提高技术水平。
其实这个规律，自从16世纪现代科学诞生后一直是这样。小到加密、解密，大到环境、人口，最终的接盘侠都是科学家和新技术。
好，这节就到这里。
下节我们要讲这门课的最后一项技术——量子加密。
这或许是量子计算机也无法破解的终极加密法。
