我知道对于4096位RSA，数字p和q应该是质数。为了获得最佳的安全性，p和q的长度都应约为2048位。 gpg使用的素数生成实现经过64轮Miller-rabin轮次，足以给出$ 1-2 ^ {-128} $的素数概率。
鉴于这些素数只是概率性的素数，如果我们选择p或q的复合值会怎样？
RSA算法是否会遇到任何问题？
我的猜测是不会有问题并且RSA继续正常运行（加密和解密均如此），因为如果出现问题，我们可以使用该问题来检测数字不是素数。这将为我们提供一种非常快速的方法来验证极大的质数。我猜不是这样。
因此，我的结论是RSA可与质数p或复合p，q一起使用...但是使用复合p，q可以很容易地破坏加密（因为可以很容易地从n）得出p，q。
这个结论正确吗？
#1 楼
前提“我们没有办法以100％的精度生成和验证2048位素数”是错误的（如果我们相信执行操作的计算机）：长期以来，人们一直知道可行的方法来生成随机种子可证明的素数，这是RSA密钥生成中的一种（有点边际）做法（请参阅FIPS 186-4附录B.3.2）。我们甚至可以使用多种方法来实际证明（或反证）任意2048位整数的素性，包括（如注释中所指出的）：Daniel J. Bernstein，《计算数学》中的基本四次随机时间证明素性76（2007），389-403（这是给出确定性的随机检验；只有达到确定性所花费的时间取决于所使用的特定随机性）。或者更好（如另一条评论中所述）APR-CL或ECPP。但是这很复杂，实用的密码学对更简单的概率素数测试感到满意。请注意，针对一个2048位整数随机进行了64轮Miller-Rabin测试（这是RSA密钥生成的情况），而不是从一个潜在的敌对方那里收到，这是过分地排除具有较低剩余赔率的复合性的方法比$ 2 ^ {-128} $多； 4轮绰绰有余，请参阅FIPS 186-4表C-2，并在附录F及其参考中找到依据：Ivan Damgard，Peter Landrock和Carl Pomerance，《计算61（1993），177–194。
如果我们意外地尝试使用$ p $或$ q $复合之一来执行RSA（因为在执行素数测试时出错），通常的公式为$ \ varphi（p \ cdot q）=（p-1） \ cdot（q-1）$或$ \ lambda（p \ cdot q）= \ operatorname {lcm}（p-1，q-1）$会导致错误的值，并且具有压倒性的优势，解密或签名验证将第一次真正使用时失败（假设$ p $和$ q $的选择是非恶意的，并且使用了随机消息或适当的填充）。在PKI上下文中，证书颁发机构对公钥证书请求（通常是自签名）的验证几乎肯定会失败。构成了功能强大的$ p $和$ q $素数测试，实质上是对$ p $和$ q $进行了Fermat测试；这没有Miller-Rabin测试强大，但对随机的$ p $和$ q $仍然非常有效。但是（就像所有针对大整数的实用素数测试一样），它提供了复合性的指示，但并未揭示以前未知的因素；
更准确地说，假设$ e $和$ d $遵循必要条件，足以匹配两个素数RSA中的公共和私有指数，即是$ e \ cdot d \ equiv1 \ pmod {\ operatorname {lcm}（p-1，q-1）} $。
等价$ \存在于\ mathbb N，e \ cdot d = 1 + u \ cdot \ operatorname {lcm}（p-1，q-1）$。
通过设置$ v = \ gcd（p-1，q-1）\ cdot（q-1）$，我们得到$ e \ cdot d = 1 + u \ cdot v \ cdot（p-1）$。
现在，如果对于某些随机$ x
注释中指出的一个例外是，潜入的复合$ p $恰好是Carmichael数。这些是（稀有）合成，使得$ x \ not \ equiv0 \ pmod p \暗示x ^ {p-1} \ equiv 1 \ pmod p $;也就是说，Fermat测试无法检测到Carmichael数是复合的！
相应地，RSA将使用Carmichael数而不是质数来“工作”，但是可以说比$ p $是质数时要安全得多，因为$ p \ cdot q $相对容易分解：如果$ p $是2048位，它将至少有一个小于682位的因数（如果$ p $具有三个以上的因数，则它会更少）。但是，这不会是偶然的，因为卡迈克尔数很少见：到目前为止，最丰富的种类有三个因素，其中不超过$ x ^ {5/14 + \ mathcal o（1）} $低于$ x $（请参阅R. Balasubramanian和SV Nagaraj，《具有三个主要因子的卡迈克尔数的密度》，《数学计算》 66（1997），1705-1708）。随机的2048位整数是Carmichael数，赔率小于$ 2 ^ {-1300} $。因此，如果$ p $是一个Carmichael数，则这可能仅是出于恶意目的：除了素数检验之外，故意选择$ p $的随机选择还有缺陷，并且使用$ p \ cdot q $进行因式分解的可能性它具有较小的主要因素是一个相对较无聊的问题。
评论
$ \ begingroup $
残差$ \ mapsto $残差$ \; $
$ \ endgroup $
–user991
15年5月24日在8:49
$ \ begingroup $
有两条评论：1）以我的经验，FIPS 140中的确定性素数生成方法（基于Shawe-Taylor）与使用多次Miller-Rabin迭代验证素数的速度差不多，以及2）一个恰好是Carmichael numer的复合p（或q），RSA实际上起作用（！）。这是因为RSA的正确性取决于$ x ^ p \ equiv x \ pmod {p} $，这对于Carmichael数是正确的。
$ \ endgroup $
–雨披
15年5月24日在16:57
$ \ begingroup $
“发生蠕变” $ \：\ mapsto \：$“发生蠕变” $ \; \; \; \; $
$ \ endgroup $
–user991
15年5月24日在21:50
$ \ begingroup $
我们将使用APR-CL或ECPP（而不是AKS或Bernstein的AKS变体）对这种大小的通用数字进行实际证明。据我所知，后者没有实现，而且他指出它反而比ECPP慢。
$ \ endgroup $
– DanaJ
2015年5月25日下午6:29
评论
cr.yp.to/primetests/quartic-20060914-ams.pdf $ \; $伯恩斯坦（Bernstein）的AKS并没有真正实现，但是是针对实际算法的：2048位是600位以上的位数，因此一个内核的APR-CL或ECPP证明大约需要15-30秒。 BPSW可能的主要测试约为7毫秒。probableprime.org/images/primality-times.png。正如其他人指出的那样，我们当然确实具有构造随机证明的素数方法：Maurer和Shawe-Taylor仅举两个。
我有一个代码可使用Maurer算法生成可证明的素数，请参见s13.zetaboards.com/Crypto/topic/7234475/1