2015级计算机 网络工程7班 梁格 20152100168
1.文章主要思想和工作：
摘要：
本文主要讨论后量子RSA。
首先，本文提出RSA参数
（1）密钥生成，加密，解密，签名和验证是可行的。
（2）所有已知的攻击都是不可行的，即使是高度可扩展的量子计算机也是如此。
其次，本文介绍了一种新的量子分解算法，它比Shor的算法快得多，比预量子分解算法快得多。
评价和比较后量子 RSA。
关键词：
后量子密码，RSA可扩展性，Shor算法，ECM，Grover算法，RSA再次成功
内容：
Shor算法的1994年出版引起了普遍的说法，定量计算机将会破坏密码学，或者至少是公钥密码学。然而，这些说法远远超出了Shor算法的实际限制，对量子密码分析的后续研究几乎没有缩小差距。量子计算机将杀死RSA和ECC，但不会杀死基于哈希的密码学，基于代码的密码学，基于格子的密码学或多元二次方程式密码学。传统的看法是Shor算法将RSA公钥考虑在内几乎和合法的RSA用户一样可以解密， 其实，今天在互联网上，所有已知的量子攻击算法在加密时都是不可行的，解密仍然可行。
本文的重点在于加快RSA的标准技术，当被推到极端时，用户的成本和攻击者的成本在合法之间造成更大的差距。具体而言，对于本文的RSA版本，攻击代价在使用成本上基本上是二次的。这些极端情况需要仔细分析量子因子分解算法。
本文还介绍了使用量子的GEECM（Grover plus EECM）计算机如下加速相同的EECM计算。与传统计算机的搜索算法相比，Grover算法在量子搜索算法上有二次方的提速。我们不确定Grover算法是否有实际意义，若有，则将密钥规模增大一倍即可保证安全。此外，指数级提速的搜索算法已经被证明不可能存在，故在量子时代对称密码算法和散列函数仍然是可用的。GEECM结果是后量子RSA参数选择的主要制约因素之一。
关于后量子因子分解，对于RSA的每个现代变体，包括本文中考虑的变体，已知的最好的攻击是分解算法。本节分析后整数分解的量子复杂度。有两个重要的分解算法类。 第一类由算法组成在寻找小素数方面特别快速。第二类由同余组合算法组成。
后量子RSA 3推导出一种新的算法来生成大批独立的均匀随机数，比任何已知算法更有效地生成这样的素数。RSA参数的初始实施结果很大，足以将所有已知的量子攻击推到2100 qubit操作以上。 这些结果包括成功完成后期量子RSA中最昂贵的操作，即生成1TB的公钥。
评估：后量子RSA不符合安全，老式的安全定义需要渐进的安全性多项式时间对手。 然而，后量子RSA似乎提供了一个合理的具体安全水平。
比较两个机制：三重加密与基于代码的密码学，基于格子的密码学和后量子对于负担得起的用户，RSA提供了更高的信心。后量子RSA在允许后量子加密，签名和更高级的加密功能方面也是非常不寻常的。
建议：我们的批量生成算法建议，以帮助减少能源消费和保护环境，RSA的所有用户 - 包括用户，传统的预量子RSA应该将他们的密钥生成计算委托给NIST或另一个可信的第三方。允许用户更频繁地生成新的RSA密钥并擦除旧的RSA密钥，限制了重点盗窃的危害。
2、相关技术
量子加密技术：是量子通信科学发展的成果之一，又被称为量子密钥分发（QuantumKey Distribution）。依靠包括叠加态、量子纠缠和不确定性等在内的量子物理独特性质，量子密钥分发技术能够实现传统密钥交换的功能，并且可以检测和规避窃听企图。但这种方案也面临着包括成本和传播距离等因素在内的限制，而且攻击者还能够通过拒绝服务式攻击严重削弱量子密钥分发的效率。尽管上述两种加密手段目前都处于发展阶段，依然存在诸多问题需要解决，但是未来量子安全措施必然包含这些解决方案的恰当组合。
后量子密码：后量子密码（post-quantumcryptography），又被称为抗量子密码（quantum-resistantcryptography），是被认为能够抵抗量子计算机攻击的密码体制。此类加密技术的开发采取传统方式，即基于特定数学领域的困难问题，通过研究开发算法使其在网络通信中得到应用，从而实现保护数据安全的目的。后量子密码的应用不依赖于任何量子理论现象，但其计算安全性据信可以抵御当前已知任何形式的量子攻击。尽管大数分解、离散对数等问题能够被量子计算机在合理的时间区间内解决，但是基于其他困难问题的密码体制依然能够对这种未来威胁形成足够防御能力。更为重要的是，它们还可以与当前网络系统实现较高程度的兼容，从而会减小当前密码系统向后量子密码迁移可能面临的阻力。
舒尔算法(Shor's algorithm)：以应用数学家彼得·舒尔(Peter Williston Shor)命名，针对整数分解问题的量子算法 (在量子计算机上面运作的算法)。
RSA可扩展性：很明显，后量子RSA公钥n需要相当大抵御第2节中描述的攻击。本节分析的可扩展性，可用于RSA密钥生成，加密，解密，签名生成和签名验证。在最初的RSA文件[43]中，e是一个随机数，有很多位作为n。拉宾在[42]建议，而不是使用一个小常数e，并说e = 2是“几百倍”。拉宾的加速因子增长为Θ（lg n），这对本文所考虑的大尺寸的n值尤其重要。
3、相关算法伪代码
Shor算法：
将暂存器初始化成x从0到Q − 1。所以这一个初始态是Q 个状态的叠加。
建立量子函式版本的f(x) ，并且应用于上面的叠加态, 得到 .这里仍旧是Q个状态的叠加。
对输入暂存器进行量子傅立叶变换。这个变换（操作于二的幂次--Q = 2q个叠加态上面） 使用一个Qth单位根例如将任意给定态的振幅平均分布在所有Q个态上。另一个方法是对于每个不同的x： 。由此得到最终状态： .这是一个远多过Q个状态的叠加态，但是远低过Q2个。虽然在和中有Q2项，但只要x0 和 x的值相同，态就可被提出来。令 为 Qth 的一个单位根，r 为 f 的周期，x0为一个产生相同 f(x) 的 x 的集里面的最小元素（我们已经有x0 < r），以及b在0到之间使得。那么则是复平面的一个单位向量（是一个单位根，r 和 y 是整数），而在最终状态下的系数则为 。这一求和的每一项代表一个获得相同结果的不同路径，而量子干涉发生。在单位向量几乎与复平面指向同一方向（要求指向正实数轴）时，干涉将是相长的。
进行测量。我们由输入寄存器取得结果y，由输出寄存器取得。 而既然f 是周期，对某对y和 进行测量的概率则由 给出。 分析显示这个概率越高，单位向量就越接近正实数轴，或者yr/Q就越接近一个整数。除非r是2的乘方，否则它不会是Q的因子。
对y/Q进行连分数展开来计算其近似值，并生成满足下列两个条件的c/r′： A: r′
检查f(x) = f(x + r′) 。 如果成功了，我们就完成了。
否则，以接近y左右的数值作为r的候选，或者说多取几个r′. 如果任何候选成功了，我们就完成了。
否则，回到第一步骤(也就是全部重新作一次)。
Grover算法：
RSA算法：
4、发展方向
除量子公钥密码外,后量子公钥密码都是基于不能转换成离散傅立叶变换的数学难题而建立,主要有以下几种类型。
(1)基于hash算法构造的Merkle型签名算法基于hash算法构造的签名体制,最经典的是Merkle hash树签名体制[6],由传统的hash函数和任意的一次性签名算法,共同构造出一个完全二叉树来实现数字签名。
(2) 基于编码的公钥算法基于编码理论构造的公钥体制,其理论基础是解码问题的困难性,即仅在已知生成矩阵的情况下,在码空间中寻找一个码字与已知码的Hamming距离最短。
(3) 基于格的公钥算法基于格的公钥密码是指在大维数的格上,基于最短向量问题(S V P)和最近向量问题(CVP)等数学难题而构造的公钥密码体制。
(4)基于多变量的公钥算法多变量公钥密码体制(M u l t i v a r i a t e-q u a d r a t i c-p o l y n o m i a l s P u b l i c K e y Cryptosystem,简称MQ或MPKC)是一大类各具特色的公钥密码算法的统称,也是近年来后量子公钥密码的研究热点。这类体制主要基于有限域上的多元二次多项式方程组的难解性。与RSA、DH、ECC相比,多变量公钥密码的安全性很难被证明等价于一个已知的可简单表述的数学难题,因而也被认为是很难找到相应量子攻击算法的难题,从而被看成具有抗量子计算的性能。
值得一提的是,除了上述几种公钥算法外,国内也由管海明、张焕国等在多变量体制的基础上自主提出了基于有理分式的公钥算法。3后量子公钥密码研究新的特点目前,国际上关于后量子公钥密码的研究趋势有以下几个明显的特点。一是研究步伐逐步加快。这从近几年召开的后量子密码会议可见一斑。2006年,在比利时的Leuven召开了第一届国际后量子密码学会议,2008年在美国的Cincinnati召开了第二届,2010年在德国的Darmstadt召开了第三届,基本上是两年一届。但今年,将在中国台北召开第四届,且以后将每年一届,时间节奏明显加快。二是更加注重相关基础研究。例如对近年提出的后量子算法的数学理论基础有了更多的探讨,加强了对算法的安全性分析,对与抗量子性能相关的量子复杂性理论的研究也越来越多。三是更加注重算法的有效性与可用性。因为可实用的量子计算机的问世已越来越迫近,可用性与效率都是无法回避的问题。四是各国政府的支持力度也越来越大。表面上看,后量子密码的研究属于学术领域,但背后往往有政府的参与,因为这是涉及未来若干年国家安全的重大学术问题 。
网友评论