RSA泄漏位为N因子

#1 楼

我认为，对于所需的“最少”位数没有一个下界的证明。但是，铜匠展示了如何给定$ p $的最小$ n / 4 $或$ n / 4 $个最高有效位，其中$ n $是模量$ N = pq $的大小，$ N $可以有效地分解。另外，给定$ n / 4 $的最低有效位$ d $，如果$ e <\ sqrt {N} $，则可以重构$ d $（并因此分解$ N $）。请参阅Boneh对RSA攻击的20年调查。请参见该论文以及其中的算法参考等。

从那时起，$ e $的边界已经有所更新，但是仍然需要泄漏相同数量的位。同样，位的随机子集足以说明$ p $的$（1- \ frac {H_r} {r}）\ log {N} $位已知的情况（$ H_r $是第r次谐波数）。

#2 楼

回复较晚，但希望对您有所帮助。

您还可以看到本文：Kenneth G. Paterson和Antigoni Polychroniadou和Dale L. Sibborn撰写的“一种用于恢复嘈杂RSA密钥的编码理论方法”。提供许多攻击，但是他们给出的答案是范围与Coppermith的logN/4 bits大致相同。令人高兴的是，即使对于随机位，界限仍然保留。关于该算法的一个好处是，即使有时给您错误的位值（允许纠错），您也可以检索正确的因式分解。

#3 楼

我认为，泄漏适当的sigma位来描述平滑顺序的椭圆曲线将是最有效的，这将导致在容许的工作量之后进行因式分解

#4 楼

如果您想故意泄漏信息，以便特定实体可以使用N，但是通常它是安全的，因为这是我从下一篇文章中可以了解的内容，因此您必须研究一下SETUP（具有Universal Protection的秘密嵌入式活板门）。原始作品来自Young＆Yung，请参见：http://dl.acm.org/citation.cfm?id=706030

#5 楼

从数论和计算机科学的角度来看，这是一个非常有趣的问题。

但是，如果您正在考虑可以“后门”系统并让后门将很少的信息发送回植入机以进行分解的实用方法，则可能有另一种方法虽然。您可以使用种子为256位的PRNG生成p，q。然后，您可能会泄漏256位或其某些子集。或完全避免泄漏：生成PRNG种子的熵后，您可以用硬编码值替换某些位（例如，除64位外的所有位），或者在攻击情形下推断出的某些位（源自用户） -id，硬件序列号等）。通过散列来运行它（如果PRNG是安全的，则可能不需要），并将其用作PRNG生成p，q的种子。这样，即使系统似乎具有更高的安全级别，您也可以仅使用2 ^ 64个操作就可以强行使用p，q。如果将其嵌入无法提取硬编码值的硬件（即硬件RNG）中，您将对自己有好处-对于其他所有人，它确实需要2 ^ 256次操作。通过本质上“强制” RNG，耗尽其映射到的子空间，并注意您得到的重复次数比预期的要多，就可以实现其他人的后门。您可以尝试采取规避措施。因此，如果您的暴力破解能力比审核该系统的人员高得多，那么该攻击最有效。