哈希游戏- 哈希游戏平台- 哈希游戏官方网站1994年，美国麻省理工学院的彼得·肖尔（Peter Shor）发表了一篇论文，题为《量子计算机上的质因数分解和离散对数的多项式时间算法》（Polynomial Time Algorithms for Prime Factorisation and Discrete Logarithms on a Quantum Computer）。这篇论文被认为是一剂催化剂，催生了一场延续至今的建造量子计算机的竞赛。本质上说，通过使用量子平行处理，肖尔算法(Shor’s Algorithm)使量子计算机上的大整数的因式分解比在经典计算中使用已知最快的算法还要快出很多。更精确地说，肖尔算法差不多可以在多项式时间内因式分解N比特整数，与此相比，在经典计算中最有效的算法（称作广义数域筛法，缩写为GNFS）则差不多需要指数时间。这就预示着RSA方法——它的安全性极其依赖于经典计算机因式分解大数N所需的时间——会立即变得不堪一击，同样面临崩溃的还有互联网上公钥密码的主体部分。

　　确定这个函数的周期正是量子计算的性质发挥作用的地方，特别是准确地引入量子平行处理这一概念。我们使用两个量子存储寄存器——第一个被放置在所有a（a的范围是从0到q，其中q是2的指数倍，并且满足N2 q 2N2）的可能值的叠加态上。注意，这个寄存器必须有足够的量子比特来表示这个大小的整数，比如说，如果N是一个2048比特数（RSA模数的典型大小），那我们就需要大约4000个量子比特。在第一个寄存器中，会用到以N为模的函数xa，而结果会被存储在第二个寄存器中（在这一步中，我们利用了量子平行处理的性质）。

　　当肖尔算法成为密码学（公钥）最直接的威胁时，其他一些已经发展起来的算法也对对称式加密产生冲击。特别是格罗弗算法(Grover’s Algorithm)，这种算法使得量子计算机的使用者只使用0.758 N0.5次运算就可以在N项列表中发现特定的一项。这又是一个量子计算允许的与直觉完全相反却又强有力的结果。来看看为什么。想象一下，我们有10000个盒子，并且随机地把一个物品藏在其中一个盒子里。如果我们让某个人去找到这个物品，那么他们将最多不得不打开所有10000个盒子才能确定找到这个物品（这个物品也许正好被藏在他们决定最后一个打开的盒子里）。平均来说，我们可能不得不打开盒子数量的一半才能找到被藏起来的物品，也就是找5000次。然而，使用格罗弗算法，我们实际上可以在0.758√N次运算中就找到结果。在这个例子中，这意味着我们找75.8次（0.758 * √10000）就可以找到这个物品！

　　这种算法的力量与穷举搜索攻击有关。正如我们可以回想起来的，穷举搜索攻击就是检查每一个密钥的单值来看看那个密钥是否解码了一条信息。使用格罗弗算法，我们可以极大地加速穷举搜索攻击的过程——例如对于一个长度为128比特的密钥来说，使用格罗弗算法的话，一次穷举搜索攻击可以在√2128=264次内完成。同样，一台可以运行格罗弗算法的量子计算机将意味着某些标准的密钥长度需要增加，特别是AES 128比特不再被认为是安全的，而是需要AES 256比特的密钥。

　　对以上的一个解释也许是，实际上我们并不处在建造一台有能力打破目前公钥密码学的量子计算机的中期阶段（例如2-5年）内。执行肖尔算法所需的量子比特的数量，远远超过今天我们制造的最强大的量子计算机的能力，而且肖尔算法大规模的可靠的应用还没有被展示出来。今天，我们并不清楚诸如量子比特的退相干，和管理噪声以减少量子系统中的差错等面临的挑战能否被解决。正因为如此，在短期或者中期内建造这样一台可规模化的扩展的量子计算机似乎不太现实。

　　然而，放眼较长的时间（5-20年），忽视量子计算机对于目前的现代密码学标准的威胁将会是错误的。正如美国国家标准与技术研究院的描述：“一些人预测在接下来的20年左右，足够规模的量子计算机会被制造出来，基本上可以打破目前使用中的所有公钥方案。在历史上，我们花了差不多20年时间去配置现代公钥密码基础架构。因此，不论我们能否准确估计量子计算时代到来的时间，我们都必须现在开始准备我们的信息安全系统，使之能够对抗量子计算。”

　　后量子密码学以数学方法为基础定义了一系列新的密码学标准，其中主要是针对公钥密码学。这些方法很强大，足以抵挡来自量子计算机的攻击。美国国家标准与技术研究院已经开始着手实施一项计划来发展这些新的标准。他们将通过一个阶段性的招标流程，收集学术界和工业界对新的密码算法的建议。2018年4月，这个机构组织的一次会议，讨论了第一阶段提交的建议。然而，标准草案可能在2022-2024年才会被提出。下面介绍一些有潜力的新方法。

　　基于格点的密码 (Lattice Based Cryptography)——格点是N维空间中带有周期性结构的点集，它和N维的有斑点图案的壁纸有些相似。某些数学上的格点问题被认为解决起来非常困难，比如最短向量问题（Shortest Vector Problem），就是给定一个特定的基矢，然后找出一些最短的非零向量。这样的格点问题已经被用来作为构建一些密码学方法的基础。一项正在研究的方法叫做NTRU，它于1996年被提出，使用12881比特的密钥去提供标准的128比特密钥长度具有的安全性。在第一阶段中，众多提交给美国国家标准与技术研究院的方案都是以NTRU的变体（例如NTRU Prime）为基础，这些方法具有在效率和安全性之间提供一种优质平衡的潜力。

　　基于编码的密码 (Code Based Cryptography)——这类方法是以纠错码为基础的加密系统，最早于1978年被提出，目前已经发展起来，其中最著名的是麦克利斯（McEliece）算法。这些算法以解码线性代码的困难为基础，算法中的私钥与一个纠错码相联系，公钥与加扰版本相联系。这些类型的加密方案的密钥长度往往会长一些，因此令人不免对它们的效率有些担忧（如果密钥长度太长，它的储存和交换会占用相当多的资源）。

　　以上的这些方法依赖于一个相似的方法——它们都使用被认为是非常困难的数学问题作为自身安全性的基础（与RSA类似）。把量子计算的发展先放到一边，如果一个数学家能够发展一种新的数学方法或者技术，可以解决这些“困难的问题”中的一个，比如说大整数N的因式分解，那基于这个问题的加密系统的安全性就只能让步。2017年2月，著名的以色列密码学家阿迪·沙米尔（Adi Shamir）表示：“在我所担心的事情中，量子计算机并不是排在首位的，我认为更有可能发生的是RSA因为一次数学攻击而崩溃”。因式分解是RSA的基础，这个问题至少在几个世纪里被很多伟大的数学家广泛研究过，不过仍然没有被解决。

　　P&M协议使用海森堡不确定性原理——对一个量子态的测量将会以某种方式改变那个状态。这个概念就是BB84协议背后的思想，该协议由查尔斯·本内特（Charles Bennett）和吉列斯·布德（Gilles Brassard）于1984年提出。在这个系统里，我们用单光子的极化来传输信息比特，其中接受者和发送者使用极化的方向来确定被传输的比特是0还是1。这种方法的安全性来自于这样一个事实，即如果一个窃听者拦截并且试着看被传输的光子的数值，他们就会以某种方式干扰光子的模式，而这种干扰在消息的传输之后是可以被测量到的。我们可以用这种方法建立共享密钥，因而解决了最早给公钥密码学以灵感的这个难题。

　　理论上这样一个基于量子原理的系统是安全的，然而实际操作上，量子密钥分配的物理实现曾经被破坏过，也就是在发送者或者接受者不知情的情况下密钥被拦截过。同时还要注意，在实践中，光子在最佳光缆上的实际物理传输也会不可避免地持续向系统中引入误差，因此在现实中，一个估计的误码率必须和实际的误码率相比较，以确定是否有传输达不到标准从而提供了较低的安全水平。从技术上讲，发射单光子是很有挑战性的，因此我们使用发射多光子的激光，但这也使这个系统容易遭受光子数分束（PNS）攻击的影响。在光子可以传输的距离上同样也存在限制——使用标准光缆的线千米，在这个范围内量子密钥分配的方法是可行的。目前的数据传输速率也很低，在比较短的距离上，每秒几百比特是有代表性的速率。不过，即便存在这些挑战，一些实用的、具有商业可行性的量子密钥分配系统还是已经成功落地，现在一些机构（例如一些瑞士及中国的银行）正在用这样的系统进行密钥交换。

　　量子密钥分配机制的第二种类型是基于纠缠协议，由阿图尔·埃克特（Artur Ekert）最早在1991年提出。在这种被称为E91的方法中，一个单独的源发射一对发生量子纠缠的物体，例如一对极化的光子，比如给爱丽丝和鲍勃，其中一个给爱丽丝，另一个给鲍勃，而他们两个人在地理位置上是分开的。由于纠缠的性质，如果爱丽丝和鲍勃都以某种方式测量这个极化的话，光子会得到相反的结果（例如，爱丽丝测到的是+1，鲍勃测到的是-1）。通过彼此结果相反的光子对中的一个光子，爱丽丝和鲍勃就可以得到一个共享密钥。

　　纠缠作为一种量子密钥分配的实验方法一直是研究的热点。值得注意的是，2017年6月，由中国科学技术大学的潘建伟领导的团队成功演示了光子之间的纠缠。这些光子由在轨道上的卫星发射，而被位于地面上的基站测量，卫星与基站之间相距1200千米。虽然每600万个从卫星发射的光子中只有1个能够被基站探测到，目前实现量子密钥分配还不足够，但是这个实验受人瞩目之处在于它证明了“鬼魅般的超距作用”——爱因斯坦如此描述量子纠缠。这个团队未来的研究计划包括通过更长的光子流分发实际的量子密钥到中国的基站。

　　人类不同个体之间希望保持信息的私密这一愿望，同语言本身一样古老，而这个愿望所面临的最根本的挑战也存在了相同长的时间。两个人如何商定一个安全的沟通方法，比如说给物品以特别的词语或代号，或者某种共享密钥，使得双方可以彼此理解对方的意思，但是第三方却做不到？伴随着数字技术对我们生活的方方面面的侵入，这些问题之于我们自身安全感的重要性无疑在增加——现在我们想使我们的隐私不被我们的各类连接设备触及几乎不可能，因此正确地保护信息的安全就变得非常重要。

　　现代密码学已经发展出有效、安全的标准和方法，来促进人与人之间对信息的共享，但是这种共享仍然有其脆弱性。一方面，尽管量子计算机的发展似乎在短期内可能性较低，但是却也使重新考虑和加强这些标准成为必要。快速完成美国国家标准与技术研究院提出的旨在发展安全的后加密算法的计划是非常重要的，从而安全地升级目前网络协议的安全性。另一方面，继续信赖困难的数学问题作为加密系统的基础，限制了我们对这些系统充满十足的信心——因为当明天我们醒来的时候，一位聪明的数学家可能已经很好地解决了这些问题。