量子计算可以破解RSA加密算法了吗?

发布时间:2023-07-10

  答:RSA加密算法是第一个比较完善的公钥密码算法,自1977年被提出以来,至今仍被广泛使用于Email的数据加密、HTTPS 加密连接、网络数字交易和数字签名中,对现代生活有着广泛且深远的影响。RSA加密算法的安全性基础是大数的质因数分解这一困难任务。例如,对于3216487和5613787这两个质数,计算它们的乘积18,056,672,906,269很容易。然而,反过来分解18,056,672,906,269得到3216487和5613787这两个质因数就困难得多了。而破解RSA-2048就相当于分解一个2048位的大数,这一任务的计算量大到什么程度呢?就算是用最快的超级计算机花费等同于地球年龄(46亿年)的时间都无法得到结果!而RSA的安全性正是依赖于此。

  不过,量子计算将撼动RSA安全性的基石,甚至会对现有的密码系统带来崩溃性的冲击。得益于量子叠加与量子纠缠所带来的并行特性,量子算法在某些问题上可以实现指数级的加速,从而求解经典计算机无法解决的问题。1994年提出的Shor算法就是可以对质因数分解实现指数级加速的量子算法。根据著名量子计算学者、现就职于谷歌量子计算团队的Craig Gidney教授的估计,通过Shor算法破解RSA-2048仅需耗时数个小时!

  然而,Shor算法的实现对量子系统的要求极高,无论是量子比特的数目、量子比特的稳定性以及门操作准确性的要求,都远远超过现阶段量子技术的水平。在Craig Gidney的估计中,破解RSA-2048需要2千万个物理比特,而目前可相干操纵的量子比特数仅仅为100个左右。按照量子计算的发展趋势,学术界普遍认为达到千万量级的量子比特数至少还需要15年以上的时间。尽管如此,已有众多国家关注未来的量子计算对网络安全的潜在威胁,并开始采取必要的部署以应对。

相关文章