让我更具体一些。我想要的安全性与具有2048位模数的标准RSA所获得的安全性相当。我可以使用$ k = 3 $（三个素数）而不会显着降低安全性吗？ $ k = 4 $？在不显着降低安全性的情况下，我可以使用的最大质数$ k $是多少？假定每个素数的长度为$ 2048 / k $位，因此所有素数因子的长度相等。
相关：另请参见谁首先对RSA中的两个素数因子感兴趣？询问这项技术的发明者。我要问的是有些不同的东西。在这个问题上，我不是在问它的发明者。我在问具体的安全级别。
#1 楼
如果我们考虑大约$ n / k $位的$ k $素数的$ n $位的RSA模数$ N $（在问题中，$ n = 2048 $）乘积，那么在不损失安全性的情况下，$ k $可以有多高？甚至在命名Multiprime-RSA之前，就已经研究了这个问题，除了没有其他明确的答案：$ k = 2 $，我们不能在不安全的一面犯错。 2美元？与$ k = 2 $相比，RSA私钥功能可能节省了多达$ k ^ 2/4 $的因数，并且在实践中实现了很多这种加速；加上它允许在$ k $内核上进行简单而有效的并行化。当有硬件执行强制执行最大模数宽度的模块化乘法时，增加$ k $是增加$ n $的唯一方法（因此针对分解的安全性） ），而没有使用此硬件资源。
保存$ k = 2 $的分解记录的算法[GNFS和以前的（MP）QS]的运行时间取决于$ n $，而没有$ k $的影响;因此，当$ k $增长为常数$ n $时，使用这些算法进行因数分解攻击的安全性保持不变。
给出一个公钥及其证书，并（无侧边通道）访问实现RSA私钥函数$ x \ mapsto x ^ d \ bmod N $，这是判断$ k = 2 $是否涉及因子$ N $的最著名方法；因此我们可以增加$ k $，而不必担心与仅与公钥相关的设备之间的互操作性。
为什么我们总要坚持$ k = 2 $？
自从它包含RSA以来，它一直是美国标准FIPS 186-4的强制性要求，并作为参考来遵守某些或全部FIPS 140;根据法国RGS官方建议；上次我检查时，几乎每个安全机构都对该参考网站列出的密钥大小提出了建议。然后是一些。
在无数情况下，$ k = 2 $是唯一与周围环境兼容的东西。在智能卡领域，有很多例子：Java Card 3 Classic API。
虽然PKCS＃1标准化了Multi-Prime RSA甚至是私有密钥交换格式，但仍有一些设备，包括一些声称不支持PKCS＃11兼容性。如果您想将私钥移至其他设备，或者甚至备份以机载格式生成的机载密钥，请当心！
一些模块化求幂硬件或软件都需要主要因素$ p $确切的位大小是某事的倍数（通常是2的幂，例如64）；这是另一个互操作性障碍（在$ n = 2048 $，$ k = 3 $的情况下，为64的倍数将迫使一个质数为640位而不是683位）。注意：可以通过在模幂运算过程中减少素数的适当倍数然后进行最终减少的方法来解决。
至少在美国和欧洲（5,848,159，US 7,231,040，EP0950302）引发了关于使用Multiprime-RSA是否带来法律风险的恐惧，不确定性和疑问。
考虑$ k> 2时还应考虑哪些其他事项？$
到目前为止，主要问题是：使用ECM进行因式分解攻击的努力（无论如何）以$ n / k $增加（比多项式更快），因此对于恒定$ n $，以kk $大大减少。对手（我们必须假设，知道$ k $）可以选择因式分解方法，并且如果有利的话将选择ECM。因此，我所知的所有有关确定$ k $的文献（在下面列出）都旨在尽可能地选择它，以使ECM的预期工作量（或运行时，成本..）不低于GNFS，有时会做出预测这些未来的预期努力中；
ECM很容易在许多不需要相互通信的商用计算机上分发，而据我们所知，GNFS的矩阵步骤需要紧密连接具有大量内存的超级计算机（或者可能是在筛选步骤中花费了更多二进制数量级的计算能力，而筛选步骤支配了当前参数化的计算工作）。这在某种程度上使GNFS和ECM之间的考虑计算工作量，工作量或运行时间的比较无效，而不是某些成本的尝试度量方法。但这并不是一个很大的争论，因为将来GNFS可以通过内部使用ECM来从GPU中受益]。当谈到已发布的因式分解算法的未来运行时（成本要低得多）时（如果只考虑它们的相对成本，或者如果我们考虑未发布的改进或算法，这可能会更糟）。无论我们在ECM和GNFS之间进行比较，在将来我们想要更多的安全性时，基于这些不确定性，我们应有更多的保证金，并将余额转移到较低的k $（四舍五入之前）。
AFAIK，尚未通过认证实验室检查Multiprime-RSA的实施是否有旁道攻击。这不仅仅是一个认证问题：不必担心较小的灌注量或最终的CRT步骤（必须获得任何速度优势）会使实施更容易受到侧通道泄漏的影响。至少在非受信任环境中运行的HSM和智能卡中，这是一个潜在的问题。
使用ECM时，在预期工作量的\ epsilon $的小数\ epsilon中大约会得到\ epsilon $（用于$ 2 ^ {-20} \ le \ epsilon \ le0.3 $和通用ECM参数）。这与GNFS和QS相反，在GNFS和QS中，只有在预期工作的最后几个百分比之前，我们才能进行分解。如果我们希望对手成功完成某项工作的剩余风险\ epsilon $，则我们的目标应至少是针对GNFS的工作，并且目标至少是针对ECM的工作的$ 1 / \ epsilon $。将分频移向较低的$ k $（四舍五入前）。在安全性方面，对于已知攻击的可接受残余风险尚无共识，我已经看到这样的\ epsilon $被完全忽略，或者从5％（对于整个系统）设置为$ 2 ^ {-40} $（对于对称密码）当然，没有强烈的动机去调整它。）
当我们想生成$ m $密钥，而对手会满意地分解任何一个密钥时（就像在机器对机器应用程序中将密钥用于身份验证或签名时一样），我们应该付出一些代价。注意另外两个分解算法：Pollard的p-1和Williams的p + 1。问题是：在随机选择大小为$ n / k $的素数的情况下，这些算法（尤其是第一个算法）从小$的比率$ \ text {odds to factor} \ over \ text {runtime} $的角度来看，大大超过了ECM。 \ text {赔率} $。因此，在使用ECM之前，通过在可用的$ m $模数下尝试Pollard的p-1，然后是Williams的p + 1，将使对手受益。并可以在与$ m $成比例的预期工作中受益。为了证实这一点：GMP-ECM从业者使用该策略，p-1取得了显著成功，p + 1取得了较小的扩展。除了评估这种风险外，我们还可以生成素数$ p $，使得$ p-1 $和$ p + 1 $具有已知的高素数因子，这会使这些算法无用（如果不是简单的话，这是有效的可行方法，例如，如FIPS 186-4附录B.3中所述，对于$ k = 2 $，该命令要求使用512位素数，但不能使用1024位素数。）
在平衡内存中，还应考虑到ECM与使用可比较大小的随机$ N $和具有较低大小$ n / k $的素数的随机$ N $相比，预期将Multiprime-RSA $ N $分解所需的工作量将减少近$ k $。
参考文献
仅限于本世纪，我只知道4个参考文献，涉及为$ k $寻找余额：
Arjen K. Lenstra：难以置信的安全性：使用公钥系统匹配AES安全性，Asiacrypt 2001（备用链接）。
Dan Boneh，Hovav Shacham：RSA的快速变体，在CryptoBytes，Vol。1中有删节版。 5，2002年第1号。
M. Jason Hinek：关于多主RSA的安全性，滑铁卢大学应用密码研究中心（CACR）的技术报告，2006年（备用链接）。
让-塞巴斯蒂安·科隆（Jean-SébastienCoron），艾琳·古格（Aline Gouget） Pascal Paillier，Karine Villegas：SPAKE：用于无接触式应用程序的单方公共密钥验证密钥交换协议（2010年金融密码学讲习班，带免费提取内容的付费隔离）
最近的答案！
后面的参考简要地涉及到不平衡RSA中$ p $大小的几乎相同的问题（1.四舍五入以获得$ k $，4.可能与最终CRT步骤不同，7。不适用）。作者得出的结论是，$ n = 2048 $，$ p = 560 $具有良好的平衡；从中得出，$ k = 3 $是可以的，但$ k = 4 $则不是。这是基于对ECM和GNFS的分析（据我所知，仅考虑1.），参考：
Paul Zimmermann，布鲁斯·道森（Bruce Dodson）：ECM 20年，在2006年第七届算法数论研讨会论文集（付费壁垒链接）中。 ，达格·阿恩·奥斯维克（Dag Arne Osvik），赫尔曼·特里尔（Herman te Riele），安德烈·蒂莫费耶夫（Andrey Timofeev），保罗·齐默尔曼（Paul Zimmermann）：768位RSA模数的因式分解，在Crypto 2010诉讼中。
有关ECM的最新数据点：2013年末，Ryan Propper报告使用GMP-ECM 6.4.3 + GMP 5.1.0从787位组合$（7 ^ {337} +1）/中找到274位因子8/101020140256422276570987002251440602782290400709 $两个未知素数的乘积，在使用少于6GB RAM的商用CPU上。他进一步报告说，这是对斯坦福大学集群进行的为期10天的工作，并且在经过5000条曲线后发现了因式分解。通过对日志进行推断，我得到了16小时/曲线的运行时间和预期的$ 2 ^ {21} $曲线（约$ 2 ^ {12} $ core.years），如果几乎可以纠正的话，则平均超过300已经使用了核，并且在1/400处发现分解的速度非常快；轻描淡写说：“这真是个幸运的发现。” ECM记录的第二大记录也是相当幸运的。如果考虑到上面的5.，那就可以预期了！
#2 楼
对于2048位模数，根据当前的攻击知识：您最多可以使用$ k = 3 $个质数，而不会损失任何安全性。使用$ k = 4 $质数显然会导致安全性损失（尽管我不清楚它会造成多少损失）。我发现了两个支持该结论的资料： />
博客文章多重底数RSA的权衡取舍分析了针对NFS和ECM分解算法的2048位$ k $底数模数的安全性。对于$ k = 2 $和$ k = 3 $，安全级别为107位（NFS是最佳攻击）。对于$ k = 4 $，该文章声称安全级别为106位（对于四个素数，ECM比NFS稍快），因此我们损失了大约一位安全性，尽管此估计似乎过于简化了。 。
论文的表3令人难以置信的安全性：使用公钥系统匹配AES安全性也解决了这个问题。它表明，对于2048位模数，$ k = 3 $素数不会提供可测量的安全性损失。从2030年开始，$ k = 4 $素数将不会造成安全性损失（它会随着时间变化，因为NFS分解速度比ECM分解速度快）。这是表3：
评论
$ \ begingroup $
这忽略了一个问题：假设预期功的1％可以分解给定的实际模数，则ECM可以将其分解为1％的可能性；但是GNFS简直无法想象成功。如果我们希望对手在给定的努力下获得成功的残留风险非常低，则必须考虑到这一点，这将使结果显着地朝着减少因素的方向转移。
$ \ endgroup $
–fgrieu♦
14-4-25在22:11
$ \ begingroup $
独立地：在Lenstra的表3中的1024位列中，右侧的5和4（表示使用计算等效模型）是不合理的。 2013年，GMP-ECM从两个未知素数的787位数字乘积中减去了274位因子。当使用可比较的资源无法使用1024位GNFS分解时，将其从1024位数字中提取不会太难。 [注意：从$（7 ^ {337} +1）/ 8/101020140256422276570987002251440602782290400400 $中找到$ 16559819925107279963180573885975861071762981898238616724384425798932514688349020287 $]。
$ \ endgroup $
–fgrieu♦
2014年4月25日在22:46
$ \ begingroup $
@fgrieu，太好了，谢谢您的详细评论！您是否要创建自己的答案或将该答案编辑为可解决这些问题的表格？我不太确定如何考虑您提到的第一个问题（成功的几率约为1％），因此需要帮助。再次感谢你！
$ \ endgroup $
– D.W.
2014年4月26日下午5:38
$ \ begingroup $
我试图做出回答，但是几乎没有对事实和参考文献的阐述。我引用了另一个导致$ k = 3 $的值。
$ \ endgroup $
–fgrieu♦
2014年4月27日在19:55