是否可以在RSA中验证公钥？

#1 楼

有两种方法可以进行这种验证：



测试：您可以查看数字并做出决定，而无需涉及提供给您的人。
< br证明：生成数字的人还可以为您提供其他信息，使您确信它是正确的RSA编号。

没有针对RSA编号的测试。

有RSA编号的证明，包括“零知识”证明。零知识意味着生成数字的人可以说服您拥有两个主要因素，而无需向您提供有关这两个因素是什么的任何信息。

零知识证明可以是交互式的：您和发起方交换消息（类似于挑战/响应），这使您变得很有说服力。它也可以是非交互的：它是一个记录，可以说服所有看过它的人。因此，如果产生方给您编号和证明，您可以将其转发给其他任何人，他们也会被说服。使用交互式证明，除非您看着每条消息来回往返，并且知道正在交互的两方都没有勾结，否则您无法确信它是正确的。

#2 楼

不，我们不知道以线性时间（甚至是相对于$ n $中位数的多项式时间）运行的算法，如果$ n $是两个素数的乘积，则输出“ true”，而“ false” '否则。

如果存在这样的算法，我认为这并不意味着有可能分解$ n $或破坏RSA。可以肯定的是，RSA密钥的安全性不是一个很好的测试（我们知道生成有效RSA密钥的方法，而实际上知道一个秘密就可以分解该RSA密钥，即使知道$的因子分解也无法检测到n $）。

据我所知，我们拥有的最接近的东西是


测试$ n $是否为素数，在这种情况下输出“ false” ;
否则，请尝试使用ECM的最新实现方式对$ n $进行分解（例如EECM-MPFQ），以使其在假定$ n $的最小因子约为$ n ^ {1 / 3} $，并且
如果没有表现出一个因数，或者


如果结果足够好，则输出“可能为真”，或者
因数$ n $使用GNFS，然后继续


对所显示的因子进行素数测试，并输出“ true”（对于两个素数）或“ false”（否则）。

对于错误输出“可能为真”（如果我们愿意运行GNFS则为零）的可能性很小，该算法是次指数的（在$ n $的位数），但是是超多项式。


使用上述否定答案，明确提出的问题并不要求我们是否可以在多项式时间内检验$ \ gcd（\ phi（n），e）= 1 $给出$（n，e）$;但我希望我知道答案！

#3 楼

如果您只有1024位数字，则不能，您无法确定它是否是RSA密钥。您可以通过RSA加密任意数量的内容。

您可以通过对照常见的主要因素并查看是否有两个以上来证明它是密钥。可能还有其他估计方法，但是如果不检查每个可能的素数，就无法证明它只有两个素数。

#4 楼

您无法在分解之前确定因素的性质。

在RSA中，分解公钥所需的时间与两个因素中的较小者成正比。

请记住这一点可以使用一些启发式方法来推断可能的RSA公钥。您所要做的就是选择一个较大的X，然后尝试查找N的从2到X的除数。如果没有找到任何内容，则可以假定N是RSA中的公钥，并且两个因子都大于X 。