Shor算法提出近三十年，为何RSA仍未被终结？

光子盒研究院出品

1977年，来自麻省理工大学的Ron Rivest、Adi Shamirh和Len Adleman开发出RSA公钥加密算法，这一算法名字则来自他们三人名字首字母的组合。

RSA公钥加密算法是第一个能同时用于加密和数字签名的算法，这一算法基于一个十分简单的数论事实：将两个大素数相乘十分容易，但对其乘积进行因式分解却极其困难，因此可以将乘积公开作为加密密钥。

RSA是目前最有影响力的公钥加密算法，它能够抵抗到目前为止已知的所有密码攻击，已被ISO推荐为公钥数据加密标准。目前该加密方式广泛用于网上银行、数字签名、通讯领域等场合。

由于RSA加密算法严重依赖于大整数素因数分解的计算量以及耗费的时间，它的核心设计就是通过提高破解成本来提高安全性，因此任何能够提高计算速度的方法都会威胁到这种常用加密算法的安全性。

而撼动这一加密算法地位的Shor算法发明者Peter Shor，1977年还在加利福尼亚读高中。

Peter Shor（2017）

RSA加密的终结者

Peter Shor自幼就对数学十分感兴趣，他的数学天赋在学生时代早早就展露无遗。在高中，他在1977年美国数学奥林匹克竞赛中获得了第三名。高中毕业后，他紧接着又参加了在南斯拉夫举行的国际数学奥林匹克竞赛，并获得了银牌。

随后，他进入加州理工大学，攻读数学专业。大学毕业后，他进入麻省理工大学继续深造，并在那里获得应用数学博士学位，师承F. Thomson Leighton门下。在被授予博士学位后，他在加州大学伯克利分校做了一年的博士后研究员，然后接受了贝尔实验室的邀约。

而在贝尔实验室的这段时间，他研发出了个人生中最为重要的2个成果，一个是Shor算法，一个是Shor量子纠错码。

这2个成果，一个让占据大多数互联网应用的加密方法瞬间失效，一个则是让量子计算机的实现成为可能。

Shor算法是Shor于1994年提出的一种大数质因子分解的量子多项式算法。这一算法将NP问题变为了P问题,利用数论中的一些定理将大数因子分解转化为求某个函数的周期,由于在量子环境下可以提高傅立叶变换效率,从而可以对大数质因子进行化简。

Shor算法一经问世，就让物理界和计算机界为之一震。

RSA算法的安全性取决于大整数的分解，因为长期以来,人们普遍认为,大数质因子分解不存在经典的多项式算法,或者说是有效算法。然而，Shor算法的功能可以在多项式步骤内进行大数质因子分解，所以Shor算法在理论上破解了RSA公钥密码。

对每秒可执行10⁶次基本运算的计算机而言,分解664位大整数要用1000年的时间,但采用Shor算法的量子计算,分解664位大整数的时间只有大约44秒,而分解1024位的大整数也仅需要约2分钟的时间。

量子计算采用Shor算法可以在几分钟内实现1000位数的因子分解,这将使现有公开密钥RSA体系无密可保。

Shor算法由两部分组成。第一部分是将因式分解问题简化为周期问题，这种方法可以在经典计算机上实现；第二部分是用量子算法解决周期问题。

它的基本思想是：首先利用量子并行性特点通过进一步计算获得所有的函数值，并利用测量函数得到相关联的函数自变量的叠加态，然后对其进行快速傅里叶变换（Quantum fast Fourier transformation）。

Shor算法程序流程图

一旦可以运行Shor算法的量子计算机成功建造出来,那么现行的RSA公钥密码体制将毫无安全性可言。

1995年，Shor发布了关于实现量子计算机需克服的一个关键问题的论文。量子计算机的实现依赖于量子态，但量子态对环境要求极为苛刻，它极其不稳定且十分容易受到干扰，从而导致信息丢失。

Shor则提出了容错量子计算和量子纠错码，从而让量子计算的实现更靠近现实一步。

量子纠错是量子计算中用来保护量子信息不受退相干和其他量子噪声的影响。经典计算机的纠错采用冗余校验方法，即将信息多次存储，如果这些副本后来被发现不一致，则进行多数表决。由于不可克隆定理，复制量子信息是不可能的，这个给量子纠错带来了阻碍。

但是，将一个量子比特的信息传播到多个处于纠缠态的量子比特是可能的。Shor首先发现了这种方法，他通过将一个量子比特的信息存储到处于纠缠态的九个量子比特上，由此形成了量子纠错码的方法。

Shor提出的九位编码并不是最有效的量子纠错码，目前被证明最有效的纠一位错的编码方案是利用5个量子比特编码1个量子比特来完成。

Shor这一方法的发现，让量子计算机从难以实现到嘈杂中型量子（NISQ）计算机，下一步则是通往终极目标——容错量子通用计算机。

后量子加密的反击

随着Shor算法的提出，包括Diffie-Hellman、RSA和ECC等非对称密码算法已经从理论上被证明彻底丧失了安全性。因为公钥密码算法安全性依赖的数学问题可以被高效的量子算法所解决。

这让各国政府官员如坐针毡，一旦量子计算实现，高保密级的通讯直接裸露在大众眼中，国家安全保障如同虚设，由此也引发了抵抗量子算法的后量子密码的研究。

基于此，2015年1月，欧盟启动后量子密码算法SAFECRYPTO应用项目，在对称加密、对称授权、公钥加密以及公钥签名系统领域都提出了相关标准化建议。

同年8月，美国国家安全局（NSA）公开宣布由于面临量子计算的威胁，其计划将联邦政府各部门目前使用的ECC/RSA算法体系向后量子算法进行迁移。

量子计算分析并不能有效求解所有的数学难题，仍有一些计算复杂性问题尚未找到高效的量子计算攻击方法，这是研究新密码技术的突破口。

抵抗量子算法有2种方法，一种是增加数字密钥的长度，使计算所需搜索的排列数目显著增加；另一种则是从量子算法不擅长求解的一类困难问题入手，实现构造密码算法，就可以在一定程度上有效抵抗未来量子计算机的攻击。

目前，后量子密码主要包括以下4种类型：基于格(Lattice-based)、基于编码(Code-based)、基于多变量(Multivariate-based)、基于哈希(Hash-based)。

基于格的密码体制

基于格的密码体制是指在大维数的格上，基于最短向量问题（SVP）和最近向量问题（CVP）等数学难题而构造的密码体制。

基于编码的密码体制

基于编码的密码体制是以编码理论中的数论难题为基础而设计的，这类困难问题包括了随机线性编码解码问题、有界编码解码问题以及列表解码问题等。目前，量子计算的分析能力尚未能攻破此类型算法。

基于多变量的密码体制

多变量公钥密码体制（MPKC）核心是求解有限域上随机产生的多变量非线性多项式方程组的困难问题，其运算只需要在较小的有限域上完成，所以基于多变量密码的效率较高。

至今量子算法中的Shor算法和Grover算法都无法对这类方程进行有效攻击，因此，MPKC被认为能够有效抵抗量子计算攻击的密码体制。

基于Hash的密码体制

区别于传统公钥密码体制，基于Hash的密码体制核心是运用了Hash算法的抗碰撞性，由传统的Hash函数，以及任意的一次性签名算法构造并实现数字签名，能够保障信息安全和不可否认性。

在最近Shor接受《自然》杂志的访谈中，就后量子加密，他认为用一个安全的后量子密码系统取代RSA的只是时间问题，解决方法及操作路径已知，但唯一的问题是：在当下量子计算高速发展的情况下，只是不清楚能否及时完成。

另外，他预言第一个破解RSA的人要么是美国国家安全局(NSA)，要么是其他一些大型组织。

在量子计算与后量子加密的博弈上，主流观点有两种。一种是乐观派，他们认为Shor算法破解RSA加密的数据在短时间内无法实现；另一种则是悲观派。他们认为量子计算势不可挡，需要抓紧时间研发。如果掉队，小到邮件，大到一些高优先级加密文件甚至对国家安全都会构成巨大的风险。

Shor算法的拦路虎

Shor算法是量子计算中的最有实际应用价值、最重要的一种算法，但它并不完美。

这是因为Shor算法是一种随机算法,它不能保证每次运算都能得到正确的结果。它只能使得得到正确结果的概率无限接近于1。为了保证程序的有效性,在3次不能得到正确结果的时候,程序将中断一次,等待重新输入大数。

目前关于优化Shor算法的主流方法是，限定任意选取的与大数N互质的a的范围。

Shor算法的关键在于求出大数N的余因子函数的周期r,而求周期很大程度上取决于随机选择的数a。如果对a做一个限定得到偶周期,则能够大大提高Shor算法分解的成功率。

从Shor算法的提出到现在,已经实现在量子计算机上从15到21的大数质因子分解。

1996年，美国科学家Juan Pablo Paz在一个有干扰和损耗的量子电路上用了27量子比特成功分解了15。同时他指出对于分解大数N，需要的量子比特数应是n=5L+7（其中L取大于等于log₂N的最小正整数）。这项工作的开展给实际操作中实现Shor量子算法提供了很好的借鉴。

2001年，美国IBM公司和斯坦福大学合作，利用核磁共振技术演示了Shor算法对15进行分解的实验，但该实验不能显示其量子属性，也无法扩展到更多的比特，限制了进一步的研究。

2004年，美国赫尔辛基理工大学材料物理实验室的Jula J. Vartiainen利用约瑟夫森电荷量子比特实现了Shor算法。他把Shor算法的量子电路分成了一系列两量子比特和三量子比特的量子门不仅加速了Shor算法的实现，而且在此基础上通过数值优化的方法成功完成了对N=21分解的物理实现，这是目前在量子计算机上所能够实现Shor算法分解最大的数。

除了在量子计算机上运行Shor算法，一些研究者也在模拟的量子计算机上运行这一算法，分解的数更大更多位。

2007年，法国理论物理研究实验室在研究Shor算法的缺陷（量子比特间残余耦合造成）所产生的影响时，通过编写Quantware库并调用该库，用30个量子比特实现了N=943的分解。

2013年，美国卫斯理大学的Y. S. Nan等，在一个128核的传统计算机集群上构建了一个虚拟的运行Shor算法的量子计算机，该虚拟量子计算机被分为在两种模式下实现Shor算法。

Shor算法的核心部分包括模幂运算部分ME和求周期运算部分PF。这两种模式也就是基于Shor算法划分的：第一种模式称之为PF（周期查找）模式即只有周期查找部分没有Shor算法的模幂运算部分（这部分用传统模幂运算结果来代替），第二种模式称之为满Shor算法模式包括模幂运算和周期查找两部分。

在第一种模式下运行的虚拟量子计算机可以最多控制39量子比特来实现N=55793的分解，在第二种模式下，可以最多实现N=57的分解。

虽然Shor算法的实现已经有所突破，但它的实际应用仍处于起步阶段，对公钥密码的攻击目前仍构不成威胁，能分解大数和求解椭圆曲线离散对数的能力还很有限。

这是因为分解一个大数N，需要的量子比特数应是n=5L+7（其中L取大于等于log₂N的最小正整数），目前量子计算机所含的量子比特数仍然较少，只能实现Shor算法的运行，尚不能实现对现今使用的1024位RSA和163位的ECC的完全攻击。

所以要想能够在多项式时间规模内实现Shor算法对公钥密码的攻击，则必须依赖于量子比特数千位以上的通用量子计算机。

相关阅读：

-End-

1930年秋，第六届索尔维会议在布鲁塞尔召开。早有准备的爱因斯坦在会上向玻尔提出了他的著名的思想实验——“光子盒”，公众号名称正源于此。