数十年来，全世界都清楚RSA加密系统的日子屈指可数。一旦量子计算变得实用（估计还需3到20年甚至更久），它所提供的基础安全性将彻底崩溃。新的研究揭示了一种利用经典计算的新方法，可以将当前RSA的安全级别降低到一个令人无法接受的低门槛。
从眼前来看，这一发现几乎不构成实际威胁，除了少数边缘情况。即便将该攻击应用于已被弃用的1024位密钥，该方法所需的计算量也远超绝大多数人能承受的范围——除非是拥有巨额资源的国家或企业。目前广泛使用的RSA实现方式仍然是安全的。
尽管如此，这项研究依然让密码学界感到意外，因为它引入了签名伪造这一全新的破解RSA密钥的方式，而不需要进行因数分解。同样重要的是，这种新方法将所需的计算资源降低了数个数量级。
不再遥不可及
“如果这一结果经得起同行评审，那确实是一次概念上的突破，”密码学专家、Allurity创新负责人卡斯滕·诺尔在采访中表示。“RSA的破解难度一直被认为等同于对大整数进行因数分解的难度。而这位研究者提出，实际上可以在不破解密钥的情况下破解RSA。”
加州大学圣地亚哥分校教授、论文主要作者纳迪亚·赫宁格进一步解释道：
密码学界一直认为，计算有效RSA数字签名的唯一方式，是先通过因数分解求出私钥，然后用私钥来计算签名。对于1024位RSA，这被认为代价极其高昂，尽管如果拥有大型科技公司或美国国家安全局那样的计算资源，理论上是可行的——单个密钥需要耗费数千万美元的计算时间。而对于2048位RSA，此前被认为完全无法实现。
赫宁格及其团队研发出的密钥伪造攻击，使得1024位RSA被攻破的时间远早于此前的预期。即便对于2048位和4096位密钥，该方法也将RSA的安全性降低到了不可接受的水平。美国国家安全局、美国国家标准与技术研究院以及欧盟网络与信息安全局都要求，任何加密系统都应提供不低于128比特的安全级别，这意味着所需运算量必须超过2的128次方。
而这种伪造攻击将上述安全级别分别降低到了1024位、2048位和4096位密钥所对应的2的65次方、90次方和119次方。这些数值可能还会进一步下降，因为赫宁格团队在实施伪造过程中全部采用手工编码，并未使用AI或GPU。研究人员表示，借助这些工具，安全级别“几乎肯定”会进一步降低。
该攻击仅针对RSA的盲签名实现方式有效。目前绝大多数使用中的RSA都采用了PKCS或PSS填充格式，即在加密前向明文中添加额外数据。这种做法能防止密文呈现确定性规律，从而降低遭受侧信道等类似攻击的风险。不过，现实世界中仍有一些系统在使用盲签名，也就是所谓的“教科书式”RSA。赫宁格表示，最著名的例子是Privacy Pass协议，它允许用户在不暴露身份的情况下进行身份验证。苹果和Cloudflare等众多机构都在使用Privacy Pass。
若要对Privacy Pass实施攻击，攻击者需要先攻陷Cloudflare、苹果或其他机构的服务器，并生成2的43次方个签名。赫宁格表示，这个数字“听起来很多，但其数量级与Cloudflare公开表示其一天内处理的网络流量相当”。多数Privacy Pass的实现都会定期轮换密钥，这一措施大大降低了（但并未完全消除）攻击者成功的可能性。
该技术实现了一种2007年发明的数域筛法算法的变体。这种“特殊数域筛法”被用来针对一个“预言机”——即RSA及其他一些密码系统中存在的一种弱点，它会对特定查询给出是或否的答案。通过执行海量运算，攻击者可以收集到足够的信息来破译密文。（再次强调，这种技术对采用PKCS或PSS填充的RSA不构成实际威胁，因为这些填充方式消除了预言机弱点。）分解一个1024位密钥估计需要2的80次方次运算和50万到100万个CPU核心年，而利用该筛法伪造一个签名仅需（如前所述）2的65次方次运算和1380个核心年。
论文作者及其他研究人员都强调，这种新型攻击在现实世界中几乎不构成威胁。然而，它确实大幅降低了教科书式RSA的估计安全性，而且是以一种此前无人知晓的方式实现的。
近年来，密码学家们一直在努力研发不易受到量子计算攻击的替代加密系统。这一新型攻击将进一步加剧完全摆脱RSA加密系统的紧迫性。论文作者在此提供了一份更易理解的说明文档。
Q&A
Q1：这种新型RSA攻击方法目前会对普通用户造成实际威胁吗？
A：目前几乎不会。该攻击所需的计算资源仍然极为庞大，除了拥有巨额资源的国家或大型企业外，绝大多数人都难以实现。而且广泛使用的RSA实现方式（采用PKCS或PSS填充）并不受此攻击影响，因此是安全的。
Q2：这种攻击方法针对的是哪种RSA实现方式？
A：该攻击仅针对RSA的盲签名（也称“教科书式”）实现方式有效，最典型的例子是Privacy Pass协议，苹果和Cloudflare等机构都在使用该协议。而目前绝大多数RSA应用采用的PKCS或PSS填充格式并不受影响。
Q3：这种攻击方法为什么被认为是一项重要突破？
A：因为它引入了一种全新的签名伪造方式，无需通过因数分解就能破解RSA密钥，并将所需计算资源降低了数个数量级。原本被认为对2048位RSA“完全无法实现”的攻击，现在变得在理论上可行，这让密码学界感到意外。
