，通常的做法是使用加速算法来生成密钥。对，尤其是在时间资源稀少的情况下。 （我们）还在有时间限制的情况下使用了这种加速算法，称为“ Fast Prime”。此算法是基于软件的。.
“ Fast Prime”的基础可以追溯到2000年。大约十年后，经过全面的审查，它的使用开始了。作为提供给客户自己开发的基础的一个加密软件库的一部分，该软件功能已通过德国BSI（联邦信息安全局）的认证。没有任何数学上的弱点是已知的，也没有在认证过程中发现的。
什么是“ Fast Prime”，它的建议含义是什么？
以下（可能）说明此方法生成的素数的性质；但不是真正的工作原理，如果这是故意的和/或遵循某些文章/方法，如果在某个时候存在一些问题的话；我问。
ROCA漏洞/攻击的目标是一些使用“ Fast Prime”生成的RSA密钥。详细信息在论文中：Matus Nemec，Marek Sys，Petr Svenda，Dusan Klinec，Vashek Matyas； 《铜匠的攻击的回归：广泛使用的RSA Moduli的实用因式分解》在CCS 2017上发布（稍早的版本）。
换句话说：使得攻击可能发生的因素（大概是由“快速素数”）的形式为
$$ p = k \; M +（65537 ^ a \ bmod M）\ \ \ text {其中} M = P_n \＃= \ prod_ {i = 1} ^ n带有$ p_i $的p_i $$
是$ i ^ \ text {th} $素数。 $ N \ equiv65537 ^ a \ pmod {P_n \＃} $表示某个整数$ a $。
整数$ n $根据所需的$ p $位大小（始终为16的倍数）以不连续的步骤进行选择，以使$ P_n \＃$是$ p大小的很大一部分$
$$ \ begin {array} {c | ccc}
\ text {bits in} p＆n＆p_n＆\ text {bits in} P_n \＃\\
\ hline
256 \点480＆39＆167＆220 \\
496 \点976＆71＆353＆475 \\
992 \点1968＆126＆701＆971 \\
1984年\ dots 2048＆225＆1427＆1963 \\
\ end {array} $$
这个问题的前一个版本讨论了首次发布的针对脆弱密钥的ROCA测试。但是，这已经过时了：事实证明，此测试是有意简化的，以限制对该漏洞的披露。完整测试的错误检测几率更低。
#1 楼
这是在回答我自己的问题时的一个初步猜测。也许在该问题的引用中提到的“ Fast Prime”方法是这两篇论文的第二篇（第二篇抛光第一篇）：
[JPV2000]：Marc Joye，Pascal Paillier和Serge Vaudenay；在CHES 2000程序中有效生成质数
[JP2006]：Marc Joye和Pascal Paillier； CHES 2006（幻灯片）会议记录中便携式设备上质数的快速生成：更新。
有几件事情相符：
文章的目标显然是所使用的技术所追求的目标。
“ Fast Prime”是两个词[JPV2000]的发布与之匹配。
“日期可以追溯到2000年”。
“使用大约十年后才开始使用，经过全面审查”允许[JP2006]
据我们所知，素数生成器大量使用了$ M = P_n \＃= \ displaystyle \ prod_ {i = 1} ^ n p_i $，基本上是[JPV2000]和[ JP2006]会这样做（它们的$ \ Pi $是$ M / 2 $）。因此，如果我的理论是正确的，那么就有一个严重的实现错误。
$ 65537 ^ a $出现的事实使我怀疑，导致错误的原因可能是故意的，非常错误的，使计算$ e ^ {-1} \ bmod p $的速度更快，其中$ e = 65537 $；
更新：正如评论中所注意到的，丹尼尔·J·伯恩斯坦和坦贾·兰格的博客证实了实施[JP2006]的尝试出错了：
一个相关的算法“ GenPrime”由Joye和Paillier于2006年发布。Joye–Paillier生成器与Lehmer的生成器一样，从新的随机数$ r $互质数开始到$ L $，然后反复乘以恒定的$ g $模$ L $，获得$ r $乘以$ g $的幂。这可以产生任何以模$ L $为模的数字，并且在所得素数中仅产生很小的偏差。猜测是（公司）过于简化，仅产生$ g $的幂；这会产生更少的以$ L $为模的数字。
作者迅速写回信，确认这一猜测是正确的，但没有透露更多细节。
评论
$ \ begingroup $
如果您在第20页中应用JP2006的图2中的算法。 162，其中$ \ Pi = M $，$ t = 0 $，$ v $是随机抽取的，$ w = 1 $，因此$ m = w \ Pi = M $，而$ a = 65537 $，如果总是选择$ k = 1 $，而不是像您本应的那样从$（\ mathbb Z / m \ mathbb Z）^ \ times $中随机均匀地绘制它，然后从候选者$ q_0 = [[（k- t）\ bmod m] + t + l =（1 \ bmod M）+ v M $，然后尝试$ q_1 =（a \ bmod M）+ v M $，然后$ q_2 =（a ^ 2 \ bmod M）+ v M $，依此类推。
$ \ endgroup $
–吱吱作响的s骨
17年11月5日，在1:22
$ \ begingroup $
您可以通过从一个质数中恢复$ a = 65537 $的指数并检查是否有较小的指数为质数来检验该假设。我不知道该观察是否会加快保理程序。
$ \ endgroup $
–吱吱作响的s骨
17年11月5日在1:24
$ \ begingroup $
实际上，本文的下一部分建议将$ t = b \ Pi $用于随机选择的$ b $，这与我刚才描述的内容相同。
$ \ endgroup $
–吱吱作响的s骨
17年11月5日在1:28
$ \ begingroup $
好像是Bernstein和Lange在11月5日写到了这件事：blog.cr.yp.to/20171105-infineon.html。很多有趣的信息。他们推测JP2006，ROCA的作者证实了这一点。
$ \ endgroup $
– DanaJ
17年11月11日在19:19
评论
这在结构上看起来与Miller-Rabin Witness测试的素数相似。这两种方法在数学上是否不同？ Miller-Rabin还能识别这些弱键吗？展望未来，素数生成器是否应该同时使用Miller-Rabin和它来测试素数？@Russ：在Miller-Rabin中，模数是测试的（通常是大）数，此时模数是小的素数。那是巨大的差异。而且，似乎有问题的库中的问题不是与Miller-Rabin测试有关，而是在主要候选数的生成中。我的初步结论（没有阅读即将发表的论文，也没有任何内幕信息）是，一般而言，密钥生成器，尤其是（困难的）RSA密钥生成器，必须在源，对象和调试器中经过多方面的仔细研究;未测试为黑匣子。
Roca论文的结论的最后三段表明，英飞凌的算法是秘密的。
请勿将德语术语“ fast Prim”与英语术语“ fast prime”（“ fast prime功能”的缩写）混合使用。虽然两者都与近质数有关，但Q所要求的“快速质数”功能不仅仅是“快速eine Primzahl”（“几乎是质数”又称“近质数”）。因此，宁愿将“快速素数功能”视为“基于近似素数的快速素数生成功能”，而不是尝试基于错误的解释（“素数”可能不是EN）而尝试对直接翻译进行错误尝试来解释事物。 br />
考虑到时间（2000年）和确切的名称，1995年和1999年出现了毛勒的FastPrime方法。 citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.26.2151。但是您可能更喜欢CHES2000参考。