当前位置:首页 >资讯 >秀尔算法是怎样破解RSA算法的?


RSA算法曾经是最可靠的算法,但秀尔算法结束了RSA算法的神话,值得一提的是,秀尔算法不是通过暴力破解找到最终密码,而是利用量子计算的并行性,可以快速分解公约数,从而打破RSA算法的基础(假设我们不能有效地分解已知的整数)。同时,秀尔算法表明,量子计算机可以有效地解决因数分解问题,因此足够大的量子计算机可以破解RSA。

RSA加密之所以曾经强大,是因为它很难对大整数进行因数分解。乘坐两个质量数字很容易,但很难找到一个大数字的质量因素。这是大量现代技术的依赖。RSA加密以其简洁性迅速流行起来。秀尔算法可以破解RSA,但它如何才能真正有效?如果我们快速找到以下周期函数的周期,我们可以破解RSA加密f(x)=m^x(modn)。

那么,秀尔算法到底是怎么工作的呢?可采用五个步骤:

第一步:

使用传统的最大公约数分解(gcd)算法,即辗转反侧。N是你需要尝试的因素,m是一个小于N的随机正整数。

如果gcd(m,N)=1,则继续。一旦你用gcd找到一个因素,你就可以得到一个非凡的因素,然后结束。

第二步:

找到周期P

mmodN,m^2modN,m^3modN。

这是使用量子计算的一步。

第三步:

如果周期P是奇数,回到第一步,选择另一个随机整数。如果没有,继续下一步。

第四步:

检验

1

如果成立,继续第五步;相反,回到第一步。

第五步:



2

解决一个非凡素因数N的值,然后你就可以破解RSA加密。

那么第二步是如何实现的呢?

让我们来看看周期P:

mmodN,m^2modN,m^3modN。

(因为这是一个指数函数,我们可以将一个复杂的质数转换为双曲正弦。

发现周期的过程取决于量子计算机同时计算多种状态的能力,即状态的叠加,因此我们可以找到方程周期。

我们需要这样做:

1.利用Hadamardgate创建量子叠加态。
2.量子转换使方程生效。
3.执行量子傅立叶变换。

与传统情况类似,经过这些转换后,一个测量值将产生一个相似的方程周期值(您可以获得峰值,就像傅立叶变换一样,准确性会更高)。使用量子傅立叶变换,我们可以解决相同的排序和因数问题。量子傅立叶变换可以让量子计算机进行相位估计(你的算子特征值的近似值)。

当你完成量子部分(第二步)时,你可以检查周期的有效性,然后使用另一个传统的最大公约数算法来获得钥匙的质量因素。

有趣的是,因为这项技术不是为了找到所有潜在的质因数,而是为了找到潜在的周期,你不必尝试大量的随机数,直到你找到一个成功的质因数N。如果P是一个奇数,那么你必须回到第一步,这里。

3

K是一个不同于N的质因素。因此,即使你加倍密钥长度(N),搜索质因数也不会放缓。RSA不安全。同样,加倍密钥长度也不能帮助您抵御量子计算的汹涌袭击,确保安全。

破解RSA-2048(2048-bit)的密钥可能需要10亿年的时间,而量子计算机只需100秒就能完成。

量子傅立叶变换被用来建立量子线,使秀尔算法的物理实现成为量子计算机最简单的任务之一。

秀尔算法中只有一个步骤需要在量子计算机上完成,其他步骤可以在普通超级计算机上完成。量子计算机将结果返回到超级计算机,以继续完成计算过程。量子计算机可能永远不会单独存在,而是一直与超级计算机合作执行任务。通过这种合作,它们可以破解RSA密钥。

最后,小编想说的是,随着技术的不断进步,世界和社会也在不断发展。为了不被进步的社会淘汰,我们也应该不断学习。虽然听起来有点鸡汤,但所有最终的好处都是我们自己(严肃的脸)来做这碗老鸡汤。