我想问一下，如果我们构建一个模数大于2的质数的RSA系统，例如让$ n = p_ {1} p_ {2} ... p_ {L} $。我只知道经典RSA系统，其中$ n = pq $具有$ p $和$ q $大质数。
我想模数$ n = p_ {1} p_ {2} ... p_ {L} $不是一个好主意，因为可以使用中国剩余定理轻松地解密消息？
/>
谁能解释我们如何处理这种质数的模积？

评论

您可以使用多个素数，只要它们足够大即可。对于给定的模数大小，它给您的安全性较低，但可以为您提供更好的性能/安全性折衷。
一个相关的问题：是否有任何多主RSA密钥生成标准？和AGL的博客文章，关于安全性和性能如何随着素数的增加而扩展

#1 楼

PKCS＃1标准支持两个以上的主要因素。这就是所谓的“多重质数”键。从正面来看，这可能会改善性能。中国余数定理仍然适用（例如，参见第5.1.2节，该描述适用于两个以上的质数）。例如，如果您有一个1536位模数，它是三个512位素数的乘积，则CRT用三个512位幂数替换一个1536位幂，它们分别快了27倍（假设经典三次模幂运算算法），总加速比为9，而通常的加速比为2，其中有两个因素。更一般地说，在$ k $因子的情况下，预期的CRT加速大约在$ k ^ 2 $。最著名的因式分解算法的成本取决于模数大小，而不取决于各个因素的大小，因此，使用更小的因素应该没有影响……除非这些因素小到足以进入可行范围ECM：该算法的成本（主要）取决于最小因子的大小。对于正常的双基数RSA模数，ECM与GNFS不具有竞争性。但是如果您将因素设置得太小，则会降低您的安全性。

底线是，对于通常的大小，三个或四个素数应该是可以忍受的，并且可以很好地提高性能，但是不能超越。公开密钥操作不会受到任何影响。还请注意，其他一些相关的密码系统（例如Rabin）可能不接受多素数模数。

#2 楼

RFC 8017支持所谓的“多素数” RSA，其中模数可能具有两个以上的素数。只要使用了CRT，多素数RSA的好处就是可以降低解密和签名原语的计算成本。在单处理器平台上可以实现更好的性能，但是在多处理器平台上可以实现更好的性能，在多处理器平台上，可以并行完成涉及的模幂运算。

openssl-1.1.1中实现了多素数RSA。 。