量子计算机采用麻省理工学院数学教授Peter Shor的肖氏算法来破解RSA，DH/DSA和椭圆曲线签名ECC所需要的破解资源评估 Quantum Attack Resource Estimate: Using Shor’s Algorithm to Break RSA vs DH/DSA VS ECC
作者：Tommaso Gagliardoni 作者单位：瑞士库德尔斯基量子安全咨询有限公司 日期：2021年8月24号 译者：QUASAR
过去几年直到现在，全球大多数的网络安全专家逐渐已经开始意识到：量子计算机的飞速蓬勃发展，对现代公钥密码学算法构成了巨大的威胁。
尤其是麻省理工学院数学教授Peter Shor在1994年发明的Shor's Algorithm，即用于量子计算机的一种量子加速算法：肖氏算法。
肖氏算法，这种量子加速算法，针对许多公钥密码学的数学算法如RSA，ECDSA，为量子计算机破解攻击提供了理论支持。
但是，量子计算机对网络通讯，和互联网安全，国家安全等各方面的影响，到底有多大？有没有可以看见的路线图，或大致的时间点，会发生什么较确切的，什么程度的攻击，甚至破解？
尤其重要的是：究竟有哪些公钥密码学算法，相比其他算法，会更容易受到量子计算机的攻击破解的威胁？
在这篇文章中，我们将根据最近的，最新的一些技术进展较深入地研究，分析，和评估一下量子计算机攻击或破解几种主要的公钥密码学算法所需要的攻击资源。
特别是，我们将看到在量子计算机上运行Peter Shor的肖氏算法，来破解和攻击同一种公钥密码学算法的不同密钥大小，不同的经典安全等级所需要的基本资源成本，我们把这些计算攻击破解所需要的资源，与当下的量子计算机的现状联系起来。
我们将看到：RSA将如何在2027年6月25日之前被破解！（当我开玩笑咯！）
计算假设
首先，我们要从纯粹经典的角度，回顾一下现代公钥密码学算法中，所使用的各种计算难度假设的区别。
实际上，这是一个非常复杂的话题。为简单起见，这篇文章中，我们只考虑以下三点：
整数分解问题（IFP）：给定一个整数N，它是两个大素数p和q的乘积，找到p和q。 有限域离散对数问题（DLP）：给定一个场的大乘法子群的生成器g，和该子群中的一个元素y，找到x，使g^x=y。 椭圆曲线离散对数问题(ECDLP)：给定一条定义在字段\mathbb{F}上的非星形椭圆曲线\mathcal{E}，并给定一个点G，该点在\mathcal{E}的点的加性群中，产生一个大的循环子群，并给定该子群上的另一个点P，找出一个整数k，使P=kG。
实际上，在量子安全的背景下考虑这三个问题显然是过于简化了。因为在实际应用中，大多数现有公钥密码学算法，并不直接基于上述简单假设。
例如，RSA的安全性不是基于IFP，而是基于一个类似的难度假设，称为 "RSA假设"，已知它可以被还原为IFP，但反之则不知道。这意味着 "破解RSA "的难度，最多和解决IFP一样，但也可能比这更容易，这至今并没有定论。只是到目前为止，还没有数学家想出更简单的方向，或者可行的方法。大多数基于离散对数问题的方案，同样地也是如此，例如Diffie-Hellman密钥交换，或ECDSA椭圆曲线签名。
然而，从实际的角度来看，破解这些公钥密码学算法的大部分密码分析工作，都基本集中在首先解决数学方程式的问题上。
所以，这也是我们在研究量子计算机破解公钥密码学算法，所需要的量子计算机的资源评估时，可以依据这种前提理论假设。
那么，对于RSA，或ECDSA算法，应该有多大的算法密钥，才可以用来评估量子计算机破解这些算法所需要的资源呢？
1， 所需的安全参数；
2， 针对最基础要求的安全问题，可以采取评估的攻击效率。
对于因式分解，和有限域离散对数而言，情况也是类似的：计算这两个问题的最好已知算法，分别是数域筛和指数微积分法，有一个类似的渐进的亚指数复杂度。对于n位模子，可以大致近似为\mathcal{O}\left( 2^{9\sqrt[3]{n}}\right) 。
这意味着：对于RSA，和DH等算法而言，要想获得n比特的安全性，需要指数级地，极大量地增加密钥大小来保证RSA，和DH等算法的基本安全：比如，2048比特的公钥，能用于112比特的安全；而3072比特的公钥，才能用于128比特的安全；更有甚者，7680比特的公钥，才能用于192比特的安全。
而对于ECDLP问题，已知最好的一般解决算法，如Pollard's Rho，对于n位曲线的指数复杂度，大约为mathcal{O}\left(2^\frac{n}{2}\right)，其缺乏已知的亚指数攻击算法，这基本上也是椭圆曲线算法ECC迄今为止具有吸引力的原因，因为在相同的比特安全水平下，所产生的密钥可以有更小的尺寸，相应地增加带宽和效率。这一点在下面的表格中进行了总结。
经典比特安全 RSA, DH, DSA 公钥大小 椭圆曲线算法公钥大小 112 2048 224 128 3072 256 192 7680 384 表1：相同的比特安全所需要的公钥大小
从上表可见：椭圆曲线算法ECC更容易受到量子计算破解的威胁。
Peter Shor的肖氏算法：
考察Peter Shor的肖氏算法前，我们来考量一下最新的量子计算机情况。假设有这种情况，即大型可扩展的量子计算机已经制造成功，并且一切就绪，完全可用，能够运行复杂的各种量子算法。
众所周知，1994年Peter Shor教授发明的肖氏算法可在多项式时间内进行整数分解。稍深入分析一下：
首先，肖氏算法实际上由两部分组成：一个纯粹的量子部分，即量子快速傅里叶变换简称QFFT；和一个纯粹的经典前后处理阶段。稍微复杂一点的角度来看，对于n位输入整数，QFFT的多项式时间复杂度大约为\mathcal{O}\left（n^3\right）。鉴于经典部分具有类似的复杂性，我们只考虑相关量子计算或量子破解的复杂性。
对于n位整数的因式分解，运行肖氏算法的量子计算机，显然需要至少n个逻辑量子存储器来表示整数，但它也需要额外计算所需的量子寄存容器，使总的量子比特数增加。
鉴于量子比特数显然可被视为量子计算机发起攻击破解的限制性资源，目前已经提出了能够运行QFFT的电路版本，以最小化量子破解所需要的量子比特数量。目前，这些电路的技术水准所需要的量子比特数量，大约是输入的整数的比特大小的两倍。
与经典情况一样，在量子计算机运行的情况下，IFP和DLP的情况也是类似的。肖氏算法也可以被推而广之，运用到攻击或破解离散对数上，QFFT可以用来解决n位模子上的DLP，使用大约2n个逻辑量子比特，并且，同样地具有相同的多项式时间复杂度，大约是mathcal{O}left(n^3\right)。
量子计算机攻击破解椭圆曲线算法的情况稍微有些不同。同样地，QFFT也可以用来有效地解决椭圆曲线离散对数算法ECDLP，大致上是立方时间，但由于算法的经典部分需要将曲线嵌入到一个更大的数组中，其所需要的量子比特数量，大约是曲线场比特大小的十倍
根据以上情况，我们可能会认为椭圆曲线算法ECC，看起来比RSA或DSA，能更有效地对抗量子计算机的破解或攻击？因为量子计算机利用肖氏算法，发动攻击需要更多的量子比特。
但是，如果仔细分析就可以发现：实际情况恰恰相反!
这是因为椭圆曲线算法ECC有一个很大的特点，优点或缺点即椭圆曲线算法ECC的密钥很小，因为即使最强的经典计算攻击的方法，也是很低效的。但是！这种在经典计算机攻击下很低效的差异，在量子计算机攻击的情况下，却完全没有差异。
因为量子计算机攻击的时间复杂度都差不多。而且，由于RSA和离散对数算法就已需要使用RSA和离散对数算法本身很大的密钥来抵御经典攻击！
所以对RSA和离散对数算法而言，量子计算机攻击所需的量子比特数，实际上比量子攻击椭圆曲线算法ECC更大！这一点，我们在下表中总结一下：
相对的经典安全比特 攻击RSA，DSA等算法所需最少的逻辑量子比特数 攻击ECDSA和类似的椭圆曲线算法所需的最少逻辑量子比特数 112 4098 2042 128 6146 2330 192 15362 3484 表2：量子计算机攻击或破解各种算法所需的最少逻辑量子比特数及对应的经典安全等级
正如上表所示，随安全等级参数的增加，量子计算机破解或攻击RSA，DSA等算法，所需要的逻辑量子比特数，比攻击相同的经典安全等级的椭圆曲线算法ECC，ECDLP等，所需要的逻辑量子比特数增长得更快。
造成这样的原因是因为经典攻击RSA这类密钥大小很大需要更多的逻辑量子比特，即需要更多的逻辑量子比特在攻击破解RSA这类算法时，将这些量子比特运用在经典计算方面，也因为如此，RSA等算法相对椭圆算法ECC等，更能抵御量子计算机的破解或攻击。
当然，这绝不应该被解释为RSA算法，在量子计算机破解或攻击下是安全的。到目前为止，椭圆曲线算法ECC显然比RSA算法更容易被量子计算机破解，考虑到当前可用于量子计算机的逻辑量子比特数一直在快速上升，显然椭圆曲线算法ECC会比其他算法更早地，更快地被量子计算机破解。
量子计算机发动攻击所需要的计算资源评估
对各种算法发起破解或攻击，需要多少计算资源，这种评估比前述理论计算要稍微更复杂一点，需要更深入地挖掘。大致上，量子计算是由几个 "层 "组成：
算法层：量子计算机可以利用的更高效的算法，才会发动更高效的量子破解。到目前为止，正如前文所述，在没有比肖氏算法更高效的量子加速算法发明之前，我们暂时只考虑肖氏算法的QFFT算法。
电路层：对于量子计算机而言，同一种量子算法，如攻击ECC，RSA等算法的肖氏算法，或攻击哈希函数的格罗夫算法，可以在量子计算机的各种不同的电路层，以不同的电路方式实现，从而使用不同的量子门，在宽度即可以使用的逻辑量子比特数，和深度即逻辑量子比特稳定运行的时间这两者之间，不同的电路层设计，必须进行权衡，从而形成不同的应用逻辑量子比特的电路层。这些不同种类不同设计的电路层负责将运行诸如肖氏算法，格罗夫算法等不同的量子算法，这些各种不同的电路层组件被称为量子编译器。量子编译器的各种不同技术路线的飞速进展可以让人们找到那种独特的电路层设计，可以进行最有效的攻击。
逻辑层：逻辑层是量子计算机的纠错的，可以达到完美的、理想的、逻辑运行的，这些逻辑量子比特和电路操作的门。一个逻辑量子比特是通过将一些低级的、有噪声的、物理量子比特 "组合 "在一起的纠错结构来实现的。这方面最常用的方法是所谓的 "表代码"，它是一个由物理量子比特组成的方形网格，每隔一定时间进行纠错。这些时间上的纠错周期被称为 "表周期"，目前表周期能做到1mus到1ms之间，但在不久将来，200ns的目标是合理的。对量子计算机所使用的量子纠错率的提高，和纠错周期改进，可以为量子计算机破解这些算法带来更好的破解攻击效果。
物理层：物理层主要是量子计算机可以表现出的量子效应应用的基本物理单元，能帮助提高性能，或去除被视为 "噪音、杂音 "的量子比特。改进量子计算机的物理层，改进物理量子比特的可产生比率，可操作性，减少这些物理层的基础噪声，能使量子计算机有更好的整体性能
显然，以上量子计算机在算法层，电路层，逻辑层，物理层的任何改进，都将能促进量子计算机采用肖氏算法等这类量子计算算法来针对椭圆曲线算法ECC，或者RSA进行计算，或破解攻击效率的提高，以及促使攻击所需要的量子资源的减少。
因此，评估必要的资源量，需针对以上基本的四种层来评估，这种评估是比较困难的。但无论如何，最近几年，还是有些机构的学者和大学教授，对“量子攻击所需要的资源”这个话题有了一些新的研究。
首先，我们必须认识到，量子计算机对这些公钥密码学算法发动攻击破解，其所需要的量子比特数量，可能并不是限制性因素。本文上节的估计值，是考虑到量子计算机破解所需要的最小逻辑量子比特数量的下限，请注意是下限，但这并不是一个能被普遍接受的，必要攻击资源的衡量标准。
事实上，还有更好的方法。如果我们考虑从最底层的物理量子比特到算法层的全部实现堆栈，我们会发现某些常见的基本量子门比其他门更昂贵。泡利门通常是 "经济划算的 "，因为泡利门较容易快速实现，而陀佛利门（Toffoli Gates）则很难实现。事实上，陀佛利门的实现因为是如此之难，以至于作为一个第一考量的近似值，我们可以简单地忽略其他所有的量子门，而只计算陀佛利门的数量，作为运行量子算法的复杂性的衡量标准。
陀佛利门（Toffoli Gates）数的复杂度恰恰反映了这点：一个量子加速算法的陀佛利门数的复杂度越高，能够成功地建造一个能够运行这种陀佛利门的量子计算机，就会越困难。
鉴于上述情况，量子编译器通常可在一种模式下运行，量子编译器的电路层并不去优化逻辑量子比特的数量，而是去优化陀佛利门的数量。
这会带来一个副效用：量子计算机所需要的物理量子比特数大量增加，这是因为从物理量子比特，转换到可供量子计算机计算的逻辑量子比特，这种转换需要陀佛利门，这同时也增加了量子计算机需要的整体运行时间。
如果某个陀佛利门，只在某个量子位上，只使用一次，这也是一种浪费，而一旦有效实现陀佛利门后，应尽可能地重复使用它们。
因此，另一个很有用的指标或概念，是所谓的 "陀佛利深度Toffoli depth"，这种概念考虑了一个复杂度事实，即一个电路可以用 "层 "来描述，其中许多陀佛利门，可以在不同的物理量子比特上去并行使用。
如果能构建优化陀佛利门，或陀佛利深度更好的电路，最终也许可能会造成，相比原本需要“量子攻击的量子比特数最小值”较少数的逻辑层而言，要需要更多的逻辑层来构建优化这些陀佛利门，但这种构建优化陀佛利门所需的更多的逻辑层，会导致整体上更有效的攻击，因为它最大限度地减少了现实世界的资源，比如时间，和实施攻击所需要的成本。
最近，在量子密码分析方面的工作采用了这种方法，也有新的研究成果发表。
依据以上，下表列出了两种不同情况下的量子攻击资源评估：目前现实的基础物理量子比特的基础噪声误差为10^{-3}的情况，这种情况可以由目前最先进的超导量子比特实现，或者更乐观的10^{-5}的误差率的情况，大多数专家学者基本认为这种更乐观的误差率的情况，应该可以在未来短期内实现。值得注意的是：与之前的表格相比，逻辑量子比特的最小数量增加了，因为如前所述，最新的量子优化结果，目的在于最小化所需要的陀佛利门，和陀佛利深度，而不是电路层。
此外，量子计算机发动攻击破解所需要的时间，很大程度上取决于基础的量子加速算法单次运行的失败率，而失败率本身又取决于纠错机制所达到的纯粹程度，而这种程度又取决于表代码中使用的物理量子比特的数量。
事实证明，在所有当前可评估的情况下，量子破解所使用的物理量子比特的数量，和运行量子攻击所需的时间之间，存在一个比例，而且这种比例是相当恒定的。
所以，我们引入了一个概念，用这个概念来衡量量子计算机破解各种公钥密码学算法，所需要的量子资源的衡量标准：24小时内的百万量子比特，MQD。这是在表周期（"量子钟"）为200ns（5MHz），每次测量的错误率为{10}^{-3}或{10}^{-5}的情况下，在24小时内运行攻击所需的物理量子比特数量（以百万为单位）。。
算法 所需最小逻辑量子比特数 24小时内的百万量子比特MegaQubitsDay RSA-2048 6190 1.17 RSA-3072 9288 4.03 RSA-7680 23239 86.5 ECDSA-256 2619 7.43 ECDSA-384 3901 10.0 ECDSA-512 5273 15.6
表3: 量子计算机破解所需要的资源评估：在每表周期200ns，物理量子位为10^-3的噪声率。
算法 所需最小逻辑量子比特数 24小时内的百万量子比特MegaQubitsDay RSA-2048 6190 0.34 RSA-3072 9288 1.14 RSA-7680 23239 18.9 ECDSA-256 2619 0.89 ECDSA-384 3901 1.00 ECDSA-512 5273 1.56
表4: 量子计算机破解所需要的资源评估：在每表周期200ns，物理量子位为10^-5的噪声率。
请注意：按照MQD概念评估，有一个非常有趣的事实即：对于较低安全等级，比如RSA-3072和ECDSA-256而言，量子计算机破解或攻击RSA，实际上比攻击椭圆曲线算法ECC的成本低。这是最新的量子计算机在运用肖氏算法后，经过优化后的结果。然而随着安全等级的增加，按照MQD概念而言，攻击RSA算法所需要的量子资源在飞速增加，而量子计算机破解攻击椭圆曲线算法ECC则变得相对容易得多。
结论:
针对“在量子计算机利用Peter Shor的肖氏算法，来破解攻击公钥密码学算法如RSA，DSA，ECC等等所需要的破解资源评估”，对这个课题最新的研究成果已经很明显阐述了“公钥密码学算法在量子计算机不断提高的性能面前有多脆弱。”
过去传统的观点，即 "椭圆曲线算法ECC相比RSA和离散对数算法而言，更容易受到量子计算机的破解攻击 "仍然是正确的。
但在经过更严谨的概念锚定，和更深层的理论阐述，量子计算机破解在未来的可能实践中，量子安全的分界点已经转移到大约160位的经典安全之上来考量了，对于128位的经典安全等级，量子安全的差异并不是那么相关。这是转移是一个研究上的量子安全等级考量，这种转移主要是由最近的，最新的对Peter Shor的肖氏算法的各种优化得出的。进一步的研究结果肯定可以更准确的评估。
但显而易见的是，只要有足够多的物理量子比特，所有这些第二代公钥密码学算法那，无论是RSA签名，DSA算法，还是椭圆曲线签名算法ECC，都可以被量子计算机在几小时内破解。